Конечно аксиоматизируемый класс, теория моделей.

[Iv_Vol]

Пусть $\sigma = <f>$, где $f$ - символ 2-местной функции. Нужно построить пример конечно аксиоматизируемого класса моделей сигнатуры $\sigma$, состоящего только из бесконечных систем.

Вот мой вариант решения:
Строим теорию из аксиом
$\forall a (\neg (a f a))$
$\forall a \forall b \forall c ((a f b) \wedge (b f c) \to (a f c))$
$\forall a \forall b ((a f b) \wedge (b f a) \to (a = b))$
$\forall a \exists z (z f a)$

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

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

Все ли правильно? И достаточно ли вышесказанного, для того чтобы утверждать что это к.а. класс?

[mihaild]

Да, так. Только $f$ должно быть предикатным, а не функциональным символом.

[Iv_Vol]

mihaild
А что делать в случае, если $f$ не предикат?

[mihaild]

А если $f$ - не предикатный символ (не путайте предикатные символы и предикаты), то вы вообще не можете собрать ни одной формулы, т.к. у вас нет предикатных символов.

[knizhnik]

(Оффтоп)

Модель теории - понятно. А что за модель сигнатуры?

[mihaild]

knizhnik в сообщении #1180060 писал(а):

А что за модель сигнатуры?

Модель сигнатуры - то же, что интерпретация этой сигнатуры (эквивалентно модели пустой теории в этой сигнатуре).

[Iv_Vol]

А вот, например, решение для случая когда $f$ - функциональный символ.
запишем теорию состоящую из одной аксиомы:
$\forall x \forall y ((\neg((x f y) = x)) \wedge (\neg (( x f y) = y))) $

Это получается что-то вроде доказательства того, что все системы в классе будут бесконечны.
Допустим, множество $ M$ имеет мощность $\left\lvert M \right\rvert$, те оно конечно.
Тогда на месте первого элемента в двухместной функции может быть $\left\lvert M \right\rvert$ вариантов элементов. Аналогично для второго. Итого получается $\left\lvert M \right\rvert ^2 $ различных(!) вариантов результата функции
Но это противоречит тому, что мощность множества всего $\left\lvert M \right\rvert$
Следовательно, множество $ M$ бесконечно и класс является конечно аксиоматизируемым.

Поправьте меня, пожалуйста, если я не прав.

[knizhnik]

Iv_Vol в сообщении #1179902 писал(а):

Пусть $\sigma = <f>$

Вы не можете этого написать, поскольку используется неупомянутый предикатный символ равенства. Этот символ предварительно придется добавить в сигнатуру.

Iv_Vol в сообщении #1180178 писал(а):

Тогда на месте первого элемента в двухместной функции может быть $\left\lvert M \right\rvert$ вариантов элементов. Аналогично для второго. Итого получается $\left\lvert M \right\rvert ^2 $ различных(!) вариантов результата функции

Нет, получается $\left\lvert M \right\rvert ^2 $ различных вариантов пар. Всевозможных значений функции $\left\lvert M \right\rvert$ штук.

Iv_Vol в сообщении #1180178 писал(а):

$\forall x \forall y ((\neg((x f y) = x)) \wedge (\neg (( x f y) = y))) $

Пусть $M=\{1,2,3\}$ и:
$(2 f 3) = (3 f 2) = (3 f 3) = 1$
$(1 f 3) = (3 f 1) = (1 f 1) = 2$
$(1 f 2) = (2 f 1) = (2 f 2) = 3$
Это конечный случай.

[Iv_Vol]

Положим, знак равенства использовать можно (по крайней мере, у нас на семинарах разрешалось :) )
изменим аксиому:
$ \forall x \forall y (\neg((x f y) = x)) \wedge (\neg ((x f y) = y)) \wedge (\neg (x = y)))$
Получается что пример с $M = \{1,2,3\}$, который предложил knizhnik не работает.
Вроде как тогда класс содержит лишь бесконечные системы.

[Xaositect]

Тут вообще моделей нет, из этой аксиомы следует очевидно ложное $\forall x \forall y\, x \neq y$.

[Iv_Vol]

Как вариант, эту задачу можно попробовать решить через верхнюю полурешетку. Т.е. задаем аксиомы:
$af(bfc)=(afb)fc$,
$afb=bfa$,
$afa=a$.
Тогда на множестве можно задать отношение порядка:
$a \leqslant b \Leftrightarrow afb=b$, где $ afb = sup(a,b)$ - точная верхняя грань. Для этой операции можно также задать коммутативность, идемпотентность и ассоциативность.

И с помощью отношения порядка уже задаем аксиомы, такие, что в классе будут содержаться только бесконечные системы, как это было в начале этой темы.

[knizhnik]

Iv_Vol в сообщении #1186630 писал(а):

$a \leqslant b $

Дело в том, что в сигнатуре у вас нет символа $\leqslant$. Если $a \leqslant b$ это просто сокращение для $afb=b$, то это просто равенство. А $f$ - никакая не точная верхняя грань. $f$, как вы ее определили, это коммутативная операция, поэтому
$a \leqslant b \leftrightarrow b=afb=bfa=a$.

[Iv_Vol]

Я и не добавляю символ $\leqslant$ в сигнатуру. Просто показываю, что таким образом можно установить порядок на множестве.
Это как бы естественный порядок, он существует и без символа $\leqslant$, если я все правильно понимаю.
Материал взят вот отсюда:
http://mathhelpplanet.com/static.php?p= ... lureshetki

-- 22.01.2017, 22:54 --

Получается, что понятие $\leqslant$ задается через $sup(x,y)$, а это, в свою очередь, задается $ sup(a,b)=afb $, а f в нашей сигнатуре есть.

[knizhnik]

Iv_Vol в сообщении #1186634 писал(а):

Я и не добавляю символ $\leqslant$ в сигнатуру. Просто показываю, что таким образом можно установить порядок на множестве.
Это как бы естественный порядок, он существует и без символа $\leqslant$, если я все правильно понимаю.

Равенство на множестве всегда существует и естественно. Но никакие бесконечные системы оно не определяет.

Iv_Vol в сообщении #1186634 писал(а):

Материал взят вот отсюда:

Не знаю. У меня не открывается этот материал.

Iv_Vol в сообщении #1186634 писал(а):

Получается, что понятие $\leqslant$ задается через $sup(x,y)$, а это, в свою очередь, задается $ sup(a,b)=afb $, а f в нашей сигнатуре есть.

К сожалению, $f$ есть не только в вашей сигнатуре, но и в аксиоме коммутативности, что немедленно делает отношение $\leqslant$ равенством.

[arseniiv]

knizhnik в сообщении #1186632 писал(а):

$f$, как вы ее определили, это коммутативная операция, поэтому
$a \leqslant b \leftrightarrow b=afb=bfa=a$.

Можно вывести это подробнее?

-- Пн янв 23, 2017 00:08:47 --

В общем, это, конечно, риторический вопрос, потому что

knizhnik в сообщении #1186637 писал(а):

что немедленно делает отношение $\leqslant$ равенством

Неа.

Идемпотентность $\sup$ даёт рефлексивность $\leqslant$, коммутативность — антисимметричность, ассоциативность — транзитивность, так что $\leqslant$ — частичный порядок. (Предлагаю knizhnik вывести эти свойства. )