Счетный набор

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

Некоторые авторы используют счетное множество только для обозначения счетной бесконечности . ^[1] Чтобы избежать этой двусмысленности, термин не более чем счетный может использоваться, когда включены конечные множества, и счетно бесконечный , перечислимый , ^[2] или счетный ^{[3] в} противном случае.

Георг Кантор ввел термин счетное множество , противопоставляя счетные множества несчетным (т. Е. Несчетным или неисчислимым ^[4] ). Сегодня счетные множества составляют основу раздела математики, называемого дискретной математикой .

Определение [ править ]

Множество S является счетным , если существует инъективная функция п от S к натуральным числам N = {0, 1, 2, 3, ... }. ^{[ необходима ссылка ] [5]}

Если можно найти такое f , которое также является сюръективным (и, следовательно, биективным ), то S называется счетно бесконечным .

Другими словами, множество счетное , если она имеет взаимно-однозначное соответствие с естественным набором чисел, N . В этом случае мощность множества обозначается ( aleph-null ) - первая в ряду чисел aleph. ^[6]${\ displaystyle \ aleph _ {0}}$

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

Также могут быть даны альтернативные (эквивалентные) формулировки определения в терминах биективной функции или сюръективной функции. ^[7] См. Также § Формальный обзор без подробностей ниже.

История [ править ]

В 1874 году в своей первой статье по теории множеств Кантор доказал, что множество действительных чисел несчетно, тем самым показывая, что не все бесконечные множества являются счетными. ^[8] В 1878 году он использовал взаимно однозначные соответствия для определения и сравнения мощностей. ^[9] В 1883 году он расширил натуральные числа с помощью своих бесконечных ординалов и использовал наборы ординалов для создания бесконечного множества множеств, имеющих различные бесконечные мощности. ^[10]

Введение [ править ]

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

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

Чтобы понять, что это означает, сначала рассмотрим, что это не означает. Например, существует бесконечно много нечетных целых чисел, бесконечно много четных целых чисел и (следовательно) бесконечно много целых чисел в целом. Однако оказывается, что количество четных целых чисел, которое совпадает с количеством нечетных целых чисел, также совпадает с количеством целых чисел в целом. Это потому, что мы можем организовать вещи так, чтобы для каждого целого числа было отдельное четное целое число:

или, в более общем смысле, (см. рисунок). Что мы здесь сделали, так это расположили целые числа и четные целые числа во взаимно-однозначное соответствие (или биекцию ), которая представляет собой функцию, которая отображает между двумя наборами, так что каждый элемент каждого набора соответствует одному элементу в другом набор.${\ displaystyle n \ rightarrow 2n}$

Однако не все бесконечные множества имеют одинаковую мощность. Например, Георг Кантор (который ввел эту концепцию) продемонстрировал, что действительные числа не могут быть поставлены во взаимно однозначное соответствие с натуральными числами (неотрицательными целыми числами), и поэтому набор действительных чисел имеет большую мощность, чем набор натуральных чисел.

Множество является счетным, если: (1) оно конечно или (2) оно имеет ту же мощность (размер), что и множество натуральных чисел (т. Е. Счетное). ^[11] Аналогично, набор является счетным, если он имеет ту же мощность, что и некоторое подмножество набора натуральных чисел. В противном случае это бесчисленное множество .

Формальный обзор без подробностей [ править ]

По определению, множество S является счетным , если существует инъективную функция F  : S → N от S до натуральных чисел N = {0, 1, 2, 3, ...}.

Может показаться естественным разделить наборы на разные классы: собрать вместе все наборы, содержащие один элемент; все наборы, содержащие два элемента вместе; ...; наконец, соберите все бесконечные множества и рассмотрите их как имеющие одинаковый размер. Однако эта точка зрения не соответствует естественному определению размера.

Чтобы прояснить это, нам понадобится концепция биекции . Хотя «биекция» кажется более продвинутой концепцией, чем число, обычное развитие математики в терминах теории множеств определяет функции перед числами, поскольку они основаны на гораздо более простых наборах. Здесь появляется концепция взаимного соответствия: определить соответствие

а ↔ 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, и наоборот. Следовательно, они имеют одинаковый размер. Это пример набора того же размера, что и одно из его собственных подмножеств, что невозможно для конечных наборов.

Точно так же набор всех упорядоченных пар натуральных чисел счетно бесконечен, что можно увидеть, пройдя путь, подобный показанному на картинке:

Результирующее отображение происходит следующим образом:

0 ↔ (0,0), 1 ↔ (1,0), 2 ↔ (0,1), 3 ↔ (2,0), 4 ↔ (1,1), 5 (0,2), 6 ↔ (3,0) ....

Это отображение покрывает все такие упорядоченные пары.

Если каждая пара рассматривается как числитель и знаменатель в виде обыкновенной дроби , то для каждой положительной дроби, мы можем прийти с отличным номером , соответствующим ему. Это представление включает также натуральные числа, поскольку каждое натуральное число также является дробью N / 1. Таким образом, мы можем сделать вывод, что положительных рациональных чисел ровно столько, сколько положительных целых. Это верно также для всех рациональных чисел, как можно увидеть ниже.

Теорема: декартово произведение конечного числа счетных множеств счетно.

Эта форма треугольного отображения рекурсивно обобщается на векторы конечного числа натуральных чисел путем многократного преобразования первых двух элементов в натуральное число. Например, (0,2,3) отображается в (5,3), что соответствует 39.

Иногда полезно более одного отображения: набор, который должен быть счетно бесконечным, отображается на другой набор, затем этот другой набор отображается на натуральные числа. Например, положительные рациональные числа могут быть легко отображены в (подмножество) пар натуральных чисел, потому что p / q отображается в ( p , q ).

