2014 dxdy logo

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

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


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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Линейность порядка
Сообщение22.06.2014, 01:22 
Аватара пользователя


03/01/12
32
Задача:
Пусть $\varphi :A\times A\rightarrow A$ и для всех $x, y , z\in A$, $\varphi(x,y)=\varphi(y,x)$, $\varphi(x, (\varphi(y,z))=\varphi(\varphi(x,y),z)$, $\varphi(x,x)=x$. Докажите, что отношение $x\leq y \Leftrightarrow \varphi(x,y)=x$ есть отношение линейного порядка на $A$.

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

  • Рефлексивность.
    Так как $\forall x: \varphi(x, x)=x$, то $\forall x: x\leq x$.
  • Антисимметричность.
    Если $x\leq y$, то $\varphi(x, y)=x$. Если $y\leq x$, то $\varphi(y, x)=y$. Так как $\varphi(x, y)=\varphi(y,x)$, то $x=\varphi(x, y)=\varphi(y,x)=y.$ Значит, $x=y$, и отношение антисимметрично.
  • Транзитивность.
    Пусть $x\leq y$ и $y\leq z$, докажем, что $x\leq z$.
    Так как $x\leq y$, то $\varphi(x, y)=x$; $y\leq z$, то $\varphi(y, z)=y.$
    $\varphi(x, z)=\varphi(\varphi(x, y),z)=\varphi(x, \varphi(y, z))=\varphi(x, y)=x.$ Значит, $x\leq z$, и отношение транзитивно.

Все просто. Но вот как быть с доказательством линейности - непонятно. Мне кажется, что из условия задачи линейность никак не следует. Можно привести вот такой вот пример.
Пусть $A=\mathbb{N}$ и $\varphi (x, y)=\operatorname{\text{НОД}}(x, y)$, тогда условия задачи будут выглядеть следующим образом:
$\operatorname{\text{НОД}}(x, x)=x$;
$\operatorname{\text{НОД}}(x, y)=\operatorname{\text{НОД}}(y, x)$;
$\operatorname{\text{НОД}}(\operatorname{\text{НОД}}(x, y), z)=\operatorname{\text{НОД}}(x, \operatorname{\text{НОД}}(y, z))$.
А отношение $x\leq y$ заменим на отношение $x$ делит $y$, или, если коротоко, $x|y$.
По определению, наше бинарное отношение $|$ будет являться отношением линейного порядка, если $\forall x, y\in \mathbb{N}$ либо $x|y$ либо $y|x$. Но очевидно, что отношение $|$ выполняется не для всех $x$ и $y$.
Хотя, скорее всего, я чего-то не понимаю :-(

 Профиль  
                  
 
 Re: Линейность порядка
Сообщение22.06.2014, 01:43 
Заслуженный участник


27/04/09
28128
Видимо, там было не линейного. Линейность — это плюс ещё $\forall x,y\in A : x\leqslant y \vee y\leqslant x$, т. е. сравнимость любой пары элементов. У вас доказана просто «порядочность» отношения $\leqslant$, и она должна бы и требоваться. И пример с НОДом как раз в точку.

Если только я чего-то не упустил.

 Профиль  
                  
 
 Re: Линейность порядка
Сообщение22.06.2014, 02:13 
Аватара пользователя


03/01/12
32
arseniiv, я тоже к этому начинаю склоняться, потому как встречал около месяца назад эту задачу то ли в каком-то задачнике, то ли где-то в интернете, и она была слово в слово как у меня, за небольшим исключением: там не было слова "линейного". Было просто написано "Докажите, что отношение $x\leq y \Leftrightarrow \varphi(x,y)=x$ есть отношение порядка на $A$."

Обращался с этим вопросом к преподавателю. Он объяснил, что нужно доказать линейность не на всем множестве $A$, а только для множества чисел, для которых выполняется равенство $\varphi(x, y)=x$. Возможно, я неправильно запомнил его слова, но что-то тут явно не так.

 Профиль  
                  
 
 Re: Линейность порядка
Сообщение22.06.2014, 23:25 
Заслуженный участник


27/04/09
28128
Действительно. Потому что в зависимости от кванторов, приделанных к этой формуле, или понимания какой-то из этих букв как константы, получатся разные множества или вообще не обязательно единственные и существующие.

Случай с НОД и делимостью иллюстрирует это: мы можем ограничить $\mid$ на, скажем, $\{1,3,9,27,\ldots\}$, а можем на $\{1,2,4,8,16,\ldots\}$, у $(\mathbb Z_{>0},\mid)$ много линейно упорядоченных подмножеств, но ни одного включающего все остальные. (Какие-нибудь другие способы выделения вряд ли более осмысленны, думаю.)

Приведите преподавателю пример с НОД — думаю, он поймёт, что не так с пониманием его формулировки или правильностью задачи. :lol:

 Профиль  
                  
 
 Re: Линейность порядка
Сообщение22.06.2014, 23:39 
Заслуженный участник


11/05/08
32166
eg__13, чем Вас не устроила Ваша же предыдущая тема:

http://dxdy.ru/post864825.html#p864825

??

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

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



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

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


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

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