Mulţime finită

O mulțime finită - o mulțime care este echivalentă cu un segment al seriei naturale, precum și cu o mulțime goală, se numește finită . În caz contrar, mulțimea se numește infinită . De exemplu,

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

un set finit de cinci elemente. Numărul de elemente ale unei mulțimi finite este un număr natural și se numește cardinalitatea mulțimii. Mulțimea numerelor naturale este infinită:

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

Mulțimile finite joacă un rol special în combinatorică , care studiază obiectele discrete. Raționamentul cu mulțimi finite folosește principiul lui Dirichlet , conform căruia nu poate exista o injecție dintr-un set finit mai mare într-unul mai mic.

Definiție formală

Două mulțimi și se spune că sunt echivalente dacă există o mapare bijectivă de la o mulțime la alta. Dacă mulțimile X și Y sunt echivalente, atunci acest fapt este scris sau și se spune că mulțimile au aceeași cardinalitate. $X$ $Y$ $X\sim Y$ $|X|=|Y|$

O mulțime se numește finită dacă este echivalentă cu o mulțime pentru un întreg nenegativ . În acest caz, numărul se numește numărul de elemente ale mulțimii , care este scris ca . [unu] $X$ $\{1,2,\dots ,n\}$ $\n$ $\n$ $X$ $|X|=n$

În special, mulțimea goală este o mulțime finită al cărei număr de elemente este 0, adică . $|\varnothing |=0$

Există și alte definiții ale unei mulțimi finite:

o multime este finita daca este inductiva ;
o multime este finita daca multimea tuturor submultimii sale este nereflexiva [2] ;
o multime este finita daca este nereflexiva;
o mulțime este finită dacă nu este unirea a două mulțimi disjunse, fiecare dintre ele echivalentă cu o mulțime dată [2] .

Problema determinării finității mulțimilor este în general indecidabilă ( teorema lui Trakhtenbrot ). Nu există nici cea mai slabă, nici cea mai puternică definiție a unei mulțimi finite. Pentru fiecare formulă logică care este definiția unei mulțimi finite, există o formulă mai puternică și una mai slabă. Există un număr nelimitat de formule logice care definesc mulțimi finite, iar printre acestea există un număr nelimitat de definiții independente.

Proprietăți

Un set obișnuit nu este echivalent cu niciuna dintre propriile sale submulțimi ; [unu]
Dacă mulțimile finite sunt disjunse în perechi (adică ), atunci $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}|$ ;
Dacă sunt mulțimi finite, atunci $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 }|$ ;
Dacă este o mulțime finită, atunci cardinalitatea booleanului său este $X$ $\ |2^{X}|=2^{|X|}.$

Vezi și

Set infinit

Note

↑ 1 2 Soboleva T. S., Chechkin A. V. Matematică discretă . - Academia, 2006. - ISBN 5-7695-2823-0 .
↑ 1 2 Frenkel, 1966 , p. 87.

Literatură

Frenkel A. A. , Bar-Hillel R. Fundamentele teoriei mulțimilor. — M .: Mir, 1966. — 555 p.

Dicționare și enciclopedii	Mare catalană Mare catalană Britannica (online)