Логическая теорема?

[Qlin]

Имеется такая теорема: в полугруппах произведение не зависит от способа расстановки скобок. Относится ли эта теорема к теории полугрупп?

Если да, то непонятно, как записать в языке теории полугрупп способ расстановки скобок, и почему классическое доказательство этой теоремы использует схему аксиом индукции. Разве в аксиоматике теории полугрупп присутствует схема аксиом индукции?

[mihaild]

Нет, не относится.
Можно считать, что эта теорема утверждает "для любых двух произведения $A$ и $B$, отличающихся только расстановкой скобок, "$A = B$" - теорема теории полугрупп".

[george66]

Если в аксиоматике первого порядка, то нет. А если в ZF рассуждать о полугруппах, то да.

[arseniiv]

Добавлю. «Теория полугрупп» (или групп и т. п.) в обычном смысле — это область алгебры и она обычно определяет полугруппу как кортеж такой-то, что выполняется то и сё, и работает она по идее над некоторой неформальной теорией множеств или чем-то основательно эквивалентным. В хитром же смысле «[элементарная] теория полугрупп» это вот та конкретная теория первого порядка (или какая-то ещё? но в любом случае классические теории первого порядка — это большинство), в которой ничего интересного не выведешь про которую интересны уже метатеоремы, для чего её собственно и формализовали.

[Qlin]

george66, а что из себя представляет расстановка скобок с точки зрения ZF ?

[arseniiv]

Что представляет собой терм с точки зрения ZF? Расстановка скобок — вещь оттуда производная. (Ой ну и зачем прям ZF-то?)

-- Ср апр 03, 2019 08:30:12 --

Ещё можно сказать как будто претенциозно, но на самом деле и правда довольно осмысленно, что расстановка скобок не нужна, а нужен предикат «в двух термах переменные идут в одном и том же порядке». Дальше теорема выглядит например как «если в двух термах $t, u$ языка теории полугрупп переменные идут в одном и том же порядке, $\vdash t = u$» (или там «в моделях теории полугрупп $\vDash t = u$»).

-- Ср апр 03, 2019 08:38:59 --

arseniiv в сообщении #1385652 писал(а):

«в двух термах переменные идут в одном и том же порядке»

А для более сложного случая — когда у нас больше функциональных символов, чем один — что некая процедура обхода терма даст одну и ту же строку (в сущности это просто удаление скобок из записи, что особенно просто делать, если мы изначально определяем термы-формулы как строки (а не деревья); мне это не по душе, но так делают во всех вводных текстах, и грех не воспользоваться!). И это ведь действительно чертовски умно: «совпадают с точностью до скобок» это и должно значить, что мы их убрали и получили одинаковое. И ещё и очевидно. Но возможно для таких озарений нужно минимум несколько лет копаться в формальных языках, а не всем это дано.

[george66]

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

[svv]

Если ( сопоставить $+1$, а ) сопоставить $-1$, то сумма в конце должна быть $0$ и по дороге нигде не стать отрицательной. С «содержимым», конечно, сложнее.

[Qlin]

arseniiv в сообщении #1385652 писал(а):

Что представляет собой терм с точки зрения ZF?

Терм с точки зрения ZF представляет собой объект невыясненной структуры, природы и назначения. Проще говоря, в ZF не может быть никаких термов. Если сомневаетесь, возьмите какой-нибудь терм и задайте любой вопрос, который обычно задают про объекты теории ZF. Например, какие у него (у этого терма) имеются подмножества?

[mihaild]

В $ZF$ можно закодировать термы множествами. Например договориться что $\varnothing$ будет означать символ $($, $\{\varnothing\}$ - символ $)$, $\mathbb{R}$ - букву $a$, $\omega$ - букву $b$. Тогда строки в алфавите $(, ), a, b$ можно считать функциями из начального отрезка $\mathbb{N}$ в $\{\varnothing, \{\varnothing\}, \mathbb R, \omega\}$. И дальше уже можно написать в сигнатуре $ZF$ формулу с одной свободной переменной, означающую "$x$ кодирует корректную в смысле расстановки скобок последовательность".

[george66]

Терм - это то, что можно построить из переменных и констант с помощью умножения. Представлять его естественно в виде дерева с двоичным ветвлением. Например, терм $x(yz)$ есть дерево, которое ветвится первый раз на $x$ и $yz$, а потом вторая ветвь ветвится на $y$ и $z$. Если стереть скобки, получается строка $xyz$. Теорема утверждает, что если два дерева дают одинаковую строку, то они равны.

[arseniiv]

george66 в сообщении #1385711 писал(а):

Кстати, не так просто определить, что такое "правильная расстановка скобок" и почему так можно $(())$, а так нельзя $)()($

Да, вот потому лишне отдельно говорить о расстановках скобок: мы два раза сделаем одну и ту же работу (определим сначала правильные термы, потом правильные расстановки — хотя те из них, которые встретятся нам в термах, можно получить, выкидывая всё кроме скобок из этих как раз термов).

Qlin в сообщении #1385729 писал(а):

Терм с точки зрения ZF представляет собой объект невыясненной структуры, природы и назначения. Проще говоря, в ZF не может быть никаких термов. Если сомневаетесь, возьмите какой-нибудь терм и задайте любой вопрос, который обычно задают про объекты теории ZF. Например, какие у него (у этого терма) имеются подмножества?

(В дополнение к тому, что уже и так ответили.) Если рассуждать в таком ключе, вы выкинете из ZF пары, натуральные числа и прочие штуки, делающие её полезной как основание математики, а раз вы ввели её в разговор как основание, это значит, что мысль ушла куда-то не туда.

То, что нет смысла спрашивать об объектах вида А некоторые вещи, которые можно спрашивать об объектах вида Б, не означает, что нельзя кодировать первые вторыми.