alexey_rom: (Default)
Сегодня случайно узнал, что у Н. Н. Непейводы есть аккаунт в ЖЖ: [livejournal.com profile] nepejvoda_n_n
alexey_rom: (Default)
Из принципа познаваемости следует существование разумной жизни во всех возможных мирах. Доказательство:

1 будет обозначать тождественную истину

K1 = "кто-то когда-то знает тождественно истинное утверждение". Это истинно в мире α тогда и только тогда, когда его истории есть разумная жизнь.

Kp → K1 ("если в мире кто-то что-то знает, то он знает тождественно истинное утверждение") примем за аксиому.

Рассиотрим такой мир α, где разумной жизни нет. Тогда в нём истинно

1) ¬K1
2) ◊K¬K1 (из 1 по принципу познаваемости)
В каком-то достижимом мире β верно
3) K¬K1 (из 2 по семантике возможных миров) То есть в этом мире есть кто-то, что-то знающий.
4) ¬K1 (из 3 по корректности знания)
5) K1 (из 3 по аксиоме Kp → K1)

Пришли к противоречию. По-моему, это позволяет локализовать проблему вполне чётко: пункт 2 должен говорить, что в мире β мы знаем, что в α нет разумной жизни; а вместо этого получается, что мы знаем, что её нет в β.
alexey_rom: (Default)
http://terrytao.wordpress.com/2010/03/19/a-computational-perspective-on-set-theory/

При этом он допускает счётно-бесконечные вычислительные ресурсы.

Правильно ли я понимаю, что это единственное отличие от конструктивизма и если его убрать, получим хорошую конструктивную теорию множеств?
alexey_rom: (Default)
Формулировка парадокса
Однажды в воскресенье начальник тюрьмы вызвал преступника, приговорённого к казни, и сообщил ему:

* Вас казнят на следующей неделе в полдень.
* День казни станет для вас сюрпризом, вы узнаете о нем только когда палач в полдень войдет к вам в камеру.

Начальник тюрьмы был честнейшим человеком и никогда не врал.
Заключённый подумал над его словами и улыбнулся: «В воскресенье меня казнить не могут! Ведь тогда уже в полдень субботы я буду знать об этом. А по словам начальника я не буду знать день своей казни. Следовательно последний возможный день моей казни — суббота. Но если меня не казнят в пятницу, то я буду заранее знать что меня казнят в субботу, значит и ее можно исключить.» Последовательно исключив пятницу, четверг, среду, вторник и понедельник преступник пришел к выводу, что начальник не сможет его казнить, выполнив все свои слова.

На следующей неделе, палач постучал в его дверь в полдень в среду — это было для него полной неожиданностью. Все, что начальник тюрьмы сказал, осуществилось. Где недостаток в рассуждении заключённого?

Одно из решений

Знание мы будем понимать стандартно: «заключённый знает p» <=> «p есть истинное и обоснованное мнение заключённого».

Обозначим s = "приговор будет в точности исполнен", Ks = "заключённый знает, что s"

Заметьте, что шаг: «В воскресенье меня казнить не могут! Ведь тогда уже в полдень субботы я буду знать об этом.» требует истинности Ks. В самом деле, если заключённый не уверен в исполнении приговора, и его не казнили до полудня субботы, то у него нет оснований полагать, что его казнят в воскресенье, а не (например) в следующий понедельник или вечером субботы. Так что строго говоря, доказано только Ks → ¬s. Из истинности знания мы также имеем Ks → s и Ks → (s ∧ ¬s).

Но само по себе это не противоречие; для противоречия нужно ещё, чтобы Ks было истинно. Это и призвано обеспечить условие «Начальник тюрьмы был честнейшим человеком и никогда не врал.» Но мы видим, что оно эту работу не выполняет: ведь заключённый в результате приходит к выводу, что приговор привести в исполнение нельзя, то есть что начальник соврал!

Значит:
1) приговор может быть приведён в исполнение
2) при этом заключённый не знает, что приговор будет приведён в исполнение
alexey_rom: (Default)
SEAR (Sets, elements and relations) По-моему, симпатично и достаточно практично (для "нормальной" математики). Мне больше нравится приведённый в конце вариант, где в базовые понятия включены пары и подмножества вместо отношений.

ECTS (Elementary Theory of the Category of Sets)
alexey_rom: (Default)
Не помню, у кого из френдов была ссылка, но введение действительно неплохое:

