Основания математики - элементарное рассмотрение

[vek88]

man в сообщении #373688 писал(а):

Написано же неразрешимо.

А что, по Вашему возможно, что распознавание $a \in E$ алгоритмически разрешимо, а $a \notin E$ нет?

man в сообщении #373688 писал(а):

Это как ?

Не понял - что как?

ЗЫ. У меня предложение. Коли речь пошла о математических деталях, давайте по возможности будем точно и аккуратно формулировать вопросы.

[man]

vek88 в сообщении #373695 писал(а):

А что, по Вашему возможно, что распознавание $a \in E$ алгоритмически разрешимо, а $a \notin E$ нет?

Случай брадобреев
$\frac {x\in A}{x \notin B}$, $\frac {x \in B}{x \notin A}$ Вам не понравился, но он возможен.
Возьмем исчисление с пустым алфавитом и правилом вывода $\frac {x}{Ax}$
$A$ выводимо ? Пустое слово принадлежит пустому алфавиту ?

[vek88]

man в сообщении #373732 писал(а):

vek88 в сообщении #373695 писал(а):

А что, по Вашему возможно, что распознавание $a \in E$ алгоритмически разрешимо, а $a \notin E$ нет?

Случай брадобреев
$\frac {x\in A}{x \notin B}$, $\frac {x \in B}{x \notin A}$ Вам не понравился, но он возможен.
Возьмем исчисление с пустым алфавитом и правилом вывода $\frac {x}{Ax}$
$A$ выводимо ? Пустое слово принадлежит пустому алфавиту ?

Случай с брадобреем? Да, мне так не нравится, но я уже сказал, что имеете право. Это будет некоторая "нестандартная" семантика отрицания. Если Вам это интересно, пользуйтесь ей.

Далее, если в исчислении пустой алфавит, то по определению ничего в ней не выводимо, кроме, максимум, пустого слова, если есть аксиома - пустое слово.

И вообще, man!

Вы не ответили на мой четкий вопрос и продолжаете задавать непонятные вопросы. Я с большим удовольствием постараюсь объяснить все, что могу. Но не ставьте, пожалуйста, меня в трудное положение, когда я даже не могу понять Ваши проблемы:
- или Вам что-то непонятно;
- или Вы считаете, что где-то ошибка;
- или Вы считаете, что следует что-то излагать иначе;
- или что-то еще.

Плюс я не знаю Вашей подготовки в этих вопросах, но готов отвечать на любом уровне (от "на пальцах" до суровой математики в пределах моих знаний, разумеется).

Короче, давайте оптимизируем затраты нашего времени. Давайте задавать четкие и понятные вопросы, и по одному за раз. Я постараюсь давать, если смогу, четкие ответы.

[man]

vek88 в сообщении #373742 писал(а):

Вы не ответили на мой четкий вопрос и продолжаете задавать непонятные вопросы. Я с большим удовольствием постараюсь объяснить все, что могу. Но не ставьте, пожалуйста, меня в трудное положение, когда я даже не могу понять Ваши проблемы:
- или Вам что-то непонятно;
- или Вы считаете, что где-то ошибка;
- или Вы считаете, что следует что-то излагать иначе;
- или что-то еще.

Я извиняюсь за глупые вопросы, четкий ответ - считаю, что невозможно, чтобы $x \in E$ было разрешимо, а $x \notin E$ неразрешимо.
Просматривать тему начал с парадокса брадобрея. Меня заинтересовал случай с двумя брадобреями.
Просмотрев книгу увидел кое-что непонятное, Ваших разъяснений достаточно. Я не считаю, что где-то ошибка, все верно.
Я пытаюсь сформулировать пока несовсем ясную мысль с двумя брадобреями, поэтому задаю такие вопросы.

[vek88]

man в сообщении #373779 писал(а):

Я пытаюсь сформулировать пока несовсем ясную мысль с двумя брадобреями, поэтому задаю такие вопросы.

Отлично. Завтра тоже попробую посмотреть на этих брадобреев на свежую голову.

[man]

Есть вопросы о соотношении К-систем с классической логикой.
Скажем так, в К-системах нет противоречий, есть только неразрешимые утверждения.
Вопрос о противоречивости самой К-системы с точки зрения классической логики.
Дпустим, в К-системе выводимо $a \land \neg a$ (Л-вывод), с точки зрения классической логики, если в теории выводимо противоречие, она противоречива.
С другой стороны, если алгоритм не останавливается, проблема может быть, как в самом алгоритме, так и в объектах, с которыми он работает.
В общем есть выбор, или изменить алгоритм, или изменить объекты.

