Конечное множество

Конечное множество — множество, равномощное отрезку натурального ряда, а также пустое множество, называется конечным. В противном случае множество называется бесконечным. Например,

[math]\displaystyle{ \{2,4,6,8,10\} }[/math]

конечное множество из пяти элементов. Число элементов конечного множества является натуральным числом и называется мощностью множества. Множество натуральных чисел бесконечно:

[math]\displaystyle{ \{1,2,3,\ldots\}. }[/math]

Конечные множества играют особую роль в комбинаторике, которая изучает дискретные объекты. Рассуждения о конечных множествах используют принцип Дирихле, согласно которому не может существовать инъекция из большего конечного множества в меньшее.

Формальное определение

Два множества [math]\displaystyle{ X }[/math] и [math]\displaystyle{ Y }[/math] называются эквивалентными, если существует биективное отображение одного множества в другое. Если множества X и Y эквивалентны, то этот факт записывают [math]\displaystyle{ X \sim Y }[/math] или [math]\displaystyle{ |X|=|Y| }[/math] и говорят, что множества имеют одинаковые мощности.

Множество [math]\displaystyle{ X }[/math] называется конечным, если оно эквивалентно множеству [math]\displaystyle{ \{1, 2, \dots, n\} }[/math] при некотором неотрицательном целом [math]\displaystyle{ \ n }[/math]. При этом число [math]\displaystyle{ \ n }[/math] называется количеством элементов множества [math]\displaystyle{ X }[/math], что записывается как [math]\displaystyle{ |X|=n }[/math].

В частности, пустое множество является конечным множеством, количество элементов которого равно 0, то есть, [math]\displaystyle{ |\varnothing|= 0 }[/math].

Существуют и другие определения конечного множества:

• множество конечно, если оно индуктивно;
• множество конечно, если множество всех его подмножеств нерефлексивно;
• множество конечно, если оно нерефлексивно;
• множество конечно, если оно не является объединением двух непересекающихся множеств, каждое из которых эквивалентно данному множеству.

Проблема определения конечности множеств в общем случае неразрешима (теорема Трахтенброта). Не существует ни самого слабого, ни самого сильного определения конечного множества. Для каждой логической формулы, являющейся определением конечного множества, существует более сильная и более слабая формулы. Существует неограниченное число логических формул, определяющих конечные множества, и среди них неограниченное множество независимых определений.

Свойства

• Регулярное множество не эквивалентно никакому своему собственному подмножеству;
• Если конечные множества [math]\displaystyle{ X_1, \dots, X_n }[/math] попарно не пересекаются (то есть, [math]\displaystyle{ X_i\cap X_j =\varnothing }[/math]), то

  [math]\displaystyle{ |X_1 \cup X_2 \cup \dots \cup X_n| = |X_1| + |X_2| + \dots + |X_n| }[/math];

• Если [math]\displaystyle{ X_1, \dots, X_n }[/math] — конечные множества, то

  [math]\displaystyle{ |X_1 \times X_2 \times \dots \times X_n|=|X_1| \times|X_2| \times \dots \times|X_n| }[/math];

• Если [math]\displaystyle{ X }[/math] — конечное множество, то мощность его булеана равна

  [math]\displaystyle{ \ |2^X|=2^{|X|}. }[/math]

См. также

• Бесконечное множество

Литература

• Френкель А. А., Бар-Хиллел Р. Основания теории множеств. — М.: Мир, 1966. — 555 с.