2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Конечно аксиоматизируемый класс, теория моделей.
Сообщение25.12.2016, 17:14 


25/12/16
22
Пусть $\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)$

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

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

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

 Профиль  
                  
 
 Re: Конечно аксиоматизируемый класс, теория моделей.
Сообщение25.12.2016, 17:28 
Заслуженный участник
Аватара пользователя


16/07/14
8353
Цюрих
Да, так. Только $f$ должно быть предикатным, а не функциональным символом.

 Профиль  
                  
 
 Re: Конечно аксиоматизируемый класс, теория моделей.
Сообщение25.12.2016, 17:32 


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

 Профиль  
                  
 
 Re: Конечно аксиоматизируемый класс, теория моделей.
Сообщение25.12.2016, 18:27 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Конечно аксиоматизируемый класс, теория моделей.
Сообщение26.12.2016, 00:09 


11/08/16

312

(Оффтоп)

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

 Профиль  
                  
 
 Re: Конечно аксиоматизируемый класс, теория моделей.
Сообщение26.12.2016, 00:34 
Заслуженный участник
Аватара пользователя


16/07/14
8353
Цюрих
knizhnik в сообщении #1180060 писал(а):
А что за модель сигнатуры?
Модель сигнатуры - то же, что интерпретация этой сигнатуры (эквивалентно модели пустой теории в этой сигнатуре).

 Профиль  
                  
 
 Re: Конечно аксиоматизируемый класс, теория моделей.
Сообщение26.12.2016, 11:21 


25/12/16
22
А вот, например, решение для случая когда $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$ бесконечно и класс является конечно аксиоматизируемым.

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

 Профиль  
                  
 
 Re: Конечно аксиоматизируемый класс, теория моделей.
Сообщение26.12.2016, 13:43 


11/08/16

312
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$
Это конечный случай.

 Профиль  
                  
 
 Re: Конечно аксиоматизируемый класс, теория моделей.
Сообщение26.12.2016, 19:21 


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

 Профиль  
                  
 
 Re: Конечно аксиоматизируемый класс, теория моделей.
Сообщение26.12.2016, 19:37 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Конечно аксиоматизируемый класс, теория моделей.
Сообщение22.01.2017, 19:25 


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

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

 Профиль  
                  
 
 Re: Конечно аксиоматизируемый класс, теория моделей.
Сообщение22.01.2017, 19:42 


11/08/16

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

 Профиль  
                  
 
 Re: Конечно аксиоматизируемый класс, теория моделей.
Сообщение22.01.2017, 19:49 


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

-- 22.01.2017, 22:54 --

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

 Профиль  
                  
 
 Re: Конечно аксиоматизируемый класс, теория моделей.
Сообщение22.01.2017, 20:01 


11/08/16

312
Iv_Vol в сообщении #1186634 писал(а):
Я и не добавляю символ $\leqslant$ в сигнатуру. Просто показываю, что таким образом можно установить порядок на множестве.
Это как бы естественный порядок, он существует и без символа $\leqslant$, если я все правильно понимаю.
Равенство на множестве всегда существует и естественно. Но никакие бесконечные системы оно не определяет.
Iv_Vol в сообщении #1186634 писал(а):
Материал взят вот отсюда:
Не знаю. У меня не открывается этот материал.
Iv_Vol в сообщении #1186634 писал(а):
Получается, что понятие $\leqslant$ задается через $sup(x,y)$, а это, в свою очередь, задается $ sup(a,b)=afb  $, а f в нашей сигнатуре есть.
К сожалению, $f$ есть не только в вашей сигнатуре, но и в аксиоме коммутативности, что немедленно делает отношение $\leqslant$ равенством.

 Профиль  
                  
 
 Re: Конечно аксиоматизируемый класс, теория моделей.
Сообщение22.01.2017, 21:51 
Заслуженный участник


27/04/09
28128
knizhnik в сообщении #1186632 писал(а):
$f$, как вы ее определили, это коммутативная операция, поэтому
$a \leqslant b \leftrightarrow b=afb=bfa=a$.
Можно вывести это подробнее?

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

В общем, это, конечно, риторический вопрос, потому что
knizhnik в сообщении #1186637 писал(а):
что немедленно делает отношение $\leqslant$ равенством
Неа.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу 1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group