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

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

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

Определение

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

$f:S\to \{1,\dots ,n\}$

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

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

$x_1,x_2,\dots ,x_n(x_i\in S,1\le i\le n)$.

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

Основни свойства

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

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

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

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

Също така:

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

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

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

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

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