10 / 10 / 1
Регистрация: 17.02.2013
Сообщений: 344
1

Мощность бинарного отношения

27.09.2014, 22:36. Показов 7735. Ответов 26
Метки нет (Все метки)

Здравствуйте. Проверьте, пожалуйста мое решение.
Задача:
Задано пять матриц: https://www.cyberforum.ru/cgi-bin/latex.cgi?{A}_{1}=\begin{pmatrix}2 & 1 \\ -3 & 2\end{pmatrix}, https://www.cyberforum.ru/cgi-bin/latex.cgi?{A}_{2}=\begin{pmatrix}0 & 2 \\ 4 & -1\end{pmatrix}, https://www.cyberforum.ru/cgi-bin/latex.cgi?{A}_{3}=\begin{pmatrix}-2 & -2 \\ 0 & 1\end{pmatrix}, https://www.cyberforum.ru/cgi-bin/latex.cgi?{A}_{4}=\begin{pmatrix}1 & 1 \\ -1 & -1\end{pmatrix}, https://www.cyberforum.ru/cgi-bin/latex.cgi?{A}_{5}=\begin{pmatrix}1 & 5 \\ 1 & 3\end{pmatrix}
На множестве M этих матриц определено бинарное отношение https://www.cyberforum.ru/cgi-bin/latex.cgi?\rho : https://www.cyberforum.ru/cgi-bin/latex.cgi?{A}_{i}\rho {A}_{j} \Leftrightarrow (определитель матрицы https://www.cyberforum.ru/cgi-bin/latex.cgi?{A}_{i} не превышает определителя матрицы https://www.cyberforum.ru/cgi-bin/latex.cgi?{A}_{j} ). Найти мощность этого бинарного отношения, определить, является ли оно рефлексивным, симметричным, антисимметричным, транзитивным, отношением эквивалентности, отношением порядка, отношением линейного порядка. Если бинарное отношение является отношением эквивалентности, указать разбиение на классы эквивалентности.

Решение:
Определители этих матриц соответственно равны: 7, -8, -2, 0, -2.
Получается, что мощность этого бинарного отношения: https://www.cyberforum.ru/cgi-bin/latex.cgi?11.
Рефлексивность присутствует: т.к. имеются пары (7,7), (-8,-8), (-2,-2), (0,0).
Симметричность отсутствует: т.к. нет элементов вида (-8,7) и (7,-8).
Антисимметричность присутствует: годится для элементов (7,7), (-8,-8), (-2,-2), (0,0).
Транзитивность присутствует: годится для элементов (7,7), (-8,-8), (-2,-2), (0,0).

Спасибо.
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
27.09.2014, 22:36
Ответы с готовыми решениями:

Найти мощность этого бинарного отношения, определить его свойства
В пространстве на прямой x=1+2t, y= -2-4t, z=3+2t,t€(-inf;+inf), заданы точки M1,M2,...,M5,...

Матрица бинарного отношения
Матрица бинарного отношения. Подскажите, как получается данная матрица и чему равна {A}^{2} здесь ?...

Пример бинарного отношения
Рефлексивность не симметричность транзитивность A={1,2} {<1,1><1,2><2,2>} Правильно ли я его...

Множество бинарного отношения
Матрица бинарного отношения P\subseteq {A}^{2}, A={1,2,3}, заданного на рисунке, имеет вид =...

26
1129 / 788 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
28.09.2014, 00:32 2
Цитата Сообщение от Garold Посмотреть сообщение
На множестве M этих матриц определено бинарное отношение
Garold, отношение определено на множестве матриц. Т.е. элементами отношения являются не пары (7,-8) и т.п., а пары матриц.

Добавлено через 7 минут
Например, (A2,A3) и (A2,A5) это разные пары матриц, т.е. разные элементы отношения.

Добавлено через 16 минут
Цитата Сообщение от Garold Посмотреть сообщение
определить, является ли оно рефлексивным
Это можно определить (доказать), не зная вообще определителей матриц. Отношение рефлексивно, потому что ... И далее можно объяснить, почему. (Для этого не нужно знать, чему равны определители.)

