Мощность множества. Конечные и бесконечные множества. План: Мо́щность, или кардина́льное

Мощность множества. Конечные и бесконечные множества.

План:
1.Мо́щность, или кардина́льное
2. Конечные и бесконечные множества


число́, мно́жества (лат. cardinalis ← cardo «главное обстоятельство; основа; сердце») — характеристика множеств (в том числе бесконечных), обобщающая понятие количества (числа) элементов конечного множества.
В основе этого понятия лежат естественные представления о сравнении множеств:

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

До того, когда была построена теория мощности множеств, множества различались по признакам: пустое/непустое и конечное/бесконечное, также конечные множества различались по количеству элементов. Бесконечные же множества нельзя было сравнить.
Мощность множеств позволяет сравнивать бесконечные множества. Например, счётные множества являются самыми «маленькими» бесконечными множествами.
Мощность множества {\displaystyle A}  обозначается через {\displaystyle |A|} . Иногда встречаются обозначения {\displaystyle {\overline {\overline {A}}}} , {\displaystyle \#A}  и {\displaystyle \mathrm {card} (A)} .
Если аксиому выбора принять верной, мощность множества формально будет определяться как наименьшее порядковое число {\displaystyle \alpha } , при котором между {\displaystyle X}  и {\displaystyle \alpha }  можно установить биективное соответствие. Данное определение также называется распределением кардинальных чисел по фон Нейману.
Если не принимать аксиому выбора, то требуется иной подход. Самое первое определение мощности множества {\displaystyle X}  (оно неявно присутствует в работах Кантора и явным образом сформулировано у Фреге, а также в Principia Mathematica) представляет собой класс {\displaystyle [X]}  всех множеств, равномощных {\displaystyle X} . В аксиоматических системах, основанных на теории ZFC, такое определение неприменимо, поскольку при непустом {\displaystyle X}  такая совокупность слишком велика, чтобы подходить под определение множества. Точнее, если {\displaystyle X\neq \varnothing } , то существует инъективное отображение универсального множества в {\displaystyle [X]} , при котором каждое множество {\displaystyle m} переходит в {\displaystyle \{m\}\times X} , откуда, в силу аксиомы ограничения размера следует, что {\displaystyle [X]}  — собственный класс. Данное определение можно использовать в теории типов и «новых основаниях»^[en], а также в связанных с ними аксиоматических системах. В случае ZFC определение можно использовать, если ограничить коллекцию {\displaystyle [X]}  равномощными множествами с наименьшим рангом (этот приём, предложенный Даной Скоттом, работает благодаря тому, что совокупность объектов, обладающих заданным рангом, является множеством).
Формальный порядок среди кардинальных чисел вводится следующим образом: {\displaystyle |X|\leq |Y|}  означает, что множество {\displaystyle X}  можно инъективно отобразить на {\displaystyle Y} . Согласно теореме Кантора — Бернштейна, из пары неравенств {\displaystyle |X|\leq |Y|}  и {\displaystyle |Y|\leq |X|}  следует, что {\displaystyle |X|=|Y|} . Аксиома выбора эквивалентна утверждению о том, что для любых множеств {\displaystyle X}  и {\displaystyle Y}  выполняется по крайней мере одно из неравенств {\displaystyle |X|\leq |Y|}  или {\displaystyle |Y|\leq |X|} .
Множество {\displaystyle X}  называется бесконечным по Дедекинду^[en], если в нём существует такое собственное подмножество {\displaystyle Y} , что {\displaystyle |X|=|Y|} . В противном случае множество называется конечным по Дедекинду. Конечные кардинальные числа совпадают с обычными натуральными числами или нулём, — иначе говоря, множество {\displaystyle X} конечно тогда и только тогда, когда {\displaystyle |X|=|n|=n}  при некотором натуральном {\displaystyle n}  или при {\displaystyle n=0}  (если множество пустое). Все остальные множества бесконечны. При соблюдении аксиомы выбора можно доказать, что определения по Дедекинду совпадают со стандартными. Кроме того, можно доказать, что мощность множества натуральных чисел {\displaystyle \aleph _{0}}  (алеф-нуль, или алеф-0, — название образовано от первой буквы еврейского алфавита {\displaystyle \aleph } ) представляет собой наименьшее бесконечно большое кардинальное число, то есть в любом бесконечном множестве есть подмножество мощности {\displaystyle \aleph _{0}} . Следующее по порядку кардинальное число обозначается {\displaystyle \aleph _{1}}  и так далее, число алефов бесконечно. Любому порядковому числу {\displaystyle \alpha }  соответствует кардинальное число {\displaystyle \aleph _{\alpha }} , причём таким образом можно описать любое бесконечно большое кардинальное число.

• 
  Мощность множества натуральных чисел {\displaystyle {\mathbb {N} }}  обозначается символом {\displaystyle \aleph _{0}}  («алеф-нуль»). Множество называется бесконечным, если его мощность не меньше {\displaystyle \aleph _{0}} (не меньше мощности множества натуральных чисел), таким образом, счётные множества — это «самые маленькие» из бесконечных множеств. Следующие кардинальные числа в порядке возрастания обозначаются {\displaystyle \aleph _{1},\aleph _{2},\dots \aleph _{\omega },\aleph _{\omega +1},\dots \aleph _{\omega _{1}},\dots }  (где индекс пробегает все порядковые числа). Среди кардинальных чисел нет наибольшего: для любого множества кардинальных чисел существует кардинальное число, большее всех элементов этого множества.
  

• 
  Про множества, равномощные множеству всех вещественных чисел, говорят, что они имеют мощность континуума, и мощность таких множеств обозначается символом {\displaystyle {\mathfrak {c}}} . Предположение о том, что {\displaystyle {\mathfrak {c}}=\aleph _{1}} , называется континуум-гипотезой.
  

• 
  Для мощностей, как и в случае конечных множеств, имеются понятия: «равенство», «больше», «меньше». То есть для любых множеств {\displaystyle A}  и {\displaystyle B}  возможно только одно из трёх:
  
  1. 
     {\displaystyle |A|=|B|} , или {\displaystyle A}  и {\displaystyle B}  равномощны;
     
  2. 
     {\displaystyle |A|>|B|} , или {\displaystyle A}  мощнее {\displaystyle B} , то есть {\displaystyle A}  содержит подмножество, равномощное {\displaystyle B} , но {\displaystyle A}  и {\displaystyle B}  не равномощны;
     
  3. 
     {\displaystyle |A|<|B|} , или {\displaystyle B}  мощнее {\displaystyle A}  — в этом случае {\displaystyle B}  содержит подмножество, равномощное {\displaystyle A} , но {\displaystyle A}  и {\displaystyle B}  не равномощны.
     

1. 
   Ситуация, в которой {\displaystyle A}  и {\displaystyle B}  не равномощны и при этом ни в одном из них нет части, равномощной другому, невозможна. Это следует из теоремы Цермело. Иначе это означало бы существование несравнимых между собой мощностей (что в принципе возможно, если не принимать аксиому выбора).
   
2. 
   Ситуация, в которой {\displaystyle |A|>|B|}  и {\displaystyle |A|<|B|} , невозможна по теореме Кантора — Бернштейна.
   
• 
  Множества {\displaystyle A}  и {\displaystyle B}  называются эквивалентными, если существует взаимно однозначное отображение множества {\displaystyle A}  на множество {\displaystyle B} .^[1]
  

Примеры[править | править код]

• 
  Множество называется конечным, если оно равномощно отрезку натурального ряда {\displaystyle I_{n}=\{1,2,...,n\}}  при некотором неотрицательном целом {\displaystyle n} . Число {\displaystyle n} выражает количество элементов конечного множества. При {\displaystyle n=0}  множество не содержит элементов (пустое множество). Если {\displaystyle m>n} , то не существует инъективного отображения из {\displaystyle I_{m}}  в {\displaystyle I_{n}}  (принцип Дирихле), а значит, не существует и биекции между ними. Поэтому множества {\displaystyle I_{m}}  и {\displaystyle I_{n}}  имеют различную мощность.
  

• 
  Множество называется счётным, если оно равномощно множеству всех натуральных чисел {\displaystyle \mathbb {N} } . Счётными множествами являются:
  
  • 
    Множество {\displaystyle \mathbb {N} \setminus I_{k}}  при любом натуральном {\displaystyle k} . Биективное соответствие, отображающее {\displaystyle \mathbb {N} }  в {\displaystyle \mathbb {N} \setminus I_{k}} : {\displaystyle n\rightarrow n+k} .
    
  • 
    Множество {\displaystyle \mathbb {N} \cup \{0\}} . Соответствие: {\displaystyle n\rightarrow n-1} .
    
  • 
    Множество целых чисел {\displaystyle \mathbb {Z} } . Соответствие получается, если члены бесконечной суммы {\displaystyle 0+1-2+3-4+5-6+\dots }  сопоставить его частичным суммам (члены ряда берутся без учёта знака).
    
  • 
    Множество пар натуральных чисел {\displaystyle \mathbb {N} \times \mathbb {N} } .
    
  • 
    Множество рациональных чисел {\displaystyle \mathbb {Q} }  инъективно отображается во множество {\displaystyle \mathbb {Z} \times \mathbb {N} }  (то есть любой несократимой дроби вида {\displaystyle p/q}  инъективно соответствует пара чисел {\displaystyle (p,q)\in \mathbb {Z} \times \mathbb {N} } ). Поэтому множество рациональных чисел не более чем счётно. Но так как оно содержит множество натуральных чисел, то оно и не менее чем счётно. Соответственно, по теореме Кантора — Бернштейна оно ровно счётно.
    

• 
  Бесконечные множества, неравномощные множеству {\displaystyle \mathbb {N} } , называются несчётными. По теореме Кантора несчётным является множество всех возможных бесконечных последовательностей, составленных из цифр 0 и 1. Мощность этого множества называется континуум.
  

• 
  Мощность множества вещественных чисел {\displaystyle \mathbb {R} }  равна континууму.
  

• 
  Два конечных множества равномощны тогда и только тогда, когда они состоят из одинакового числа элементов. То есть для конечного множества понятие мощности совпадает с привычным понятием количества.
  
• 
  Для бесконечных множеств мощность множества может совпадать с мощностью своего собственного (то есть не совпадающего с исходным множеством) подмножества, например {\displaystyle |{\mathbb {N} }|=|\mathbb {Z} |} .
  
• 
  Более того, множество бесконечно тогда и только тогда, когда оно содержит равномощное собственное подмножество.
  
• 
  Любое бесконечное множество {\displaystyle A}  равномощно множеству всех его конечных подмножеств.^[2]
  
• 
  Теорема Кантора: булеан любого множества A имеет большую мощность, чем A, то есть {\displaystyle |2^{A}|>|A|} .
  
  • 
    В частности, для любого множества существует множество мощнее.
    
• 
  С помощью канторова квадрата можно также доказать следующее: декартово произведение бесконечного множества A с самим собой равномощно самому множеству A.
  
• 
  Мощность декартова произведения:
  

{\displaystyle |A\times B|=|A|\cdot |B|}Формула включения-исключения для двух и трёх множеств:
{\displaystyle |A\cup B|+|A\cap B|=|A|+|B|} {\displaystyle |A\cup B\cup C|+|A\cap B|+|A\cap C|+|B\cap C|=|A|+|B|+|C|+|A\cap B\cap C|}

• 
  Мощность симметрической разности двух и трёх множеств:
  

{\displaystyle |A\bigtriangleup B|+2\cdot |A\cap B|=|A|+|B|}{\displaystyle |A\bigtriangleup B\bigtriangleup C|+2|A\cap B|+2|A\cap C|+2|B\cap C|=|A|+|B|+|C|+3|A\cap B\cap C|}Обычные арифметические операции над числами натурального ряда можно обобщить на случай кардинальных чисел. Можно также показать, что в случае конечных кардинальных чисел эти операции совпадают с соответствующим арифметическими действиями над числами. Помимо этого, операции над кардинальными числами сохраняют многие свойства обычных арифметических операций.