Ändlig uppsättning

En finit mängd - en mängd som är ekvivalent med ett segment av den naturliga serien, såväl som en tom mängd, kallas finit . Annars kallas uppsättningen oändlig . Till exempel,

{\displaystyle \{2,4,6,8,10\))

en ändlig uppsättning av fem element. Antalet element i en finit mängd är ett naturligt tal och kallas mängdens kardinalitet . Mängden naturliga tal är oändlig:

\{1,2,3,\ldots\}.

Finita uppsättningar spelar en speciell roll i kombinatorik , som studerar diskreta objekt. Finita mängd resonemang använder Dirichlets princip , enligt vilken det inte kan finnas en injektion från en större finit mängd till en mindre.

Formell definition

Två uppsättningar och sägs vara ekvivalenta om det finns en bijektiv mappning från den ena mängden till den andra. Om mängderna X och Y är ekvivalenta, så skrivs detta faktum eller och mängderna sägs ha samma kardinalitet. $X$ $Y$ $X\sim Y$ $|X|=|Y|$

En mängd kallas finit om den är ekvivalent med en mängd för något icke-negativt heltal . I det här fallet kallas numret för antalet element i mängden , vilket skrivs som . [ett] $X$ $\{1,2,\dots ,n\}$ $\n$ $\n$ $X$ $|X|=n$

I synnerhet är den tomma mängden en finit mängd vars antal element är 0, det vill säga . $|\varnothing |=0$

Det finns andra definitioner av en ändlig mängd:

en mängd är finit om den är induktiv ;
en mängd är finit om mängden av alla dess delmängder är icke- reflexiv [2] ;
en mängd är finit om den är icke-reflexiv;
en mängd är finit om den inte är föreningen av två disjunkta mängder, som var och en är ekvivalent med en given mängd [2] .

Problemet med att bestämma mängdernas ändlighet är i allmänhet oavgörbart ( Trakhtenbrots teorem ). Det finns varken den svagaste eller starkaste definitionen av en finit mängd. För varje logisk formel som är definitionen av en finit mängd finns det en starkare och en svagare formel. Det finns ett obegränsat antal logiska formler som definierar ändliga mängder, och bland dem finns det ett obegränsat antal oberoende definitioner.

Egenskaper

En vanlig uppsättning är inte likvärdig med någon av dess egna delmängder ; [ett]
Om de ändliga mängderna är parvis disjunkta (det vill säga ), då $X_{1},\dots ,X_{n}$ $X_{i}\cap X_{j}=\varnothing$ $|X_{1}\cup X_{2}\cup \dots \cup X_{n}|=|X_{1}|+|X_{2}|+\dots +|X_{n}|$ ;
Om är ändliga mängder, alltså $X_{1},\dots ,X_{n}$ $|X_{1}\times X_{2}\times \dots \times X_{n}|=|X_{1}|\times |X_{2}|\times \dots \times |X_{n }|$ ;
Om är en finit mängd, då är kardinaliteten för dess booleska $X$ $\ |2^{X}|=2^{|X|}.$

Se även

Oändligt set

Anteckningar

↑ 1 2 Soboleva T. S., Chechkin A. V. Diskret matematik . - Akademin, 2006. - ISBN 5-7695-2823-0 .
↑ 1 2 Frenkel, 1966 , sid. 87.

Litteratur

Frenkel A. A. , Bar-Hillel R. Mängdlärans grunder. — M .: Mir, 1966. — 555 sid.

Ordböcker och uppslagsverk	Stor katalanska Stor katalanska Britannica (online)