2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Упорядоченные множества
Сообщение26.01.2015, 22:25 
Построить линейный порядок на $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)$

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

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

 
 
 
 Re: Упорядоченные множества
Сообщение26.01.2015, 22:33 
Аватара пользователя
kojirh в сообщении #968880 писал(а):
Второе задание: Пусть множества A и B – частично упорядочены. Доказать что A×B тоже можно частично упорядочить.

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

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

 
 
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 02:38 
Аватара пользователя
kojirh в сообщении #968880 писал(а):
Будем считать что $(x,y) \leqslant  (z,t)$, если $y \leqslant t$ и если $y=t$,то $ \leqslant $.
???

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

 
 
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 03:05 
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$ должны были стоять переменные, но не проставлены. Видимо, задумывался лексикографический порядок?


Да, вы правы)

 
 
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 03:15 
Лексикографический порядок действительно линейный, если строится из линейных. Только вы не стесняйтесь, докажите. :-) С частичным же попытались.

kojirh в сообщении #968880 писал(а):
Может надо рефлексивность, антисимметричность и транзитивность доказать?
Да-да, конечно! И ещё то, что останется, для того чтобы порядок стал линейным.

 
 
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 13:47 
kojirh в сообщении #968880 писал(а):
Так как это множество является декартовым квадратом множества натуральных чисел, которое само по себе является линейным порядком, то в нём можно ввести такое отношение.
Я никак не могу понять, достаточно ли этого

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

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

 
 
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 16:28 
Биекцию на $\mathbb N$ ведь не обязательно — линейно упорядоченное множество не обязано быть вполне упорядоченным.

 
 
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 16:31 
arseniiv в сообщении #969279 писал(а):
Биекцию на $\mathbb N$ ведь не обязательно

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

 
 
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 16:37 
Наверно. Но откажется ли kojirh от лексикографического порядка? :-)

 
 
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 16:41 
А зачем ему отказываться? И, кстати, это ещё зачем:

arseniiv в сообщении #969015 писал(а):
И ещё то, что останется, для того чтобы порядок стал линейным.

?

 
 
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 16:56 
ewert в сообщении #969290 писал(а):
А зачем ему отказываться?
Он подтвердил, что в первом задании хотел построить лексикографический порядок и просто недонабрал формулу.

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

 
 
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 17:08 
arseniiv в сообщении #969302 писал(а):
Ну, иначе же докажется только то, что это частичный порядок.

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

 
 
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 17:33 
Лексикографический или биективный-на-$\mathbb N$?

 
 
 [ Сообщений: 20 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group