Крайно множество

Формално, множеството S се нарича крайно, ако съществува биекция

${\displaystyle f\colon S\rightarrow \{1,\ldots ,n\}}$

за някакво естествено число n. Числото n е кардиналността на множеството, обозначавана като |S|. Празното множество Ø се счита за крайно, имайки нулева кардиналност.^[1][2][3][4]

Ако дадено множество е крайно, неговите елементи могат да се запишат по много начини в числова редица:

${\displaystyle x_{1},x_{2},\ldots ,x_{n}\quad (x_{i}\in S,\ 1\leq i\leq n)}$ .

В комбинаториката, крайно множество с n елементи понякога се нарича n-множество, а подмножество с k елементи се нарича k-подмножество.

Всяко собствено подмножество на крайно множество S е крайно и разполага с по-малко елементи, отколкото S. Следователно, не може да съществува биекция между крайното множество S и собственото подмножество на S.

Всяка инективна функция между две крайни множества с еднаква кардиналност е също и сюрективна функция. Аналогично, всяка сюрекция между две крайни множества с еднаква кардиналост е също и инекция.

Обединението на две крайни множества също е крайно:

${\displaystyle |S\cup T|\leq |S|+|T|.}$

Също така:

${\displaystyle |S\cup T|=|S|+|T|-|S\cap T|.}$

В по-общ смисъл, обединението на всеки краен брой крайни множества е крайно. Декартовото произведение на крайни множества също е крайно:

${\displaystyle |S\times T|=|S|\times |T|.}$

Крайно множество с n елемента има 2ⁿ различни подмножества.

Всички крайни множества са изброими, но не всички изброими множества са крайни.