alt text

задан 9 Ноя '18 6:00

@logic: здесь, мне кажется, всё уже дано в указаниях. Конечно-порождённая абелева группа изоморфна Z+...+Z. На ней линейный порядок, стабильный относительно сложения, задать легко: сначала сравниваем наборы по первой координате; если она та же самая -- по второй, и так далее. А потом -- теорема компактности.

(21 Ноя '18 23:53) falcao

Как применять теорему компактности? Она говорит, что если есть теория Т, каждое конечное подмножество которой выполнимо (satisfiable), то и теория выполнима. При чем тут выполнимость? И при чем тут конечные подмножества, если конечно порожденные абелевы группы бесконечны?

(22 Ноя '18 2:49) logic

@logic: я понял теперь, что именно надо разъяснять. Мне казалось, что если упражнение сопровождено упоминанием теоремы компактности, то "технология" её применения уже рассматривалась. Но, если этого не было, то имеет смысл поговорить более подробно. Сейчас я уже ухожу, а завтра напишу и по этому вопросу, и по "близлежащим". Теорема компактности -- вещь действительно полезная и хорошая -- в отличие от введения "мусорных" алгебраических структур и проверок их бесполезных формальных свойств.

(22 Ноя '18 3:27) falcao
10|600 символов нужно символов осталось
1

Прежде всего, выписываем аксиомы абелевой группы в подходящей сигнатуре, а также аксиомы строго линейного порядка при помощи бинарного предиката P(x,y). Помимо этого, добавляем аксиому устойчивости P относительно операции: P(x,y)->P(x+z,y+z).

Основной приём таков: пусть дана абелева группа G. Добавим её элементы в сигнатуру в качестве предметных констант. Далее, если a+b=c в группе, то добавляем к теории аксиому f(a,b)=c с участием тех же констант, где двуместный функциональный символ f отвечает за операцию в группе.

Мы получаем "огромную" теорию (скажем, если группа континуальна, то у нас получается континуальное число символов и аксиом. Как и всякая теория, она либо противоречива, либо непротиворечива. В последнем случае теория выполнима по теореме Гёделя о полноте, то есть она имеет модель. Последнее означает, что мы можем проинтерпретировать предикатный символ P так, что все аксиомы теории станут истинными. Это даст упорядочение группы G.

Таким образом, если теория непротиворечива, то она выполнима, и мы всё доказали. Допустим, что она противоречива. Тогда (это и есть компактность) противоречие следует из конечного числа аксиом. В них задействовано конечное число предметных констант. Они порождают подгруппу H. Она упорядочиваема. Значит, на ней в подходящей интерпретации будут истинными все аксиомы рассматриваемой подсистемы. Но из них следует противоречие, которое истинным ни в какой интерпретации быть не может. Тем самым, мы от противного доказали, что G упорядочиваема.

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

ссылка

отвечен 22 Ноя '18 10:25

Они порождают подгруппу H. Она упорядочиваема.

Почему она упорядочиваема? Тут была использована лемма о том, что любая конечно порожденная абелева группа упорядочиваема?

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

Этот момент тоже четко не укладывается. Может, я не очень понимаю понятие противоречивости? Это значит, что T |- False (что то же самое, что T |= False)? Тогда конечное T' |= False. Но у T' есть модель M, и M|= T'. Потом используется транзтивность |=? Если да, то почему не может быть M |= False?

(22 Ноя '18 21:39) logic

@logic: цитирую комментарий: Конечно-порождённая абелева группа изоморфна Z+...+Z. На ней линейный порядок, стабильный относительно сложения, задать легко: сначала сравниваем наборы по первой координате; если она та же самая -- по второй, и так далее.

Концовка доказательства подразумевает, что все логические следствия истинной системы утверждений являются истинными (на M). А противоречие (утверждение вида A&not(A)) ложно всегда.

(22 Ноя '18 21:53) falcao

P(x,y)->P(x+z,y+z)

А почему один и тот же z прибавляется? В условии a < b, c <= d => a+b <= c+d (b и d не равны).

где двуместный функциональный символ f отвечает за операцию в группе

Этот функциональный символ - из сигнатуры, рассмотренной в 1 абзаце? То есть G - это не какая-то произвольная группа, а модель теории групп, в сигнатуре которой есть именно тот функциональный символ, который был рассмотрен ранее?

Они порождают подгруппу H.

Наверное, не они, а соответствующие им элементы группы G?

[Продолжение следует]

(29 Ноя '18 7:49) logic

это и есть компактность

Компактность говорит, что если каждое конечное подмножество теории выполнимо, то теория выполнима. Вы пользуетесь тем, что если теория не выполнима, то она противоречива? И тогда по компактности каждое конечное подмножество противоречиво. Это Вы и называете "противоречие следует из конечного числа аксиом"?

[Продолжение следует]

(29 Ноя '18 7:54) logic

Значит, на ней в подходящей интерпретации будут истинными все аксиомы рассматриваемой подсистемы

H - это модель рассматриваемой теории, из которой выброшены константы, соответствующие элементам, лежащим в G-H, а также из которой выброшены аксиомы, в которых участвуют эти константы. (Моё понимание именно таково). Что такое "все аксиомы рассматриваемой подсистемы"? Это то, что я написал? Что значит "в подходящей интерпретации"? В интерпретации чего?

(29 Ноя '18 7:55) logic

1) Условия P(x,y)->P(x+z,y+z) достаточно, так как при a < b, c<=d мы имеем a+c<=a+d=d+a < d+b=b+d.

2) Группа G задана в самом начале. Именно про неё доказывается упорядоченность. Конечно, далее рассматривается теория с участием f и P, моделью которой она должна являться.

3) По теореме Гёделя о полноте, непротиворечивость = выполнимость, поэтому на варианты формулировок можно не обращать внимания. То, что противоречие следует из конечного числа аксиом -- простой, но важный факт, лежащий в основе доказательства теоремы компактности в Вашей формулировке.

(30 Ноя '18 3:18) falcao

4) Наверное, не они, а соответствующие им элементы группы G? У нас элементы G и были взяты в качестве новых предметных констант, поэтому различать одно и другое незачем.

5) H -- это модель "подтеории", в которую входит конечное число аксиом, приводящих (якобы) к противоречию. Интерпретируется f как сумма, а также P как порядок на H, который имеется на конечно-порождённой абелевой группе без кручения.

(30 Ноя '18 3:21) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,971
×696

задан
9 Ноя '18 6:00

показан
125 раз

обновлен
30 Ноя '18 3:21

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru