Бинарные отношения

сколько рефлексивных бинарных отношений можно ввести на множестве из n элементов. задача гимназии 1543, 9 класс

Я думаю, что таких отношений будет столько, сколько подмножеств в декартовом произведении AxA, содержащих диагональ.

у ьня множество состоит из n элементов, в моем варианте n=5. мне надо подсчитать количество отгошений как формулу от n и число для n=5.

Помогите, пожалуйста, скоро сдавать. Обращался за помощью к студента-математикам(1 курс), говорят не проходили такого. А у меня дополнительные вопросы: сколько симметричных, антисимметричных, асимметричных отношений?

Попробуем. Отвечай сначала на следующие вопросы:
1. Сколько у множества мощности n подмножеств. Из комбинаторики.
2. Что такое декартово произведение двух множеств, какова мощность этого произведения, если умножается множество мощности n само на себя.
3. Что такое вообще бинарное отношение через подмножества.
4. Является ли пустое подмножество множества бинарных отношений бинарным отношением и с какими свойствами.
Отсюда получить ответ на вопрос: сколько всего бинарных отношений можно задать на множестве. Все время веди исследование на пимере простого множества, например, A= {1,2}.

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

Все верно. Ответ на Ваш вопрос содержится в посте 2.

Я не совсем понимаю(точнее, совсем не понимаю) , что такое подмножество, содержащее диагональ. Не могли бы Вы перечислить все рефлексивные отношения для множества A= {1,2}. Я их себе уже выписал, хочу проверить. Пожалуйста. Или хотя сказать, сколько их штук.

Диагональ={(1,1),(2,2)}.
Рефлексивных отношений четыре:
{(1,1),(2,2)},
{(1,1),(2,2),(1,2)},
{(1,1),(2,2),(2,1)},
{(1,1),(2,2),(1,2),(2,1)}.

А пустое подмножество?????? Ведь пустое подмножеств обладает любыми свойствами, в том числе рефлексивностью.
Тем более среди общего количества бинарных отношений для множества А={1,2} есть обязательно пустое, иначе их не будет 16 по формуле 2^(n^2). А это формула верна, как следует из того, что меня спрашивал здесь Борис Кругликов, да я и проверил в школе.

Почему это пустое подмножество обладает любыми свойствами? Например пустое подмножество точно не обладает свойством "содержит все элементы множества"? Запиши еще раз определение рефлексивности.

"Ведь пустое подмножеств обладает любыми свойствами"
Я думаю, что Вы перепутали свойства пустого множества со свойствами
элементов пустого множества. Элементы пустого множества, действительно,
обладают любыми свойствами (по той простой причине, что их просто нет).
Можно, например, доказать, что все элементы пустого множества — зелёные.
Действительно, импликация
[m](x\in\varnothing)\Longrightarrow (x\;\;is\;green)[/m]
истинна, так как ложна её посылка.

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

Да, я был не прав. Но тогда вопрос : является ли пустое множество бинарным отношением?

Да, среди всех бинарных отношений есть и пустое множество.

Да, но к каким( в число каких) входит это бинарное отношение-пустое множество. Оно входит в состав рефлексивных (Вы сказали нет), симметричных, антисимметричных, асимметричных, транзитивных и т.п. ?????????

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

Проверьте , пожалуйста, мои симметричные отношения: пустое, квадрат самого множества, {(1,1)}, {(2,2)}, {(1,1) (2,2)} , {(1,2) (2,1)} , {(1,1)(1,2)(2,1)},
{(1,2)(2,1)(2,2)}. Всего 8. Следует ли отсюда, что асимметричных будет тоже 8? Антисимметричных у меня получилось 12, но вместе с пустым. И все же с пустым наибольшие сомнения.

С симметричными отношениями всё просто: пара (1,2) принадлежит симметричному
отношению R тогда и только тогда, когда принадлежит отношению R пара (2,1).
Поэтому для задания симметричного отношения достаточно указать, какие из
трёх пар (1,1), (2,2), (1,2) принадлежат отношению. Количество симметричных
отношений получается равным 2^3=8, все они у Вас перечислены правильно.

Хуже обстоит дело с антисимметричными отношениями, потому что я обнаружил
в литературе два разных определения антисимметричного отношения:
1) xRy и yRx возможно только в случае, когда x=y (Математическая Энциклопедия
в 5 томах);
2) xRy и yRx невозможно ни в каком случае (Дж. Келли, Общая топология).

"Асимметричное отношение" — это вообще новый термин, в литературе я такого
термина не нашёл.

Меня пугает Ваша любовь к бинарным отношениям. Язык бинарных отношений — это
очень хорошая составная часть математического языка. Использование
соответствующей терминологии может сделать математическую речь более
точной и лаконичной. Но только при одном условии. При условии, что есть,
что сказать. Можете ли Вы сообщить нам какие-нибудь интересные, глубокие
математические факты, используя язык бинарных отношений?

Я позавчера перелистывал старый задачник по геометрии и наткнулся
на очень интересную задачу: вывести геометрически формулу Герона.
Формула Герона выражает площадь треугольника через его стороны.
Формулу Герона я знаю с детства и много раз тренировался в её выводе,
и при этом всегда получались очень громоздкие вычисления. А оказывается,
формулу Герона можно получить очень-очень просто из чисто геометрических
соображений. Это очень красивая математика!
Это интереснее, чем подсчитывать количество бинарных отношений.

"Меня пугает Ваша любовь к бинарным отношениям" ( Боравлев Юрий Анатольевич ).
Бинарные отношения- на этом языке излагается криптология( криптография и криптоанализ).
Странное поведение- не будучи специалистом в абстрактной алгебре помогать мальчику 9 класса, у которого знания (но не умение) явно выше. Видимо, теперь на Физтехе не изучается абстрактная алгебра-один из важнейших разделов классической математики, все приходит в упадок.

1) Если Вы были внимательны, глядя на мой пост #18, то должны были прочитать:
"Язык бинарных отношений — это очень хорошая составная часть математического
языка. Использование соответствующей терминологии может сделать математическую
речь более точной и лаконичной."
Я очень рад тому, что наши с Вами мнения о важности бинарных отношений
совпадают.

2) Если Вы обнаружили какие-либо неточности в моих ответах ученику 9 класса,
то я буду Вам очень благодарен, если Вы укажете на них. Когда я отвечаю, я
стараюсь быть внимательным и ошибок не допускать.

3) Я обнаружил ошибку в Вашем посте #30. Вы указали только два асимметричных
отношения и забыли указать ещё одно асимметричное отношение — пустое.
Пустое отношение тоже является асимметричным, если исходить из определения,
которое дал ученик в #20: "для любых х и у из xRy следует ¬ yRx".
Если же Вы исходите из какого-либо другого, неравносильного этому, определения
асимметричного отношения, то Вы должны были это оговорить.

Бинарные отношения есть рабочий инструмент в криптологии, Ваши неточности обнаружил Валерий. Про пустое множество Вы ,конечно, правы, я в автомате про него забыл, считая это всем известным.
В мое время на Физтехе изучалась абстрактная алгебра, теория меры, интеграл Лебега и............ Сейчас этого нет даже у математиков.
Изучение математики в таком объеме, как в 1543, считаю вредным, идет в ущерб глубине понимания и умению думать. Это просто показывают "крутость" школы. Знаю это, живу рядом с 1543 и делал неоднократно домашние задания.

