Перечисление

Перечисление — это полный упорядоченный список всех элементов коллекции. Этот термин обычно используется в и информатике для обозначения списка всех элементов множества математике . Точные требования к перечислению (например, должно ли множество быть конечным или разрешено ли в списке содержать повторения) зависят от дисциплины исследования и контекста конкретной проблемы.

Некоторые наборы могут быть пронумерованы посредством естественного порядка (например, 1, 2, 3, 4, ... для набора натуральных чисел ), но в других случаях может потребоваться наложить (возможно, произвольный) порядок. В некоторых контекстах, таких как перечислительная комбинаторика , термин перечисление используется больше в смысле подсчета — с упором на определение количества элементов, содержащихся в наборе, а не на составление явного списка этих элементов.

Комбинаторика

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

Теория множеств

В теории множеств понятие перечисления имеет более широкий смысл и не требует, чтобы перечисляемое множество было конечным.

Листинг

Когда перечисление используется в контексте упорядоченного списка , мы налагаем своего рода требования к структуре упорядочения для набора индексов . Хотя мы можем сделать требования к упорядочению довольно мягкими, чтобы обеспечить большую общность, наиболее естественной и распространенной предпосылкой является то, чтобы набор индексов был хорошо упорядочен . Согласно этой характеристике, упорядоченное перечисление определяется как сюръекция (отношение онто) с хорошо упорядоченной областью. Это определение является естественным в том смысле, что заданный правильный порядок в наборе индексов обеспечивает уникальный способ составить список следующего элемента при частичном перечислении.

Счётное и неисчисляемое

Если не указано иное, перечисление осуществляется с помощью натуральных чисел . То есть нумерация множества S $является$ биективной функцией натуральных чисел $\mathbb {N}$ или начальный сегмент ${1, ..., n}$ натуральных чисел в $S$ .

Множество счетно , если его можно перечислить, то есть если существует его перечисление. В противном случае это неисчислимо . Например, множество действительных чисел несчетно.

Множество является конечным , если его можно перечислить с помощью собственного начального отрезка ${1, ..., n}$ натуральных чисел, и в этом случае его мощность равна $n$ . Пустое множество конечно, так как его можно перечислить с помощью пустого начального отрезка натуральных чисел.

Термин перечислимое множество иногда используется для счетных множеств. Однако он также часто используется для вычислимо перечислимых множеств , которые представляют собой счетные множества, для которых функция перечисления может быть вычислена с помощью алгоритма.

Чтобы не различать конечное и счетное бесконечное множество, часто полезно использовать другое эквивалентное определение: множество $S$ счетно тогда и только тогда, когда существует инъективная функция из него в натуральные числа.

Примеры

Натуральные числа перечислимы функцией f ( x ) = x . В этом случае $f\colon \mathbb {N} \to \mathbb {N}$ это просто тождественная функция .
$\mathbb {Z}$ , набор целых чисел перечислим с помощью $f(x):={\frac {1-(-1)^{x}\,(2\,x+1)}{4}}$ $f\colon \mathbb {N} _{0}\to \mathbb {Z}$ является биекцией, поскольку каждому натуральному числу соответствует ровно одно целое число. В следующей таблице приведены первые несколько значений этого перечисления:
х 0 1 2 3 4 5 6 7 8
е ( х ) 0 1 -1 2 -2 3 -3 4 -4
Все (непустые) конечные множества перечислимы. Пусть S — конечное множество с n > 0 элементами и пусть K = {1,2,..., n }. Выберите любой элемент s в S и присвойте f ( n ) = s . Теперь положим S' = S − { s } (где − обозначает разность множеств ). Выберите любой элемент s' ∈ S' и присвойте f ( n − 1) = s' . Продолжайте этот процесс до тех пор, пока всем элементам набора не будут присвоены натуральные числа. Затем $f:K\to S$ является перечислением S .
Действительные числа не имеют счетного перечисления, что доказано диагональным аргументом Кантора и первым доказательством несчетности Кантора .

Характеристики

Перечисление множества (в этом смысле) существует тогда и только тогда, когда множество счетно .
Если набор перечислим, он будет иметь несчетное количество различных перечислений, за исключением вырожденных случаев пустого набора или (в зависимости от точного определения) множеств с одним элементом. Однако, если требуется, чтобы перечисления были инъективными , и допускается только ограниченная форма частичности, так что если f ( n ) определено, то f ( m ) должно быть определено для всех m < n , тогда конечный набор из N элементов имеет ровно N ! перечисления.
Нумерация e множества S с областью определения $\mathbb {N}$ индуцирует хороший порядок ≤ на этом множестве, определенном как s ≤ t , тогда и только тогда, когда $\min e^{-1}(s)\leq \min e^{-1}(t)$ . Хотя порядок может иметь мало общего с базовым набором, он полезен, когда необходим некоторый порядок набора.

