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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Математическая логикаЛектор:Подымов Владислав Васильевич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 , . .

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций