НГУ

Студенты попросили меня завести тему для обсуждения лекций по логике и других близких тем. С удовольствием выполняю просьбу.

Здравствуйте, Павел Евгеньевич.
1. Вопрос по доказательству леммы о том, что если непустой конец формулы A равен началу B, то этот конец равен B. Представляем B=B'B''. Рассматриваем случай A=(A1&A2) и предполагаем, что B' конец в "A2)". Тогда непустой конец A2 есть начало B => он равен B. В чем здесь заключается противоречие?
2. Лемма об основных синтаксических эквивалентностях. Доказываем, что если A=(A1->A2), A1 эквивалентна A1', A2 - A2', то А экивалентна A'=(A1'->A2'):

A1' |- A1 ; A1->A2 |- A1->A2 (удаление ->)
-----------------------------------------------------------------------
A1->A2, A1' |- A2 ; A2 |- A2' (сечение)
---------------------------------------------------------------------------
А1|- А2 ; А1'|- А2'
---------------------------------------------
A1->A2 |- A1'->A2'
Непонятно, как работают удаление -> и сечение.

Вот более подробное рассуждение:
1. B' - это начало B.
2. B' состоит из непустого конца A2 и закрывающей скобки.
3. По предположению индукции этот непустой конец A2 равен B.
4. Значит, часть B', которая по длине строго меньше B', оказалась равной B. Это явно противоречит п.1.

Второй вопрос - чуть позже.

Вы красиво наставили в дереве пробелов, а они все стёрлись, увы. Но я понял, о чём речь. Поскольку при этом я не совсем понял, в каком именно месте трудность, попробую дать общий комментарий. Правило удаления -> выглядит так:



При этом мы договариваемся, что при построении дерева можно пропускать структурные правила, которые позволяют переставлять формулы в левой части секвенции и добавлять туда новые формулы (при движении сверху вниз). Значит, использование правила удаления -> может иметь и такой вид:



В дереве, которое Вы привели, оно как раз так и выглядит.
Более формально этот переход раскладывается в три правила: два структурных и стандартное удаление ->:



Если всё ещё неясно, я могу подробнее объяснить. Попробуйте точно сформулировать, что именно неясно. В любом случае, спасибо за вопросы!

Все понятно. А то я уже думала, что противоречие заключается в лишней закрывающей скобке.


А здесь все дело в различных .

Большое спасибо за помощь!

Здравствуйте, Павел Евгеньевич.
После введения аксиомы выбора Вы упомянули о том, что мы уже использовали её ранее. Аналогичное замечание присутствует и в кратком конспекте. Можете уточнить: где именно она использовалась? Абсолютно любой пример из курса

В критерии фундированности частичного порядка: при доказательстве в одну из сторон нам нужно строить бесконечно убывающую последовательность элементов. Мы выбираем произвольный a0, потом a1<a0, потом a2<a1, и т.д. Каждый раз мы должны выбрать какой-то один ai из, вообще говоря, нескольких вариантов, и здесь нужна аксиома выбора.

Да, стоит сделать и здесь объявление: на страничке кафедры "Алгебры и математической логики", в разделе учебных материалов выложена методичка по первой части нашего курса. В ней есть все основные определения и формулировки, а также небольшое число примеров и комментариев. Доказательств и подробных разъяснений там нет.

В лекциях было несколько небольших тем, которые в методичку пока не вошли; думаю, что это не страшно. Не знаю, насколько термин "методичка" является идеальным в данном случае, но точно является традиционным. Самоназвание текста - "краткий конспект".

Теперь ясно, спасибо большое!

И это, по-видимому, единственное место, где аксиома выбора была нужна (до момента, когда она в явном виде была сформулирована). Дальше таких мест много - например, везде, где использовалась лемма Цорна.

Здравствуйте! Вы просили говорить об опечатках в кратком конспекте вроде)
На странице 6 есть: в предложении о допустимых в ИС правилах - в строке с контрапозицией два крайних справа правила выглядят явно как-то не так.
На той же странице, в теореме о замене есть просто опечатка - "синтаксически".
На странице 20 - следующее замеченное: строчка перед принципом трансфинитной рекурсии, первое слово... "формально"
Вроде всё, больше ничего не заметила. )

О, спасибо! Опечатки замечены верно, а это вообще серьёзный огрех. В лекциях, кажется, всё было правильно. Эти четыре правила легко запомнить: мы меняем местами A и B и одновременно меняем у них "знаки": если отрицание есть, убираем, если нет, ставим.

Правила, указанные в тексте, вообще не являются допустимыми. Наверное, я сделаю так: текст менять уже не буду, чтобы не вносить путаницу, но добавлю в конце раздел "Замеченные неточности".

Здравствуйте, Павел Евгеньевич! Не совсем понятно, как действует аксиома регулярности. Поясните, пожалуйста, на примере.

Сначала общее замечание: коль скоро мы хотим представить все математические объекты в виде множеств, получается, что элементы любого множества - тоже множества, их элементы опять множества, и т.д. Аксиома регулярности нужна, чтобы внести в эти заросли некоторый порядок.

Аксиома говорит, что для любого непустого множества A существует X, лежащий в A, т.ч. пересечение X и A пусто. Пусть A = {3,5,7}. Множество 3 по определению равно {0,1,2}. Выбрав X = 3, получим, что пересечение X и A пусто.

Если же говорить про аксиому регулярности более глубоко, то в рамках остальных аксиом ZFC она эквивалентна утверждению о том, что не существует бесконечной последовательности множеств вида

Иными словами, не существует функции т.ч. и при .

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