В.Н. Нефедов - Алгебра множеств, бинарные отношения в примерах и задачах (1013084), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Предположим, что бинарное отношение1   2 не является антисимметричным на A . Тогда x, y  A : x  y, x, y ,  y, x   1   2 . Пусть для определенности  x, y  1(случай  x, y   2 рассматривается аналогично). Тогда, в силу анти48симметричности 1 ,  y, x   2 , откуда  x, y   2 , следователь1но,  x, y  1   2 , однако, x  y, а следовательно,  x, y  e A ,1т.е. пришли к противоречию с исходным предположением.Задача 3.4. Построить бинарное отношение  на некотором множестве A : (а) рефлексивное, симметричное, не транзитивное; (б) рефлексивное, транзитивное, не симметричное; (в) антисимметричное,транзитивное, не рефлексивное; (г) рефлексивное, антисимметричное,не транзитивное; (д) симметричное, транзитивное, не рефлексивное.Решение.

(а) A  {1,2,3},   { 1,1 ,  2,2 ,  3,3 ,  1,2 , 2,1 ,  1,3 ,  3,1 } ; (б) A  {1,2},   { 1,1 ,  2,2 ,  1,2 } ;(в) A  {1,2},   { 1,2 } ; (г) A  {1,2,3},   { 1,1 ,  2,2 , 3,3 ,  1,2 ,  2,3 } ; (д) A  {1,2},   { 1,1 } .Задача 3.5. Пусть 1 ,  2 – бинарные отношения на множестве A .Тогда (а) если 1 рефлексивно, то  2  1   2 ; (б) если  2 рефлексивно, то 1  1   2 ; (в) если 1 ,  2 рефлексивны, то 1  2  1   2 ; (г) если 1 ,  2 рефлексивны, то 1   2 рефлексивно.Решение. (а) Пустьx, y   2 . Тогда, используя рефлексивность1 , имеем: x, x  1 , x, y   2 , откуда x, y  1   2 . Утверждение (б) доказывается аналогично.

Утверждение (в) является следствием(а),(б). Утверждение (г) является следствием утверждения (в).Задача 3.6. Доказать, что пересечение любого числа (а) рефлексивных бинарных отношений на множестве A является рефлексивнымна A ; (б) симметричных бинарных отношений на A является симметричным на A ; (в) антисимметричных бинарных отношений на A является антисимметричным на A ; (г) транзитивных бинарных отношенийна A является транзитивным на A .Решение. Утверждение (а) очевидно. Утверждение (в) являетсяследствием утверждения 3.1. Покажем справедливость утверждения (г)(утверждение (б) доказывается аналогично). Пусть { i | i  I } – некоторое семейство транзитивных бинарных отношений на множестве A .49Покажем транзитивность     i .

Действительно, x, y, z  AiI x, y   ,  y, z    x, y   i ,  y, z   i , i  I  x, z   i , i  I   x, z    i   .iIЗадача 3.7. Пусть  – произвольное бинарное отношение на множестве A . Доказать, что для бинарного отношения  , являющегосяпересечением всех транзитивных бинарных отношений на A , включающих в себя  , выполняется: (а)    ; (б)  транзитивно на A ;(в) для любого бинарного отношения   на A , если   транзитивно и    , то      ; (г) k  N  k    ; (д) если | A | n , то      2  ...   n .Решение.

Утверждение (а) следует из определения  . Утверждение (б) следует из утверждения (г) задачи 3.6. Утверждение (в) следуетиз определения  . Утверждение (г) легко доказывается индукцией поk , используя включение     , а также транзитивность   . Докажемсправедливость утверждения (д). В силу (в),(г), для этого достаточно~     2  ...   n .доказать транзитивность бинарного отношения ~ . Докажем, что  x, z  ~ . Из  x, y ,Пусть  x, y ,  y, z   y, z  ~ следует, что m  2, x1 ,..., xm  A :x  x1 ;  x1 , x2 ,  x2 , x3 ,  x3 , x4 ,...,  xm1 , xm   ; xm  z.

