Помогите, пожалуйста, решить задачу:
Пусть t: AxA -> A и для всех x,y,z из A t(x,y)=t(y,x), t(x,(t(y,z)=t(t(x,y),z),  t(x,x)=x. Доказать, что отношение x<=y <-> t(x,y)=x есть отношение линейного порядка на A.

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

задан 20 Май '17 17:09

10|600 символов нужно символов осталось
0

К теории чисел эта задача не имеет отношения, так как здесь рассматривается произвольное множество A. Легко заметить, что t есть бинарная операция на A, поэтому вместо t(x,y) удобно писать xy (как для умножения). Тогда в условии даны коммутативный закон xy=yx, ассоциативный закон x(yz)=(xy)z (только надо чуть исправить левую часть равенства), а также условие идемпотентности xx=x. То есть дана коммутативная полугруппа идемпотентов.

Проверка того, что <= есть нестрогий частичный порядок, достаточно проста. Рефлексивность и антисимметричность очевидны сразу. Для доказательства транзитивности можно заметить, что x<=y, y<=z означают xy=x, yz=y, откуда xz=(xy)z=x(yz)=xy=x, то есть x<=z.

Линейным этот порядок в общем случае не будет. Коммутативные полугруппы идемпотентов имеют известное структурное описание -- см. здесь стр. 83 и далее. Если в качестве A взять "булеан" некоторого множества B и задать операцию как пересечение подмножеств, то получится полугруппа с указанными в условии свойствами. Тогда <= совпадает с отношением включения подмножеств, а оно в общем случае свойством линейности порядка не обладает.

ссылка

отвечен 20 Май '17 20:16

Спасибо! А вы не могли бы пояснить доказательство транзитивности? Из того, что x<=y следует, что xy=x по условию t(x,y)=x, верно? Не совсем понял, как вы получили x<=z. Я подставил z в ассоциативный закон, то тогда получаю только t(x,y)=t(x,z). И как тогда записать доказательство, что отношение не является отношением линейного порядка, если честно, тоже не понял. Заранее спасибо.

(21 Май '17 20:38) ki12

@ki12: так ведь у меня полное доказательство приведено! Нам дано, что x<=y и y<=z; надо доказать, что x<=z. Перечитайте последнюю строку второго абзаца.

Конкретный контрпример к отсутствию линейности порядка: положим A={0,{p},{q}}, где 0 -- пустое множество, p, q -- различные символы. Через t(x,y) обозначим пересечение множеств. Эта операция коммутативна, ассоциативна и идемпотентна. Для x={p} и y={q} выполнено t(x,y)=0, что не равно ни x, ни y. Значит, ни x<=y, ни y<=x не выполняется, и порядок не линеен.

(21 Май '17 21:05) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×879
×860

задан
20 Май '17 17:09

показан
482 раза

обновлен
21 Май '17 21:05

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru