Войти
В математике, счетный набор - это набор с той же мощностью (количество элементов), что и некоторое подмножество набора натуральные числа. Счетное множество - это либо конечное множество, либо счетно бесконечное множество . Независимо от того, конечны они или бесконечны, элементы счетного множества всегда можно подсчитать по одному, и - хотя подсчет может никогда не закончиться - каждому элементу набора соответствует уникальное натуральное число.
Некоторые авторы используют счетное множество только для обозначения счетной бесконечности. Чтобы избежать этой двусмысленности, можно использовать термин «не более чем счетное», когда включены конечные множества, а в противном случае - счетно-бесконечные, перечислимые или счетные.
Георг Кантор ввел термин «счетное множество», противопоставляя счетные множества несчетным (т. Е. Неисчислимым или неисчислимым). Сегодня счетные множества составляют основу раздела математики под названием дискретная математика.
Множество S счетно если существует инъективная функция f от S до натуральных чисел N= {0, 1, 2, 3,...}.
Если такое f может быть найдено, что также сюръективно (и, следовательно, биективно ), то S называется счетно бесконечным.
Другими словами, набор является счетно бесконечным, если он имеет взаимно однозначное соответствие с набором натуральных чисел, N . В этом случае мощность набора обозначается 
Эта терминология не универсальна. Некоторые авторы используют счетный для обозначения того, что здесь называется счетно бесконечным, и не включают конечные множества.
Также могут быть приведены альтернативные (эквивалентные) формулировки определения в терминах биективной функции или сюръективной функции. См. § Формальный обзор без подробностей ниже.
В 1874 году, в своей первой статье по теории множеств, Кантор доказал, что множество действительных чисел неисчислимо, тем самым показывая, что не все бесконечные множества счетны. В 1878 году он использовал взаимно однозначные соответствия для определения и сравнения мощностей. В 1883 году он расширил натуральные числа с помощью своих бесконечных ординалов и использовал наборы ординалов для создания бесконечного множества множеств, имеющих различные бесконечные мощности.
A set - это набор элементов, который можно описать разными способами. Один из способов - просто перечислить все его элементы; например, набор, состоящий из целых чисел 3, 4 и 5, может быть обозначен {3, 4, 5}. Однако это эффективно только для небольших наборов; для больших наборов это займет много времени и может привести к ошибкам. Вместо перечисления каждого отдельного элемента иногда используется многоточие («...»), если автор считает, что читатель может легко угадать, чего не хватает; например, {1, 2, 3,..., 100} предположительно обозначает набор целых чисел от 1 до 100. Однако даже в этом случае все элементы все еще можно перечислить, потому что множество конечно.
Некоторые наборы бесконечны; эти наборы содержат более n элементов для любого целого n. Например, набор натуральных чисел, обозначаемый {0, 1, 2, 3, 4, 5,...}, имеет бесконечно много элементов, и мы не можем использовать какое-либо обычное число для определения его размера. Тем не менее, оказывается, что у бесконечных множеств действительно есть четко определенное понятие размера (или, точнее, мощности, технический термин для количества элементов в наборе), и не все бесконечные множества имеют одинаковую мощность.
Биективное отображение целых чисел в четные Чтобы понять, что это означает, сначала исследуем, что это не означает. Например, существует бесконечно много нечетных целых чисел, бесконечно много четных целых чисел и (следовательно) бесконечно много целых чисел в целом. Однако оказывается, что количество четных целых чисел, которое совпадает с количеством нечетных целых чисел, также совпадает с количеством целых чисел в целом. Это потому, что мы можем расположить вещи так, что для каждого целого числа существует различное четное число:... −2 → −4, −1 → −2, 0 → 0, 1 → 2, 2 → 4,... ; или, в более общем смысле, n → 2n (см. рисунок). Здесь мы расположили целые числа и четные целые числа во взаимно-однозначном соответствии (или bijection ), что является функцией , которая отображает два набора таким образом, что каждый элемент каждого набора соответствует одному элементу в другом наборе.
Однако не все бесконечные множества имеют одинаковую мощность. Например, Георг Кантор (который ввел эту концепцию) продемонстрировал, что действительные числа не могут быть поставлены во взаимно однозначное соответствие с натуральными числами (неотрицательными целыми числами), и, следовательно, что множество действительных чисел числа имеет большую мощность, чем набор натуральных чисел.
Набор является счетным, если: (1) он конечен или (2) имеет ту же мощность (размер), что и набор натуральных чисел (т. Е. Счетный). Точно так же набор является счетным, если он имеет ту же мощность, что и некоторое подмножество набора натуральных чисел. В противном случае это бесчисленное множество.
По определению, множество S является счетным, если существует инъективная функция f: S → N от S до натуральные числа N= {0, 1, 2, 3,...}.
Может показаться естественным разделить наборы на разные классы: собрать вместе все наборы, содержащие один элемент; все наборы, содержащие два элемента вместе;...; наконец, соберите все бесконечные множества и рассмотрите их как имеющие одинаковый размер. Однако эта точка зрения не соответствует естественному определению размера.
Чтобы прояснить это, нам понадобится концепция биекции. Хотя «биекция» кажется более продвинутой концепцией, чем число, обычное развитие математики с точки зрения теории множеств определяет функции перед числами, поскольку они основаны на гораздо более простых наборах. Именно здесь появляется концепция биекции: определите соответствие
Поскольку каждый элемент {a, b, c} соединен ровно с одним элементом { 1, 2, 3}, и наоборот, это определяет биекцию.
Теперь мы обобщаем эту ситуацию и определяем два множества одинакового размера, если и только если между ними существует взаимное соответствие. Для всех конечных множеств это дает нам обычное определение «одинакового размера».
Что касается случая бесконечных множеств, рассмотрим множества A = {1, 2, 3,...}, множество положительных целых чисел и B = {2, 4, 6,...}, множество четных натуральных чисел. Мы утверждаем, что по нашему определению эти множества имеют одинаковый размер и, следовательно, B счетно бесконечен. Напомним, чтобы доказать это, нам нужно продемонстрировать взаимное соответствие между ними. Это может быть достигнуто с помощью присвоения n 2n, так что
Как и в предыдущем примере, каждый элемент A имеет были спарены ровно с одним элементом B, и наоборот. Следовательно, они имеют одинаковый размер. Это пример набора того же размера, что и одно из его собственных подмножеств, что невозможно для конечных наборов.
Точно так же набор всех упорядоченных пар натуральных чисел является счетно бесконечным, что можно увидеть, пройдя путь, подобный показанному на рисунке:
Кантор функция сопряжения присваивает одно натуральное число каждой паре натуральных чисел Полученное отображение происходит следующим образом:
Это отображение покрывает все такие упорядоченные пары.
Если каждую пару рассматривать как числитель и знаменатель вульгарной дроби, то для каждой положительной дроби мы можем придумать соответствующий ему отдельный номер. Это представление включает также натуральные числа, поскольку каждое натуральное число также является дробью N / 1. Таким образом, мы можем сделать вывод, что положительных рациональных чисел ровно столько, сколько положительных целых. Это верно также для всех рациональных чисел, как можно увидеть ниже.
Теорема: Декартово произведение конечного числа счетных множеств счетно.
Эта форма треугольного отображения рекурсивно обобщается на векторы конечного числа натуральных чисел путем многократного преобразования первых двух элементов в натуральное число.. Например, (0,2,3) сопоставляется с (5,3), которое сопоставляется с 39.
Иногда полезно более одного сопоставления: набор, который должен быть счетно бесконечным, отображается на другой set, то этот другой набор отображается на натуральные числа. Например, положительные рациональные числа можно легко сопоставить (подмножество) пар натуральных чисел, потому что p / q отображается в (p, q).
Следующая теорема касается бесконечных подмножеств счетно бесконечных множеств.
Теорема: Каждое подмножество счетного множества счетно. В частности, каждое бесконечное подмножество счетно бесконечного множества является счетно бесконечным.
Например, набор простых чисел является счетным, отображая n-е простое число в n:
Есть также наборы, которые «естественно больше, чем» N . Например, Z набор всех целых чисел или Q, набор всех рациональных чисел, которые интуитивно могут показаться намного больше, чем N . Но внешний вид может быть обманчивым, поскольку мы утверждаем:
Теорема: Z(набор всех целых чисел) и Q (набор всех рациональных чисел) счетны.
Подобным образом множество алгебраических чисел является счетным.
Эти факты легко вытекают из результата, который многие люди считают неинтуитивным.
Теорема: Любое конечное объединение счетных множеств счетно.
Имея дальновидность, зная, что существует неисчислимое множество множеств, мы можем задаться вопросом, можно ли продвинуть этот последний результат дальше. Ответ - «да» и «нет», мы можем расширить его, но для этого нам нужно принять новую аксиому.
Теорема: (в предположении аксиомы счетного выбора ) Объединение счетного числа счетных множеств счетно.
Например, для счетных множеств a, b, c,...
Перечисление для счетного числа счетных множеств Используя вариант треугольного перечисления, который мы видели выше:
Это работает, только если наборы a, b, c,... не пересекаются. Если нет, то объединение еще меньше и, следовательно, тоже счетно по предыдущей теореме.
Нам нужна аксиома счетного выбора, чтобы индексировать все множества a, b, c,... одновременно.
Теорема: Множество всех последовательностей натуральных чисел конечной длины является счетным.
Этот набор представляет собой объединение последовательностей длины 1, последовательностей длины 2, последовательностей длины 3, каждая из которых является счетным набором (конечное декартово произведение). Итак, мы говорим о счетном объединении счетных множеств, которое счетно по предыдущей теореме.
Теорема: Множество всех конечных подмножеств натуральных чисел счетно.
Элементы любого конечного подмножества можно упорядочить в конечную последовательность. Существует только счетное число конечных последовательностей, поэтому также существует только счетное число конечных подмножеств.
Следующая теорема дает эквивалентные формулировки в терминах биективной функции или сюръективной функции. Доказательство этого результата можно найти в тексте Лэнга.
(Основная) Теорема: Пусть S - множество. Следующие утверждения эквивалентны:
Следствие: Пусть S и T - множества.
Теорема Кантора утверждает, что если A - это множество, а P (A) - его набор мощности, то есть набор всех подмножеств A, то не существует сюръективной функции от A до P (А). Доказательство приведено в статье Теорема Кантора. Как непосредственное следствие этого и основной теоремы выше мы имеем:
Предложение: Множество P (N ) не счетно; т.е. он неисчислим.
Для уточнения этого результата см. диагональный аргумент Кантора.
Набор действительных чисел неисчислим (см. первое доказательство несчетности Кантора ), а также множество всех бесконечных последовательностей натуральных чисел.
Доказательства утверждений в предыдущем разделе основаны на существовании функций с определенными свойствами. В этом разделе представлены функции, обычно используемые в этой роли, но не проверки того, что эти функции обладают необходимыми свойствами. Основная теорема и ее следствие часто используются для упрощения доказательств. Заметим, что N в этой теореме можно заменить любым счетно бесконечным множеством.
Предложение: Любое конечное множество счетно.
Доказательство: Пусть S - такое множество. Необходимо рассмотреть два случая: либо S пусто, либо нет. 1.) Пустое множество само является подмножеством натуральных чисел, поэтому оно счетно. 2.) Если S непусто и конечно, то по определению конечности существует биекция между S и множеством {1, 2,..., n} для некоторого натурального положительного числа n. Эта функция является инъекцией из S в N.
Предложение: Любое подмножество счетного множества является счетным.
Доказательство: Ограничение инъективной функции на подмножество его области все еще инъективно.
Предложение: Если S - счетное множество, то S ∪ {x} счетно.
Доказательство: Если x ∈ S, показывать нечего. В противном случае пусть f: S → N будет инъекцией. Определим g: S ∪ {x} → N как g (x) = 0 и g (y) = f (y) + 1 для всех y в S. Эта функция g является инъекцией.
Предложение: Если A и B - счетные множества, то A ∪ B счетно.
Доказательство: Пусть f: A → N и g: B → N быть инъекциями. Определите новую инъекцию h: A ∪ B → N как h (x) = 2f (x), если x находится в A, и h (x) = 2g (x) + 1, если x находится в B, но не в A.
Утверждение: Декартово произведение двух счетных множеств A и B счетно.
Доказательство: Обратите внимание, что N× Nсчетно как следствие определение, потому что функция f: N× N→ N, заданная f (m, n) = 23, инъективна. Тогда из основной теоремы и следствия следует, что декартово произведение любых двух счетных множеств счетно. Это следует потому, что если A и B счетны, существуют сюръекции f: N → A и g: N → B. Итак
- это сюръекция из счетного множества N× Nна множество A × B, и из следствия следует, что A × B счетно. Этот результат обобщается на декартово произведение любого конечного набора счетных множеств, и доказательство следует с помощью индукции по количеству множеств в наборе.
Предложение: целые числа Zявляются счетными, а рациональные числа Qсчетными.
Доказательство: Целые числа Z являются счетными, потому что функция f: Z→ Nзадана как f (n) = 2, если n неотрицательно, и f (n) = 3, если n отрицательная, является инъективной функцией. Рациональные числа Q являются счетными, поскольку функция g: Z× N→ Q, заданная как g (m, n) = m / (n + 1), является сюръекцией из счетного множества Z× Nна рациональные числа Q.
Предложение: алгебраические числа Aсчетны.
Доказательство: Согласно определению, каждое алгебраическое число (включая комплексные числа) является корнем многочлена с целыми коэффициентами. Дано алгебраическое число 
Предложение: Если A n является счетным множеством для каждого n в N, тогда объединение всех A n также является счетным.
Доказательство: Это следствие того факта, что для каждого n существует сюръективная функция g n: N→ A n и, следовательно, функция
задано G (n, m) = g n (m) является сюръекцией. Поскольку N× Nсчетно, из следствия следует, что объединение счетно. Мы используем аксиому счетного выбора в этом доказательстве, чтобы выбрать для каждого n в N сюръекцию g n из непустого набора сюръекций из N - A n.
Топологическое доказательство несчетности действительных чисел описывается в свойстве конечного пересечения.
Если существует множество это стандартная модель (см. внутренняя модель ) теории множеств ZFC, тогда существует минимальная стандартная модель (см. Конструируемая вселенная ). Теорема Левенгейма – Сколема может использоваться, чтобы показать, что эта минимальная модель счетна. Тот факт, что понятие "несчетность" имеет смысл даже в этой модели, и, в частности, что эта модель M содержит элементы, которые являются:
считалась парадоксальной на заре теории множеств, подробнее см. парадокс Сколема.
Минимальная стандартная модель включает все алгебраические числа и все эффективно вычислимые трансцендентные числа, а также многие другие виды чисел.
Счетные наборы могут быть полностью упорядочены различными способами, например:
В обоих примерах порядков лунок здесь любое подмножество имеет наименьший элемент; и в обоих примерах порядков, не являющихся лунками, некоторые подмножества не имеют минимального элемента. Это ключевое определение, которое определяет, является ли общий заказ также заказом на скважину.
Открытие Кантором несчетных множеств в 1874 году было одним из самых неожиданных событий в истории математики. До 1874 года бесконечность не существовала. даже считается законным математическим предметом для большинства людей, поэтому необходимость различать счетные и несчетные бесконечности не могла быть воображаемой инед.
 | Искать счетный в Wiktionary, бесплатный словарь. |