(3.2)Предположим, что i, j : 1  i  j  m такие, что xi  x j и приэтом не выполняется i  1, j  m . Тогда для последовательностиx1 ,..., xi , x j 1 ,..., xm (имеющей меньшее число членов, чем последовательность x1 ,..., xm ) аналогично (3.2) выполняется x  x1 ;  x1 , x2 , x2 , x3 ,...,  xi1 , xi ,  xi , x j 1 ,  x j1 , x j 2 ,...,  xm1 , xm   ;xm  z . Производя и далее аналогичное уменьшение длины каждой по50лучаемой таким образом последовательности (пока это возможно),окончательно придем к последовательности x1 , xi1 , xi2 ,..., xir , xm , в которой в случае x1  x  z  xm все члены попарно различны, а в случаеx1  x  z  xm все члены, кроме последнего, попарно различны и выполняется  x1 , xi1 ,  xi1 , xi2 ,...,  xir 1 , xir ,  xir , xm   .

Но тогда в этой последовательности не может быть более n  1 членов, а впоследовательности  x1 , xi1 ,  xi1 , xi2 ,...,  xir 1 , xir ,  xir , xm  не~.может быть более n пар, откуда и следует, что  x, z  x1 , xm  Задача 3.8. Доказать, что пересечение любого числа эквивалентностей на множестве A является эквивалентностью на A .Решение. Утверждение этой задачи следует из утверждений (а),(б), (г) задачи 3.6.Задача 3.9. Доказать, что если  – транзитивное и симметричноебинарное отношение на множестве A и D  R  A , то  – эквивалентность на A .Решение. Докажем рефлексивность  .

Пусть a  A . В силу того,что D  R  A , x  A :  x, a   , или  a, x   . Но тогда, всилу симметричности  ,  a, x   ,  x, a   , откуда, используятранзитивность  , получаем  a, a   . Таким образом a  A a, a   .Задача 3.10. Пусть 1 ,  2 – эквивалентности на множестве A .Доказать, что 1   2 – эквивалентность на A тогда и только тогда, когда 1   2 =  2  1 .Решение. (а) Пусть 1   2 – эквивалентность на A . Тогда бинарное отношение 1   2 является симметричным на A , откуда, используя симметричность 1 ,  2 на A , а также утверждение 2.1 (см. тему№2), имеем 1   2  ( 1   2 ) 1   2  1   2  1 . (б) Пусть15111   2 =  2  1 .

Покажем, что 1   2 – эквивалентность на A . Рефлексивность: см. задачу 3.5(г). Симметричность: ( 1   2 ) 1   21  11   2  1  1   2 . Транзитивность. Используя утверждения 2.2,3.4, имеем ( 1  2 )  ( 1  2 )  1  ( 2  1 )  2  1  ( 1   2 )   2  ( 1  1 )  (  2   2 )  1   2 , откуда, в силуутверждения 3.2, и следует транзитивность 1   2 .Задача 3.11. Пусть 1 ,  2 – эквивалентности на множестве A .Доказать, что 1   2 – эквивалентность на A тогда и только тогда,когда 1   2 = 1   2 .Решение.

(а) Пусть 1   2 – эквивалентность на A . Тогда изтранзитивности и рефлексивности 1   2 следует (см. утверждения3.4,2.4) 1   2  ( 1   2 )  ( 1   2 )  ( 1  1 )  ( 1  2 )  (  2  1 )  (  2   2 )  1   2  1   2 . С другой стороны, изрефлексивности 1 ,  2 следует (см. задачу 3.5(в)), что 1   2  1   2 , а следовательно, 1   2  1   2 . (б) Пусть 1   2 = 1   2 . Покажем, что 1   2 – эквивалентность на A . Очевидно,что бинарное отношение 1   2 рефлексивно и симметрично на A(см. задачу 2.4). Докажем его транзитивность. Заметим (см.

утверждение 2.1 и задачу 2.4), что  2  1   21  11  ( 1   2 ) 1  ( 1   2 ) 1  11   21  1   2 , откуда ( 1   2 )  ( 1   2 )  ( 1  1 )  ( 1   2 )  (  2  1 )  (  2   2 )  1  ( 1   2 )  (  2  1 )   2  1   2 , т.е., в силу утверждения 3.2, транзитивность 1   2 доказана.Тема №4. Отношение порядка.

