НГУ

Форумы НГУ
Текущее время: Вт ноя 21, 2017 4:15 am

Часовой пояс: UTC + 7 часов




Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 26 ]  На страницу 1, 2  След.
Автор Сообщение
СообщениеДобавлено: Пт май 04, 2012 10:03 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Студенты попросили меня завести тему для обсуждения лекций по логике и других близких тем. С удовольствием выполняю просьбу.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Вопросы по ИВ и ИС
СообщениеДобавлено: Пт май 04, 2012 10:31 pm 
Не в сети
Редкий гость

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вопросы по ИВ и ИС
СообщениеДобавлено: Сб май 05, 2012 1:07 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
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.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вопросы по ИВ и ИС
СообщениеДобавлено: Сб май 05, 2012 1:30 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Eseniya писал(а):
2. Лемма об основных синтаксических эквивалентностях. Доказываем, что если A=(A1->A2), A1 эквивалентна A1', A2 - A2', то А экивалентна A'=(A1'->A2'): ...

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



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



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



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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Вопросы по ИВ и ИС
СообщениеДобавлено: Сб май 05, 2012 7:25 pm 
Не в сети
Редкий гость

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

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

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



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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт май 08, 2012 8:27 pm 
Не в сети
Частый гость

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср май 09, 2012 1:31 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
tom-anjelo писал(а):
Можете уточнить: где именно она использовалась?

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср май 09, 2012 1:47 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Да, стоит сделать и здесь объявление: на страничке кафедры "Алгебры и математической логики", в разделе учебных материалов выложена методичка по первой части нашего курса. В ней есть все основные определения и формулировки, а также небольшое число примеров и комментариев. Доказательств и подробных разъяснений там нет.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср май 09, 2012 11:55 am 
Не в сети
Частый гость

Зарегистрирован: Ср авг 18, 2010 4:22 pm
Сообщения: 25
Откуда: Панасенко Александр
Pavel E. Alaev писал(а):
В критерии фундированности частичного порядка...

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср май 09, 2012 3:53 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
И это, по-видимому, единственное место, где аксиома выбора была нужна (до момента, когда она в явном виде была сформулирована). Дальше таких мест много - например, везде, где использовалась лемма Цорна.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт май 11, 2012 12:25 am 
Не в сети
Редкий гость

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт май 11, 2012 1:13 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Annya писал(а):
На странице 6 есть: в предложении о допустимых в ИС правилах - в строке с контрапозицией два крайних справа правила выглядят явно как-то не так.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт май 11, 2012 9:52 am 
Не в сети
Редкий гость

Зарегистрирован: Пт май 04, 2012 10:10 pm
Сообщения: 4
Здравствуйте, Павел Евгеньевич! Не совсем понятно, как действует аксиома регулярности. Поясните, пожалуйста, на примере.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Пт май 11, 2012 7:46 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Eseniya писал(а):
Не совсем понятно, как действует аксиома регулярности.

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс май 13, 2012 9:58 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Если же говорить про аксиому регулярности более глубоко, то в рамках остальных аксиом ZFC она эквивалентна утверждению о том, что не существует бесконечной последовательности множеств вида

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

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


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Эта тема закрыта, вы не можете редактировать и оставлять сообщения в ней.  [ Сообщений: 26 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: Samueliks и гости: 8


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB