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

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

Текст из файла (страница 2)

. , u)} , {(x, y , . . . , u), v }}отношенияN-арное отношение — это множество кортежей длины NВыразительные возможности теории множествА как много всего можно определить, используя толькопростые множества и операции ∪, ∩, \?Например,функцииПусть f : X → YТогдаf = {(x, f (x)) | x ∈ X },где (x, f (x)) — это кортеж размера 2 (пара)графыГраф — это пара (V , E ), где V — множество и E — множествопар элементов VВыразительные возможности теории множествА как много всего можно определить, используя толькопростые множества и операции ∪, ∩, \?Например,сигнатуры логики предикатовСигнатура логики предикатов — это кортеж, состоящий изIIIмножества константмножества пар, состоящих из функционального символа инатурального числа (местности)множества пар, состоящих из предикатного символа инатурального числа (местности)Выразительные возможности теории множествА как много всего можно определить, используя толькопростые множества и операции ∪, ∩, \?Например,интерпретации в логике предикатовИнтерпретация — это кортеж, состоящий изIIIIмножества Dфункции, отображающей константы в Dфункции, отображающей функциональные символы вфункции, переводящие кортежи элементов D в Dфункции, отображающей предикатные символы вотношения над DВыразительные возможности теории множествА как много всего можно определить, используя толькопростые множества и операции ∪, ∩, \?Например,множества, заданные на естественном языке:IIIIмножество студентов, сидящих в этой комнатемножество людей, живущих на Солнцемножество действительных решений уравненияx 2 − 2x + 1 = 0множество всех чисел, оканчивающихся на букву “н”Выразительные возможности теории множествА любое ли описание множествана естественном языке корректно что-либо задаёт?Оказывается, это не так: определение множества,сформулированное Кантором, позволяет определятьпарадоксальные множества, которых “не может существовать”Хорошо это или плохо?IIУстранить парадоксы — одна из основных задач логики“Сущность математики состоит именно в её свободе” 1,2Но каковы бы ни были мнения на этот счёт, факт наличияпарадоксальных умозаключений в наивной теории множествостаётся12Кантор.

1883. Mathematische Annalen, 21Имеется ли в виду, что в парадоксах нет ничего страшного?Ответа на этот вопрос в лекциях нетПарадоксы теории множествПарадокс Рассела(теперь формализованный в терминахнаивной теории множеств)Рассмотрим такое множество:Ω = {x | x ∈/ x}Верно ли, что Ω ∈ Ω?IIЕсли Ω ∈ Ω, то по заданию этого множества Ω ∈/ΩЕсли Ω ∈/ Ω, то по заданию этого множества Ω ∈ ΩПарадоксы теории множествПарадокс КантораРассмотрим такое множество:Ω = {x | true}Что это за множество?Это множество всех множествА какова мощность множества Ω?У этого множества есть мощность |Ω|, как и у множества всехего подмножеств: |2Ω |По теореме Кантора верно: |2Ω | > |Ω|Но при этом 2Ω ⊆ Ω, а значит, |2Ω | ≤ |Ω|Парадоксы теории множествПарадокс Тристрама Шенди1Тристрам Шенди прожил невероятно насыщенную жизнь иоднажды решил написать мемуарыЦелый год жизни понадобился Тристраму, чтобы изложить всесобытия первого дня его жизниЕщё один год понадобился для изложения второго дняПредставим себе, что Тристрам будет жить вечно, и что все егодни настолько же насыщенны, как и первые дваТогда каждый день его жизни рано или поздно будет изложенЗначит ли это, что Тристрам Шенди проживёт столько же дней,сколько и лет?1Это герой юмористического романа Л.СтернаПарадоксы теории множествПарадокс Гранд-отеляПредставьте себе отель со счётным числом комнат в самыйразгар сезона: все комнаты заняты постояльцамиСколько новых гостей мы сможем разместить в этом отеле?IIМы можем разместить одного гостя: достаточно переселитькаждого постояльца из комнаты N в комнату N + 1 — иодно место освободитсяМы можем разместить любое конечное число гостей:достаточно разместить их одного за однимПарадоксы теории множествПарадокс Гранд-отеляПредставьте себе отель со счётным числом комнат в самыйразгар сезона: все комнаты заняты постояльцамиСколько новых гостей мы сможем разместить в этом отеле?IIМы можем разместить счётно-бесконечное число гостей:достаточно переселить каждого постояльца из комнаты N вкомнату 2N и заселить i-го гостя в (2i − 1)-ю комнатуЕсли к нам приедет счётно-бесконечное число автобусов, ив каждом будет сидеть счётно-бесконечное число гостей,мы всё так же сможем их разместитьНе буду убивать интригу и говорить, как это сделатьПарадоксы теории множествПарадокс Росса-ЛиттлвудаЗа минуту до полудня перед нами стоит пустая ваза и лежитбесконечное число шаровЗа 30 секунд до полудня положим в неё 10 шаров и извлечём 1,лежащий в вазе дольше всехЗа 15 секунд до полудня опять положим в неё 10 шаров иизвлечём 1, лежащий в вазе дольше всех...За 260N секунд до полудня ещё раз положим в неё 10 шаров иизвлечём 1, лежащий в вазе дольше всех...Сколько шаров окажется в вазе к полудню?IIВ вазе будет бесконечное число шаров, потому что мыбесконечное число раз добавляем в неё 9 шаровВаза будет пуста, потому что каждый опущенный в вазушар обязательно будет вынутПарадоксы теории множествПарадокс БерриКаждое число можно определить фразой на русском языке,например:I сто пятнадцать(это число 115 )I наибольший общий делитель чисел “двенадцать” и “девять”(это число 3 )I наименьшее совершенное число(это число 6 )Рассмотрим множество Ω всех натуральных чисел, которыеможно определить менее чем восемьюдесятью буквамиЧисло фраз из менее чем восьмидесяти букв конечно, а значит,множество Ω конечноПри этом |N| = ℵ0 , а значит, существуют числа, которые невходят в Ω, и среди них есть наименьшееЧему равнонаименьшее натуральное число, которое нельзяопределить менее чем восемьюдесятью буквами?Парадоксы теории множествМожно ли избежать всех парадоксов, если достаточно хорошоописать понятие “множества”?Нет, потому что парадоксальность вывода не обязательноозначает его ошибочностьНо некоторые парадоксы наивной теории множеств основаны нанекорректности принятого определения множестваТакие парадоксы можно попытаться устранить, используя дляэтого аппарат аксиоматических теорийКонец лекции 13.

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

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