Частичный и линейный порядкиЧастичный порядок. Рефлексивное, транзитивное и антисимметричное бинарное отношение  на множестве A называется частич52ным порядком на A .Пример 4.1. Бинарное отношение  на множестве действительных чисел R является частичным порядком: (а) рефлексивность:x  A x  x ; (б) транзитивность: x, y, z  A x  y, y  z  x  z;(в) антисимметричность: x, y  A x  y, y  x  x  y .Пример 4.2. Бинарное отношение  на множестве R2 определяемое следующим образом: x1 , x2  y1 , y 2  xi  yi , i  1,2 (называемое отношением Парето), является частичным порядком. Обоснование аналогично приведенному в примере 4.1.

Аналогичным образом можно задать частичный порядок на R3, R4 и т.д.Пример 4.3. Бинарное отношение  на множестве 2U всех подмножеств некоторого универсального множества U   (см. тему №1)является частичным порядком: (а) рефлексивность: A  2U A  A ;(б) транзитивность: A, B, C  2U A  B, B  C  A  C ; (в) антисимметричность: A, B  2UA  B, B  A  A  B .Пример 4.4. Рассмотрим отношение «подчиненности» на множестве должностей некоторого предприятия (см. рис. 4.1; кружками и овальными рамками обозначены сотрудники предприятия , не имеющие других в своем подчинении).

По определению считаем, что каждый работник предприятия подчиняется самому себе (аналогично параллельностипрямой самой себе в курсе геометрии). Для нормального функционирования предприятия отношение подчиненности с необходимостью должно быть антисимметричным (так как в противном случае найдутся дведолжности x и y такие, что x подчиняется y и, наоборот, yподчиняется x , что приводит к абсурдной ситуации). А для централизованного управления предприятием в целом, а также внутри любогоего подразделения необходима транзитивность отношения подчиненности, чтобы распоряжения, отдаваемые руководителем данного подразделения предприятия, относились ко всем работникам этого подразделения.53Рис. 4.1Линейный порядок.

Пусть  – частичный порядок на множествеA . Элементы x, y  A называются сравнимыми по  , если выполняется либо xy , либо yx .Частичный порядок  на множестве A называется линейным, если любые два элемента из A сравнимы по  .Пример 4.5. Отношение частичного порядка  на множестве действительных чисел R является линейным порядком на R. Действительно, x, y  R возможны случаи: (а) min( x, y)  x , и тогда x  y ;(б) min( x, y)  y , и тогда y  x .Пример 4.6. Отношение частичного порядка  на множестве R2(см. пример 4.2) не является линейным, так как пары0,1 , 1,0  R2не сравнимы.Пример 4.7.

Отношение частичного порядка  на 2U (см. пример 4.3) не является линейным при | U | 2 . Например, при U  {1;2} ,A  {1} , B  {2} множества A и B не сравнимы (ни одно из них не является подмножеством другого).Пример 4.8. Бинарное отношение «подчиненности» на множестведолжностей некоторого предприятия, соответствующее рис. 4.1, не является линейным порядком, так как , например, кассир не подчиняетсябригадиру 1, а бригадир 1 не подчиняется кассиру.Множество A с заданным на нем отношением частичного (линейного) порядка  называется частично (линейно) упорядоченным.54Будем далее для произвольного отношения частичного прядка вместо символа  (общего для всех бинарных отношений), использоватьсимвол ≼. Введем для произвольного отношения частичного порядка≼ на множестве A ассоциированное с ним отношение строгого порядка ≺ на множестве A , определяемое условием: x, y  A x ≺ y  x ≼ y , x  y .

Характеристики

Список файлов книги