Ключевое слово
28 | 03 | 2024
Новости Библиотеки
Шахматы Онлайн
Welcome, Guest
Username: Password: Remember me

TOPIC: Gödel's Theorem: An Incomplete Guide to Its Use and Abuse

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 12 Май 2012 15:42 #241

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
LUKA написал(а):
Не все общезначимые формулы доказуемы.
Почем тогда уверены в их общезначимость? Не ли поэтому логики высших порядков как-бы неудовлетворительны и значит результаты (скажем, Гёделя) в логике первого порядка обретают особую тяжесть истинных?

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 12 Май 2012 15:48 #242

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
Хайдук написал(а):
Последнее остаётся ли счётным?
LUKA написал(а):
Да, остаётся. Меня тоже этот факт забавляет. Но это - факт.
Нечего удивлятся, кстати - ежели формулы конечные, то их множество не более, чем счётно

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 12 Май 2012 16:04 #243

  • LUKA
  • LUKA's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 639
  • Karma: 0
Хайдук написал(а):
Почем тогда уверены в их общезначимость?
Хороший вопрос. Буду честен. Я когда-то успел доучить матлогику лишь по монографии Чёрча, да не до конца дочитал Булоса. Так что я - не самый компетентный человек для ответа на этот вопрос. Отвечу, как думаю.
Алгоритма распознавания общезначимости нет даже для логики первого порядка (если был бы, то это обеспечисло полноту). Даже поиск доказательство теорем - проблема в некотором роде творческая, не сводящаяся к механическим процедурам. То же самое наверно относится и к поиску общезначимых формул.
В логике второго порядка не справедливы ни теорема компактности, ни Левенгейма-Сколема, ни теорема полноты (доказывается полнота только для частного случая формул).
В известных Семи размышлениях... a-bugaev.chat.ru/uspensky.html Успенский назвал семантику логики второго порядка туманной и неопределённой.
Last Edit: 27 Март 2015 13:04 by Vladimirovich.

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 12 Май 2012 16:06 #244

  • Олег
  • Олег's Avatar
  • OFFLINE
  • Бездумный дворянин
  • Posts: 10251
  • Thank you received: 43
  • Karma: 1
Хайдук написал(а):
Нечего удивлятся, кстати - если формулы конечные, то их множество не более, чем счётно
Гёдели - куда Инфо дели ?

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 12 Май 2012 16:07 #245

  • Автор: infolio
  • Автор: infolio's Avatar
Вот и неперечислимость нарисовалась неизбежная: а вдруг она красивенько с несчетностью и безграничностью с Новым Годом уйдет нафиг за Вселенсконатуральное?
З павагай к перечислимости и кратности логик (хотя очень уже модной становится и бесконечнозначная= непрерырвная так называемая логика, так что и тут бесконечность ПОКА жиреет)

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 12 Май 2012 16:08 #246

  • LUKA
  • LUKA's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 639
  • Karma: 0
Хайдук написал(а):
Нечего удивлятся, кстати - если формулы конечные, то их множество не более, чем счётно
Сами по себе канторовские манипуляции со счётностью удивления не вызывают. Вызывает удивление несовпадение понятий алгоритмическая счётность (перечислимость) и просто счётность.

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 12 Май 2012 16:17 #247

  • Олег
  • Олег's Avatar
  • OFFLINE
  • Бездумный дворянин
  • Posts: 10251
  • Thank you received: 43
  • Karma: 1
LUKA написал(а):
просто счётность.
ну наконец то

= просто считай до бесконечности

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 12 Май 2012 16:20 #248

  • LUKA
  • LUKA's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 639
  • Karma: 0
Олег написал(а):
ну наконец то
= просто считай до бесконечности
Множество может быть счётным, но не будет ни одной механической процедуры (алгоритма) с помощью которого мы могли бы сделать этот счёт. Множество истин в арифметике первого порядка со сложением и умножением как раз такое,

Отредактировано LUKA (2012-05-12 20:21:16)

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 12 Май 2012 16:33 #249

  • Олег
  • Олег's Avatar
  • OFFLINE
  • Бездумный дворянин
  • Posts: 10251
  • Thank you received: 43
  • Karma: 1
LUKA написал(а):
Множество может быть счётным, но не будет ни одной механической процедуры (алгоритма) с помощью которого мы могли бы сделать этот счёт.
ну это к Инфо ! Не валяй дурака с меня. Считай- что ты сосчитал множество.