Если бы матриц было не 5, а 10000, как бы Вы, Garold, проверяли рефлексивность, транзитивность, и т.д ?
1
Нарушитель
Эксперт C
26236 / 16266 / 3525
Регистрация: 24.12.2010
Сообщений: 35,901
28.09.2014, 03:07 3
Давайте проведем небольшое обобщение. Есть некое Множество M. (это могут матрицы, люди, атомные бомбы, закаты). Каждому элементу множества М поставлено в соответствие Число (определитель, сумма диагональных элементов, рост, вес, тротиловый эквивалент, время). И есть отношение, определенное как в стартовом топике. Совершенно очевидно, что это отношение является отношением порядка (рефлексивность, транзитивность)

Добавлено через 7 минут
Цитата Сообщение от Alex5 Посмотреть сообщение
отношение определено на множестве матриц. Т.е. элементами отношения являются не пары (7,-8) и т.п., а пары матриц.
По большому счету вы правы, но тут имеется отображение M -> R и используется отношение уже определенное в R. Те каждый элемент из M имеет своего представителя в R и дальше все идет на языке этого представления. Те вполне допустимо отвлечься от природы первоначального множества и говорить в терминах представления

Добавлено через 3 минуты
Цитата Сообщение от Garold Посмотреть сообщение
Транзитивность присутствует: годится для элементов (7,7), (-8,-8), (-2,-2), (0,0).
не годится. Транзитивность, это совсем не то
0
10 / 10 / 1
Регистрация: 17.02.2013
Сообщений: 344
28.09.2014, 10:02  [ТС] 4
Цитата Сообщение от Байт Посмотреть сообщение
не годится. Транзитивность, это совсем не то
Да, действительно, разобрался.
Цитата Сообщение от Alex5 Посмотреть сообщение
Это можно определить (доказать), не зная вообще определителей матриц. Отношение рефлексивно, потому что ... И далее можно объяснить, почему. (Для этого не нужно знать, чему равны определители.)
Если бы матриц было не 5, а 10000, как бы Вы, Garold, проверяли рефлексивность, транзитивность, и т.д ?
И как Вы предложили бы мне доказать ? Я не понимаю.
0
2624 / 2209 / 237
Регистрация: 03.07.2012
Сообщений: 7,988
Записей в блоге: 1
28.09.2014, 11:27 5
Отношение рефлексивно, потому, что определитель любой матрицы не превышает определителя этой же матрицы.
И вообще - это отношение очень похоже на отношение "меньше либо равно" для целых чисел. Я уже не помню, есть ли какие теоремы про "индуцированные " отношения (насчет наследования свойств).
0
Нарушитель
Эксперт C
26236 / 16266 / 3525
Регистрация: 24.12.2010
Сообщений: 35,901
28.09.2014, 12:14 6
Цитата Сообщение от zer0mail Посмотреть сообщение
есть ли какие теоремы про "индуцированные " отношения (насчет наследования свойств).
Рассмотрим множества M, X, отношения r на M и s на X и отображение f: M->X. и пусть m r n тогда и только тогда, когда f(m) s f(n)
Теорема 1. Если s рефлексивно, то и r рефлексивно
Теорема 2. Если s транзитивно, то и r транзитивно
Если отображение f является инъекцией, то теоремы 1,2 допускают обращение (тогда и только тогда)
Доказательство оставляется читателю в качестве упражнения
0
1129 / 788 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
28.09.2014, 12:16 7
Цитата Сообщение от Байт Посмотреть сообщение
вполне допустимо ... говорить в терминах представления
Байт, допустимо, или нет - зависит от рассматриваемого вопроса. "Является ли рефлексивным", "какова мощность отношения".

