Линейность порядка

[eg__13]

Задача:
Пусть $\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$.
Хотя, скорее всего, я чего-то не понимаю

[arseniiv]

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

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

[eg__13]

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

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

[arseniiv]

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

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

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

[ewert]

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

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

??