В математике , А счетное множество является набором с теми же мощностями ( количество элементов) в качестве некоторого подмножества множества натуральных чисел . Счетное множество - это либо конечное, либо счетно бесконечное множество. Независимо от того, конечны они или бесконечны, элементы счетного множества всегда можно подсчитать по одному, и - хотя счет может никогда не закончиться - каждый элемент набора связан с уникальным натуральным числом.
Некоторые авторы используют счетное множество только для обозначения счетной бесконечности . [1] Чтобы избежать этой двусмысленности, термин не более чем счетный может использоваться, когда включены конечные множества, и счетно бесконечный , перечислимый , [2] или счетный [3] в противном случае.
Георг Кантор ввел термин счетное множество , противопоставляя счетные множества несчетным (т. Е. Несчетным или несчетным [4] ). Сегодня счетные множества составляют основу раздела математики, называемого дискретной математикой .
Определение
Множество S является счетным , если существует инъективная функция п от S к натуральным числам N = {0, 1, 2, 3, ... }. [ необходима ссылка ] [5]
Если можно найти такое f , которое также является сюръективным (и, следовательно, биективным ), то S называется счетно бесконечным .
Другими словами, множество счетное , если она имеет взаимно-однозначное соответствие с естественным набором чисел, N . В этом случае мощность множества обозначается( aleph-null ) - первое в ряду чисел алеф. [6]
Эта терминология не универсальна. Некоторые авторы используют счетный для обозначения того, что здесь называется счетно бесконечным, и не включают конечные множества.
Также могут быть даны альтернативные (эквивалентные) формулировки определения в терминах биективной функции или сюръективной функции. [7] См. Также § Формальный обзор без подробностей ниже.
История
В 1874 году в своей первой статье по теории множеств Кантор доказал, что множество действительных чисел несчетно, тем самым показывая, что не все бесконечные множества являются счетными. [8] В 1878 году он использовал взаимно однозначные соответствия для определения и сравнения мощностей. [9] В 1883 году он расширил натуральные числа с помощью своих бесконечных ординалов и использовал наборы ординалов для создания бесконечного множества множеств, имеющих различные бесконечные мощности. [10]
Вступление
Набор представляет собой набор элементов , и может быть описан во многих отношениях. Один из способов - просто перечислить все его элементы; например, набор, состоящий из целых чисел 3, 4 и 5, может быть обозначен {3, 4, 5}, что называется формой реестра. [11] Однако это эффективно только для небольших наборов; для больших наборов это может занять много времени и привести к ошибкам. Вместо перечисления каждого отдельного элемента иногда используется многоточие ("...") для представления множества элементов между начальным и конечным элементами в наборе, если автор считает, что читатель может легко догадаться, что ... представляет ; например, {1, 2, 3, ..., 100} предположительно обозначает набор целых чисел от 1 до 100. Однако даже в этом случае можно перечислить все элементы, потому что количество элементов в множество конечно.
Некоторые наборы бесконечны ; эти наборы содержат более n элементов, где n - любое целое число, которое можно указать. (Независимо от того, насколько велико заданное целое число n , например, n = 9 × 10 32 , бесконечные наборы содержат более n элементов.) Например, набор натуральных чисел, обозначаемый {0, 1, 2, 3, 4 , 5, ...}, имеет бесконечно много элементов, и мы не можем использовать какое-либо натуральное число для определения его размера. Тем не менее, оказывается, что бесконечные множества действительно имеют четко определенное понятие размера (или, точнее, мощности , технический термин для числа элементов в наборе), и не все бесконечные множества имеют одинаковую мощность.
Чтобы понять, что это означает, сначала рассмотрим, что это не означает. Например, существует бесконечно много нечетных целых чисел, бесконечно много четных целых чисел и (следовательно) бесконечно много целых чисел в целом. Однако оказывается, что количество четных целых чисел, которое совпадает с количеством нечетных целых чисел, также совпадает с количеством целых чисел в целом. Это потому, что мы можем организовать вещи так, чтобы для каждого целого числа было отдельное четное целое число:
Однако не все бесконечные множества имеют одинаковую мощность. Например, Георг Кантор (который ввел эту концепцию) продемонстрировал, что действительные числа не могут быть поставлены во взаимно однозначное соответствие с натуральными числами (неотрицательными целыми числами), и поэтому набор действительных чисел имеет большую мощность, чем набор натуральных чисел.
Множество является счетным, если: (1) оно конечно или (2) оно имеет ту же мощность (размер), что и множество натуральных чисел (т. Е. Счетное). [12] Аналогично, набор является счетным, если он имеет ту же мощность, что и некоторое подмножество набора натуральных чисел. В противном случае это бесчисленное множество .
Формальный обзор без подробностей
По определению, множество S является счетным , если существует инъективную функция F : S → N от S до натуральных чисел N = {0, 1, 2, 3, ...}. Это просто означает , что каждый элемент в S имеет соответствие другой элемент в N .
Может показаться естественным разделить наборы на разные классы: собрать вместе все наборы, содержащие один элемент; все наборы, содержащие два элемента вместе; ...; наконец, соберите все бесконечные множества и рассмотрите их как имеющие одинаковый размер. Однако эта точка зрения не соответствует естественному определению размера.
Чтобы прояснить это, нам понадобится концепция биекции . Хотя «биекция» кажется более продвинутой концепцией, чем число, обычное развитие математики в терминах теории множеств определяет функции перед числами, поскольку они основаны на гораздо более простых наборах. Здесь появляется концепция взаимного соответствия: определить соответствие
- а ↔ 1, б 2, в ↔ 3
Поскольку каждый элемент из { a , b , c } спарен ровно с одним элементом из {1, 2, 3}, и наоборот, это определяет биекцию.
Теперь мы обобщаем эту ситуацию; мы определяем, что два множества имеют одинаковый размер тогда и только тогда, когда между ними существует взаимно однозначное соответствие. Для всех конечных множеств это дает нам обычное определение «одинакового размера».
Что касается случая бесконечных множеств, рассмотрим множества A = {1, 2, 3, ...}, множество натуральных чисел , и B = {2, 4, 6, ...}, множество четных положительные целые числа. Мы утверждаем, что по нашему определению эти множества имеют одинаковый размер и, следовательно, B счетно бесконечен. Напомним, чтобы доказать это, нам нужно продемонстрировать взаимное соответствие между ними. Этого можно добиться с помощью присваивания n ↔ 2 n , так что
- 1 ↔ 2, 2 ↔ 4, 3 ↔ 6, 4 ↔ 8, ....
Как и в предыдущем примере, каждый элемент A был спарен ровно с одним элементом B, и наоборот. Следовательно, они имеют одинаковый размер. Это пример набора того же размера, что и одно из его собственных подмножеств , что невозможно для конечных наборов.
Точно так же набор всех упорядоченных пар натуральных чисел ( декартово произведение двух наборов натуральных чисел, N × N ) счетно бесконечен, что можно увидеть, проследив путь, подобный показанному на рисунке:
Результирующее отображение происходит следующим образом:
- 0 ↔ (0, 0), 1 ↔ (1, 0), 2 ↔ (0, 1), 3 ↔ (2, 0), 4 ↔ (1, 1), 5 ↔ (0, 2), 6 ↔ (3, 0), ....
Это отображение покрывает все такие упорядоченные пары.
Если пара рассматриваются как числитель и знаменатель в виде вульгарной фракции (фракции в виде в / б , где и б ≠ 0 являются целыми числами), то для каждой положительной фракции, мы можем прийти с особым натуральным числом , соответствующее к нему. Это представление также включает натуральные числа, поскольку каждое натуральное число также является дробью N / 1. Таким образом, мы можем сделать вывод, что положительных рациональных чисел ровно столько, сколько положительных целых. Это также верно для всех рациональных чисел, как можно увидеть ниже.
Иногда полезно более одного отображения: набор A, который должен отображаться как счетный, взаимно однозначно отображается (инъекция) в другой набор B, тогда A доказывается как счетный, если B однозначно отображается в набор натуральные числа. Например, набор положительных рациональных чисел может быть легко взаимно однозначно сопоставлен с набором пар натуральных чисел (2-кортежей), потому что p / q отображается на ( p , q ). Поскольку набор пар натуральных чисел взаимно однозначно отображается (фактически взаимно однозначное соответствие или биекция) на набор натуральных чисел, как показано выше, набор положительных рациональных чисел доказывается как счетный.
Теорема: декартово произведение конечного числа счетных множеств счетно.
Эта форма треугольного отображения рекурсивно обобщается на п - кортежи натуральных чисел, то есть ( в 1 , в 2 , 3 , ..., п ) , где я и п натуральные числа, путем многократного отображения первых двух элементов из п -кратного к натуральному числу. Например, (0, 2, 3) можно записать как ((0, 2), 3). Затем (0, 2) отображается в 5, поэтому ((0, 2), 3) отображается в (5, 3), затем (5, 3) отображается в 39. Поскольку другой кортеж из 2, это пара, такая как ( a , b ), отображается на другое натуральное число, разницы между двумя кортежами по одному элементу достаточно, чтобы гарантировать, что кортежи из n отображаются в разные натуральные числа. Итак, инъекция из множества n -наборов в множество натуральных чисел N доказана. Для набора n-кортежей, образованного декартовым произведением конечного числа различных наборов, каждый элемент в каждом кортеже соответствует натуральному числу, поэтому каждый кортеж можно записать в натуральных числах, тогда та же логика применяется для доказательства теоремы .
Следующая теорема касается бесконечных подмножеств счетно бесконечных множеств.
Теорема: каждое подмножество счетного множества счетно. В частности, каждое бесконечное подмножество счетно бесконечного множества счетно бесконечно. [13]
Например, набор простых чисел можно подсчитать, если отобразить n-е простое число в n :
- 2 карты в 1
- 3 карты в 2
- 5 карт в 3
- 7 карт в 4
- 11 карт в 5
- 13 карт в 6
- 17 карт в 7
- 19 карт в 8
- 23 карт в 9
- ...
Есть также наборы , которые «естественно , больше , чем» N . Например, Z множество всех целых чисел или Q , множество всех рациональных чисел , которые интуитивно может показаться гораздо больше , чем N . Но внешний вид может быть обманчивым, потому что мы утверждаем:
Теорема: Z (множество всех целых чисел) и Q (множество всех рациональных чисел) счетны.
Точно так же счетно множество алгебраических чисел . [14]
Эти факты легко вытекают из результата, который многие люди считают не интуитивным.
Теорема: любое конечное объединение счетных множеств счетно.
С предвидением зная, что существует бесчисленное множество множеств, мы можем задаться вопросом, можно ли продвинуть этот последний результат дальше. Ответ - «да» и «нет», мы можем расширить его, но для этого нам нужно принять новую аксиому.
Теорема: (в предположении аксиомы счетного выбора ) Объединение счетного числа счетных множеств счетно.
Например, заданы счетные множества a , b , c , ...
Используя вариант треугольного перечисления, который мы видели выше:
- a 0 соответствует 0
- а 1 карты на 1
- b 0 соответствует 2
- а 2 карты до 3
- b 1 соответствует 4
- c 0 соответствует 5
- а 3 карты до 6
- b 2 соответствует 7
- c 1 соответствует 8
- d 0 соответствует 9
- а 4 карты до 10
- ...
Это работает, только если наборы a , b , c , ... не пересекаются . Если нет, то объединение еще меньше и, следовательно, также счетно по предыдущей теореме.
Нам нужна аксиома счетного выбора, чтобы индексировать все множества a , b , c , ... одновременно.
Теорема: множество всех последовательностей натуральных чисел конечной длины счетно.
Этот набор представляет собой объединение последовательностей длины 1, последовательностей длины 2, последовательностей длины 3, каждая из которых является счетным набором (конечное декартово произведение). Итак, мы говорим о счетном объединении счетных множеств, которое счетно по предыдущей теореме.
Теорема: множество всех конечных подмножеств натуральных чисел счетно.
Элементы любого конечного подмножества можно упорядочить в конечную последовательность. Существует только счетное число конечных последовательностей, поэтому также существует только счетное число конечных подмножеств.
Следующая теорема дает эквивалентные формулировки в терминах биективной функции или сюръективной функции . Доказательство этого результата можно найти в тексте Лэнга. [3]
(Основная) Теорема: Пусть S - некоторое множество. Следующие утверждения эквивалентны:
- S счетно, то существует инъективный функция F : S → N .
- Либо S пусто , либо существует Сюръекция г : N → S .
- Либо S конечен , либо существует взаимно однозначное соответствие ч : N → S .
Следствие: пусть S и T - множества.
- Если функция f : S → T инъективна и T счетно, то S счетно.
- Если функция g : S → T сюръективна и S счетна, то T счетно.
Теорема Кантора утверждает, что если A - это множество, а P ( A ) - его множество степеней , то есть множество всех подмножеств A , то не существует сюръективной функции из A в P ( A ). Доказательство приведено в статье Теорема Кантора . Как непосредственное следствие этого и основной теоремы выше мы имеем:
Предложение: множество P ( N ) не счетно; т.е. бесчисленно .
Для уточнения этого результата см . Диагональный аргумент Кантора .
Множество действительных чисел неисчислимо (см . Первое доказательство несчетности Кантора ), как и множество всех бесконечных последовательностей натуральных чисел.
Некоторые технические детали
Доказательства утверждений в предыдущем разделе основаны на существовании функций с определенными свойствами. В этом разделе представлены функции, обычно используемые в этой роли, но не проверки того, что эти функции обладают необходимыми свойствами. Основная теорема и ее следствие часто используются для упрощения доказательств. Заметим, что N в этой теореме можно заменить любым счетно бесконечным множеством.
Предложение: любое конечное множество счетно.
Доказательство. Пусть S - такое множество. Следует рассмотреть два случая: либо S пусто, либо нет. 1.) Пустое множество само является подмножеством натуральных чисел, поэтому оно счетно. 2.) Если S непусто и конечно, то по определению конечности существует биекция между S и множеством {1, 2, ..., n } для некоторого натурального положительного числа n . Эта функция является инъекцией из S в N .
Предложение: любое подмножество счетного множества счетно. [15]
Доказательство: ограничение инъективной функции на подмножество ее области определения остается инъективным.
Предложение: если S счетное множество, то S ∪ { x } счетно. [16]
Доказательство. Если x ∈ S, показывать нечего. В противном случае пусть f : S → N инъекция. Определить г : S ∪ { х } → N по г ( х ) = 0 и г ( у ) = е ( у ) + 1 для всех у в S . Эта функция g является инъекцией.
Предложение: если A и B счетные множества, то A ∪ B счетно. [17]
Доказательство. Пусть f : A → N и g : B → N инъекции. Определение нового впрыска час : ∪ B → N по ч ( х ) = 2 F ( х ) , если х находится в А и ч ( х ) = 2 г ( х ) + 1 , если х в B , но не в A .
Предложение: декартово произведение двух счетных множеств A и B счетно. [18]
Доказательство. Заметим, что N × N счетно как следствие определения, потому что функция f : N × N → N, заданная формулой f ( m , n ) = 2 m 3 n , инъективна. [19] Тогда из основной теоремы и следствия следует, что декартово произведение любых двух счетных множеств счетно. Это следует из того, если и В счетны есть сюръекции F : N → A и г : N → B . Так
- f × g : N × N → A × B
является сюръекцией из счетного множества N × N в множество A × B, и из следствия следует, что A × B счетно. Этот результат обобщается на декартово произведение любого конечного набора счетных множеств, и доказательство следует индукцией по количеству множеств в наборе.
Предложение: целые числа Z счетны и рациональные числа Q счетны.
Доказательство: целые числа Z счетны, потому что функция f : Z → N, заданная формулой f ( n ) = 2 n, если n неотрицательно, и f ( n ) = 3 - n, если n отрицательно, является инъективной функцией. Рациональных чисел Q счетны , так как функция г : Z × N → Q задается г ( т , п ) = т / ( п + 1) , является сюръекцией от счетного множества Z × N к Rationals Q .
Предложение: В алгебраических числах A счетны.
Доказательство: Согласно определению, каждое алгебраическое число (включая комплексные числа) является корнем многочлена с целыми коэффициентами. Учитывая алгебраическое число, позволять - многочлен с целыми коэффициентами такой, что является k- м корнем полинома, где корни сортируются по абсолютной величине от маленького к большому, а затем по аргументу от маленького к большому. Мы можем определить инъекционную (т.е. взаимно однозначную) функцию f : A → Q, задаваемую формулой, пока является n -м простым числом .
Предложение: если A n - счетное множество для каждого n в N, то объединение всех A n также является счетным. [20]
Доказательство: это следствие того факта, что для каждого n существует сюръективная функция g n : N → A n и, следовательно, функция
заданный формулой G ( n , m ) = g n ( m ), является сюръекцией. Поскольку N × N счетно, из следствия следует, что объединение счетно. В этом доказательстве мы используем аксиому счетного выбора, чтобы выбрать для каждого n в N сюръекцию g n из непустого набора сюръекций из N в A n .
Топологическое доказательство несчетности действительных чисел описано в свойстве конечного пересечения .
Минимальная модель теории множеств счетна
Если есть набор, который является стандартной моделью (см. Внутреннюю модель ) теории множеств ZFC, то существует минимальная стандартная модель ( см. Конструируемая вселенная ). Теорема Левенгейма – Сколема может быть использована, чтобы показать, что эта минимальная модель счетна. Тот факт, что понятие «несчетность» имеет смысл даже в этой модели, и, в частности, что эта модель M содержит элементы, которые:
- подмножества M , следовательно, счетные,
- но бесчисленное количество с точки зрения М ,
считалось парадоксальным на заре теории множеств, подробнее см . парадокс Сколема .
Минимальная стандартная модель включает все алгебраические числа и все эффективно вычислимые трансцендентные числа , а также многие другие типы чисел.
Всего заказов
Счетные наборы можно полностью упорядочить различными способами, например:
- Квитанции (см. Также порядковый номер ):
- Обычный порядок натуральных чисел (0, 1, 2, 3, 4, 5, ...)
- Целые числа в порядке (0, 1, 2, 3, ...; −1, −2, −3, ...)
- Другое ( не очень хорошие заказы):
- Обычный порядок целых чисел (..., −3, −2, −1, 0, 1, 2, 3, ...)
- Обычный порядок рациональных чисел (не может быть явно записан как упорядоченный список!)
В обоих примерах порядков скважин здесь любое подмножество имеет наименьший элемент ; и в обоих примерах порядков не-лунки некоторые подмножества не имеют минимального элемента . Это ключевое определение, которое определяет, является ли общий заказ также и заказом на скважину.
Смотрите также
- Число Алеф
- Подсчет
- Парадокс Гильберта в Гранд Отеле
- Бесчисленное множество
Заметки
- ↑ Рудин 1976 , Глава 2
- ^ Камке 1950 , стр. 2
- ^ a b Ланг 1993 , § 2 главы I
- ↑ Апостол 1969 , Глава 13.19
- ^ Поскольку существует очевидное взаимно однозначное соответствие между N и N * = {1, 2, 3, ... }, не имеет значения, считать ли 0 натуральным числом или нет. В любом случае, эта статья соответствует ISO 31-11 и стандартному соглашению в математической логике , согласно которому 0 является натуральным числом.
- ^ "Исчерпывающий список символов теории множеств" . Математическое хранилище . 2020-04-11 . Проверено 6 сентября 2020 .
- ^ Халмош 1960 , стр. 91, называют S счетноесли взаимно однозначное отображение между подмножеством S и N существует. Камке 1950 , стр. 2, требует взаимно однозначное соответствие между S и N .
- ^ Стиллвелл, Джон С. (2010), Дороги в бесконечность: математика истины и доказательства , CRC Press, стр. 10, ISBN 9781439865507,
Открытие Кантора несчетных множеств в 1874 году было одним из самых неожиданных событий в истории математики. До 1874 года бесконечность даже не считалась законным математическим предметом для большинства людей, поэтому невозможно было вообразить необходимость различать счетные и бесчисленные бесконечности.
- Перейти ↑ Cantor 1878, p. 242.
- ^ Ferreiros 2007, стр. 268, 272-273.
- ^ "Что такое комплекты и форма списка?" . истечение срока . 2021-05-09.
- ^ Вайсштейн, Эрик В. «Счетное множество» . mathworld.wolfram.com . Проверено 6 сентября 2020 .
- ^ «9.2: Счетные множества» . Математика LibreTexts . 2017-09-20 . Проверено 6 сентября 2020 .
- ^ Камке 1950 , стр. 3-4
- ^ Халмош 1960 , стр. 91
- ^ Avelsgaard 1990 , стр. 179
- ^ Avelsgaard 1990 , стр. 180
- ^ Халмош 1960 , стр. 92
- ^ Avelsgaard 1990 , стр. 182
- Перейти ↑ Fletcher & Patty 1988 , p. 187
Рекомендации
- Апостол, Том М. (июнь 1969 г.), Исчисление с несколькими переменными и линейная алгебра с приложениями , Исчисление, 2 (2-е изд.), Нью-Йорк: John Wiley + Sons, ISBN 978-0-471-00007-5
- Авельсгаард, Кэрол (1990), Основы высшей математики , Scott, Foresman and Company, ISBN 0-673-38152-8
- Кантор, Георг (1878), «Ein Beitrag zur Mannigfaltigkeitslehre» , Journal für die Reine und Angewandte Mathematik , 1878 (84): 242–248, doi : 10.1515 / crelle-1878-18788413
- Феррейрос, Хосе (2007), Лабиринт мысли: история теории множеств и ее роль в математической мысли (2-е исправленное издание), Биркхойзер, ISBN 978-3-7643-8349-7
- Флетчер, Питер; Пэтти, К. Уэйн (1988), Основы высшей математики , Бостон: PWS-KENT Publishing Company, ISBN 0-87150-164-3
- Халмос, Пол Р. (1960), Теория наивных множеств , D. Van Nostrand Company, Inc. Перепечатано Springer-Verlag, Нью-Йорк, 1974. ISBN 0-387-90092-6 (издание Springer-Verlag). Перепечатано Martino Fine Books, 2011. ISBN 978-1-61427-131-4 (издание в мягкой обложке).
- Камке, Эрих (1950), Теория множеств , серия Dover по математике и физике, Нью-Йорк: Dover, ISBN 978-0486601410
- Ланг, Серж (1993), Реальный и функциональный анализ , Берлин, Нью-Йорк: Springer-Verlag, ISBN 0-387-94001-4
- Рудин, Уолтер (1976), Принципы математического анализа , Нью-Йорк: McGraw-Hill, ISBN 0-07-054235-X