У меня нет любви к бинарным отношения, но есть школьная прогамма.
Гимназия 1543, 9-В класс Листик 12, 11 октября 2010
Отношения эквивалентности и комбинаторика
Определение. Пусть M – множество. Произвольное множество упорядоченных пар элементов из М называется отношением на M. Если , то пишут или просто .
Отношения можно изображать в виде таблицы. Строки и столбцы таблицы занумерованы элементами множества M, на пересечении строки a и столбца b таблицы стоит 1, если , иначе клетка пустая.
Также отношения можно изображать в виде ориентированного графа. Вершинами графа будут элементы множества M. В графе из вершины a ведет ребро в вершину b если .
1. Изобразите в виде графа и таблицы следующие отношения.
а) M={1,2,3,4,5,6,7,8,9}, , если
б) M={1,2,3,4,5,6,7,8,15}, , если a кратно b (таблицу можно не рисовать)
в) M – множество подмножеств множества {0,1,2}, , если .
Определение. Отношение R называется рефлексивным, если .
Отношение R называется симметричным, если из следует, что .
Отношение R называется транзитивным, если из и следует . Отношение R называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно одновременно.
2. а) Какие свойства выполняются для отношений из задачи 1?
б) Что означают свойства рефлексивности, симметричности и транзитивности для изображения отношения в виде таблицы. Что означает свойство отношения быть эквивалентностью?
в) Что означают эти свойства для изображения в виде графа?
3. Пусть в множестве M n элементов. а) Сколько существует отношений на множестве M?
б) Сколько их них являются рефлексивными? в) Сколько из них являются симметричными?
4. Являются ли эквивалентностями следующие отношения?
а) Отношение быть братом на множестве людей.
б) Отношение быть параллельным на множестве прямых.
в) Отношение быть перпендикулярным на множестве прямых.
г) Отношение равносоставленности на множестве многоугольников. (Два многоугольника называются равносоставленными, если один из них можно перекроить в другой (то есть разрезать на части, переложив которые, можно получить другой)).
д) Придумайте свой пример отношения эквивалентности.
Определение. Пусть на множестве M задано отношение эквивалентности. Для каждого элемента определим множество класс эквивалентности элемента x. Элемент x при этом называется представителем класса [x].
5. Докажите, что любые два класса эквивалентности или не пересекаются или совпадают.
Докажите, что каждое отношение эквивалентности на M задаёт разбиение множества M на непересекающиеся классы эквивалентности.
Верно, очевидно, и обратное: если произвольное множество разбито на непустые непересекающиеся классы, то отношение «лежать в одном классе» будет отношением эквивалентности. Получается, что разбить множество на непустые классы и задать на нём отношение эквивалентности – это, по сути, одно и то же.
6. Дан граф. Его вершины разбиты на несколько кусков (компоненты связности). Придумайте отношение эквивалентности, которое задает такое разбиение.
7. а) Проведены несколько прямых. Они разбивают плоскость на части. Придумайте отношение эквивалентности на множестве точек плоскости, которое задает это разбиение на части.
б) Проведены несколько прямых и окружностей. Они разбивают плоскость на части. Придумайте отношение эквивалентности на множестве точек плоскости, которое задает это разбиение на части.
Определение Отношение сравнимости по модулю m является отношением эквивалентности. Множество классов эквивалентности обозначается (другое обозначение ).
8. а) Пусть a и m взаимно просты. Рассмотрим отображение по правилу: . Является ли это отображение инъекцией? Сюръекцией? Биекцией?
б) Пусть m1 и m2 взаимно простые числа, m=m1m2. Рассмотрим отображение определенное формулой . Является ли это отображение инъекцией? Биекцией?
В комбинаторике нередко какие-то ситуации считаются эквивалентными, и требуется подсчитать количество классов эквивалентности.
9. а) В Марсианском языке ровно n букв, а словом является любая последовательность из k различных букв. Но слова отливающиеся только перестановкой букв являются синонимами. Сколько всего слов и сколько разных по смыслу слов в Марсианском языке?
б) Тоже самое, но буквы в слове не обязательно различные. (хотя бы для k=5)
10. Сколькими способами можно раскрасить: а) грани куба в шесть данных цветов? (все цвета надо использовать) б) грани правильного тетраэдра в четыре данных цвета?
11. В жезле n полосок, каждую из которых можно покрасить в черный или белый цвет. Если одна раскраска получается из другой переворотом жезла, то они считаются одинаковыми. Сколько существует различных жезлов?
12. В карусели p сидений, где p – простое число. Рассмотрим множество раскрасок этих сидений в n цветов. Понятно, что раскраски получающиеся поворотом карусели считаются одинаковыми. Сколько существует различных раскрасок?
13. То же самое, но число сидений составное, например 4 или 6.
14. На плоскости отмечены вершины правильного p-угольника, где p – простое число.
а) Посчитайте число замкнутых ориентированных ломанных, проходящих по всем вершинам этого p-угольника.
б) Будем считать одинаковыми ломанные, переходящие друг в друга при повороте. Сколько теперь есть различных ломанных?

 Антисимметричное отношение — двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy и xR-1y следует х = у (то есть R и R-1 выполняются одновременно лишь для равных между собой членов).
 Асимметричное отношение — двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy следует ¬ yRx. Пример: отношение «больше» (>) и «меньше» (<).

У меня проблема в том, что я насчитал 8 симметричных отношений, всего же отношений 16. Поскольку симметричность и асимметричность несовместимы, то асимметричных должно быть тоже 8, но вот здесь у меня и проблема.

Естественно назвать отношение несимметричным, если оно не является
симметричным. И тогда, действительно, поскольку симметричных отношений 8,
а всего отношений 16, то несимметричных отношений будет 16-8=8.

Но из определения асимметричного отношения, которое Вы привели в #20,
вовсе не следует, что симметричность и асимметричность несовместимы.
Например, пустое отношение является одновременно и симметричным, и
асимметричным. А можно привести примеры и таких отношений, которые
не являются ни симметричными, ни асимметричными.

Извините, но отношения могут быть симметричными, антисимметричными и асимметричными . Несимметичных отношений не бывает, нет такого термина вообще.Асимметричное отношение — двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy следует ¬ yRx. Разве отсюда не следует их несовместимость???

