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

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

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

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

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

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

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

Листинг

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

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

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

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

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

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

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

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

Примеры

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

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

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

Икс	0	1	2	3	4	5	6	7	8
ƒ(Икс)	0	−1	1	−2	2	−3	3	−4	4

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

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

Перечисление для множества (в этом смысле) существует тогда и только тогда, когда множество счетный.
Если набор перечислим, он будет иметь бесчисленный бесконечность различных перечислений, за исключением вырожденных случаев пустого множества или (в зависимости от точного определения) множеств с одним элементом. Однако, если требуется, чтобы перечисления были инъективными и допускает только ограниченную форму пристрастности, такую, что если ƒ(п) определяется тогда ƒ(м) должен быть определен для всех м < п, то конечный набор N элементы имеет ровно N! перечисления.
Перечисление е набора S с доменом ${ Displaystyle mathbb {N}}$ вызывает в порядке ≤ на этом множестве, определяемом s ≤ т если и только если ${ displaystyle min}$ е⁻¹(s) ≤ ${ displaystyle min}$ е⁻¹(т). Хотя порядок может иметь мало общего с базовым набором, он полезен, когда необходим некоторый порядок набора.

Порядковые

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

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

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

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

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

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

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

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

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

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

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

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

внешняя ссылка

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

Математическая логика
Общий	Формальный язык Правило формирования Формальное доказательство Формальная семантика Правильная формула Набор Элемент Учебный класс Классическая логика Аксиома Правило вывода Связь Теорема Логическое следствие Теория типов Символ Синтаксис Теория
Системы	Формальная система Дедуктивная система Аксиоматическая система Системы гильбертового стиля Естественный вычет Последовательное исчисление
Традиционная логика	Предложение Вывод Аргумент Срок действия Силлогизм Площадь оппозиции Диаграмма Венна
Исчисление высказываний и Логическая логика	Логические функции Исчисление высказываний Пропозициональная формула Логические связки Таблицы истинности Многозначная логика
Логика предикатов	Первый заказ Квантификаторы Предикат Второго порядка Монадическое исчисление предикатов
Наивная теория множеств	Набор Пустой набор Элемент Перечисление Расширяемость Конечный набор Бесконечный набор Подмножество Набор мощности Счетный набор Бесчисленное множество Рекурсивный набор Домен Codomain Изображение карта Функция Связь Упорядоченная пара
Теория множеств	Основы математики Теория множеств Цермело – Френкеля Аксиома выбора Общая теория множеств Теория множеств Крипке – Платека Теория множеств фон Неймана – Бернейса – Гёделя. Теория множеств Морса – Келли Теория множеств Тарского – Гротендика
Теория моделей	Модель Интерпретация Нестандартная модель Теория конечных моделей Ценность правды Срок действия
Теория доказательств	Формальное доказательство Дедуктивная система Формальная система Теорема Логическое следствие Правило вывода Синтаксис
Вычислимость теория	Рекурсия Рекурсивный набор Рекурсивно перечислимый набор Проблема решения Тезис Черча – Тьюринга Вычислимая функция Примитивная рекурсивная функция