- я то просто пьянный вые***аюсь (

= а вы охренели от Евангилев от Луки алгоритмами


= Инфо тоже охренел

(V)

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 12 Май 2012 17:00 #250

  • Автор: infolio
  • Автор: infolio's Avatar
LUKA написал(а):

Множество может быть счётным, но не будет ни одной механической процедуры (алгоритма) с помощью которого мы могли бы сделать этот счёт.
ну это к Инфо ! Не валяй дурака с меня. Считай- что ты сосчитал множество.

- я то просто
предполагаю не доказываю и не настаиваю. что не только даже когда тебя сожрали то есть ТРИ выхода, а что не менее, чем ТРИ, во всем, всегда, везде.
И зависит сие великолепие многообразия только от точки зрения:
1. от аксиоматики
2. от себялюбия (незаменимости)
3. от точки зрения в пространстве (уже не раз упоминал, что когда два мальчика смотрят на 2 котов, которые сидят между ними), то абсолютно без разницы о чем они спорят: мой котенок слева- говорит Сева, НЕТ, твой котенок справа- говорит Слава.
Так что
не будет ни одной механической процедуры (алгоритма) с помощью которого мы могли бы сделать этот счёт.
можно считать иеверным, ПОКА, верным, причем по информационно-абстрактным, по субъективным так и по всем понятным общеприемлемым критериям.
Подтверждать неинтересно, а то тут и Хайдук не поможет: вместо
не будет ни одной механической процедуры (алгоритма)
будет счетное число-количество таких процедур, ибо даже если нет НИ ОДНОЙ, то это 0, это множество считается счетным (нулевое)... З павагай

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 12 Май 2012 17:11 #251

  • Олег
  • Олег's Avatar
  • OFFLINE
  • Бездумный дворянин
  • Posts: 10251
  • Thank you received: 43
  • Karma: 1
infolio написал(а):
З павагай
Ты ЛУКЕ лучше так не говори - а то всякое бывает))

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 13 Май 2012 15:22 #252

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
LUKA написал(а):
Вызывает удивление несовпадение понятий алгоритмическая счётность (перечислимость) и просто счётность.
В чем корни такого различия, откуда проистекает? Почему арифметика первого порядка со сложением и умножением неполная, а таковая лишь со сложением (арифметика Пресбургера) полная? Не ли случайность распределения простых чисел/множителей приложила руку?

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 13 Май 2012 15:53 #253

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
LUKA написал(а):
Алгоритма распознавания общезначимости нет даже для логики первого порядка (если был бы, то это обеспечисло полноту)
Полноту чего, логики (первого порядка) или арифметики? Полноты (или не) эти разные. Как раз Гёдель доказал полноту логики первого порядка в смысле доказуемости общезначимых формул, то бишь т.н. логических законов. Такой полноты НЕ хватает логикам высших порядков. Трудно представить в каком смысле может не быть алгоритма распознавания доказуемости общезначимости лишь логической оболочки (первого порядка), ДО наполнения арифметическим или каким-либо другим содержанием

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 13 Май 2012 20:42 #254

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
Полагаю решение такое: логика первого порядка перечислима (полна), но НЕ разрешима (теорем алгоритмом не узнать)


А арифметика даже неперечислима (неполна)

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 14 Май 2012 02:43 #255

  • LUKA
  • LUKA's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 639
  • Karma: 0
Хайдук написал(а):
Полноту чего, логики (первого порядка) или арифметики?
Полноту логики первого порядка. Она и полна на самом деле.
Теорема Геделя о полноте: в логике первого порядка всякая общезначимая формула доказуема.
В случае логики второго порядка - фигвам. Нет полноты. Зато арифметика в ней полна.
Но неполнота уже конкретных вариантов теории множеств (Цермелло-Френкеля или Геделя-Неймана и Барвайса) всё равно будет.
Хайдук написал(а):
Трудно представить в каком смысле может не быть алгоритма распознавания доказуемости общезначимости лишь логической оболочки (первого порядка), ДО наполнения арифметическим или каким-либо другим содержанием
Если бы алгоритм распознавания был, то проблема остановки машины Тьюринга была бы разрешима (довольно изящно доказывали когда-то Чёрч и Гедель).
Хайдук написал(а):
Полагаю решение такое: логика первого порядка перечислима (полна), но НЕ разрешима (теорем алгоритмом не узнать)
Именно так. Перечислима, но не разрешима. Зато частных случаев проблемы разрешения - вагон и мальнекая тележка. Для одноместных предикатов, например, эта проблема разрешима.

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 14 Май 2012 02:59 #256

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 14 Май 2012 03:11 #257

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
LUKA написал(а):
неполнота уже конкретных вариантов теории множеств (Цермелло-Френкеля или Геделя-Неймана и Барвайса) всё равно будет.
В чем конкретно будет выражаться такая неполнота (в логике 2-ого порядка)? Я лично как-будто НЕ знаю о других существенно неполных (в логике 1-ого порядка) теориях кроме арифметики, а разные варианты теории множеств неполны (в логике 1-ого порядка) именно за счёт ими содержимой уже арифметики

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 14 Май 2012 06:13 #258

  • LUKA
  • LUKA's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 639
  • Karma: 0
