Перечисление — это полный упорядоченный список всех элементов коллекции. Этот термин обычно используется в математике и информатике для обозначения списка всех элементов множества . Точные требования к перечислению (например, должно ли множество быть конечным или разрешено ли в списке содержать повторения) зависят от дисциплины исследования и контекста конкретной проблемы.
Некоторые наборы можно пронумеровать посредством естественного порядка (например, 1, 2, 3, 4, ... для набора натуральных чисел ), но в других случаях может потребоваться наложить (возможно, произвольный) порядок. В некоторых контекстах, таких как перечислительная комбинаторика , термин перечисление используется больше в смысле подсчета — с упором на определение количества элементов, содержащихся в наборе, а не на составление явного списка этих элементов.
В комбинаторике перечисление означает подсчет , т. е. определение точного числа элементов конечных множеств, обычно сгруппированных в бесконечные семейства, например семейство множеств, каждое из которых состоит из всех перестановок некоторого конечного множества. Во многих разделах математики существуют развитые разделы, связанные с перечислением в этом смысле объектов особого рода. Например, при перечислении разделов и перечислении графов цель состоит в том, чтобы подсчитать разделы или графы, соответствующие определенным условиям.
В теории множеств понятие перечисления имеет более широкий смысл и не требует, чтобы перечисляемое множество было конечным.
Когда перечисление используется в контексте упорядоченного списка , мы налагаем своего рода требования к структуре упорядочения для набора индексов . Хотя мы можем сделать требования к упорядочению довольно мягкими, чтобы обеспечить большую общность, наиболее естественной и распространенной предпосылкой является то, чтобы набор индексов был хорошо упорядочен . Согласно этой характеристике, упорядоченное перечисление определяется как сюръекция (отношение онто) с хорошо упорядоченной областью. Это определение является естественным в том смысле, что заданный правильный порядок в наборе индексов обеспечивает уникальный способ составить список следующего элемента при частичном перечислении.
Если не указано иное, перечисление осуществляется с помощью натуральных чисел . То есть нумерация множества S является биективной функцией натуральных чисел или начального сегмента {1, ..., n } натуральных чисел до S .
Множество счетно , если его можно перечислить, то есть если существует его перечисление. В противном случае это неисчислимо . Например, множество действительных чисел несчетно.
Множество является конечным , если его можно перечислить с помощью собственного начального отрезка {1, ..., n } натуральных чисел, и в этом случае его мощность равна n . Пустое множество конечно, так как его можно перечислить с помощью пустого начального отрезка натуральных чисел.
Терминперечислимое множествоиногда используется для счетных множеств. Однако он также часто используется длявычислимо перечислимых множеств, которые представляют собой счетные множества, для которых функция перечисления может быть вычислена с помощью алгоритма.
Чтобы не различать конечное и счетное бесконечное множество, часто полезно использовать другое эквивалентное определение: множество S счетно тогда и только тогда, когда существует инъективная функция из него в натуральные числа.
В теории множеств существует более общее понятие перечисления, чем характеристика, требующая, чтобы область определения перечисляющей функции была начальным сегментом натуральных чисел, где область определения перечисляющей функции может принимать любой порядковый номер . Согласно этому определению, нумерация множества S — это любая сюръекция ординала α на S. Более ограничительная версия перечисления, упомянутая ранее, представляет собой особый случай, когда α — конечный ординал или первый предельный ординал ω. Эта более обобщенная версия расширяет вышеупомянутое определение, включив в него трансфинитные списки.
Согласно этому определению, первый несчетный ординал можно занумеровать тождественной функцией так , что эти два понятия не совпадают. В более общем смысле, это теорема ZF о том, что любое хорошо упорядоченное множество можно перечислить в соответствии с этой характеристикой так, чтобы оно с точностью до перемаркировки совпадало с перечислением обобщенного списка. Если также принять аксиому выбора , то все множества можно перечислить так, чтобы они с точностью до перемаркировки совпадали с наиболее общей формой перечислений.
Поскольку теоретики множеств работают с бесконечными множествами сколь угодно большой мощности , определением по умолчанию среди этой группы математиков нумерации множества является любая произвольная α-последовательность, в которой точно перечислены все ее элементы. Действительно, в книге Джеха, на которую часто ссылаются теоретики множеств, перечисление определяется именно так. Поэтому, чтобы избежать двусмысленности, можно использовать термин «конечно перечислимый» или « счетный» для обозначения одного из соответствующих типов выделенных счетных перечислений.
Формально наиболее всеобъемлющим определением нумерации множества S является любая сюръекция из произвольного набора индексов I на S. В этом широком контексте каждое множество S можно тривиально пронумеровать с помощью тождественной функции из S на себя. Если не принимать аксиому выбора или один из ее вариантов, S не обязательно должен иметь какой-либо хороший порядок . Даже если принять аксиому выбора, S не обязательно должно иметь естественное упорядочение.
Таким образом, это общее определение подходит для понятия подсчета, когда нас интересует «сколько», а не «в каком порядке». На практике это широкое значение перечисления часто используется для сравнения относительных размеров или мощностей различных наборов. Если кто-то работает в теории множеств Цермело-Френкеля без аксиомы выбора, он может захотеть наложить дополнительное ограничение, согласно которому перечисление также должно быть инъективным (без повторений), поскольку в этой теории существование сюръекции из I на S не обязательно. предполагают существование инъекции из S в I.
В теории вычислимости часто рассматриваются счетные перечисления с дополнительным требованием, чтобы отображение (множества всех натуральных чисел) в перечислимое множество было вычислимым . Перечисляемый набор затем называется рекурсивно перечислимым (или вычислимо перечислимым на более современном языке), имея в виду использование теории рекурсии при формализации того, что означает вычислимость карты.
В этом смысле подмножество натуральных чисел является вычислимо перечислимым, если оно является диапазоном вычислимой функции. В этом контексте перечисляемый может использоваться для обозначения вычислимо перечислимого. Однако эти определения характеризуют отдельные классы, поскольку существует несчетное количество подмножеств натуральных чисел, которые можно перечислить произвольной функцией с областью определения ω, и только счетное число вычислимых функций. Конкретным примером множества с перечислением, но не вычислимым перечислением, является дополнение останавливающего множества .
Более того, эта характеристика иллюстрирует место, где порядок списка важен. Существует вычислимое перечисление останавливающегося множества, но не такое, в котором элементы перечислены в возрастающем порядке. Если бы оно было, то останавливающее множество было бы разрешимо , что доказуемо неверно. В общем, быть рекурсивно перечислимым — более слабое условие, чем быть разрешимым множеством .
Понятие перебора также изучалось с точки зрения теории сложности вычислений для различных задач в контексте алгоритмов перебора .
Словарное определение перечисления в Викисловаре