[man]

Давайте опять о брадобреях.
Брадобрей - это не житель деревни. Назовем это классом множеств. Нельзя сказать, что брадобрей живет в деревне, можно лишь сказать, что какой-либо житель деревни является брадобреем или нет, принадлежит он соответсвующему классу или нет.
Если брадобрей - это класс, опеределенный как $A \in A \leftrightarrow A \notin A$, то вопрос о том, является ли какой-либо житель брадобреем в классической логике имеет отрицательный ответ - нет таких жителей. А вот как это выглядит в К-системе не очень понятно. Если этот класс не пуст, то объектами К-системы могут быть противоречия (в классическом понимании).
Вот тут и появляются два брадобрея с вопросом об их тождестве.

[vek88]

man в сообщении #373823 писал(а):

(1) Есть вопросы о соотношении К-систем с классической логикой.
(2) Скажем так, в К-системах нет противоречий, есть только неразрешимые утверждения.
Вопрос о противоречивости самой К-системы с точки зрения классической логики.
(3) Допустим, в К-системе выводимо $a \land \neg a$ (Л-вывод), с точки зрения классической логики, если в теории выводимо противоречие, она противоречива.
(4) С другой стороны, если алгоритм не останавливается, проблема может быть, как в самом алгоритме, так и в объектах, с которыми он работает.
В общем есть выбор, или изменить алгоритм, или изменить объекты.

Отвечаю на Ваши вопросы постепенно, по мере своего понимания и наличия времени. Вставил нумерацию для удобства ссылок.

1. О связи (мета)логики К-систем и классической логики. В случае полных К-систем их логика в точности классическая. А в случае произвольных К-систем более сложная и включает в определенном смысле классическую и интуиционистскую логики. См. в теме выше начиная с поста post293513.html#p293513.

2. К-система непротиворечива в том смысле, что любое слово в ней не может быть одновременно истинным и ложным. Оно либо истинно, либо ложно, либо неразрешимо.

3. Но представить в К-системе Вы можете что угодно, например, противоречивую аксиоматическую теорию, поскольку она включает в себя все финитные формальные системы. Грубо говоря, любая финитная теория - это К-система с точностью до обозначений, причем служебный знак $\ominus$ не нужен для представления финитной теории.

С учетом сказанного в К-системе может быть выводима формула $a \land \neg a$. При этом знак $\neg$ вводился не правилом $\frac{\ominus x}{\neg x}$, а этой самой аксиоматической теорией. Какое значение истинности Вы присвоите этой формуле в К-системе? ИМХО - это Ваша селедка - все зависит от того что Вы хотите. Если Вы просто объявили финитную теорию К-системой, то эта формула будет истинной. А если Вы еще добавите в К-системе что-то дополнительное для "интерпретации" рассматриваемой финитной теории, то можно представить так, что противоречивые формулы будут ложными.

Правда, я не вижу в этом смысла. Но имеете право.

Про Л-вывод в этом пункте я не понял.

4. Этот пункт пока не понял.

[man]

vek88 в сообщении #374062 писал(а):

2. К-система непротиворечива в том смысле, что любое слово в ней не может быть одновременно истинным и ложным. Оно либо истинно, либо ложно, либо неразрешимо.

Это интересный вариант, его следует обсудить применительно к словам, которые в классической логике противоречивы.

vek88 в сообщении #374062 писал(а):

3. Но представить в К-системе Вы можете что угодно, например, противоречивую аксиоматическую теорию, поскольку она включает в себя все финитные формальные системы. Грубо говоря, любая финитная теория - это К-система с точностью до обозначений, причем служебный знак $\ominus$ не нужен для представления финитной теории.

Возьмем две противоречивые финитные теории, например состоящие из единственных аксиом $a\in a \land a\notin a$ и $a\in a \leftrightarrow a\notin a$
Разрешим ли в К-системе вопрос об их эквивалентности.
Разрешим ли вопрос об эквивалентности двух К-систем, которыми представлены эти финитные теории.

vek88 в сообщении #374062 писал(а):

