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

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

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

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

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

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

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

Листинг

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

Счетное против бесчисленного

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

Мы также можем определить его по-другому при работе с конечными множествами. В этом случае перечисление может быть определено следующим образом:

  • Как биективное отображение S на начальный отрезок натуральных чисел. Это определение особенно подходит для комбинаторных вопросов и конечных множеств; то начальный сегмент {1,2, ..., п } для некоторого п , которая является мощность из S .

В первом определении меняется, требуется ли отображение также быть инъективным (т. Е. Каждый элемент S является изображением ровно одного натурального числа) и / или разрешено быть частичным (т. Е. Отображение определено только для некоторого естественного числа). числа). В некоторых приложениях (особенно в тех, которые связаны с вычислимостью множества S ), эти различия не имеют большого значения, потому что речь идет только о простом существовании некоторого перечисления, а перечисление в соответствии с либеральным определением обычно подразумевает, что перечисления удовлетворяют более строгим требованиям. требования тоже существуют.

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

Примеры

  • Эти натуральные числа перечислимы функция ф ( х ) = х . В данном случае это просто функция идентичности .
  • , набор целых чисел перечислим
    является биекцией, поскольку каждое натуральное число соответствует ровно одному целому числу. В следующей таблице приведены первые несколько значений этого перечисления:
    Икс 0 1 2 3 4 5 6 7 8
    f ( x ) 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 ' . Продолжайте этот процесс, пока всем элементам набора не будут присвоены натуральные числа. Тогда это перечисление S .
  • В действительных числах не имеют счетное перечисления как доказано диагональный аргументом Кантора и первый несчетность доказательством Кантора .

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

  • Перечисление для множества (в этом смысле) существует тогда и только тогда, когда множество счетно .
  • Если набор перечислим, он будет иметь бесчисленное множество различных перечислений, за исключением вырожденных случаев пустого набора или (в зависимости от точного определения) наборов с одним элементом. Однако, если требуется, чтобы перечисления были инъективными и допускаются только ограниченные формы пристрастности, такие, что если f ( n ) определено, то f ( m ) должно быть определено для всех m  <  n , тогда конечный набор из N элементов имеет ровно N ! перечисления.
  • Перечисление e множества S с областью определения индуцирует порядок ≤ на этом множестве, определяемом st, тогда и только тогда, когда . Хотя порядок может иметь мало общего с базовым набором, он полезен, когда необходим некоторый порядок набора.

Порядковые

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

Рекомендации

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

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