Упорядоченные множества

[kojirh]

Построить линейный порядок на $N^2$.
${N^2} = \{ (x,y)|x,y \in N\}$
Чтобы построить линейный порядок на множестве надо ввести на нём отношение линейного порядка, которое обладает свойствами рефлексивности, антисимметричности и транзитивности, а также для любых пар $(x,y),(z,t) \in N^2$ должно выполняться $(x,y) \leqslant (z,t)$ или $(z,t) \leqslant (x,y)$.
Будем считать что $(x,y) \leqslant (z,t)$, если $y \leqslant t$ и если $y=t$,то $ \leqslant $.
Так как это множество является декартовым квадратом множества натуральных чисел, которое само по себе является линейным порядком, то в нём можно ввести такое отношение.
Я никак не могу понять, достаточно ли этого и вообще подойдёт ли такое решение или есть что-то лишнее? Может надо рефлексивность, антисимметричность и транзитивность доказать? Направьте на путь истинный так сказать

Второе задание: Пусть множества A и B – частично упорядочены. Доказать что A×B тоже можно частично упорядочить.
Множество может быть частично упорядоченным, если на нём можно ввести отношение частичного порядка ≤, обладающее свойствами рефлексивности, антисимметричности и транзитивности.
Для любых $(x,y),(a,b) \in A×B$: $(x,y) \leqslant (a,b)$, если одновременно $x \leqslant a$ и $y \leqslant b$

Рефлексивность: для любых $(a,b) \in A×B$: $(a,b) \leqslant (a,b)$

Антисимметричность: для любых $(x,y),(a,b) \in A×B$: если $(x,y) \leqslant (a,b)$, т.е. $x \leqslant a$ и $y \leqslant b$; и $(a,b) \leqslant (x,y)$, т.е. $a \leqslant x$ и $b \leqslant y$; т. к. $x \leqslant a$ и $a \leqslant x$, то $x=a$; т.к. $b \leqslant y$ и $y \leqslant b$, то $b=y$; значит $(a,b)=(x,y)$

Транзитивность: для любых $(x,y),(a,b),(c,d) \in AxB $ если $(x,y) \leqslant (a,b)$, т.е. $x \leqslant a$ и $y \leqslant b$ ; а также $(a,b) \leqslant (c,d)$, т.е. $a \leqslant c$ и $b \leqslant d$; то $x \leqslant a \leqslant c$ и $y \leqslant b \leqslant d$, т.е. $(x,y) \leqslant (c,d)$

Значит множество можно частично упорядочить

Тоже не уверен в правильности

[provincialka]

kojirh в сообщении #968880 писал(а):

Второе задание: Пусть множества A и B – частично упорядочены. Доказать что A×B тоже можно частично упорядочить.

Как связано второе утверждение с первым? Любое множество можно частично упорядочить. Хотя бы отношением "=". Другое дело, если бы этот новый порядок надо было как-то согласовывать с заданными на $A$ и $B$.

[mihailm]

Сойдет. Только достаточно это или недостаточно зависит еще от того, кто это будет спрашивать. Если сдавать в письменном виде, наверно лучше доказательства в первом утверждении добавить.
Замечание. Упорядочиваний в утв_1 полно, например, по сумме.

[Someone]

kojirh в сообщении #968880 писал(а):

Будем считать что $(x,y) \leqslant (z,t)$, если $y \leqslant t$ и если $y=t$,то $ \leqslant $.

???

[arseniiv]

Судя по коду формул, наверно, вокруг последнего $\leqslant$ должны были стоять переменные, но не проставлены. Видимо, задумывался лексикографический порядок?

[kojirh]

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

kojirh в сообщении #968880 писал(а):

Будем считать что $(x,y) \leqslant (z,t)$, если $y \leqslant t$ и если $y=t$,то $ \leqslant $.

???

Там в конце $x \leqslant z$, просто опечатался, что скажете насчёт самого решения?

-- 27.01.2015, 04:05 --

arseniiv в сообщении #969012 писал(а):

Судя по коду формул, наверно, вокруг последнего $\leqslant$ должны были стоять переменные, но не проставлены. Видимо, задумывался лексикографический порядок?

Да, вы правы)

[arseniiv]

Лексикографический порядок действительно линейный, если строится из линейных. Только вы не стесняйтесь, докажите. С частичным же попытались.

kojirh в сообщении #968880 писал(а):

Может надо рефлексивность, антисимметричность и транзитивность доказать?

Да-да, конечно! И ещё то, что останется, для того чтобы порядок стал линейным.

[ewert]

kojirh в сообщении #968880 писал(а):

Так как это множество является декартовым квадратом множества натуральных чисел, которое само по себе является линейным порядком, то в нём можно ввести такое отношение.
Я никак не могу понять, достаточно ли этого

Конечно, недостаточно. Было же сказано "построить" -- значит, надо именно строить. А Вы всего лишь указали на возможность построения.

Фактически надо предложить какюю-либо конкретную биекцию этого множества на $\mathbb N$.

[arseniiv]

Биекцию на $\mathbb N$ ведь не обязательно — линейно упорядоченное множество не обязано быть вполне упорядоченным.

[ewert]

arseniiv в сообщении #969279 писал(а):

Биекцию на $\mathbb N$ ведь не обязательно

Не обязательно, конечно. Но раз уж мы знаем, что оно счётно, то проще всего построить именно биекцию.

[arseniiv]

Наверно. Но откажется ли kojirh от лексикографического порядка?

[ewert]

А зачем ему отказываться? И, кстати, это ещё зачем:

arseniiv в сообщении #969015 писал(а):

И ещё то, что останется, для того чтобы порядок стал линейным.

?

[arseniiv]

ewert в сообщении #969290 писал(а):

А зачем ему отказываться?

Он подтвердил, что в первом задании хотел построить лексикографический порядок и просто недонабрал формулу.

ewert в сообщении #969290 писал(а):

И, кстати, это ещё зачем:

Ну, иначе же докажется только то, что это частичный порядок. (То, что ниже, ведь относится к другому заданию, и тот частичный порядок не является линейным в любом случае.)

[ewert]

arseniiv в сообщении #969302 писал(а):

Ну, иначе же докажется только то, что это частичный порядок.

Так он же просто по построению линеен.

[arseniiv]

Лексикографический или биективный-на-$\mathbb N$?