С учетом сказанного в К-системе может быть выводима формула $a \land \neg a$. При этом знак $\neg$ вводился не правилом $\frac{\ominus x}{\neg x}$, а этой самой аксиоматической теорией. Какое значение истинности Вы присвоите этой формуле в К-системе? ИМХО - это Ваша селедка - все зависит от того что Вы хотите. Если Вы просто объявили финитную теорию К-системой, то эта формула будет истинной.

Т.е. если в теории $a$ истинно, $\neg a$ ложно, то в К-системе и $a$ истинно и $\neg a$ истинно, а $\ominus a, \ominus \neg a$ ложно.

vek88 в сообщении #374062 писал(а):

4. Этот пункт пока не понял.

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

[vek88]

man в сообщении #374353 писал(а):

vek88 в сообщении #374062 писал(а):

2. К-система непротиворечива в том смысле, что любое слово в ней не может быть одновременно истинным и ложным. Оно либо истинно, либо ложно, либо неразрешимо.

Это интересный вариант, его следует обсудить применительно к словам, которые в классической логике противоречивы.

vek88 в сообщении #374062 писал(а):

3. Но представить в К-системе Вы можете что угодно, например, противоречивую аксиоматическую теорию, поскольку она включает в себя все финитные формальные системы. Грубо говоря, любая финитная теория - это К-система с точностью до обозначений, причем служебный знак $\ominus$ не нужен для представления финитной теории.

Возьмем две противоречивые финитные теории, например состоящие из единственных аксиом $a\in a \land a\notin a$ и $a\in a \leftrightarrow a\notin a$
Разрешим ли в К-системе вопрос об их эквивалентности.
Разрешим ли вопрос об эквивалентности двух К-систем, которыми представлены эти финитные теории.

vek88 в сообщении #374062 писал(а):

С учетом сказанного в К-системе может быть выводима формула $a \land \neg a$. При этом знак $\neg$ вводился не правилом $\frac{\ominus x}{\neg x}$, а этой самой аксиоматической теорией. Какое значение истинности Вы присвоите этой формуле в К-системе? ИМХО - это Ваша селедка - все зависит от того что Вы хотите. Если Вы просто объявили финитную теорию К-системой, то эта формула будет истинной.

Т.е. если в теории $a$ истинно, $\neg a$ ложно, то в К-системе и $a$ истинно и $\neg a$ истинно, а $\ominus a, \ominus \neg a$ ложно.

vek88 в сообщении #374062 писал(а):

4. Этот пункт пока не понял.

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

2. Вы пишете "Это интересный вариант". Вариант чего? ИМХО это не вариант чего-то, а свойство К-систем по определению!

3. В полной К-системе представимы все арифметические множества, в частности, дополнение любого РП множества является полным К-множеством. Следовательно, проблема распознавания эквивалентности двух РП множеств (или финитных формальных теорий) разрешима в полных К-системах.

А как трактовать противоречивую аксиоматическую теорию, представленную в К-системе? Дык это Ваша селедка - как хотите трактуйте - К-система здесь нам не указ. Она лишь позволяет Вам воплотить в жизнь любую Вашу трактовку противоречивой формальной системы.

А вот это: "а $\ominus a, \ominus \neg a$ ложно" - вы пишете некорректно - таких слов в К-системе нет. Знак $\ominus$ - особый и в словах не используется.

4. По прежнему не понимаю - этот вопрос не относится к К-системам. А то что Вы пишете про зацикливание программы - это ИМХО общая банальность. Кстати, проблема распознавания зацикливания программы разрешима в полных К-системах.

[man]

vek88 в сообщении #374785 писал(а):

2. Вы пишете "Это интересный вариант". Вариант чего? ИМХО это не вариант чего-то, а свойство К-систем по определению!

Я тоже могу сказать, арифметика непротиворечива по определению, или ZFC непротиворечива по определению. Ничего не имею против, К-система не противоречива по определению.

vek88 в сообщении #374785 писал(а):

3. В полной К-системе представимы все арифметические множества, в частности, дополнение любого РП множества является полным К-множеством.

Эту теорему я видел.

vek88 в сообщении #374785 писал(а):

Следовательно, проблема распознавания эквивалентности двух РП множеств (или финитных формальных теорий) разрешима в полных К-системах.

Это я уже читал.

vek88 в сообщении #374785 писал(а):

