Введение
Перечисление – это полный, упорядоченный список всех элементов коллекции. Этот термин обычно используется в математике и информатике для обозначения списка всех элементов множества. Точные требования к перечислению (например, должно ли множество быть конечным или список может содержать повторения) зависят от области исследования и контекста конкретной задачи. Некоторые множества можно перечислить, используя естественный порядок (например, 1, 2, 3, 4 для множества положительных целых чисел), но в других случаях может потребоваться задать (возможно, произвольный) порядок. В некоторых контекстах, таких как энумеративная комбинаторика, термин "перечисление" используется скорее в значении подсчета – с акцентом на определение количества элементов, содержащихся в множестве, а не на создание явного списка этих элементов.
An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the elements of a set. The precise requirements for an enumeration (for example, whether the set must be finite, or whether the list is allowed to contain repetitions) depend on the discipline of study and the context of a given problem. Some sets can be enumerated by means of a natural ordering (such as 1, 2, 3, 4, for the set of positive integers), but in other cases it may be necessary to impose a (perhaps arbitrary) ordering. In some contexts, such as enumerative combinatorics, the term enumeration is used more in the sense of counting – with emphasis on determination of the number of elements that a set contains, rather than the production of an explicit listing of those elements.
Комбинаторная теория
В комбинаторике перечисление означает подсчёт, то есть определение точного числа элементов конечных множеств, обычно объединённых в бесконечные семейства, такие как семейство множеств, каждое из которых состоит из всех перестановок некоторого конечного множества. Во многих областях математики существуют активно развивающиеся направления, посвящённые перечислению в этом смысле объектов особого типа. Например, в задаче перечисления разбиений и перечисления графов целью является подсчёт разбиений или графов, удовлетворяющих определённым условиям.
Теория множеств
В теории множеств понятие перечисления имеет более широкий смысл и не требует, чтобы множество, которое перечисляется, было конечным.
Включение
Когда перечисление используется в контексте упорядоченного списка, мы накладываем определенные требования к структуре упорядочивания на множество индексов. Хотя эти требования к упорядочиванию могут быть достаточно мягкими для обеспечения высокой обобщенности, наиболее естественным и распространенным предварительным условием является то, что множество индексов должно быть вполне упорядочено. В соответствии с этим, упорядоченное перечисление определяется как сюръекция (отображение «на») с вполне упорядоченной областью определения. Это определение естественно, поскольку заданное вполне упорядочивание множества индексов предоставляет единственный способ определить следующий элемент при частичном перечислении.
Подсчитываемые и не подсчитываемые
Если не указано иное, перечисление осуществляется посредством натуральных чисел. То есть, перечисление множества S – это биекция из множества натуральных чисел или начального сегмента натуральных чисел в S. Множество называется счетным, если его можно перечислить, то есть если существует его перечисление. В противном случае оно называется несчетным. Например, множество вещественных чисел несчетно. Множество называется конечным, если его можно перечислить посредством собственного начального сегмента натуральных чисел, в этом случае его мощность равна n. Пустое множество конечно, поскольку его можно перечислить посредством пустого начального сегмента натуральных чисел. Термин «множество» иногда используется для счетных множеств. Однако он также часто используется для вычислимо перечислимых множеств, которые представляют собой счетные множества, для которых функцию перечисления можно вычислить алгоритмически. Чтобы избежать различия между конечным и счетно бесконечным множеством, часто полезно использовать другое, эквивалентное определение: множество S счетно тогда и только тогда, когда существует инъективное отображение из S в натуральные числа.
A set is countable if it can be enumerated, that is, if there exists an enumeration of it. Otherwise, it is uncountable. For example, the set of the real numbers is uncountable. A set is finite if it can be enumerated by means of a proper initial segment of the natural numbers, in which case, its cardinality is n. The empty set is finite, as it can be enumerated by means of the empty initial segment of the natural numbers. The term set is sometimes used for countable sets. However it is also often used for computably enumerable sets, which are the countable sets for which an enumeration function can be computed with an algorithm. For avoiding to distinguish between finite and countably infinite set, it is often useful to use another definition that is equivalent: A set S is countable if and only if there exists an injective function from it into the natural numbers.
Свойства
Существует перечисление для множества (в этом смысле) тогда и только тогда, когда множество счетно. Если множество счетно, оно будет иметь несчетное множество различных перечислений, за исключением вырожденных случаев пустого множества или (в зависимости от точного определения) множеств, содержащих один элемент. Однако, если требуется, чтобы перечисления были инъективными и допускается лишь ограниченная форма частичности, а именно, если f(n) определено, то f(m) должно быть определено для всех m < n, то конечное множество из N элементов имеет ровно N! перечислений. Перечисление e множества S с областью определения индуцирует на этом множестве отношение полного порядка ≤, определяемое условием s ≤ t тогда и только тогда, когда… Хотя этот порядок может мало зависеть от исходного множества, он полезен, когда требуется какое-либо упорядочение элементов множества.
Оригиналы
В теории множеств существует более общее понятие перечисления, чем характеристика, требующая, чтобы область определения функции перечисления была начальным отрезком натуральных чисел. В этом определении область определения функции перечисления может быть любым ординалом. Согласно этому определению, перечисление множества S – это любое сюръективное отображение из ординала α на S. Более ограничивающая версия перечисления, упомянутая ранее, является частным случаем, когда α – конечный ординал или первый предельный ординал ω. Эта более общая версия расширяет вышеупомянутое определение, охватывая трансфинитные перечисления. Согласно этому определению, первое несчётное ординальное число можно перечислить функцией тождества на самом себе, так что эти два понятия не совпадают. В более общем виде, это теорема ZF, что любое хорошо упорядоченное множество можно перечислить в соответствии с этой характеристикой, так что оно совпадает с обобщённым перечислением с точностью до переобозначения. Если также принять аксиому выбора, то все множества можно перечислить так, чтобы они совпадали с наиболее общей формой перечислений с точностью до переобозначения. Поскольку теоретики множеств работают с бесконечными множествами произвольно больших кардинальностей, определение перечисления множества, принятое среди этой группы математиков, как правило, представляет собой любую α-последовательность, точно перечисляющую все его элементы. Действительно, в книге Джеха, которая является общепринятой ссылкой для теоретиков множеств, перечисление определяется именно так. Поэтому, чтобы избежать неоднозначности, можно использовать термины конечно перечислимое или счётное, чтобы обозначить один из соответствующих типов выделенных счётных перечислений.
Сравнение кардинальностей
Формально, наиболее всеобъемлющим определением перечисления множества S является любое сюръективное отображение из произвольного множества индексов I на S. В этом широком контексте любое множество S может быть тривиально перечислено тождественным отображением из S на само себя. Если не предполагать аксиому выбора или один из её вариантов, множество S не обязательно должно обладать каким-либо хорошим порядком. Даже если аксиома выбора предполагается, множество S не обязательно должно обладать естественным хорошим порядком. Это общее определение, следовательно, хорошо подходит для понятия счета, где нас интересует "сколько", а не "в каком порядке". На практике это широкое понимание перечисления часто используется для сравнения относительных размеров или кардинальностей различных множеств. Если работать в теории множеств Цермело — Френкеля без аксиомы выбора, может потребоваться наложить дополнительное ограничение, что перечисление также должно быть инъективным (без повторений), поскольку в этой теории существование сюръекции из I на S не обязательно влечет за собой существование инъекции из S в I.
Теория вычислимости и сложности
В теории вычислимости часто рассматривается счетное перечисление с дополнительным требованием, что отображение из (множества всех натуральных чисел) в перечисляемое множество должно быть вычислимым. Перечисляемое множество называется рекурсивно перечислимым (или вычислимо перечислимым в более современной терминологии), что отражает использование теории рекурсии в формализации понятия вычислимости отображения. В этом смысле подмножество натуральных чисел является вычислимо перечислимым, если оно является областью значений вычислимой функции. В этом контексте термин "перечислимое" может использоваться для обозначения "вычислимо перечислимого". Однако эти определения характеризуют различные классы, поскольку существует несчетно много подмножеств натуральных чисел, которые могут быть перечислены произвольной функцией с областью определения ω, и лишь счетно много вычислимых функций. Конкретным примером множества, имеющего перечисление, но не вычислимое перечисление, является дополнение к множеству останавливающихся вычислений. Более того, эта характеристика иллюстрирует важность порядка перечисления. Существует вычислимое перечисление множества останавливающихся вычислений, но не такое, которое перечисляет элементы в возрастающем порядке. Если бы такое перечисление существовало, то множество останавливающихся вычислений было бы разрешимым, что, как доказано, неверно. В общем случае, рекурсивная перечислимость является более слабым условием, чем разрешимость. Понятие перечисления также изучалось с точки зрения теории вычислительной сложности для различных задач в контексте алгоритмов перечисления.