Konečná sada - Finite set

V matematiky (zejména nastavení teorie ), je konečná množina je soubor , který má konečný počet prvků . Konečně množina je množina, kterou lze v zásadě spočítat a dokončit počítání. Například,

je konečná sada s pěti prvky. Počet prvků konečné množiny je přirozené číslo ( nezáporné celé číslo ) a nazývá se mohutnost množiny. Množina, která není konečná, se nazývá nekonečná . Například sada všech kladných celých čísel je nekonečná:

Konečné množiny jsou zvláště důležité v kombinatorice , matematické studii počítání . Mnoho argumentů zahrnujících konečné množiny se opírá o princip pigeonhole , který uvádí, že nemůže existovat injektivní funkce z větší konečné sady do menší konečné sady.

Definice a terminologie

Formálně se množina S nazývá konečná, pokud existuje bijekce

pro nějaké přirozené číslo n . Číslo n je mohutnost množiny, označená jako | S | . Prázdná množina {} nebo ∅ je považován za konečný, s mohutností nula.

Pokud je množina konečná, její prvky lze zapisovat - mnoha způsoby - v pořadí :

V kombinatorice se konečná množina s n prvky někdy nazývá n -set a podmnožina s k prvky se nazývá k -subset . Například množina {5,6,7} je 3-množina - konečná množina se třemi prvky - a {6,7} je její 2 podmnožina.

(Ti, kteří znají definici přirozených čísel jako konvenčních v teorii množin, takzvanou von Neumannovu konstrukci , mohou raději využít existenci bijekce , která je ekvivalentní.)

Základní vlastnosti

Jakákoli správná podmnožina konečné množiny S je konečná a má méně prvků než samotná S. V důsledku toho nemůže existovat bijection mezi konečné množiny S a řádné podmnožinu S . Jakákoli sada s touto vlastností se nazývá Dedekind-finite . Při použití standardních ZFC axiomů pro teorii množin je každá Dedekindova-konečná množina také konečná, ale tuto implikaci nelze prokázat pouze v ZF (Zermelo – Fraenkelovy axiomy bez zvoleného axiomu ). Axiom spočetného výběru , slabá verze axiomu výběru, je dostačující k prokázání této rovnocennosti.

Jakákoli injektivní funkce mezi dvěma konečnými množinami stejné mohutnosti je také surjektivní funkcí (surjekce). Podobně jakékoli vstříknutí mezi dvěma konečnými množinami stejné mohutnosti je také injekcí.

Sjednocení dvou konečných množin je konečná, s

Ve skutečnosti principem zahrnutí - vyloučení :

Obecněji řečeno, sjednocení libovolného konečného počtu konečných množin je konečné. Kartézský součin konečných množin je také konečný, s:

Podobně je kartézský součin konečně mnoha konečných množin konečný. Konečná množina s n prvky má 2 n odlišných podmnožin. To znamená, že výkonová sada konečné sady je konečná, s mohutností 2 n .

Jakákoli podmnožina konečné množiny je konečná. Sada hodnot funkce při použití na prvky konečné sady je konečná.

Všechny konečné množiny jsou spočetné , ale ne všechny počitatelné množiny jsou konečné. (Někteří autoři však používají výraz „countable“ ve smyslu „countably infinite“, takže nepovažujte konečné množiny za spočetné.)

Bez semilattice přes konečné množiny je množina jeho non-prázdné podmnožiny s tím, že spojit operace je dána nastavenou unie.

Nezbytné a dostatečné podmínky pro konečnost

V teorii množin Zermelo – Fraenkel bez axiomu volby (ZF) jsou všechny následující podmínky ekvivalentní:

  1. S je konečná množina. To znamená, že S lze umístit do korespondence jedna k jedné se sadou těchto přirozených čísel menší než nějaké konkrétní přirozené číslo.
  2. ( Kazimierz Kuratowski ) S má všechny vlastnosti, které lze dokázat matematickou indukcí počínaje prázdnou množinou a přidáním jednoho nového prvku po druhém. (Viz níže teoretická formulace Kuratowského konečnosti.)
  3. ( Paul Stäckel ) S může dostat celkové pořadí, které je dobře uspořádané jak dopředu, tak dozadu. To znamená, že každá neprázdná podmnožina S má v podmnožině nejméně i největší prvek.
  4. Každá funkce jedna k jedné od P ( P ( S )) do sebe je na . To znamená, že sada výkonů sady pohonů S je Dedekind-konečná (viz níže).
  5. Každá surjektivní funkce od P ( P ( S )) k sobě je jedna k jedné.
  6. ( Alfred Tarski ) Každá neprázdná rodina podmnožin S má minimální prvek, pokud jde o začlenění. (Ekvivalentně každý neprázdný rodina podmnožin S má maximální prvek s ohledem na začlenění.)
  7. S může být dobře uspořádané a jakékoli dvě dobře uspořádané řádky jsou řádově izomorfní . Jinými slovy, pořadí objednávek na S má přesně jeden typ objednávky .