Следующая теорема касается бесконечных подмножеств счетно бесконечных множеств.

Теорема: каждое подмножество счетного множества счетно. В частности, каждое бесконечное подмножество счетно бесконечного множества счетно бесконечно. ^[12]

Например, набор простых чисел можно подсчитать, если отобразить 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 (множество всех рациональных чисел) счетны.

Точно так же счетно множество алгебраических чисел . ^[13]

Эти факты легко вытекают из результата, который многие люди считают не интуитивным.

Теорема: любое конечное объединение счетных множеств счетно.

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

Теорема: (в предположении аксиомы счетного выбора ) Объединение счетного числа счетных множеств счетно.

Например, заданы счетные множества a , b , c , ...

Используя вариант треугольного перечисления, который мы видели выше:

• a ₀ соответствует 0
• а ₁ карты на 1
• b ₀ соответствует 2
• а ₂ карты до 3
• b ₁ соответствует 4
• c ₀ соответствует 5
• а ₃ карты до 6
• b ₂ соответствует 7
• c ₁ соответствует 8
• d ₀ соответствует 9
• а ₄ карты до 10
• ...

Это работает, только если наборы a , b , c , ... не пересекаются . Если нет, то объединение еще меньше и, следовательно, также счетно по предыдущей теореме.

Нам нужна аксиома счетного выбора, чтобы индексировать все множества a , b , c , ... одновременно.

Теорема: множество всех последовательностей натуральных чисел конечной длины счетно.

Этот набор представляет собой объединение последовательностей длины 1, последовательностей длины 2, последовательностей длины 3, каждая из которых является счетным набором (конечное декартово произведение). Итак, мы говорим о счетном объединении счетных множеств, которое счетно по предыдущей теореме.

Теорема: множество всех конечных подмножеств натуральных чисел счетно.

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

Следующая теорема дает эквивалентные формулировки в терминах биективной функции или сюръективной функции . Доказательство этого результата можно найти в тексте Лэнга. ^[3]

(Основная) Теорема: Пусть S - некоторое множество. Следующие утверждения эквивалентны:

1. S счетно, то существует инъективный функция F  : S → N .
2. Либо S пусто , либо существует Сюръекция г  : N → S .
3. Либо S конечен , либо существует взаимно однозначное соответствие ч  : N → S .

Следствие: пусть S и T - множества.

1. Если функция f  : S → T инъективна и T счетно, то S счетно.
2. Если функция 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 .

Предложение: любое подмножество счетного множества счетно. ^[14]

Доказательство: ограничение инъективной функции на подмножество ее области определения остается инъективным.

Предложение: если S счетное множество, то S ∪ { x } счетно. ^[15]

Доказательство. Если x ∈ S, показывать нечего. В противном случае пусть f : S → N инъекция. Определить г : S ∪ { х } → N по г ( х ) = 0 и г ( у ) = е ( у ) + 1 для всех у в S . Эта функция g является инъекцией.

Предложение: если A и B - счетные множества, то A ∪ B счетно. ^[16]

Доказательство. Пусть f : A → N и g : B → N инъекции. Определение нового впрыска час : ∪ B → N по ч ( х ) = 2 F ( х ) , если х находится в А и ч ( х ) = 2 г ( х ) + 1 , если х в B , но не в A .

Предложение: декартово произведение двух счетных множеств A и B счетно. ^[17]

Доказательство. Заметим, что N × N счетно как следствие определения, потому что функция f  : N × N → N, заданная формулой f ( m , n ) = 2 ^m 3 ⁿ , инъективна. ^[18] Тогда из основной теоремы и следствия следует, что декартово произведение любых двух счетных множеств счетно. Это следует потому, что если A и B счетны, существуют сюръекции f  : N → A и g  :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 счетны, потому что функция g  : Z × N → Q, заданная формулой g ( m , n ) = m / ( n+ 1) сюръекция из счетного множества Z × N к Rationals Q .

Предложение: В алгебраических числах A счетны.

Доказательство: Согласно определению, каждое алгебраическое число (включая комплексные числа) является корнем многочлена с целыми коэффициентами. Для данного алгебраического числа , пусть будет многочлен с целыми коэффициентами, такой, что является k- м корнем многочлена, где корни сортируются по модулю от маленького к большому, а затем сортируются по аргументу от маленького к большому. Мы можем определить инъекционную (т.е. взаимно однозначную) функцию f  : A → Q, заданную как , while является n -м простым числом .${\ displaystyle \ alpha}$${\displaystyle a_{0}x^{0}+a_{1}x^{1}+a_{2}x^{2}+\cdots +a_{n}x^{n}}$${\displaystyle \alpha }$${\displaystyle f(\alpha )=2^{k-1}\cdot 3^{a_{0}}\cdot 5^{a_{1}}\cdot 7^{a_{2}}\cdots {p_{n+2}}^{a_{n}}}$${\displaystyle p_{n}}$

Предложение: если A _n - счетное множество для каждого n в N, то объединение всех A _n также является счетным. ^[19]

Доказательство: это следствие того факта, что для каждого n существует сюръективная функция g _n  : N → A _n и, следовательно, функция

${\displaystyle G:\mathbf {N} \times \mathbf {N} \to \bigcup _{n\in \mathbf {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, ...)
  • Обычный порядок рациональных чисел (не может быть явно записан как упорядоченный список!)

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

См. Также [ править ]

• Число Алеф
• Подсчет
• Парадокс Гильберта в Гранд Отеле
• Бесчисленное множество

Заметки [ править ]

Ссылки [ править ]

• Апостол, Том М. (июнь 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

Поищите счетчики в Викисловаре, бесплатном словаре.