Почем тогда уверены в их общезначимость? Не ли поэтому логики высших порядков как-бы неудовлетворительны и значит результаты (скажем, Гёделя) в логике первого порядка обретают особую тяжесть истинных?
Хороший вопрос. Буду честен. Я когда-то успел доучить матлогику лишь по монографии Чёрча, да не до конца дочитал Булоса. Так что я - не самый компетентный человек для ответа на этот вопрос. Отвечу, как думаю.
Алгоритма распознавания общезначимости нет даже для логики первого порядка (если был бы, то это обеспечисло полноту). Даже поиск доказательство теорем - проблема в некотором роде творческая, не сводящаяся к механическим процедурам. То же самое наверно относится и к поиску общезначимых формул.
В логике второго порядка не справедливы ни теорема компактности, ни Левенгейма-Сколема, ни теорема полноты (доказывается полнота только для частного случая формул).
В известных Семи размышлениях... a-bugaev.chat.ru/uspensky.html Успенский назвал семантику логики второго порядка туманной и неопределённой.
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
12 Май 2012 16:07 #245
Автор: infolio
Вот и неперечислимость нарисовалась неизбежная: а вдруг она красивенько с несчетностью и безграничностью с Новым Годом уйдет нафиг за Вселенсконатуральное?
З павагай к перечислимости и кратности логик (хотя очень уже модной становится и бесконечнозначная= непрерырвная так называемая логика, так что и тут бесконечность ПОКА жиреет)
Нечего удивлятся, кстати - если формулы конечные, то их множество не более, чем счётно
Сами по себе канторовские манипуляции со счётностью удивления не вызывают. Вызывает удивление несовпадение понятий алгоритмическая счётность (перечислимость) и просто счётность.
Множество может быть счётным, но не будет ни одной механической процедуры (алгоритма) с помощью которого мы могли бы сделать этот счёт. Множество истин в арифметике первого порядка со сложением и умножением как раз такое,
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
12 Май 2012 17:00 #250
Автор: infolio
LUKA написал(а):
Множество может быть счётным, но не будет ни одной механической процедуры (алгоритма) с помощью которого мы могли бы сделать этот счёт.
ну это к Инфо ! Не валяй дурака с меня. Считай- что ты сосчитал множество.
- я то просто
предполагаю не доказываю и не настаиваю. что не только даже когда тебя сожрали то есть ТРИ выхода, а что не менее, чем ТРИ, во всем, всегда, везде.
И зависит сие великолепие многообразия только от точки зрения:
1. от аксиоматики
2. от себялюбия (незаменимости)
3. от точки зрения в пространстве (уже не раз упоминал, что когда два мальчика смотрят на 2 котов, которые сидят между ними), то абсолютно без разницы о чем они спорят: мой котенок слева- говорит Сева, НЕТ, твой котенок справа- говорит Слава.
Так что не будет ни одной механической процедуры (алгоритма) с помощью которого мы могли бы сделать этот счёт. можно считать иеверным, ПОКА, верным, причем по информационно-абстрактным, по субъективным так и по всем понятным общеприемлемым критериям.
Подтверждать неинтересно, а то тут и Хайдук не поможет: вместо
не будет ни одной механической процедуры (алгоритма)
будет счетное число-количество таких процедур, ибо даже если нет НИ ОДНОЙ, то это 0, это множество считается счетным (нулевое)... З павагай
Вызывает удивление несовпадение понятий алгоритмическая счётность (перечислимость) и просто счётность.
В чем корни такого различия, откуда проистекает? Почему арифметика первого порядка со сложением и умножением неполная, а таковая лишь со сложением (арифметика Пресбургера) полная? Не ли случайность распределения простых чисел/множителей приложила руку?
Алгоритма распознавания общезначимости нет даже для логики первого порядка (если был бы, то это обеспечисло полноту)
Полноту чего, логики (первого порядка) или арифметики? Полноты (или не) эти разные. Как раз Гёдель доказал полноту логики первого порядка в смысле доказуемости общезначимых формул, то бишь т.н. логических законов. Такой полноты НЕ хватает логикам высших порядков. Трудно представить в каком смысле может не быть алгоритма распознавания доказуемости общезначимости лишь логической оболочки (первого порядка), ДО наполнения арифметическим или каким-либо другим содержанием
Полноту чего, логики (первого порядка) или арифметики?
Полноту логики первого порядка. Она и полна на самом деле.
Теорема Геделя о полноте: в логике первого порядка всякая общезначимая формула доказуема.
В случае логики второго порядка - фигвам. Нет полноты. Зато арифметика в ней полна.
Но неполнота уже конкретных вариантов теории множеств (Цермелло-Френкеля или Геделя-Неймана и Барвайса) всё равно будет.
Хайдук написал(а):
Трудно представить в каком смысле может не быть алгоритма распознавания доказуемости общезначимости лишь логической оболочки (первого порядка), ДО наполнения арифметическим или каким-либо другим содержанием
Если бы алгоритм распознавания был, то проблема остановки машины Тьюринга была бы разрешима (довольно изящно доказывали когда-то Чёрч и Гедель).
Хайдук написал(а):
Полагаю решение такое: логика первого порядка перечислима (полна), но НЕ разрешима (теорем алгоритмом не узнать)
Именно так. Перечислима, но не разрешима. Зато частных случаев проблемы разрешения - вагон и мальнекая тележка. Для одноместных предикатов, например, эта проблема разрешима.
неполнота уже конкретных вариантов теории множеств (Цермелло-Френкеля или Геделя-Неймана и Барвайса) всё равно будет.
В чем конкретно будет выражаться такая неполнота (в логике 2-ого порядка)? Я лично как-будто НЕ знаю о других существенно неполных (в логике 1-ого порядка) теориях кроме арифметики, а разные варианты теории множеств неполны (в логике 1-ого порядка) именно за счёт ими содержимой уже арифметики
В чем конкретно будет выражаться такая неполнота (в логике 2-ого порядка)? Я лично как-будто НЕ знаю о других существенно неполных (в логике 1-ого порядка) теориях кроме арифметики, а разные варианты теории множеств неполны (в логике 1-ого порядка) именно за счёт ими содержимой уже арифметики
Я некомпетентен ответить точно и грамотно на этот вопрос, так как моё познание логики второго порядка закончилось на монографии Чёрча с его теоремой Хенкина о полноте для частного случая формул логики второго порядка - вторично общезначимых. Поэтому причину неполноты второпорядковых теорий множеств типа Z2 я не знаю.
Поэтому отвечу просто, как думаю. Могу предположить, что, если в арифметике второго порядка для выводимости всех истинных формул могут используются только вторично общезначимые формулы (а логика второго порядка относительно этих формул полна - см. теорему Хенкина о полноте), то в теории множеств этого класса недостаточно для выводимости истинных высказываний второпорядковой теории множеств. Это - моё предположение и оно может оказаться неверным.
если в арифметике второго порядка для выводимости всех истинных формул могут используются только вторично общезначимые формулы (а логика второго порядка относительно этих формул полна - см. теорему Хенкина о полноте)
Если эта логика полна и арифметика в ней полна, то почему результат Гёделя о неполноте арифметики не потерял своего значения?
Если эта логика полна и арифметика в ней полна, то почему результат Гёделя о неполноте арифметики не потерял своего значения?
Я тоже себе задаю этот вопрос иногда и ответа не знаю. Думаю, что причина в моей недостаточной образованности в этой области. Самообразованием занимаюсь постоянно, но очень медленно. Когда-то - возможно через несколько месяцев - и смогу ответить на этот вопрос.
А в целом, к логике второго порядка отношение почему-то настороженное - это настоящая терра инкогнито. Ссылки не буду давать, так как сам многого в них не понимаю.
Моё отношение к логике - это своеобразный способ архивации высказываний. Задаём что-то финитными методами, а потом вычисляем следствия.
Очевидно, что способы архивации могут различаться как по области применимости, так и по эффективности их применения.
Gödel's Theorem: An Incomplete Guide to Its Use and Abuse
15 Май 2012 13:59 #261
Автор: инфолио
Очевидно, что способы архивации могут различаться как по области применимости, так и по эффективности их применения.
А где +3 составляющая?
Вот вчера по ТВ услышал, что Это МЫ освободили Германию от коричневой чумы- ну если не дословно, то прошу простить, так как смысл БЕЗОГОВОРОЧНО ПРАВДИВОГО высказывания, предполагаю, понятен. (З павагай к интересующимся и верящим, это я как БАРАН по гороскапу с 1950 г сказал. Тут даже с учетом вашего ответа, троичная логика отдыхает: ДА/НЕТ/ВОЗМОЖНО)
Дружище, попрошу не писать здесь о забегаловках всторону Вашего воображения (Германия, коричневая чума и пр.), фокусируйте внимание на содержание обсуждения, без метафор и литературщины
Вообще неполные теории отличаются вроде как раз неперечислимым набором аксиом
Неперечислимого набора аксиом НЕ бывает.
Доказательство. Должен существовать алгоритм распознавания того, является ли высказывание аксиомой. Область примененения алгоритма есть перечислимое множество. А его подмножество аксиом - разрешимое. Разрешимое подмножество перечислимого множества перечислимо. Вот.
Ну, правда, мы знаем, что в основаниях кое-где запрятана Аксиома Выбора вместе с прочей ZF
ZFC - конечно мощная и красивая система. Но зачем Вам в ней аксиома фундирования? Кому она вообще нафиг нужна? Почему-то журналисты помешались на аксиоме выбора, а куда более экзотичную аксиому, которая за пределами самой теории множеств всесте со своими экзотическими выводами больше ничего не даёт (утрирую конечно, но где-то так), да и в саму теорию множеств как кандидат на универсальную модель ничем таким не улучшает.
Аксиома Выбора вполне упорядочивает мощности множеств, без нее мощности эти могут удовлетворять любому частичному порядку, включающему несравнимые мощности
Но зачем Вам в ней аксиома фундирования? Кому она вообще нафиг нужна?
?
Если честно, я вообще не знаю, что это такое.
Наверное, если она есть, то значит кому-то зачем-то понадобилась. Но это надо у специалистов по матлогике спрашивать, а я пас, моих знаний недостаточно, чтоб ответить на такой вопрос.
LUKA написал(а):
Почему-то журналисты помешались на аксиоме выбора
Ясно почему - потому что некоторые теоремы, полученные с ее помощью, противоречат здравому смыслу. Но Аксиому Выбора мы не сдадим - (навскидку) от теоремы Хана-Банаха и леммы Цорна отказываться негоже
Если не изменяет память, аксиома фундирования запрещает бесконечную йерархию элементов (множеств), являющихся в свою очередь множествами. То бишь в конце концов достучались до настоящих неделимых/фундаментальных элементов-атомов. По мне, аксиома разумная, и без того мыслим именно такими элементами-точками
Она самая - фундирования. Идею того, что она очень искуственна для такой глобальной модели, как теория множеств даёт даже в своём учебнике для шестиклассников Л.В. Тарасов, написавший для них учебник.
Там он пишет про попугая, который рассказывал Слону (из мультфильма 38 попугаев) что такое бисяка. Бисяка - это такой ящичек, где лежит кукаляка. А что такое кукаляка, - спросил Слон.
Это - такой мешочек, где лежит пампуськая хрюка. А шо це такэ? Это такой свёрток, в который завёрнута ..., в общем ещё одна х...ня.
Короче, когда его спросили, а что лежит там в самом конце всех мешков, сундучков и свёртков, он не смог ответить. Проблема фундирования была им не решена. Если развернув конечное число всех свёртков и пакетиков Вы дойдёте до неделимого - вот аксиома и верна. Если нет - Вы столкнётесь с т.н. гипермножествами, которые зачем-то запрещены в ZF.
Ещё во времена диалектического материализма была издана-переведена книга Анри Пуанкаре О науке, где автор весьма растерянно-рассеянно писал про эту аксиому - а фиг, дескать, её знает.
И между прочим - очень примечательно:
Serge_P написал(а):
Если честно, я вообще не знаю, что это такое.
Естественно! На хрена она Вам! Это же не аксиома выбора, которую сплошь и рядом применяют. А эту грёбаную аксиому во всей остальной математике и не применяют.
А если и применяют - только по недоразумению - например, в выводе основного свойства упорядочённой пары по Куратовскому, без которого можно обойтись.
В теории множеств ещё некоторые очень примитивные св-ва ординалов чуть быстрей доказываются с применением этой аксиомы и всё.
В теории множеств ещё некоторые очень примитивные св-ва ординалов чуть быстрей доказываются с применением этой аксиомы и всё.
Если честно, то я не знаю о чем речь
, но выражение чуть быстрей доказываются с применением мене как бы не нравится.
Ежели что-то доказывается без нее, но медленнее, это значит, что это не аксиома, а лемма.