Открыть главное меню

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

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

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

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

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

Два множества   и   называются эквивалентными, если существует биективное отображение одного множества в другое. Если множества X и Y эквивалентны, то этот факт записывают   или   и говорят, что множества имеют одинаковые мощности.

Множество   называется конечным, если оно эквивалентно множеству   при некотором неотрицательном целом  . При этом число   называется количеством элементов множества  , что записывается как  .[1]

В частности, пустое множество является конечным множеством, количество элементов которого равно 0, то есть,  .

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

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

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

СвойстваПравить

  • Регулярное множество не эквивалентно никакому своему собственному подмножеству;[1]
  • Если конечные множества   попарно не пересекаются (то есть,  ), то
     ;
  • Если   — конечные множества, то
     ;
  • Если   — конечное множество, то мощность его булеана равна
     

См. такжеПравить

ПримечанияПравить

  1. 1 2 Соболева Т. С., Чечкин А. В. Дискретная математика. — Академия, 2006. — ISBN 5-7695-2823-0.
  2. 1 2 Френкель, 1966, с. 87.

ЛитератураПравить