"Несимметичных отношений не бывает,..."
То есть как это не бывает? В своём посте #22 я дал строгое и, как мне
казалось, вполне понятное определение несимметричного отношения.
"...нет такого термина вообще."
Вы хотите сказать, что лично Вы раньше такого термина никогда не встречали?
Ну и что? Что из этого следует?
Лично я тоже не помню, чтобы я сам где-нибудь встречал такой термин.
И что из этого следует? Разве я не имею право ввести в рассмотрение
класс отношений, который я назвал "несимметричными отношениями"?
Или Вам само название не нравится?

Несимметричные отношения я ввёл в рассмотрение специально для Вас, чтобы
придать смысл Вашему же вычислению 16-8=8. А иначе что могло бы означать
вычитание восьми из шестнадцати?

Отношение R называется симметричным, если всегда, когда пара (х, y) входит в R, то и пара (y, x) входит в R (инверсия R совпадает с R). Отношение R называется антисимметричным, если в него входит не более одной из каждых двух пар (х, y) или (y, x). Отношение R называется асимметричным, если оно и антисимметрично, и антирефлексивно Вот, что написано в нашем учебнике. Я также уточнял у учителя только что. Несимметричных отношений он не потерпит( это его шутка).

А и ¬ А всегда несовместимы, это и в теории множеств и в логике. В теории множеств пересечение А и ¬ А есть пустое множество, в логике конъюнкция А и ¬ А есть ложь. Нас так учили.

