13. Наивная теория множеств - основные понятия, кардинальные числа, выразительные возможности, парадоксы (Лекции)

Математическая логикаЛектор:Подымов Владислав Васильевичe-mail:valdus@yandex.ru2017, весенний семестрЛекция 13Наивная теория множествКардинальные числав наивной теории множествВыразительные возможноститеории множествПарадоксы теории множествВступлениеIсигнатура — это множество . . . и множество . .

. и . . .Iсемантическая таблица — это пара множеств . . .Iинтерпретация состоит из множества предметов и . . .Iтеорема компактности Мальцева: если Γ — множество . . . ,то для любого конечного подмножества . . .Iмашина Тьюринга — это конечное множество . . .Iарифметическая интерпретация — это множествонатуральных чисел и . . .А что такое “множество”?Наивная теория множествЧасто студентам дают такое определение множества:множество — это неопределяемое понятие теории множеств1Стало ли понятно, что такое множество?Термин “множество” придумал Георг Кантор во второй половинеXIX века2 и позже3 остановился на таком определении:множество S — это коллекция многих определённых иразличимых объектов, какие только можно помыслить,объединённых в единое целое;эти объекты называются элементами SБудем придерживаться этого определения, лежащего в основенаивной теории множеств123Как, например, точка — неопределяемое понятие геометрииИ до XIX века этого термина не существовало!1915.

Beiträge zur Begründung der transfiniten MengenlehreНаивная теория множествКак работать с множествами?Например, можноIIопределить принадлежность элемента x множеству S:либо x ∈ S,либо x ∈/Sзадать множество всех элементов,обладающих свойством P:{x | P(x)}IIв том числе пустое множество ∅:∅ = {x | false}сравнить множества между собой:IIIS1 ⊆ S2 ⇔ каждый элемент S1 является элементом S2(и тогда S1 — подмножество множества S2 )S1 = S2 ⇔ S1 ⊆ S2 и S2 ⊆ S1S1 ⊂ S2 ⇔ S1 ⊆ S2 и S1 6= S2Наивная теория множествКак работать с множествами?Например, можноIполучить новые множества из имеющихся с помощьюспециальных (теоретико-множественных) операций:объединение:S1 ∪ S2= {x | x ∈ S1 или x ∈ S2 }пересечение:S1 ∩ S2= {x | x ∈ S1 и x ∈ S2 }разность:S1 \ S2= {x | x ∈ S1 и x ∈/ S2 }произведение:S1 × S2= {(x, y ) | x ∈ S1 и y ∈ S2 }степень:2S= {x | x ⊆ S}...Наивная теория множествКак работать с множествами?Например, можноIсравнить количество элементов в множествах(то есть их мощность)Если множества S1 , S2 конечны, то это сделать несложно:I если множества содержат одинаковое число элементов, тоони равномощныI если множество S1 содержит больше элементов, чем S2 , тооно мощнееА как сравнить количество элементов в бесконечныхмножествах?Наивная теория множествКак работать с множествами?Например, можноIсравнить количество элементов в множествахПримерСравним множества всех натуральных чисел N и чётныхнатуральных чисел N(2)N(2) ⊂ N,но это не означает, что множество N(2) менее мощное, чем N:N= { 1 , 2 , 3 ,..., n ,...}llllN(2) = { 2 , 4 , 6 , .

. . , 2n , . . . }Множества N и N(2) оказались “одинаково бесконечны”А N и множество действительных чисел “по-разномубесконечны”(все же знают, что континуум мощнее счётного множества)Наивная теория множествКак работать с множествами?Например, можноIсравнить количество элементов в множествах:I|S1 | = |S2 | ⇔ существует биекция f : S1 → S2II|S1 | ≤ |S2 | ⇔ существует множество S, такое чтоS ⊆ S1 и S ∼ S2IIи множества S1 , S2 равномощны: S1 ∼ S2и множество S2 не менее мощное, чем S1 : S1 S2|S1 | < |S2 | ⇔ S1 S2 и S1 S2Iи множество S2 мощнее множества S1 : S1 ≺ S2Множесто S конечно, если S ∼ ∅ или S ∼ {1, 2, .

. . , n} длякакого-либо n ∈ NОстальные множества бесконечныА можно ли определить мощность |S| множества Sкак самостоятельный объект?Кардинальные числаУтверждениеОтношение равномощности множеств — это отношениеэквивалентностиДоказательство.Рефлексивность: тождественная функция — биекцияСимметричность: для любой биекции существует обратноеотображение, также являющееся биекциейТранзитивность: если f : X → Y и g : Y → Z — биекции, тоHкомпозиция gf : X → Z — также биекцияКардинальные числаУтверждениеОтношение равномощности множеств — это отношениеэквивалентностиМощность (или кардинальное число1 ) |S| множества S — этокласс эквивалентности отношения равномощности множеств,порождаемый множеством SА какие значения может принимать мощность множества?Например,0 = |∅|, n = |{1, 2, .

. . , n}|, ℵ0 = |N|,2 ℵi+1 = |2S |, где |S| = ℵiЕсли |S| = ℵ0 , то множество S счётно-бесконечноЕсли |S| = ℵ1 , то множество S континуально1англ. cardinality — число элементов; лат. cardinalis — прил. от cardo:стержень, основная часть2ℵ — “алеф”, первая буква еврейского алфавитаКардинальные числаА как соотносятся между собой числа 1, 2, .

