Альтернативное определение сигнатуры

[dydx]

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

Определение. Сигнатура - это тройка $(M,\rho,=)$, где $M$ - множество функциональных символов, $\rho$ - функция, которая каждому функциональному символу сопоставляет его арность (начиная с нуля), $=$ - символ равенства. Функциональных символы нулевой арности будем называть константами.

Тогда, например, исчисление предикатов можно так построить. Берем сигнатуру, символы переменных, служебные символы. Говорим, что должны быть символы $T$ и $F$ среди констант (для обозначения истины и лжи). Что должны быть символы $\lor,\land,\to,\exists,\forall$ среди функциональных символов арности 2 и функциональный символ $\neg$ арности 1. Дальше, говорим, что терм - это либо символ переменной, либо запись вида $f(t_1,\cdots,t_n)$, где $f$ - функциональный символ, а $t_1,\cdots,t_n$ - термы, и что формула - это $t_1=t_2$, где $t_1,t_2$ - термы.

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

$$A\to(B\to A=T)=T$$

$$\forall x (A \to A[t/x]=T)=T$$

$$\frac{A=T, A \to B=T}{B=T}$$

где $A$, $B$ - формулы.

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

-- 11.11.2012, 01:07 --

Просьба. Если кто знает литературу по математической логике, где используется подобный подход, пожалуйста, сообщите.

[dydx]

dydx в сообщении #642759 писал(а):

Определение. Сигнатура - это тройка $(M,\rho,=)$, где $M$ - множество функциональных символов, $\rho$ - функция, которая каждому функциональному символу сопоставляет его арность (начиная с нуля), $=$ - символ равенства. Функциональных символы нулевой арности будем называть константами.

Тогда, например, исчисление предикатов можно так построить. Берем сигнатуру, символы переменных, служебные символы. Говорим, что должны быть символы $T$ и $F$ среди констант (для обозначения истины и лжи). Что должны быть символы $\lor,\land,\to,\exists,\forall$ среди функциональных символов арности 2 и функциональный символ $\neg$ арности 1. Дальше, говорим, что терм - это либо символ переменной, либо запись вида $f(t_1,\cdots,t_n)$, где $f$ - функциональный символ, а $t_1,\cdots,t_n$ - термы, и что формула - это $t_1=t_2$, где $t_1,t_2$ - термы.

Точнее не так. Сигнатура - это двойка $(M,\rho)$. А $=$ - это просто один из функциональных символов. Таким образом, формула - это частный случай терма.

[migmit]

Вы хотите убрать одну сущность, добавив вместо неё другую. Зачем?

[dydx]

migmit в сообщении #642785 писал(а):

Вы хотите убрать одну сущность, добавив вместо неё другую.

Я хочу убрать одну сущность, убрав одну сущность. Какую сущность я, по-вашему, добавил?

-- 11.11.2012, 03:37 --

dydx в сообщении #642759 писал(а):

Почему бы все не заменить функциями и оставить только равенство?

Последние четыре слова лишние в связи с post642782.html#p642782

[dydx]

Кстати, я убрал не одну сущность, а больше. Прозициональные связки и кванторы тоже свелись к функциональными символами.

[migmit]

dydx в сообщении #642786 писал(а):

migmit в сообщении #642785 писал(а):

Вы хотите убрать одну сущность, добавив вместо неё другую.

Я хочу убрать одну сущность, убрав одну сущность. Какую сущность я, по-вашему, добавил?

Ну вот же ж:

dydx в сообщении #642759 писал(а):

Говорим, что должны быть символы $T$ и $F$ среди констант (для обозначения истины и лжи). Что должны быть символы $\lor,\land,\to,\exists,\forall$ среди функциональных символов арности 2 и функциональный символ $\neg$ арности 1.

Вы убрали предикаты, и добавили восемь штук новых значков. Смысл?

[dydx]

migmit в сообщении #643333 писал(а):

Вы убрали предикаты, и добавили восемь штук новых значков.

Они у меня все функциональные символы. А в классическом подходе - это отдельные сущности.

[arseniiv]

Теперь определение модели соответствующее надо.

[bot]

dydx в сообщении #642786 писал(а):

Я хочу убрать одну сущность

Для этого придётся расширить другую. Функциональные символы - это ведь всё-таки не функции, а операции. Ваш подход - это многоосновные алг. системы. В них предикаты являются операциями. Обратный поход - операцию всегда можно заменить на предикат $P_f(x_1, x_2, \ldots, \, x_n, y)\Leftrightarrow f(x_1, x_2, \ldots, \, x_n)=y$. Это обычный приём в теории моделей.
Каждый из подходов чреват своими особенностями и не всегда удобен.
Возьмём простенький случай. Как известно, группу можно определить в терминах лишь умножения, а можно в терминах двух операций - умножения и обращения.
При втором подходе класс групп является многообразием, а при первом нет.

[dydx]

bot в сообщении #643393 писал(а):

Функциональные символы - это ведь всё-таки не функции, а операции.

Функциональные символы - это символы. Другое дело, что они в модели первого порядка интерпретируются в операции. Это да. И странно, что Вы так говорите, будто операции - это не функции. Хотя, я думаю, что Вы не это имели в виду, а то, что не всякая функция является операцией (когда, например, количество аргументов счетно).

bot в сообщении #643393 писал(а):

Ваш подход - это многоосновные алг. системы. В них предикаты являются операциями.

Спасибо за информацию.

bot в сообщении #643393 писал(а):

Обратный поход - операцию всегда можно заменить на предикат $P_f(x_1, x_2, \ldots, \, x_n, y)\Leftrightarrow f(x_1, x_2, \ldots, \, x_n)=y$.

При таком подходе возникает проблема с симметричностью равенства, например. Так что, упрощение упрощению рознь.

-- 12.11.2012, 10:27 --

http://www.univer.omsk.su/departs/compsci/kursi/disc/algsysts.htm писал(а):

Часто бывает неудобно использовать понятие алгебраической системы с однородным носителем и рассматривают многоосновные алгебраические системы <A1,...,An;WF;WR>, где A1,...,An – непустые непересекающиеся множества, WF – множество операций, определёных на некоторых декартовых произведениях множеств A1,...,An, WR – множество отношений между элементами некоторых из множеств A1,...,An.

Что-то я здесь не вижу моего подхода.

[bot]

dydx в сообщении #643423 писал(а):

И странно, что Вы так говорите, будто операции - это не функции.

Да, функции, но не просто функции, а операции, то есть значения обязаны лежать в основном множестве.

dydx в сообщении #643423 писал(а):

Что-то я здесь не вижу моего подхода.

А как Вы будете превращать предикат в функцию? Множество значений предиката - это $\text{truth (0)}$ и $\text{false (1)}$, в основном можестве системы их нет.
Можно, конечно, присоединить их к основному множеству, но тогда получится ещё один подход - операции станут частичными (не определены, если в n-ке присутствует хотя бы один из этих присоединённых символов) и получается система с частичными операциями, что тоже встречается в литературе.
Короче, каждый из подходов имеет право на существование, но ни в коем разе не может претендовать на универсальность при рассмотрения разных вопросов.

[dydx]

bot в сообщении #643437 писал(а):

Множество значений предиката - это $\text{truth (0)}$ и $\text{false (1)}$, в основном можестве системы их нет.

Как это нет? Если я правильно понял, то основным множеством Вы называете несущее. $\text{truth}$ и $\text{false}$ - это константы, т.е. функциональные символы нулевой арности. В модели первого порядка у каждого функционального символа арности $n$ есть интерпретация в операцию $D^n \to D$, где $D$ - несущее множество. Поэтому, если у функционального символа нулевая арность, то он просто интерпретируется в элемент из $D$.

[bot]

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

[Someone]

dydx в сообщении #643455 писал(а):

Как это нет? Если я правильно понял, то основным множеством Вы называете несущее.

Например, в арифметике основное множество - это множество натуральных чисел. И где там "true" и "false"?

А также мне очень интересно, какими функциями Вы заменяете кванторы "$\forall$" и "$\exists$".

[dydx]

Someone в сообщ[quote="Someone в [url=http://dxdy.ru/post643487.html#p643487]сообщении #643487 писал(а):

И где там "true" и "false"?

Ну, допустим, единица - это "true", а ноль - это "false".

Someone в сообщении #643487 писал(а):

А также мне очень интересно, какими функциями Вы заменяете кванторы "$\forall$" и "$\exists$".

$\forall$ выражается через $\exists$. $\forall$ интерпретируется, как бесконечная конъюнкция.