AidarM и Iva посвящается.
Не могу обойти вниманием ваш интерес к проблемам неопределённости в математике. Iva постоянно напрашивается на разговор по теме в нескольких топах сразу
, а AidarM ошивается в математических топах, и уже пополнил свои знания в теории множеств.
Сразу оговорюсь - я не имею именно математического образования, а просто по специальности изучал немного эту тему, плюс читал одну очень хорошую книгу ("Гёдель, Эшер, Бах", Хофстадтер). Начнём пожалуй с Гёделя, а потом познакомимся с проблемами неопределённости в теории вычислений (Туринг, Черч).
Часть 1. Парадокс Рассела.
На рубеже 19-20 вв. теор. множеств основательно вошла в математику. На основе теор. множеств и аксиоматического метода возникли попытки формализовать основу основ математики – элементарную арифметику, также именуемой теорией чисел. Некто Гётлеб Фрег, немецкий математик, занимавшийся в то время такой формализацией арифметики, наряду с Джузеппе Пеано, направил результат своих трудов на критику Бертрану Расселу. Его формализация арифметики не содержала ничего, кроме логических правил дедукции и понятия множества. Именно из-за такой простоты такая теория чисел выглядела сильной – зная только простые правила логики и операций над множествами, мы можем обьять все факты о натуральных числах! После ознакомления с трудом Фрега, Рассел выдал следующую аллегорию, в которой он хотел показать проблему с определением понятия «множества».
В некотором городе живет брадобрей мужского пола, который бреет тех и только тех горожан мужского пола, которые не бреют самих себя. Бреет ли брадобрей самого себя?
В данной постановке задачи очевидно, что ответом не может быть ни «да» (потому что это будет противоречить условию «не бреют самих себя») ни «нет» (противоречие условию «бреет»). Нетрудно преобразовать данную аллегорию на язык математики. Условно разделим все множества на два класса – «хорошие множества» это те, которые не содержат себя в качестве своего элемента, и «нехорошие множества» это те, которые содержат. (Пример «нехорошего множества» - «все множества, определённые менее чем 1000 словами на русском языке». Как видно, определение имеет длину менее чем 1000 слов, поэтому такое множество содержит ко всему прочему и себя в качестве элемента). Теперь определим множество S как множество всех «хороших множеств». Содержит ли S себя в качестве элемента? Ответ «да» прямо противоречит условию, что S – суть множества, не содержащие себя как элемент. Ответ «нет» советует, что S всё же должен содержать себя, т.к. все множества, не содержащие себя как элемент должны быть в S. Итак, мы имеем парадокс вида S = {A: A не принадл. A}. Было сразу замечено, что с теор. множеств что-то не то, если её можно прибить таким вот лёгким и незамысловатым выражением. Проблема была «решена» в какой то мере самим Расселом, спустя годы в его труде «Principles of Mathematics» методом использования типов. Немного видоизменим парадокс на S = {A: A принадл. T ^ A не принадл. A}. То есть, если рассматривать не просто множества, а множества, принадлежащие некому известному множеству (типу) T, то ответом на вопрос содержит ли S себя будет просто «нет», потому что S не будет принадлежать типу T. Использование типов позволяет избегать ссылок математических обьектов на самих себя, тем самым избегая парадоксов, схожих с парадоксом Рассела. Логические противоречия в математике были устранены, и вот уже казалось, что математику можно полно и непротиворечиво описать множествами и логикой. Но через двадцать лет Гёдель доказал теорему о неполноте, а чуть позже Туринг и Черч пришли к похожему результату – о невычисляемости определённых задач.
Вообщем, я эту вводную часть написал для того, чтобы не сложилось впечатления, о том, что до Гёделя математика развивалась без сучка и задоринки. Первые проблемы с теорией множеств возникли десятилетия до ТГ, а «парадокс лжеца» в логике был известен ещё со времён античных греков.
Продолжение следует.
С себя можно начать когда все остальное будет в порядке.