. . , ℵ0 , ℵ1 , . . . ?И есть ли ещё кардинальные числа?Теорема КантораДля любого множества S верно: S 2SДоказательство. (обобщение диагонального метода Кантора)Предоположим, что это не такТогда существует биекция f : S → 2SРассмотрим такое множество: M = {x | x ∈ S и x ∈/ f (x)}Так как f — биекция, найдётся элемент y множества S, такойчто f (y ) = MЕсли y ∈ M, то y ∈/ f (y ) = MЕсли y ∈/ M, то y ∈ f (y ) = MHКардинальные числаСемейство множеств S неограничено по мощности, если длялюбого его элемента S существует элемент S 0 , такой что S ≺ S 0SОбъединение S семействаS определим так:S множествSS=SS∈SТеорема о неограниченном по мощности семействеЕсли S — семейство множеств,неограниченное поSмощности, и S ∈ S, то S ≺ SДоказательство.От противного предположим,Sчто существует элемент Sсемейства S, такой что S 6≺ SSSS ∈ S, а значит, S ⊆ S и S SSSS ⊀ S, а значит, S ∼ SСемейство S неограничено по мощности, а значит, оносодержит элемент S 0 , такой что S ≺ S 0SSSS 0 ⊆ S, и тогда S ≺ S 0 S, а значит, S SHКардинальные числаТеорема Кантора-БернштейнаЕсли S M и M S, то S ∼ MДоказательство.S M: существует биекция f : S → M1 , где M1 ⊆ MM S: существует биекция g : M → S1 , где S1 ⊆ SНа основе f и g построим биекцию h : S → S1Тогда наличие биекции g −1 h : S → M будет обосновыватьсоотношение S ∼ MБудем использовать такое сокращение: f (S) = {f (x) | x ∈ S}(S — множество, f — отображение из S)Рассмотрим последовательность множеств S0 , S1 , S2 , S3 , .

. . :I S0 = SI Si+2 = g (f (Si ))(i ≥ 0)Кардинальные числаТеорема Кантора-БернштейнаЕсли S M и M S, то S ∼ MДоказательство.fS S1 S2 S3 . . .gM1 MКардинальные числаТеорема Кантора-БернштейнаЕсли S M и M S, то S ∼ MДоказательство.Рассмотрим последовательность C1 , C2 , C3 , . . . :Ci = Si−1 \ Si(i ≥ 1)C1C2S S1 S2 S3 . . .C3Кардинальные числаТеорема Кантора-БернштейнаЕсли S M и M S, то S ∼ MДоказательство.Рассмотрим последовательность C1 , C2 , C3 , .

