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