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

Крайното множество е множество, което има ограничен брой елементи. С други думи, това е множество, чиито елементи принципно биха могли да бъдат преброени. Например, $\{2,4,6,8,10\}$ е крайно множество с пет елемента. Броят на елементите е естествено число и се нарича кардиналност на множеството. Множество, което има безброй елементи, се нарича безкрайно множество. Например, множеството на всички положителни числа е безкрайно – $\{1,2,3,\ldots \}$.

Крайните множества са от особено значение в комбинаториката (математическото изследване на броенето). Много от аргументите, касаещи крайни множества, разчитат на принципа на Дирихле, който гласи, че не може да съществува инективна функция от по-голямо крайно множество към по-малко крайно множество.

Определение

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

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

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

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

$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.

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

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

$|S\cup T|\leq |S|+|T|.$

Също така:

$|S\cup T|=|S|+|T|-|S\cap T|.$

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

$|S\times T|=|S|\times |T|.$

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

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