Tuesday, September 15, 2009

Dangerous Knowledge - Диагональный метод доказательства Кантора. Часть III (Russian)

См. также:
Dangerous Knowledge
Dangerous Knowledge - Бесконечное множество и интуиция.Часть I
Dangerous Knowledge - Парадокс брадобрея. Часть II
Dangerous Knowledge - Диагональный метод доказательства Кантора. Часть III
Dangerous Knowledge - Континуум-гипотеза. Часть IV
Dangerous Knowledge - Аксиома выбора. Часть V
Dangerous Knowledge - Теория меры. Часть VI
Dangerous Knowledge - Тест Тьюринга. Часть VII


UPDATE 02-11-2010:
Прикоснуться к бесконечности (ВИДЕО)
END OF UPDATE

UPDATE 03-02-2011:
Ещё раз о бесконечности
Всегда ли часть строго меньше целого?
END OF UPDATE

UPDATE 29-09-2014:
Infinity: does it exist?
END OF UPDATE

Как я уже говорил, есть некоторые вещи, которые явно не раскрыты в этой доке. Здесь, я продолжу писать про Кантора. Здесь я рассмотрю "диагональный метод" доказательства Кантора. «Гёдель, Эшер, Бах: эта бесконечная гирлянда», где он в частности подробно на этом останавливается. Перевод на русский можно найти тут. На английском эта книга называется «Gödel, Escher, Bach: An Eternal Golden Braid» by Douglas Hofstadter.

Цитата из английской википедии:

On its surface, GEB examines logician Kurt Gödel, artist M. C. Escher and composer Johann Sebastian Bach, discussing common themes in their work and lives. At a deeper level, the book is a detailed and subtle exposition of concepts fundamental to mathematics, symmetry, and intelligence.

Through illustration and analysis, the book discusses how self-reference and formal rules allow systems to acquire meaning despite being made of "meaningless" elements. It also discusses what it means to communicate, how knowledge can be represented and stored, the methods and limitations of symbolic representation, and even the fundamental notion of "meaning" itself.

In response to confusion over the book's theme, Hofstadter has emphasized that GEB is not about mathematics, art, and music but rather about how cognition and thinking emerge from well-hidden neurological mechanisms. In the book, he presents an analogy about how the individual neurons of the brain coordinate to create a unified sense of a coherent mind by comparing it to the social organization displayed in a colony of ants.

http://en.wikipedia.org/wiki/Gödel,_Escher,_Bach:_An_Eternal_Golden_Braid


Ниже есть продолжение.



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

Напомню, что два множества называются равномощными (в них есть "одинаковое количество элементов"), если между ними можно установить взаимно-однозначное соответствие.

1. Следующие множества попарно равномощны: множество натуральных чисел, множество целых чисел, множество рациональных чисел. Эти примеры счётных множеств.

2. Множество действительных чисел в отрезке [0, 1) несчётно ("диагональный метод Кантора").

Краткое объяснение. Первый результат абсолютно противоречит нашей интуиции. Как часть может быть равна целому? Но, Кантор показал, что это так. Далее, числа натурального ряда можно записать как бесконечный список: $1,2,3,4....$ Счётное множество обозначает, что это множество тоже может быть представлено таким списком (ведь существует взаимно-однозначное соответствие с ним). Множество действительных чисел несчётно, это означает, что оно не может быть представлено таким списком.

Здесь я приведу идею неформального доказательства этой теоремы. Она доказывается с помощью "диагонального метода". Допустим от противного, что множество действительных чисел в отрезке [0, 1) счётно. Любое число на этом отрезке представимо в качестве бесконечной десятичной дроби. Так как это множество счётно мы можем написать следующий список:

x1=0,57893565778356...
x2=0,24896590783...
x3=0,672008765...
x4=0,9271456732...
...

Построим число x следующем способом. Оно будет начинаться на 0, чтобы принадлежать отрезку [0, 1). Первая его цифра после запятой будет любое число, но на такое, какое стоит на первом месте в числе x1, т.е. не 5. Вторая его цифра, будет не таким, как вторая цифра числа x2, т.е. не 4, и т.д. Очевидно, что это такое число будет отличаться от всех чисел, приведённых в списке выше. В самом деле, рассмотрим число x и некоторое число xk. Эти два числа различны. В самом деле, посмотрим на цифру k в десятичной записи этих чисел. В числе x эта цифра будет отличаться от цифры в числе xk, так как именно таким образом число x было "сконструировано". Итак, мы получили число, которого нет в нашем списке всех действительных чисел. Мы пришли к противоречию. Значит наше допущение о том, что множество действительных чисел в отрезке [0, 1) счётно неверно, а значит оно несчётно.


Маленькое замечание, несмотря на то, что в доказательстве использовано троеточие в построение списка, можно это построение задать абсолютно строго.

Где же в этом доказательстве была использована "ссылка на самого себя?". Делается это при рассмотрение цифры k. С одной стороны, это цифра в записи числа x, а с другой стороны оно использует как указатель на число xk (и там мы интересуемся местом k).

Если почитать доказательства Гёделя и Тьюринга именно с помощью подобных построений они доказали свои теоремы. Для неформальное ознакомления с этими доказательствами я опять порекомендую книгу Хофштадтера Дугласа «Гёдель, Эшер, Бах: эта бесконечная гирлянда». На английском эта книга называется «Gödel, Escher, Bach: An Eternal Golden Braid» by Douglas Hofstadter.