Например, если определители всех матриц равны 4, то имеется только одна пара (4,4). А мощность отношения равна квадрату количества матриц.
1
Нарушитель
Эксперт C
26236 / 16266 / 3525
Регистрация: 24.12.2010
Сообщений: 35,901
28.09.2014, 12:26 8
Цитата Сообщение от Alex5 Посмотреть сообщение
допустимо, или нет - зависит от рассматриваемого вопроса. "Является ли рефлексивным", "какова мощность отношения".
Прошу прощения. Вопрос о мощности как-то выпал у меня из головы (хотя он в заголовке топика!) Тем более, что отображение в данном случае не инъективно...
0
2624 / 2209 / 237
Регистрация: 03.07.2012
Сообщений: 7,988
Записей в блоге: 1
28.09.2014, 12:34 9
Цитата Сообщение от Байт Посмотреть сообщение
Доказательство оставляется читателю в качестве упражнения
Я читал теорию категорий и функторов, так что доказать не проблема. Интересно, давали ТС соответствующую теорему, на которую можно сослаться при решении. Можно, конечно, самому доказать, но это будет задача другого уровня (а оно им надо?)
0
10 / 10 / 1
Регистрация: 17.02.2013
Сообщений: 344
28.09.2014, 13:10  [ТС] 10
zer0mail,
Цитата Сообщение от zer0mail Посмотреть сообщение
Интересно, давали ТС соответствующую теорему, на которую можно сослаться при решении
Нет, не давали. И понятия "инъективно" тоже не упоминали.
Все как-то проще должно быть.
0
1129 / 788 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
28.09.2014, 13:23 11
Цитата Сообщение от Garold Посмотреть сообщение
И как Вы предложили бы мне доказать ? Я не понимаю.
"Отношение R рефлексивно" означает "для любого a (aRa)". "Для любой матрицы det(Mi) = det(Mi)".
0
10 / 10 / 1
Регистрация: 17.02.2013
Сообщений: 344
28.09.2014, 13:25  [ТС] 12
Alex5, понятно, в общем виде имели в виду записать.
0
1129 / 788 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
28.09.2014, 13:28 13
Цитата Сообщение от zer0mail Посмотреть сообщение
И вообще - это отношение очень похоже на отношение "меньше либо равно" для целых чисел. Я уже не помню, есть ли какие теоремы про "индуцированные " отношения (насчет наследования свойств).
По-видимому, это верно (про наследование свойств), если в определении свойства кроме таких конструкций, как "для любого элемента...", "существует такой элемент, что...", "... и ... ", "если ..., то ..." и т.п. встречаются только высказывания вида R(a,b).

Наример, "для любого a R(a,a)".
По определению R(a,a) означает R2(f(a),f(a)). Поэтому https://www.cyberforum.ru/cgi-bin/latex.cgi?\forall a R(a,a), это то же самое, что https://www.cyberforum.ru/cgi-bin/latex.cgi?\forall a R_2(f(a),f(a)).

Пример 2. "Если R(a,b) и R(b,a), то элементы совпадают. " https://www.cyberforum.ru/cgi-bin/latex.cgi?\forall a \forall b (\; (R(a,b) \:&\:  R(b,a))   \rightarrow a=b \;).

Здесь кроме R(a,b), ещё есть "a=b". В общем случае, a=b не эквивалентно f(a)=f(b). И наследование не будет выполняться.
1
10 / 10 / 1
Регистрация: 17.02.2013
Сообщений: 344
28.09.2014, 17:42  [ТС] 14
И все-таки на счет мощности:
одно и то же https://www.cyberforum.ru/cgi-bin/latex.cgi?(det({A}_{2}), det({A}_{3})) и https://www.cyberforum.ru/cgi-bin/latex.cgi?(det({A}_{5}), det({A}_{3})), если https://www.cyberforum.ru/cgi-bin/latex.cgi?det({A}_{2})=det({A}_{5}) ?