Интересно, для кого Вы всё это пишете (#25, #26)? Если хотите поделиться
своими знаниями с другими участниками форума, то большое спасибо Вам от
имени всех участников форума. Спасибо также за интересные рассказы о шутках
Вашего школьного учителя.

А то ведь мне могло показаться, что Ваши посты #25 и #26 написаны лично
для меня. Дело в том, что в #21 Вы пожаловались на то, что у Вас есть
проблема, и я попытался помочь Вам справиться с Вашей проблемой и указал
на Вашу ошибку (мой пост #22). Если Вы поняли свою ошибку и во всём уже
разобрались и смогли правильно сосчитать нужные Вам бинарные отношения,
то было бы естественным с Вашей стороны написать об этом. А если у Вас
остались вопросы, то было бы естественно задать их. Но поскольку в #25 и
в #26 Вы никаких вопросов не задаёте, то я так понимаю, что Вы уже во всём
разобрались. Я очень рад за Вас и желаю дальнейших успехов.

У меня остались вопросы. Пишу я лишь потому, что у меня есть учебник, мои ответы должны соответствовать ему. Ваши советы противоречат определениям учебника. Но я ведь уверен, что Вы лучше меня думаете. Я попробую перечислить разные бинарные отношения, а Вы меня проверите.

Вернемся к началу "Сколько рефлексивных бинарных отношений можно ввести на множестве из n элементов"- таков был первоначальный вопрос.
Мы выяснили, что всего бинарных отношений на множестве мощности n можно задать( 2^)n^2. Это получилось потому, что множество мощности n имеет 2^n подмножеств. Бинарное отношение -любое подмножество декартова произведения множества А на себя — оно имеет мощность n^2.
Рефлексивные отношения всегда обязательно содержат пары вида (1,1), (2,2) ит.д. , всего таких пар n штук. Поэтому надо из всех n^2 пар отнять n пар, из оставшихся пар взять все подмножества , вот и будет ответ.

Получается что рефлексивных отношений будет n и пустое множество?

Я забыла про подмножества

Симметричные: {(1,1)}, {(2,2)}, {(1,1), (2,2)}, {(1,2),(2,1)}, {(1,1),(1,2),(2,1)}, {(1,2),(2,1),(2,2)}, пустое и А^2. Всего 8 штук
Антисимметричные: {(1,1)}, {(2,2)}, {(1,2)}, {(2,1)}, {(1,1),(1,2)}, {(1,1),(2,1)}, {(1,1), (2,2)}, {(1,2),(2,2)} , {(2,1),(2,2)}, {(1,1),(1,2),(2,2)}, {(1,1),(2,1),(2,2)} Всего12 штук. из них:одновременно 4 симметричных. 12-4+8=16
Асимметричные:{(1,2)}, {(2,1)},

УТОЧНЕНИЕ. В число 12 антисимметричных входит пустое множество.

Отвечать на все поставленные Валерием вопросы было бы гораздо проще при представлении бинарных отношений матрицами. Но кажется даже 1543 не дошла до матриц в 9 классе.

ЭТО, ЧТОБЫ ЗАКОНЧИТЬ.
Определение 1.5. Бинарное отношение R на множестве М называется асимметричным, если ни одна пара не входит в отношение вместе с симметричной ей: Ух, у G М, если xRy, то неверно, что yRx.
Пример 1.6.
1. Отношение строгого неравенства на множестве вещественных чисел асимметрично.
2. Отношение делимости не является асимметричным ни на каком множестве целых чисел, не содержащем нуля.
Определение 1.6. Бинарное отношение R на множестве М называется антисимметричным, если никакая пара, состоящая из разных элементов, не входит в отношение вместе с симметричной ей: Ух, у G М, если xRy и yRx то х = у.
Пример 1.7.
1. Отношение нестрогого неравенства на множестве вещественных чисел антисимметрично.
2. Отношение делимости является антисимметричным на любом множестве целых чисел, не содержащем нуля.
Упражнение 1.2.
1. Верно ли, что асимметричное отношение всегда антирефлексив-но? Докажите.
2. Верно ли, что симметричное отношение всегда рефлексивно? Докажите.
3. Верно ли, что асимметричное отношение всегда антисимметрично? Докажите.
4- Верно ли, что отношение асимметрично тогда и только тогда, когда оно антирефлексивно и антисимметрично? Докажите.

Кажется, понял. Из общего числа бинарных отношений отнимаем число отношений "главной диагонали", возводим 2 в эту степень, получаем число рефлексивных отношений — 2^(n^2-n). Правильно?? думаю да???
Теперь надо понять, что надо отнимать в случае антисимметричных и асимметричных отношений.

Симметричное (коммутативное) отношение однозначно определяется составом нулей и единиц на главной диагонали и выше неё. Для антисимметричного отношения позиции (i, j) и (j, i) (i <= j) могут находиться в одном из 3 состояний при i<j и в одном из двух при i=j (почему?).

Правильно, именно столько рефлексивных отношений, при n=2 их 4, они выше перечислены.
Теперь подумай про формулу для симметричных отношений: 2^(n^2-?)???

Так, это Павел Борисович, про матрицы . Я тоже писал, что представление бинарных отношений матрицами заметно упростило бы понимание , как считать количество тех или иных бинарных отношений. Но они еще не изучали матрицы. Хотя , на вопросы, поставленные 9-классником Валерием, не смогли ответить студенты МИРЭА, обучающиеся на информационной безопасности.

Но Валерий в # 37 упомянул "главную диагональ". Ровно тот же мой тезис можно было сформулировать и без матриц, в терминах истинности aRb и bRa.

Подсказка, как получить формулу для числа симметричных отношений. Можно догадаться , что отнимать от n^2, а можно непосредственно, но для этого надо знать, что такое сочетания с повторениями.
Вопрос к Валерию-- изучал ли в комбинаторике сочетания с повторениями? Комбинаторику в 1543 в 9-ом уже изучали, сам знаю, но в каком объеме?

сочетания с повторениями изучал, но забыл, повторил. Оказывается, что симметричные бинарные отношения — это и есть сочетания из n элементов по 2, т.е. их число равно числу обычных сочетаний из (n+1) элементов по 2. При n=2 число сочетаний с повторениями равно 3, поэтому число бинарных симметричных отношений равно 2 в степени 3, т.е. 8. Это и было показано выше.

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

А теперь , Валерий, вычти из n^2 число сочетаний(без повторений) из n по два.

Вычел, получил Число сочетаний с повторениями — здорово потому,что наглядно. Но у меня еще антисимметричные и асимметричные??? Может теперь получится, но на помощь рассчитываю.
Спасибо уже всем. Я теперь лучше всех по бинарным отношениям.

Поздравляем!
Перефoрмулирую свой # 39 без матриц.

После упорядочения множества М будем говорить, что a <= b, если номер a меньше либо равен номеру b, и a<b, если номер a меньше номера b.
Симметричное (коммутативное) отношение однозначно определяется составом истинностных значений {aRb} по всем a<=b. Для антисимметричного отношения комбинация истинностных значений aRb и bRa (a <= b) может быть одной из трёх при a<b и одной из двух при a=b (почему? Вспомните определение антикоммутативного отношения).

Делаю вывод из того, что сказал Павел Борисович, не до конца понимая, что делаю. Число антисимметричных отношений равно 2 в степени n умножить на 3 в степени число сочетаний из n по два. Проверьте , пожалуйста. Неужели я стал чувствовать бинарные отношения. Наш преподаватель повторяет постоянно: математику надо освоить на уровне чувств.

Пожалуйста помогите Пусть R не рефлексивно Всегда ли отношение R 2 не рефлексивно