. . :Ci = Si−1 \ Si∞Tи множество C =Si(i ≥ 1)i=0Требуемую биекцию h : S → S1 можно определить так:∞S g (f (x)), если x ∈C2i+1i=0h(x) =∞Sx,иначе(тоестьеслиx∈C2i ∪ C )i=1Кардинальные числаТеорема Кантора-БернштейнаЕсли S M и M S, то S ∼ MДоказательство.hS S1 S2 S3 . . .HКардинальные числаСледствие. Отношение ≤ на множестве кардинальныхчисел является нестрогим частичным порядкомА существуют ли множества, имеющие несравнимые мощности?Интуиция подсказывает, что такого быть не должно: еслиэлементов не больше и не меньше, то (вроде бы) их должнобыть столько жеНо так ли просто это доказать?Отложим этот вопрос до лекции 15Кардинальные числаТак какие же бывают кардинальные числа, и как они связанымежду собой?0 < 1 < · · · < n < · · · < ℵ0 < ℵ1 < · · · < ℵn < .

. .< ℵω < ℵω+1 < · · · < ℵω+n < . . . < ℵ2ω < · · · < ℵω2 < . . .I ℵx+1 = |2S |, где |S| = ℵxSI ℵω = | {S0 , S1 , S2 , . . .}|, где |Si | = ℵi , i ≥ 0SI ℵ(x+1)ω = | {S1 , S2 , . . .}|, где |Si | = ℵxω+i , i ≥ 1SI ℵω x+1 = | {S1 , S2 , . . .}|, где |Si | = ℵiω x , i ≥ 1I ...А можно ли точно описать множество всех кардинальныхчисел?Этот вопрос также отложим до лекции 15, а сейчас заменим егоболее простымиI Существует ли бесконечная мощность меньше счётной?I Существует ли можность между счётной бесконечностью иконтинуумом?Кардинальные числа0 < 1 < · · · < n < . . . < ℵ0 < ℵ1 < · · · < ℵn < .

. .< ℵω < ℵω+1 < · · · < ℵω+n < · · · < ℵ2ω < · · · < ℵω2 < . . .УтверждениеЛюбое бесконечное подмножество счётно-бесконечногомножества счётно-бесконечноДоказательство.Достаточно показать, что любое бесконечное подмножество Sмножества N счётно-бесконечноТакая функция f : N → S является биекцией:I f (1) — это наименьшее число в SI f (i + 1) — это наименьшее число в множествеS \ {f (1), . . . , f (i)}(i ≥ 1)HКардинальные числа0 < 1 < · · · < n < · · · < ℵ0 < ℵ1 < · · · < ℵn < . . .< ℵω < ℵω+1 < · · · < ℵω+n < · · · < ℵ2ω < · · · < ℵω2 < .

. .Континуум-гипотезаЛюбое бесконечное подмножество континуальногомножества либо счётно-бесконечно, либо континуальноНасколько это утверждение правдоподобно?Оказывается,1 что в некотором смыслеэто утверждение нельзя ни опровергнуть, ни доказатьВыходит, что мы можем пользоваться двумя принципиальноразными теориями множеств, в одной из которых эта гипотезаверна, а в другой неверна?Явного ответа на этот вопрос в лекциях нет1И это тоже отложим до лекции 15Выразительные возможности теории множествА как много всего можно определить, используя толькопростые множества и операции ∪, ∩, \?Например,натуральные числа0123...n+1...====∅0 ∪ {0}1 ∪ {1}2 ∪ {2}= n ∪ {n}= {∅}= {∅, {∅}}= {∅, {∅} , {∅, {∅}}}= {0, 1, .

. . , n}Выразительные возможности теории множествА как много всего можно определить, используя толькопростые множества и операции ∪, ∩, \?Например,кортежи()(x)(x, y )=====∅{{()} , {(), x}}{{∅} , {∅, x}}{{(x)} , {(x), y }}{{{{∅} , {∅, x}}} , {{{∅} , {∅, x}} , y }}...(x, y , . . . , u, v ) = {{(x, y , . .