2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
01/01/18 20:50 UTC: Перешли на HTTPS в тестовом режиме. О проблемах пишите в ЛС cepesh.



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


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

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

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Упорядоченные множества
Сообщение26.01.2015, 22:25 


26/01/15
10
Построить линейный порядок на $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 
Заслуженный участник
Аватара пользователя


18/01/13
11482
Казань
kojirh в сообщении #968880 писал(а):
Второе задание: Пусть множества A и B – частично упорядочены. Доказать что A×B тоже можно частично упорядочить.

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

 Профиль  
                  
 
 Re: Упорядоченные множества
Сообщение26.01.2015, 22:35 


19/05/10

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

 Профиль  
                  
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 02:38 
Заслуженный участник
Аватара пользователя


23/07/05
15154
Новомосковск
kojirh в сообщении #968880 писал(а):
Будем считать что $(x,y) \leqslant  (z,t)$, если $y \leqslant t$ и если $y=t$,то $ \leqslant $.
???

 Профиль  
                  
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 03:05 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 03:05 


26/01/15
10
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 
Заслуженный участник
Аватара пользователя


27/04/09
21608
Уфа
Лексикографический порядок действительно линейный, если строится из линейных. Только вы не стесняйтесь, докажите. :-) С частичным же попытались.

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

 Профиль  
                  
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 13:47 
Заслуженный участник


11/05/08
31333
kojirh в сообщении #968880 писал(а):
Так как это множество является декартовым квадратом множества натуральных чисел, которое само по себе является линейным порядком, то в нём можно ввести такое отношение.
Я никак не могу понять, достаточно ли этого

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

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

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


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

 Профиль  
                  
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 16:31 
Заслуженный участник


11/05/08
31333
arseniiv в сообщении #969279 писал(а):
Биекцию на $\mathbb N$ ведь не обязательно

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

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


27/04/09
21608
Уфа
Наверно. Но откажется ли kojirh от лексикографического порядка? :-)

 Профиль  
                  
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 16:41 
Заслуженный участник


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

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

?

 Профиль  
                  
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 16:56 
Заслуженный участник
Аватара пользователя


27/04/09
21608
Уфа
ewert в сообщении #969290 писал(а):
А зачем ему отказываться?
Он подтвердил, что в первом задании хотел построить лексикографический порядок и просто недонабрал формулу.

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

 Профиль  
                  
 
 Re: Упорядоченные множества
Сообщение27.01.2015, 17:08 
Заслуженный участник


11/05/08
31333
arseniiv в сообщении #969302 писал(а):
Ну, иначе же докажется только то, что это частичный порядок.

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

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


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

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

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



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

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


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

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