А как трактовать противоречивую аксиоматическую теорию, представленную в К-системе? Дык это Ваша селедка - как хотите трактуйте - К-система здесь нам не указ. Она лишь позволяет Вам воплотить в жизнь любую Вашу трактовку противоречивой формальной системы.

Ок. Вопрос эквивалентности теорий $a \land \neg a$ и $a \leftrightarrow \neg a$ разрешим в К-системах. В одной эквивалентны, в другой нет.

vek88 в сообщении #374785 писал(а):

А вот это: "$\ominus a, \ominus \neg a$ ложно" - вы пишете некорректно - таких слов в К-системе нет. Знак $\ominus$ - особый и в словах не используется.

Разумеется, я имел в виду посылки, не указав следствия. Без знака одни следствия, со знаками - другие.
Например,
$\frac{a}{Aa}, \frac {\neg a}{aA}, \frac {\ominus(a)}{Ba}, \frac{\ominus(\neg a)}{aC}$

-- Вс ноя 14, 2010 12:39:14 --

Стр.121

Обратите внимание, особая аксиома – это аксиома, где вывод НЕТ в ЗАКЛЮЧЕНИИ, а не в посылках.
С учетом

особая аксиома имеет запись $\ominus a$
В итоге:

прямо сказано, что это упрощение К-системы, которого добились именно этим способом - избавились от вывода $a \rightarrow \text {НЕТ}$ в заключении, пометкой посылок, чтобы не заморачиваться с множеством таких выводов, определением приоритета "правило-исключение".
Т.е. в общем случае в К-системе по определению существует множество выводов $a \rightarrow \text {НЕТ}$, а вовсе не единственная аксиома $\ominus a$.
Построенное исчисление не более чем упрощенный вариант К-систем, небольшой подкласс.

[vek88]

man

Вы молодец - быстро вникаете - и уже ИМХО лучше меня разобрались во всей этой кухне.

Рекомендую также посмотреть логику К-систем в этой теме выше - см. post291626.html#p291626

Желаю успехов,
vek88

[vek88]

vek88 в сообщении #294896 писал(а):

Теорема 2. Пусть $A$ формула языка $A.$ $A$ является (классической) тавтологией iff формула $\neg \sim A$ истинна (в нашей логике).

Тут у меня опечатка. Надо

Теорема 2. Пусть $A$ формула языка $L.$ $A$ является (классической) тавтологией iff формула $\neg \sim A$ истинна (в нашей логике).

[DDuMoH]

vek88 в сообщении #277216 писал(а):

Lyosha в сообщении #277207 писал(а):

А у определения, как мне представляется, другая функция: короткое наименованее длинно описываемой ситуации(объекта).

Рад, что меня не втянули в какой-нибудь формализм. А если неформально, так ведь мы с Вами об одном и том же. Ведь если отвлечься от различных формализмов, определение содержит две части: (1) описание ситуации (объекта) и (2) и некоторую вновь определяемую ситуацию (свойство, объект, множество). Другими словами, посылки и следствие - если выполнены (истинны) посылки, то выполнено (истинно) и следствие (имеет место определяемая ситуация, некий элемент принадлежит определяемому множеству и т.д.).

Пример 1. Я определяю множество $A$ определением: $A \in A$ если $A \notin A$. Но оно не определяет множества, поскольку я не могу приписать значения истина/ложь выражению $A \in A$.

Пример 2. Предположим, что каким-то образом я уже определил некие множества (знак $R$ в этих определениях не использовался). И с этими множествами у меня все было в порядке в том смысле, что каждое высказывание об этих множествах было истинно или ложно. А потом пришел уважаемый Бертран Рассел и придумал себе трудность, т.е. определил еще одно множество $R$ определением: $x \in R$ если $x \notin R$. Но оно не определяет множества, поскольку мы не можем приписать значения истина/ложь выражению $R \in R$.

Таким образом, господа!
(1) Или уходите из классической логики, допустив неразрешимые утверждения, следовательно отказавшись от теории множеств в классическом понимании. С абстрактной точки зрения такая теория множеств имеет право на существование. Однако не думаю, что она интересна математикам. Хотя впрочем, кто ж это знает?
(2) Или пусть все будет как было в старой наивной теории множеств ... , но ограничьте себя корректными определениями вводимых Вами множеств (или полными в смысле либо ложь, либо истина и третьего не дано).

Кстати, наличие парадокса в некоторой системе определений, означает некорректность этой системы определений.