Просто, если учитывать элементы с одинаковыми парами, то мощность=16, если нет, то 11.
0
1129 / 788 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
28.09.2014, 20:16 15
Цитата Сообщение от Garold Посмотреть сообщение
учитывать элементы с одинаковыми парами
Garold, пары чисел (-2,7) и (-2,7) одинаковые. А пары матриц (A3,A1) и (A5,A1) разные. Мощность отношения - это количество пар матриц.
2
1 / 1 / 1
Регистрация: 13.02.2014
Сообщений: 7
30.09.2014, 04:15 16
Бинарное отношение на множестве (по определению) -- подмножество (его мощность и ищем) декартова произведения исходного множества. В данном случае, бинарному отношению действительно удовлетворяют 11 пар матриц (вот, нашли )
Проверять свойства бин. отношения нужно уже на всех парах декартова произведения, и эти пары составляют всё же матрицы, а не определители, как заметили выше. Свойства указаны правильно, проблема только с обоснованием (в общем виде, тоже было выше). Ну и забыл про:
• не является отношением эквивалентности (т.к. не симметрично)
• является отношением порядка (рефлексивно, антисимметрично и транзитивно)
• является отношением линейного порядка (для любых элементов M либо det(Ai) >= det(Aj), либо det(Aj) >= det(Ai)

P.S. передавай привет Олейник))
0
Нарушитель
Эксперт C
26236 / 16266 / 3525
Регистрация: 24.12.2010
Сообщений: 35,901
30.09.2014, 11:57 17
Цитата Сообщение от Bandikoot Посмотреть сообщение
антисимметрично
Но вот этого к сожалению нет.
A3 ro A5, A5 ro A3
Посему и линейного порядка нет. Кажется, это называется "вполне упорядочено" (но божиться не буду)
А в остальном все правильно
1
10 / 10 / 1
Регистрация: 17.02.2013
Сообщений: 344
30.09.2014, 17:22  [ТС] 18
Bandikoot, так и не понял почему мощность 11, мы же рассматриваем не значения определителей ?
Байт,
Цитата Сообщение от Байт Посмотреть сообщение
A3 ro A5, A5 ro A3
как это нет, их значения же равны -2 ?
0
Нарушитель
Эксперт C
26236 / 16266 / 3525
Регистрация: 24.12.2010
Сообщений: 35,901
30.09.2014, 18:00 19
Цитата Сообщение от Garold Посмотреть сообщение
определитель матрицы Aiне превышает определителя матрицы Aj
Цитата Сообщение от Garold Посмотреть сообщение
так и не понял почему мощность 11
Чтоб решить все споры, давайте явно выпишем отношение, т.е. перечислим пары матриц, ему принадлежащих
(A1,A1), (A2,A1), (A2,A2), (A2,A3), (A2,A4), (A2,A5),
(A3,A1), (A3,A3), (A3,A4), (A3,A5), (A4,A1), ((A4,A4),
(A5,A1), (A5,A3), (A5,A4), (A5,A5)
Нигде не ошибся? Проверьте.
Получилось 16 элементов. Это и есть мощность отношения.
И есть элементы (A3,A5) (A5,A3) которые нарушают антисимметричность
0
10 / 10 / 1
Регистрация: 17.02.2013
Сообщений: 344
30.09.2014, 19:32  [ТС] 20
Байт,

С мощностью разобрались.
А вот на счет антисимметричности я опять не понял. Ведь условие Для любых Ai и Aj таких что Ai ro Aj и Aj ro Ai тогда и только тогда, когда Ai=Aj. В нашем случае A3=A5=-2
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.09.2014, 19:32

Пример бинарного отношения
1.Отношение ( не рефлексивно, симетрично,транзитивно){<1,1><1,2><2,1>} 2.Отношение ( рефлексивно,...

Проверьте правильность бинарного отношения
Привести пример бинарного отношения (рефлексивности, не симетричности и транзитивности)...

Привести пример бинарного отношения
Привести пример бинарного отношения(иррефлексивноть симетричность и не транзитивность) Вот...

Дать пример бинарного отношения
Привести пример бинарного отношения (рефлексивность асиметричность транзитивность)...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.