The Wall Street Journal: Обама толкает Израиль к войне


Обама толкает Израиль к превентивному налету на ядерные объекты Ирана, уверяет обозреватель The Wall Street Journal Брет Стивенс. Скорее всего, этот удар будет нанесен до весны будущего года, полагает он. Не факт, что он будет эффективен, но даже за его успех придется заплатить вздорожанием барреля нефти до 300 долларов и войной, подчеркивает автор.

http://txt.newsru.co.il/press/15sep2009/wsj8976.html
http://online.wsj.com/article/SB10001424052970203917304574410672271269390.html

Нетаниягу рассказал, как схватил террористку за парик



Премьер-министр Израиля Биньямин Нетаниягу, выступая вчера перед членами комиссии кнессета по иностранным делам и обороне, рассказал о своем участи в операции по освобождению захваченного самолета бельгийской авиакомпании "Сабена" в 1972 году...

8 мая 1972 года четверо палестинских террористов из группировки "Чёрный сентябрь" (подпольный филиал ФАТХа) захватывают самолёт "Боинг 707", следовавший рейсом Вена - Тель-Авив и сажают его в аэропорту Лод.

Биньямин Нетаниягу, служивший тогда в спецназе генштаба ЦАХАЛа ("сайерет маткаль"), участвовал в операции по освобождению заложников, проведенной 9 мая.

В ходе операции двое террористов были убиты, две террористки - Тереза Халса и Рима Танус - схвачены. Они были приговорены к пожизненному заключению, но освобождены в ходе сделок с террористами.

Нетаниягу напомнил комиссии, что, несмотря на все жесты доброй воли по отношению к палестинцам, а одним из них было разрешение Терезе Халаси, проживающей в Иордании, приехать в Рамаллу на шестой съезд ФАТХа, в итоговых документах съезда нашла выражение непримиримая позиция палестинцев по отношению к Израилю.

"Я сам схватил эту Терезу тогда в "Сабене", - рассказал Нетаниягу. – Схватил за волосы, но она была в парике… Тут Марко Ашкенази, милуимник, который был с нами, ударил ее пистолетом, а тот был на боевом взводе и выстрелил и ранил меня в руку".

На одной из фотографий того дня видна Тереза, которую спускают по крылу освобожденного самолета (см. фото).

http://cursorinfo.co.il/news/novosti/2009/09/15/bibi-tresa-halsa/

Число свободных вакансий в израильских компаниях выросло на 40%


Согласно данным Центрального статистического бюро, в третьем квартале нынешнего года наблюдается резкий рост числа свободных вакансий в израильских компаниях.

С начала третьего квартала количество вакансий, предлагаемых ищущим работу израильтянам, выросло в среднем на 6.500 в день: с 21.400 вакансий во втором квартале до 27.800 – в третьем, что отражает рост в 40%, сообщает газета The Marker.

Тем не менее, этот показатель на 37% ниже, чем в аналогичный период 2008 года.

С начала третьего квартала зафиксировано также улучшение в балансе занятости, хотя общее число поступающих на работу новых сотрудников до сих пор ниже, чем число выходящих на пенсию или увольняемых.

Из компаний по трудоустройству Manpower Israel и MIT также передали о росте спроса на новых работников. Тем не менее, генеральный директор компании ЛМ Рафи Элимелех отмечает, что рост спроса касается младших должностей, тогда как для средних и руководящих должностей он незначителен.

http://txt.newsru.co.il/finance/15sep2009/jobs_605.html

Иран планировал взорвать 818-метровое здание в ОАЭ


Иран направил диверсионную группу для того чтобы взорвать в Дубаи самое высокое здание в мире, пишет сегодня "Маарив".

Власти ОАЭ арестовали 8 человек, среди них сирийского и палестинского происхождения.

http://cursorinfo.co.il/news/mivzakim/2009/09/15/09-16/
http://txt.newsru.co.il/mideast/15sep2009/burj301.html

Анекдот про крючочки (ЮМОР)

Отец пpовеpяет тетpадкy маленького сына:
- Почемy ты так неpовно пишешь кpючочки?
- Это не кpючочки, папа, это интегpалы.

За точечной ликвидацией в Сомали стоят спецслужбы США


Операция по точечной ликвидации одного из организаторов взрыва отеля Paradise в кенийской Момбасе, главаря входящей в "Аль-Каиду" "Армии Палестины" Салеха Али Салеха Набхана, была подготовлена американскими спецслужбами....

Кениец Салех Али Салех Набхан был одним из четырех организаторов взрыва принадлежащего израильтянам отеля в Момбасе, в результате которого погибли 15 человек, включая троих граждан Израиля. Кроме того, он находился в розыске за нападение на посольство США в Кении в 1998 году. Имя Салеха Али Салеха Набхана значилось в списке самых разыскиваемых ФБР террористов.

...Труп террориста коммандос забрали с собой для проведения точной идентификации. Фотографии убитого на данном этапе еще не были опубликованы.

http://txt.newsru.co.il/world/15sep2009/saleh509.html
http://txt.newsru.co.il/world/14sep2009/somalie456.html
http://www.foxnews.com/story/0,2933,550100,00.html
http://news.walla.co.il/?w=/22/1573959
http://www.ynet.co.il/articles/0,7340,L-3776942,00.html