Большое заблуждение людей состояло в том, что здесь пытались и пытаются увидеть что-то другое, страшное и серьезное.

С уважением,
vek88

Ну начнем с того, что все описанное выше называется неполнотой аксиоматики. Слово некорректность использовать некорректно, мы можем говорить либо о противоречивости либо о неполноте.
Так, например, если мы введем логическую функцию от утверждения: существует множество мощности большей алеф-нуль и меньшей континуум, так она нам не вернет ни правды ни лжи. Дело в том что еще в 1963 году П.Коэн показал непротиворечивость как существования такого множества, так и отрицания его существования в принятой аксиоматике. И было бы все гладко если бы эта неполнота была бы устранима добавлением одной двух дополнительных аксиом разрешающих такую неточность(математика, вобще говоря, считается точной наукой и на любой вопрос должна давать точный ответ), но проблема заключается в том, что бесконечно добавляя аксиомы мы будем бесконечно приходить к различного рода неточностям.
Для справки поясню, что не существует методов проверки аксиоматики на абсолютную непротиворечивость либо неполноту. Существует лишь условная проверка аксиоматик на других аксиоматических моделях построенных ранее(в таком случае говорят, что данная аксиоматика непротиворечива и полна, настолько насколько полна и непротиворечива ее модель(излюбленный пример условная проверка аксиоматики Лобачевского на геометрических моделях Кэли-Клейна и Пуанкаре, соответственно утверждая непротиворечивость аксиоматики Лобачевского на данных моделях, говорят что его аксиоматика непротиворечива настолько, насколько непротиворечива геометрия, далее можно проверить геометрию на других моделях и так далее)).
Проверяя новые модели аксиоматики на старых, мы неизбежно приходим к проверке на самой первой модели - арифметике.
Вроде бы арифметика не дает сбоев уже несколько тысяч лет(только этот факт является весомым аргументом использования арифметики, так как саму арифметику уже невозможно проверить ни на каких моделях), однако доказанным фактом является то, что она неполна.
В ней также можно вывести формулы, существование и отрицание существования которых не будет противоречить аксиоматике арифметики, и также добавление данных формул в качестве аксиом(мы будем получать новые арифметики, скажем в одной арифметике существует формула Z, в другой существует ее отрицание) будет бесконечно приводить все к новым противоречиво-непротиворечивым формулам. Соответственно, вся математика как минимум неполна настолько, насколько неполна арифметика.
Разрешением данного вопроса будет являться создание абсолютного метода проверки аксиоматики средствами самой аксиоматики(возможность создания такого метода отрицается математиками), либо усовершенствование или переработка аксиоматического метода в целом, который остается неизменным практически со времен зарождения науки.

[vek88]

DDuMoH в сообщении #379035 писал(а):

Вроде бы арифметика не дает сбоев уже несколько тысяч лет(только этот факт является весомым аргументом использования арифметики, так как саму арифметику уже невозможно проверить ни на каких моделях), однако доказанным фактом является то, что она неполна.
В ней также можно вывести формулы, существование и отрицание существования которых не будет противоречить аксиоматике арифметики, и также добавление данных формул в качестве аксиом(мы будем получать новые арифметики, скажем в одной арифметике существует формула Z, в другой существует ее отрицание) будет бесконечно приводить все к новым противоречиво-непротиворечивым формулам. Соответственно, вся математика как минимум неполна настолько, насколько неполна арифметика.
Разрешением данного вопроса будет являться создание абсолютного метода проверки аксиоматики средствами самой аксиоматики(возможность создания такого метода отрицается математиками), либо усовершенствование или переработка аксиоматического метода в целом, который остается неизменным практически со времен зарождения науки.

ИМХО мы говорим о разных вещах. Ведь термин полнота используется в разных смыслах. Я говорил о полноте в очень скромном смысле, а именно, работая в классе теорий с трехзначной логикой Клини, я называл теорию полной, если она "умещалась" в двухзначную (классическую) логику.

При этом я использовал нефинитную формальную систему - К-систему. См. пост post284210.html#p284210 и далее. В К-системе, в частности, имеет место полнота арифметики "в смысле теоремы Гёделя о неполноте арифметики".

Интересно, что при таком подходе парадоксы типа Рассела никакой катастрофы не означают - они лишь "выводят" в трехзначную логику.