ординалы

В теории множеств существует более общее понятие перечисления, чем характеристика, требующая, чтобы область определения перечисляющей функции была начальным сегментом натуральных чисел, где область определения перечисляющей функции может принимать любой порядковый номер . Согласно этому определению, нумерация множества S — это любая сюръекция ординала α S. на Более ограничительная версия перечисления, упомянутая ранее, представляет собой особый случай, когда α — конечный ординал или первый предельный ординал ω. Эта более обобщенная версия расширяет вышеупомянутое определение, включив в него трансфинитные списки.

Согласно этому определению, первый неисчисляемый порядковый номер $\omega _{1}$ можно перечислить с помощью тождественной функции на $\omega _{1}$ так что эти два понятия не совпадают. В более общем смысле, это теорема ZF о том, что любое вполне упорядоченное множество может быть пронумеровано в соответствии с этой характеристикой так, чтобы оно с точностью до перемаркировки совпадало с перечислением обобщенного списка. Если также принять аксиому выбора , то все множества можно перечислить так, чтобы они с точностью до перемаркировки совпадали с наиболее общей формой перечислений.

Поскольку теоретики множеств работают с бесконечными множествами сколь угодно большой мощности , определением по умолчанию среди этой группы математиков нумерации множества является любая произвольная α-последовательность, в которой точно перечислены все ее элементы. Действительно, в книге Джеха, на которую часто ссылаются теоретики множеств, перечисление определяется именно так. Поэтому, чтобы избежать двусмысленности, можно использовать термин «конечно перечислимый» или «счетный» для обозначения одного из соответствующих типов выделенных счетных перечислений.

Сравнение мощностей

Формально наиболее всеобъемлющим определением нумерации множества S является любая сюръекция из произвольного набора индексов I на S . В этом широком контексте каждое множество S можно тривиально пронумеровать с помощью тождественной функции из S на себя. Если не принимать аксиому выбора или один из ее вариантов, S не обязательно должен иметь какой-либо хороший порядок . Даже если принять аксиому выбора, S не обязательно должно иметь естественное упорядочение.

Таким образом, это общее определение подходит для понятия подсчета, когда нас интересует «сколько», а не «в каком порядке». На практике это широкое значение перечисления часто используется для сравнения относительных размеров или мощностей различных наборов. Если кто-то работает в теории множеств Цермело-Френкеля без аксиомы выбора, он может захотеть наложить дополнительное ограничение, согласно которому перечисление также должно быть инъективным (без повторений), поскольку в этой теории существование сюръекции из I на S не обязательно. существование инъекции из S в I. предполагают

Теория вычислимости и сложности

В теории вычислимости часто рассматривают счетные перечисления с дополнительным требованием, чтобы отображение из $\mathbb {N}$ (множество всех натуральных чисел) в перечислимом множестве должно быть вычислимо . Перечисляемый набор затем называется рекурсивно перечислимым (или вычислимо перечислимым на более современном языке), имея в виду использование теории рекурсии при формализации того, что означает вычислимость карты.

В этом смысле подмножество натуральных чисел является вычислимо перечислимым, если оно является диапазоном вычислимой функции. В этом контексте перечисляемый может использоваться для обозначения вычислимо перечислимого. Однако эти определения характеризуют отдельные классы, поскольку существует несчетное множество подмножеств натуральных чисел, которые можно перечислить произвольной функцией с областью определения ω, и только счетное число вычислимых функций. Конкретным примером множества с перечислением, но не вычислимым перечислением, является дополнение останавливающего множества .

Более того, эта характеристика иллюстрирует место, где порядок списка важен. Существует вычислимое перечисление останавливающегося множества, но не такое, в котором элементы перечислены в возрастающем порядке. Если бы оно было, то останавливающее множество было бы разрешимо , что доказуемо неверно. В общем, быть рекурсивно перечислимым — более слабое условие, чем быть разрешимым множеством .

Понятие перебора также изучалось с точки зрения теории сложности вычислений для различных задач в контексте алгоритмов перебора .

См. также

Ссылки

Джех, Томас (2002). Теория множеств, издание третьего тысячелетия (переработанное и дополненное) . Спрингер. ISBN 3-540-44085-2 .

Внешние ссылки

Словарное определение перечисления в Викисловаре