Introduction to Type Theory
alexey_rom: (Default)
Учебников по математической логике много. Зачем нужен ещё один?
1) Семантические деревья не описаны ни в одном русскоязычном учебнике. Даже такая классика, как "Логика первого порядка" Смальяна, не переведена на русский.
2) Доказательства теорем должны иметь чёткую логическую структуру. Чем она ближе к описанной в учебнике системе вывода, тем лучше. Поэтому естественный вывод в учебнике тоже должен быть, и в максимально удобном для реального использования виде.
3) Логика первого порядка не должна представляться как вершина достижений мат.логики.
4) Достойное место должны занимать приложения.
5) Такой учебник -- идеальное место, чтобы напомнить о базовых понятиях (множество, функция, и т.д.).

Ближе всего к этим требованиям подходит "Прикладная логика" Н.Н.Непейводы, но у неё, с моей точки зрения, есть свои недостатки:
1) вместо деревьев там представлены менее удобные семантические таблицы;
2) представлены не самые удобные формальные описания и доказательства полноты обеих главных систем вывода;
3) много философских и политических утверждений.

Примерное содержание: )
alexey_rom: (Default)
В принцип познаваемости вместо Фитчевского "p и не известно, что p" можно подставить "p и никто никогда не узнает, что p". Например, p может быть "на глубине 50 метров умерла бактерия".
alexey_rom: (Default)
Вынесено из комментариев к http://vic-gorbatov.livejournal.com/8026.html и расширено.

Парадокс познаваемости — известный парадокс в логике знания. Его можно сформулировать так: «Если всякую истину в принципе возможно узнать, то все истины уже известны».

В чём заключается парадокс )
Моё решение парадокса )
При сравнении с решениями, рассмотренными в SEP, моё подпадает под раздел 4. Но насколько я могу судить, приведённые там возражения к нему не применимы.

Буду рад комментариям. Особенно если кто-нибудь может сказать, почему это неправильно :)

UPD: П' можно упростить до α:(p→◊K(α:p)). Шаг 2 изменяется соответственно, остальное доказательство не меняется (только β на шаге 3 вводится свежее). Следующий вопрос -- можно ли усилить дальше до (α:p)→◊K(α:p) (с моей точки зрения, это существенно более сильное утверждение, чем разумное понимание принципа познаваемости)?
UPD 2: Да, можно. Модель построил, непротиворечивость доказал.
UPD 3: Важное уточнение. K — это не просто «известно, что». Там есть кванторы «существуют субъект x и момент времени t такие, что x в момент t известно, что». По крайней мере в книге Квэнвига по этому парадоксу именно так и у него ясно сказано, что с фиксированными временем и субъектом парадоксов нет.
alexey_rom: (Default)
http://awas1952.livejournal.com/99121.html
Доказательство несуществования Бога )
Увы, в комментариях Вассермана нет.
Полезная книжка: Torkel Franzen, Godel's Theorem: An Incomplete Guide to Its Use and Abuse.
alexey_rom: (Default)
Язык: есть предикат "быть классом" и предикат "быть элементом" (\in). Как обычно в теориях с классами, определяем множество как "класс, который является элементом какого-то класса".

Аксиомы (выделено то, что не выполняется в обычных теориях множеств):
A1. Всё, что имеет элементы -- класс.
A2. Аксиома объёмности: классы с одинаковыми элементами равны между собой
A3. Неограниченная аксиома выделения: для любой формулы P с одной свободной переменной {x | P(x)} есть класс.
A4. Есть бесконечное множество (обозначается I). Все бесконечные множества равномощны.
A5. Все собственные классы (те, которые не являются множествами) равномощны между собой; любой класс, равномощный собственному классу -- собственный.

Всё.

Насчёт того, что там можно доказать -- см. http://plato.stanford.edu/entries/settheory-alternative/#PocSetThe

alexey_rom: (Default)
Большинство знакомых мне учебников по логике используют машины Тьюринга в качестве основного примера универсальной вычислительной машины. Как мне кажется, это абсолютно аналогично использованию исчисления высказываний и/или предикатов в стиле Гильберта (если кто не помнит, это те исчисления, где есть много аксиом и единственное правило вывода modus ponens (+ могут быть правила обобщения и перехода к частному случаю в исчислении предикатов).

Read more... )
alexey_rom: (Default)
Не подскажет ли мне кто-нибудь, в каких учебниках на русском, кроме Непейводы, рассказывается о естественном выводе (natural deduction) и/или аналитических таблицах (tableaux)? В русском языке используются обычно такие переводы этих терминов или другие?

Этот же вопрос задал в [livejournal.com profile] ru_math.

Profile

alexey_rom: (Default)
alexey_rom

April 2012

S M T W T F S
1 234567
89 1011121314
15161718192021
22232425262728
2930     

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 25th, 2017 06:19 am
Powered by Dreamwidth Studios