Pokud se předpokládá také axiom volby ( axiom spočetné volby je dostatečný), pak jsou všechny následující podmínky ekvivalentní:

  1. S je konečná množina.
  2. ( Richard Dedekind ) Každá funkce jedna k jedné od S do sebe je.
  3. Každá surjektivní funkce od S k sobě je jedna k jedné.
  4. S je prázdná nebo každý částečné uspořádání z S obsahuje maximální prvek .

Základní problémy

Georg Cantor zahájil svou teorii množin, aby poskytl matematické zpracování nekonečných množin. Rozdíl mezi konečným a nekonečným tedy leží v jádru teorie množin. Někteří zakladatelé, přísní finitisté , odmítají existenci nekonečných množin, a proto doporučují matematiku založenou výhradně na konečných množinách. Matematici hlavního proudu považují přísný finitismus za příliš omezující, ale uznávají jeho relativní konzistenci: vesmír dědičně konečných množin představuje model teorie množin Zermelo – Fraenkel s axiomem nekonečna nahrazeným jeho negací.

I pro ty matematiky, kteří přijímají nekonečné množiny, může v určitých důležitých kontextech zůstat formální rozdíl mezi konečnou a nekonečnou jemnou záležitostí. Obtíž vyplývá z Gödelových vět o neúplnosti . Lze interpretovat teorii dědičně konečných množin v Peano aritmetice (a jistě také naopak), takže neúplnost teorie Peano aritmetiky implikuje teorii dědičně konečných množin. Zejména existuje nepřeberné množství takzvaných nestandardních modelů obou teorií. Zdánlivým paradoxem je, že existují nestandardní modely teorie dědičně konečných množin, které obsahují nekonečné množiny, ale tyto nekonečné množiny vypadají uvnitř modelu jako konečné. (To se může stát, když model postrádá množiny nebo funkce nezbytné k pozorování nekonečnosti těchto množin.) Z důvodu vět o neúplnosti nemůže žádný standard predikátu prvního řádu, ani dokonce žádné rekurzivní schéma predikátů prvního řádu, charakterizovat standard. součástí všech těchto modelů. Takže alespoň z hlediska logiky prvního řádu lze jen doufat, že konečně popíšeme konečnost.

Obecněji řečeno, neformální pojmy jako množina, a zejména konečná množina, mohou přijímat interpretace v celé řadě formálních systémů, které se liší v axiomatice a logickém aparátu. Mezi nejznámější teorie axiomatických množin patří Zermelo-Fraenkelova teorie množin (ZF), Zermelo-Fraenkelova teorie množin s Axiom of Choice (ZFC), Von Neumann – Bernays – Gödelova teorie množin (NBG), Nepodstatná teorie množin , Bertrand Russell ‚s teorií typu a všechny teorie svých různých modelů. Lze si také vybrat mezi klasickou logikou prvního řádu, různými logikami vyššího řádu a intuicionistickou logikou .

Formalist mohli vidět význam set se pohybuje od systému k systému. Některé druhy platonistů by mohly považovat konkrétní formální systémy za přibližující se základní realitě.

Set-teoretické definice konečnosti

V kontextech, kde pojem přirozeného čísla sedí logicky před jakýmkoli pojmem množiny, lze definovat množinu S jako konečnou, pokud S připouští bijekci k nějaké množině přirozených čísel tvaru . Matematici se v teorii množin častěji rozhodnou uzemnit pojmy čísla , například mohou modelovat přirozená čísla podle typů řádů konečných dobře uspořádaných množin. Takový přístup vyžaduje strukturální definici konečnosti, která nezávisí na přirozených číslech.

Různé vlastnosti, které vyčleňují konečné množiny mezi všemi množinami v teorii ZFC, se v logicky nerovnoměrných systémech, jako jsou ZF nebo teorie intuitivní množiny, ukázaly jako logicky nerovnoměrné. V literatuře jsou prominentně uvedeny dvě definice, jedna kvůli Richardu Dedekindovi , druhá pro Kazimierze Kuratowského . (Kuratowski je definice použitá výše.)

Sada S se nazývá Dedekind nekonečná, pokud existuje injektivní, nesurjektivní funkce . Taková funkce vykazuje bijekci mezi S a vlastní podmnožinou S , konkrétně obrazem f . Vzhledem k Dedekindově nekonečné množině S , funkci f a prvku x, který není v obraze f , můžeme vytvořit nekonečnou sekvenci odlišných prvků S , jmenovitě . Naopak vzhledem k sekvenci v S skládající se z různých prvků , můžeme definovat funkci, f tak, že na prvky v sekvenci a f chová jako funkce identity jinak. Dedekindovy nekonečné množiny tedy obsahují podmnožiny, které bijektivně odpovídají přirozeným číslům. Dedekind konečný přirozeně znamená, že každá injektivní samo-mapa je také surjektivní.