Хайдук написал(а):
В чем конкретно будет выражаться такая неполнота (в логике 2-ого порядка)? Я лично как-будто НЕ знаю о других существенно неполных (в логике 1-ого порядка) теориях кроме арифметики, а разные варианты теории множеств неполны (в логике 1-ого порядка) именно за счёт ими содержимой уже арифметики
Я некомпетентен ответить точно и грамотно на этот вопрос, так как моё познание логики второго порядка закончилось на монографии Чёрча с его теоремой Хенкина о полноте для частного случая формул логики второго порядка - вторично общезначимых. Поэтому причину неполноты второпорядковых теорий множеств типа Z2 я не знаю.
Поэтому отвечу просто, как думаю. Могу предположить, что, если в арифметике второго порядка для выводимости всех истинных формул могут используются только вторично общезначимые формулы (а логика второго порядка относительно этих формул полна - см. теорему Хенкина о полноте), то в теории множеств этого класса недостаточно для выводимости истинных высказываний второпорядковой теории множеств. Это - моё предположение и оно может оказаться неверным.

Отредактировано LUKA (2012-05-14 10:25:14)

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 14 Май 2012 11:50 #259

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
LUKA написал(а):
если в арифметике второго порядка для выводимости всех истинных формул могут используются только вторично общезначимые формулы (а логика второго порядка относительно этих формул полна - см. теорему Хенкина о полноте)
Если эта логика полна и арифметика в ней полна, то почему результат Гёделя о неполноте арифметики не потерял своего значения?

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 15 Май 2012 01:54 #260

  • LUKA
  • LUKA's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 639
  • Karma: 0
Хайдук написал(а):
Если эта логика полна и арифметика в ней полна, то почему результат Гёделя о неполноте арифметики не потерял своего значения?
Я тоже себе задаю этот вопрос иногда и ответа не знаю. Думаю, что причина в моей недостаточной образованности в этой области. Самообразованием занимаюсь постоянно, но очень медленно. Когда-то - возможно через несколько месяцев - и смогу ответить на этот вопрос.
А в целом, к логике второго порядка отношение почему-то настороженное - это настоящая терра инкогнито. Ссылки не буду давать, так как сам многого в них не понимаю.
Моё отношение к логике - это своеобразный способ архивации высказываний. Задаём что-то финитными методами, а потом вычисляем следствия.
Очевидно, что способы архивации могут различаться как по области применимости, так и по эффективности их применения.

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 15 Май 2012 13:59 #261

  • Автор: инфолио
  • Автор: инфолио's Avatar
Очевидно, что способы архивации могут различаться как по области применимости, так и по эффективности их применения.
А где +3 составляющая?
Вот вчера по ТВ услышал, что
Это МЫ освободили Германию от коричневой чумы- ну если не дословно, то прошу простить, так как смысл БЕЗОГОВОРОЧНО ПРАВДИВОГО высказывания, предполагаю, понятен. (З павагай к интересующимся и верящим, это я как БАРАН по гороскапу с 1950 г сказал. Тут даже с учетом вашего ответа, троичная логика отдыхает: ДА/НЕТ/ВОЗМОЖНО)

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 15 Май 2012 14:38 #262

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
Дружище, попрошу не писать здесь о забегаловках всторону Вашего воображения (Германия, коричневая чума и пр.), фокусируйте внимание на содержание обсуждения, без метафор и литературщины

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 01 Июнь 2012 16:40 #263

  • LUKA
  • LUKA's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 639
  • Karma: 0
Хайдук написал(а):
Вообще неполные теории отличаются вроде как раз неперечислимым набором аксиом
Неперечислимого набора аксиом НЕ бывает.
Доказательство. Должен существовать алгоритм распознавания того, является ли высказывание аксиомой. Область примененения алгоритма есть перечислимое множество. А его подмножество аксиом - разрешимое. Разрешимое подмножество перечислимого множества перечислимо. Вот.

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 01 Июнь 2012 16:42 #264

  • LUKA
  • LUKA's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 639
  • Karma: 0
Serge_P написал(а):
Ну, правда, мы знаем, что в основаниях кое-где запрятана Аксиома Выбора вместе с прочей ZF
ZFC - конечно мощная и красивая система. Но зачем Вам в ней аксиома фундирования? Кому она вообще нафиг нужна? Почему-то журналисты помешались на аксиоме выбора, а куда более экзотичную аксиому, которая за пределами самой теории множеств всесте со своими экзотическими выводами больше ничего не даёт (утрирую конечно, но где-то так), да и в саму теорию множеств как кандидат на универсальную модель ничем таким не улучшает.

