НГУ
http://forum.nsu.ru/

Математическая логика, группы 1121-1128
http://forum.nsu.ru/viewtopic.php?f=18&t=23238
Страница 1 из 2

Автор:  Pavel E. Alaev [ Пт май 04, 2012 10:03 pm ]
Заголовок сообщения:  Математическая логика, группы 1121-1128

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

Автор:  Eseniya [ Пт май 04, 2012 10:31 pm ]
Заголовок сообщения:  Вопросы по ИВ и ИС

Здравствуйте, Павел Евгеньевич.
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'
Непонятно, как работают удаление -> и сечение.

Автор:  Pavel E. Alaev [ Сб май 05, 2012 1:07 am ]
Заголовок сообщения:  Re: Вопросы по ИВ и ИС

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

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

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

Автор:  Pavel E. Alaev [ Сб май 05, 2012 1:30 am ]
Заголовок сообщения:  Re: Вопросы по ИВ и ИС

Eseniya писал(а):
2. Лемма об основных синтаксических эквивалентностях. Доказываем, что если A=(A1->A2), A1 эквивалентна A1', A2 - A2', то А экивалентна A'=(A1'->A2'): ...

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



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



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



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

Автор:  Eseniya [ Сб май 05, 2012 7:25 pm ]
Заголовок сообщения:  Re: Вопросы по ИВ и ИС

Pavel E. Alaev писал(а):
4. Значит, часть B', которая по длине строго меньше B', оказалась равной B. Это явно противоречит п.1.

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

Pavel E. Alaev писал(а):
Значит, использование правила удаления -> может иметь и такой вид:



В дереве, которое Вы привели, оно как раз так и выглядит.

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

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

Автор:  tom-anjelo [ Вт май 08, 2012 8:27 pm ]
Заголовок сообщения: 

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

Автор:  Pavel E. Alaev [ Ср май 09, 2012 1:31 am ]
Заголовок сообщения: 

tom-anjelo писал(а):
Можете уточнить: где именно она использовалась?

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

Автор:  Pavel E. Alaev [ Ср май 09, 2012 1:47 am ]
Заголовок сообщения: 

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

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

Автор:  tom-anjelo [ Ср май 09, 2012 11:55 am ]
Заголовок сообщения: 

Pavel E. Alaev писал(а):
В критерии фундированности частичного порядка...

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

Автор:  Pavel E. Alaev [ Ср май 09, 2012 3:53 pm ]
Заголовок сообщения: 

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

Автор:  Annya [ Пт май 11, 2012 12:25 am ]
Заголовок сообщения: 

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

Автор:  Pavel E. Alaev [ Пт май 11, 2012 1:13 am ]
Заголовок сообщения: 

Annya писал(а):
На странице 6 есть: в предложении о допустимых в ИС правилах - в строке с контрапозицией два крайних справа правила выглядят явно как-то не так.

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

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

Автор:  Eseniya [ Пт май 11, 2012 9:52 am ]
Заголовок сообщения: 

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

Автор:  Pavel E. Alaev [ Пт май 11, 2012 7:46 pm ]
Заголовок сообщения: 

Eseniya писал(а):
Не совсем понятно, как действует аксиома регулярности.

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

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

Автор:  Pavel E. Alaev [ Вс май 13, 2012 9:58 pm ]
Заголовок сообщения: 

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

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

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

Страница 1 из 2 Часовой пояс: UTC + 7 часов
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/