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

редактировать

Полный упорядоченный список всех элементов в коллекции

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

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

Содержание

1 Комбинаторика
2 Теория множеств
- 2.1 Листинг
- 2.2 Счетное и несчетное
  - 2.2.1 Примеры
  - 2.2.2 Свойства
- 2.3 Порядковые числа
- 2.4 Сравнение мощностей
3 Теория вычислимости и сложности
4 См. Также
5 Ссылки
6 Внешние ссылки

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

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

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

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

Листинг

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

Счетное или несчетное

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

Как сюръективное отображение из $N {\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$ (натуральные числа ) в S (т. Е. Каждый элемент S является образом хотя бы одного натурального числа). Это определение особенно подходит для вопросов вычислимости и элементарной теории множеств.

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

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

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

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

Примеры

натуральные числа перечисляются функцией f (x) = x. В этом случае $f: N → N {\ displaystyle f: \ mathbb {N} \ to \ mathbb {N}}$ $f: \ mathbb {N} \ to \ mathbb {N}$ - это просто функция идентичности.
$Z {\ displaystyle \ mathbb {Z}}$ $\ mathbb {Z}$ , набор целых чисел перечислим с помощью

f (x): = {- (x + 1) / 2, если x нечетное x / 2, если x четно. {\ displaystyle f (x): = {\ begin {cases} - (x + 1) / 2, {\ t_dv {if}} x {\ t_dv {is odd}} \\ x / 2, {\ t_dv {if}} x {\ t_dv {четно}}. \ end {case}}}

f (x): = {\ begin {cases} - (x + 1) / 2, {\ t_dv {if}} x { \ t_dv {нечетное}} \\ x / 2, {\ t_dv {if}} x {\ t_dv {четное}}. \ end {cases}}

$f: N → Z {\ displaystyle f: \ mathbb {N} \ to \ mathbb {Z}}$ $f: \ mathbb {N} \ to \ mathbb {Z }$ - это биекция, поскольку каждое натуральное число соответствует ровно одному целому числу. В следующей таблице приведены первые несколько значений этого перечисления:

x	0	1	2	3	4	5	6	7	8
ƒ (x)	0	−1	1	−2	2	−3	3	−4	4

Все (непустые) конечные множества являются перечислимый. Пусть S - конечное множество с n>0 элементами, и пусть K = {1,2,..., n}. Выберите любой элемент s в S и присвойте ƒ (n) = s. Теперь установите S '= S - {s} (где - обозначает разность множеств ). Выберем любой элемент s '∈ S' и присвоим ƒ (n - 1) = s '. Продолжайте этот процесс, пока всем элементам набора не будут присвоены натуральные числа. Тогда $f: K → S {\ displaystyle f: K \ to S}$ ${\ displaystyle f: K \ to S}$ является перечислением S.
вещественные числа не имеют счетного перечисления. как доказано диагональным аргументом Кантора и первым доказательством несчетности Кантора.

Свойства

Существует перечисление для множества (в этом смысле) тогда и только тогда, когда множество счетно.
Если набор перечислим, он будет иметь несчетное бесконечное множество различных перечислений, за исключением вырожденных случаев пустого набора или (в зависимости от точного определения) наборов с одним элементом. Однако, если требуется, чтобы перечисления были инъективными и допускаются только ограниченные формы пристрастности, такие, что если ƒ (n) определено, то ƒ (m) должно быть определено для всех m < n, then a finite set of N elements has exactly N! enumerations.
Перечисление e множества S с доменом $N {\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$ индуцирует правильный порядок ≤ для того набора, который определяется s ≤ t тогда и только тогда, когда $min {\ displaystyle \ min}$ $\ min$ e (s) ≤ $min {\ displaystyle \ min}$ $\ min$ e (t). Хотя порядок может иметь мало общего с базовым набором, он полезен, когда необходим некоторый порядок набора.

Порядковые числа

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

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

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

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

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

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

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

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

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

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

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

См. также

Ссылки

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

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

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