Отредактировано LUKA (2012-06-01 20:45:25)

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 01 Июнь 2012 17:57 #265

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
LUKA написал(а):
Неперечислимого набора аксиом НЕ бывает.
Пожалуй


LUKA написал(а):
журналисты помешались на аксиоме выбора, а куда более экзотичную аксиому
Кто она, куда более экзотичная?


LUKA написал(а):
зачем Вам в ней аксиома фундирования?
Не уверен о каком фундировании идёт речь

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 01 Июнь 2012 18:34 #266

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
Аксиома Выбора вполне упорядочивает мощности множеств, без нее мощности эти могут удовлетворять любому частичному порядку, включающему несравнимые мощности

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 01 Июнь 2012 22:55 #267

  • Serge_P
  • Serge_P's Avatar
  • OFFLINE
  • Бояринъ
  • Posts: 1568
  • Thank you received: 6
  • Karma: 1
LUKA написал(а):
Но зачем Вам в ней аксиома фундирования? Кому она вообще нафиг нужна?
?

Если честно, я вообще не знаю, что это такое.


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

LUKA написал(а):
Почему-то журналисты помешались на аксиоме выбора
Ясно почему - потому что некоторые теоремы, полученные с ее помощью, противоречат здравому смыслу. Но Аксиому Выбора мы не сдадим - (навскидку) от теоремы Хана-Банаха и леммы Цорна отказываться негоже

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 01 Июнь 2012 23:25 #268

  • Хайдук
  • Хайдук's Avatar
  • OFFLINE
  • Наместник
  • Posts: 49331
  • Thank you received: 130
  • Karma: 16
Если не изменяет память, аксиома фундирования запрещает бесконечную йерархию элементов (множеств), являющихся в свою очередь множествами. То бишь в конце концов достучались до настоящих неделимых/фундаментальных элементов-атомов. По мне, аксиома разумная, и без того мыслим именно такими элементами-точками

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 02 Июнь 2012 01:10 #269

  • LUKA
  • LUKA's Avatar
  • OFFLINE
  • Думный дворянин
  • Posts: 639
  • Karma: 0
Хайдук написал(а):
Кто она, куда более экзотичная?
Она самая - фундирования. Идею того, что она очень искуственна для такой глобальной модели, как теория множеств даёт даже в своём учебнике для шестиклассников Л.В. Тарасов, написавший для них учебник.
Там он пишет про попугая, который рассказывал Слону (из мультфильма 38 попугаев) что такое бисяка. Бисяка - это такой ящичек, где лежит кукаляка. А что такое кукаляка, - спросил Слон.
Это - такой мешочек, где лежит пампуськая хрюка. А шо це такэ? Это такой свёрток, в который завёрнута ..., в общем ещё одна х...ня.
Короче, когда его спросили, а что лежит там в самом конце всех мешков, сундучков и свёртков, он не смог ответить. Проблема фундирования была им не решена. Если развернув конечное число всех свёртков и пакетиков Вы дойдёте до неделимого - вот аксиома и верна. Если нет - Вы столкнётесь с т.н. гипермножествами, которые зачем-то запрещены в ZF.

Ещё во времена диалектического материализма была издана-переведена книга Анри Пуанкаре О науке, где автор весьма растерянно-рассеянно писал про эту аксиому - а фиг, дескать, её знает.
И между прочим - очень примечательно:

Serge_P написал(а):
Если честно, я вообще не знаю, что это такое.
Естественно! На хрена она Вам! Это же не аксиома выбора, которую сплошь и рядом применяют. А эту грёбаную аксиому во всей остальной математике и не применяют.
А если и применяют - только по недоразумению - например, в выводе основного свойства упорядочённой пары по Куратовскому, без которого можно обойтись.
В теории множеств ещё некоторые очень примитивные св-ва ординалов чуть быстрей доказываются с применением этой аксиомы и всё.

Отредактировано LUKA (2012-06-02 05:11:43)

Gödel's Theorem: An Incomplete Guide to Its Use and Abuse 02 Июнь 2012 06:13 #270

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 106493
  • Thank you received: 2058
  • Karma: 105
LUKA написал(а):
В теории множеств ещё некоторые очень примитивные св-ва ординалов чуть быстрей доказываются с применением этой аксиомы и всё.
Если честно, то я не знаю о чем речь
, но выражение чуть быстрей доказываются с применением мене как бы не нравится.
Ежели что-то доказывается без нее, но медленнее, это значит, что это не аксиома, а лемма.
Каждому - своё.
Moderators: Grigoriy
Рейтинг@Mail.ru

Научно-шахматный клуб КвантоФорум