Kuratowského konečnost je definována následovně. Vzhledem k tomu, nějaký soubor S je binární operace svazku dotuje POWERSET P ( S ) s struktuře semilattice . Psaní K ( S ) pro sub-semilattice generované prázdnou množinou a singletony, volání množiny S Kuratowski konečný, pokud S sám patří k K ( S ). Intuitivně, K ( S ) se skládá z konečných podmnožin S . Klíčové je, že nepotřebujeme indukci, rekurzi ani definici přirozených čísel, která by byla definována generováním, protože lze získat K ( S ) jednoduše tím, že vezmeme průsečík všech dílčích pololattic obsahujících prázdnou množinu a singletony .

Čtenáři, kteří neznají semilatice a jiné pojmy abstraktní algebry, mohou upřednostňovat zcela základní formulaci. Kuratowski konečný znamená, že S leží v množině K ( S ), konstruované následovně. Zápis M pro soubor všech podmnožin X o P ( S ) tak, že:

  • X obsahuje prázdnou sadu;
  • Pro každou množinu T v P ( S ), pokud X obsahuje T, pak X také obsahuje spojení T s jakýmkoli singletonem.

Pak K ( S ) může být definována jako průsečík M .

V ZF Kuratowski konečný znamená Dedekind konečný, ale ne naopak. V řeči populární pedagogické formulace, když axiom výběru selže špatně, může mít někdo nekonečnou rodinu ponožek, aniž by si mohl vybrat jednu ponožku z více než konečně mnoha párů. Díky tomu by sada takových ponožek byla Dedekind konečná: nemůže existovat žádná nekonečná sekvence ponožek, protože taková sekvence by umožnila výběr jedné ponožky pro nekonečně mnoho párů výběrem první ponožky v pořadí. Konečnost Kuratowského by však u stejné sady ponožek selhala.

Další pojmy konečnosti

V teorii množin ZF bez axiomu volby jsou následující pojmy konečnosti pro množinu S odlišné. Jsou uspořádány v přísně sestupném pořadí podle síly, tj. Pokud množina S splňuje kritérium v ​​seznamu, pak splňuje všechna následující kritéria. Při absenci axiomu volby jsou všechny reverzní implikace neprokazatelné, ale pokud se předpokládá axiom výběru, jsou všechny tyto pojmy rovnocenné. (Všimněte si, že žádná z těchto definic nepotřebuje, aby byla nejprve definována množina konečných pořadových čísel; všechny jsou čistými „množinově-teoretickými“ definicemi, pokud jde o vztahy rovnosti a členství, nezahrnující ω.)

  • I-konečný . Každá neprázdná sada podmnožin S má prvek ⊆-maximální. (To odpovídá požadavku na existenci prvku ⊆-minimal. Rovněž je to ekvivalentní standardnímu numerickému konceptu konečnosti.)
  • Ia-konečný . Pro každé rozdělení S do dvou sad je alespoň jedna ze dvou sad I-konečná.
  • II-konečný . Každá neprázdná ⊆-monotónní sada podmnožin S má ⊆-maximální prvek.
  • III-konečný . Energetická sada P ( S ) je Dedekindova konečná.
  • IV-konečný . S je Dedekind konečný.
  • V-konečný . ∣ S ∣ = 0 nebo 2⋅∣ S ∣> ∣ S |.
  • VI-konečný . ∣ S ∣ = 0 nebo ∣ S ∣ = 1 nebo ∣ S ∣ 2 > ∣ S ∣.
  • VII-konečný . S je I-konečný nebo není dobře objednatelný.

Dopředné implikace (od silných po slabé) jsou věty v rámci ZF. Protiklady k obráceným implikacím (od slabých po silné) v ZF s urelementy lze nalézt pomocí teorie modelu .

Většina z těchto definic konečnosti a jejich názvy jsou připisovány Tarski 1954 od Howard & Rubin 1998 , str. 278. Definice I, II, III, IV a V však byly uvedeny v Tarski 1924 , s. 49, 93, spolu s důkazy (nebo odkazy na důkazy) pro budoucí důsledky. V té době nebyla teorie modelu dostatečně pokročilá, aby našla protiklady.

Každá z vlastností I-konečná až IV-konečná je představou maličkosti v tom smyslu, že jakákoli podmnožina množiny s takovou vlastností bude mít také tuto vlastnost. To neplatí pro V-konečnou až VII-konečnou, protože mohou mít nespočetně nekonečné podmnožiny.

Viz také

Poznámky

Reference

externí odkazy