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

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

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

Пусть R – множество действительных чисел. Тогда  { x, yx, y  R , z  R : x  z 2  y} – бинарное отношение намножестве R, которое обычно обозначается  (  – множество точек иззаштрихованной области; см. рис.2.2). Обычно вместо x, y  пишемx  y.Рис.2.228Пример 2.6.

  { x, yx, y  R , y  x 2 } – бинарное отношениена множестве действительных чисел R (  – множество точек из заштрихованной области ; см. рис. 2.3)Рис.2.3Пример 2.7. Пусть A  {1,2} , B  {3,4} . Тогда   { 1,4 , 2,3 } – бинарное отношение между элементами множеств A и B ,так как   A  B  { 1,3 ,  1,4 ,  2,3 ,  2,4 } .Областью определения бинарного отношения  называется мно- (т.е. Dжество D  x y : x, y  – это множество всех первыхэлементов пар из  ). Множеством значений бинарного отношения  (т.е. Rназывается множество R  y x : x, y  – это множе-ство всех вторых элементов пар из  ).В примере 2.4 Dо – это множество всех отцов, а Rо – это множество всех людей. В примере 2.5 D  R, R  R.

В примере 2.6 D  R,R  {x  R | x  0} . В примере 2.7 D  {1,2} , R  {3,4} .Операции над бинарными отношениями. Для бинарных отношений определены обычным образом теоретико-множественные операции объединения, пересечения и т.д. Абсолютным дополнением бинарного отношения  между элементами множеств A и B считаетсямножество   ( A B) \  . Например, абсолютным дополнением бинарного отношения  на R является бинарное отношение  на R.29Обратным отношением для бинарного отношения   A  B называется отношение 1 { y, x | x, y  }  B  A , т.е. полу-чаемое из  переворачиванием пар.Произведением бинарных отношений 1  A B ,  2  B  C называется бинарное отношение 1   2  A C , задаваемое равенством:1   2  { x, z  A  C | y  B : x, y  1 , y, z   2 } .Если  – бинарное отношение на множестве, то будем кратко писать  2     ,  3       и т.д.Приведем некоторые свойства этих операций.Утверждение 2.1.

Для любых бинарных отношений 1  A B , 2  B  C выполняется ( 1   2 ) 1   21  11  C  A .Доказательство. Пусть z, x  C  A . Тогда z, x  ( 1   2 ) 1  x, z  1   2  y  B : x, y  1 ,y, z   2  y  B : z, y   21 , y, x  11  z, x   21  11 .Утверждение 2.2. Для любых бинарных отношений 1  A B, 2  B  C ,  3  C  D выполняется 1  (  2   3 )  ( 1   2 )   3  A D .Доказательство. Для любой парыx, u  A  D имеем:x, u  1  (  2   3 )  y  B : x, y  1 , y, u   2   3  y  B, z  C : x, y  1 , y, z   2 , z, u   3  z  C : x, z  1   2 , z, u   3  x, u  ( 1   2 )   3 .Утверждение 2.3.

Для любых бинарных отношений 1  A B, 2  A B ,  3  B  C выполняется:(а) ( 1   2 )   3  ( 1   3 )  (  2   3 )  A  C ;(б) ( 1   2 )   3  ( 1   3 )  (  2   3 )  A  C ;30(в) ( 1 \  2 )   3  ( 1   3 ) \ (  2   3 )  A  C ;(г) ( 1   2 )   3  ( 1   3 )  (  2   3 )  A  C .Доказательство. Докажем (а). Пусть  x, z  A  C . Тогдаx, z  ( 1   2 )   3  y  B : x, y  1   2 , y, z   3 x, y  1  x, z  1   3 y, z   3 ,  x, y  1  x, y   2  x, z   2   3  x, z  ( 1   3 )  (  2   3 ) .С другой стороны, x, z  ( 1   3 )  (  2   3 )  x, z  1   3  y1  B : x, y1  1 , y1 , z   3  x, z   2   3  y 2  B : x, y 2   2 , y 2 , z   3  y  B : x, y  1   2 , y, z   3  x, z  ( 1   2 )   3 .Доказательство (б), (в) аналогично, (г) следует из (а), (в).Утверждение 2.4.

Для любых бинарных отношений 1  A B , 2  B  C ,  3  B  C выполняется:(а) 1  (  2   3 )  ( 1   2 )  ( 1   3 )  A  C ;(б) 1  (  2   3 )  ( 1   2 )  ( 1   3 )  A  C ;(в) 1  (  2 \  3 )  ( 1   2 ) \ ( 1   3 )  A  C ;(г) 1  (  2   3 )  ( 1   2 )  ( 1   3 )  A  C .Доказательство утверждения 2.4 аналогично доказательству утверждения 2.3.Функции.

Бинарное отношение f между элементами множествX и Y называется функцией, если (а) D f  X ; (б) R f  Y ; (в)x  X , y1 , y 2  Yx, y1 , x, y 2  f  y1  y 2 . Кратко выполне-ние условий (а)–(в) будем обозначать f : X  Y или говорить, что f– функция из X в Y . Если f – функция, то пишем y  f (x) вместо31x, y  f . Множество всех функций из X в Y обозначается черезY X , т.е. Y X  { f | f : X  Y } .Упражнение 2.3. Доказать, что если множества X , Y конечны, то| Y X || Y || X | .Указание.

Воспользоваться рассуждениями, аналогичными доказательству утверждения 1.1.Функция f : X  Y называется: (а) сюръективной, если R f  Y ;(б) инъективной, если x1  x2  f ( x1 )  f ( x 2 ) ; (в) биективной, еслиf одновременно сюръективна и инъективна.Равенство функций f  g по определению означает: (а) D f  Dg ;(б) x  D f  Dg f ( x)  g ( x) .Сопоставление аргументу x  X значения f ( x)  Y принятообозначать при помощи ограниченной стрелки: x  f (x) .Образ, прообраз множества относительно функциональногоотображения. Образом множества A  X относительно f : X  Yназывается множество f ( A)  { f ( x) | x  A} ; прообразом множестваB  Y называется множество f1( B)  {x  X | f ( x)  B} .Утверждение 2.5. Для любой функции f : X  Y и любых множеств A1 , A2  X справедливо: (а) f ( A1  A2 )  f ( A1 )  f ( A2 ) ;(б) f ( A1  A2 )  f ( A1 )  f ( A2 ) ; (в) f ( A1 \ A2 )  f ( A1 ) \ f ( A2 ) .Доказательство.

(а)y  f ( A1  A2 )  x  A1  A2 : y  f ( x)  y  f (x ),x  A1  y  f ( A1 ) x  A  x  A  y  f ( A )  y  f ( A1 )  f ( A2 ) ;122 y  f ( A1 )  f ( A2 ) y  f ( A1 )  x1  A1 : y  f ( x1 )yf(A)yf(A)xA:yf(x)12222 32 x  A1  A2 : y  f ( x)  y  f ( A1  A2 );(б) y  f ( A1  A2 )  x  A1  A2 : y  f ( x)  x  A1 ,x  A2 , y  f ( x)  y  f ( A1 ), y  f ( A2 )  y  f ( A1 )  f ( A2 ) ;(в) y  f ( A1 ) \ f ( A2 )  y  f ( A1 ), y  f ( A2 )  x  A1 :y  f ( x), x  A2  x  A1 \ A2 : y  f ( x)  y  f ( A1 \ A2 ) .Утверждение 2.6. Если функция f : X  Y инъективна, то справедливы равенства: (г) f ( A1  А2 )  f ( A1 )  f ( А2 ) ; (д) f ( A1 \ А2 )  f ( A1 ) \ f ( А2 ) .Доказательство.

(г) В силу утверждения 2.5(б), осталось доказать,что f ( A1  А2 )  f ( A1 )  f ( А2 ) . Действительно,y  f ( A1 )  f ( A2 )  y  f ( A1 ), y  f ( A2 )  x1  A1 , x2  A2 :y  f ( x1 ), y  f ( x2 )  (в силу инъективности функции f )  x1  x2  x  x  A1  A2 , y  f ( x)  y  f ( A1  A2 ).(д) В силу утверждения 2.5(в) осталось доказать, чтоf ( A1 \ А2 )  f ( A1 ) \ f ( А2 ) . Действительно, y  f ( A1 \ A2 )  x  A1 \ A2 : y  f ( x)  x  A1 , x  A2 , y  f ( x)  y  f ( A1 ) ,y  f ( A2 ) (предположим, что y  f ( A2 ) , тогда x  A2 :y  f (x)  f ( x)  y  f (x)  x  x  x  A2 , что противоречитусловиюx  A1 \ A2 )  y  f ( A1 ) \ f ( А2 ) .Утверждение 2.7.

Для любой функции f : X  Y и любых множеств B1 , B2  Y справедливо: (е) f(ж) f f11( B1  B2 )  f( B1 ) \ f11( B1 )  f11( B1  B2 )  f1( B1 )  f1( B2 );( B2 ); (з) f 1 ( B1 \ B2 ) ( B2 ) .Доказательство. (е) x  f1( B1  B2 )  f ( x)  B1  B2 f ( x)  B1  x  f 1 ( B1 )11  x  f ( B1 )  f ( B2 );1f(x)Bf(x)Bxf(B)122 33x  f 1 ( B1 )  f 1 ( B2 ) x  f 1 ( B1 )  f ( x)  B1  f ( x)  B1  B2 11 x  f ( B1 )  x  f ( B2 )  f ( x)  B2  x  f 1 ( B1  B2 ); (ж) x  f 1 ( B1  B2 )  f ( x)  B1  B2  f ( x)  B1 , f ( x)  B2  x  f1( B1 ), x  f1( B2 )  x  f 1 ( B1 )  f 1 ( B2 ) ; (з) доказывается аналогично (ж).Композиция функций.

Композицией двух функций g : X  Y иf : Y  Z называется функция fg : X  Z , определяемая равенством( fg )( x)  f ( g ( x)), x  X (т.е. fg  g  f ). Единичной (или тождественной) функцией e X : X  X называется функция, переводящая каждый элемент x в себя, т.е. x  X e X ( x)  x .Отметим некоторые свойства композиции функций.(а) f : X  Y fe X  f , eY f  f ; (б) если h : X  Y ,g : Y  Z , f : Z  V , то f ( gh)  ( fg )h ; (в) если g : X  Y ,f : Y  Z – биекции, то fg : X  Z – биекция.Доказательство (а) очевидно.

Докажем (б). Заметим, чтоf ( gh), ( fg )h : X  V . Осталось (см. определение равенства функций)сравнить значения этих функций на произвольном элементе x  X :[ f ( gh)]( x)  f [( gh)( x)]  f [ g (h( x))]  ( fg )[h( x)]  [( fg )h]( x). Докажем (в). Сюрьективность: {( fg )( x) | x  X }  { f ( g ( x)) | x  X }  f ( g ( X ))  f (Y )  Z . Инъективность: x1  x2  g ( x1 )  g ( x2 )  f ( g ( x1 ))  f ( g ( x2 ))  ( fg )( x1 )  ( fg )( x2 ) .Обращение функций.

Если f – инъективная функция видаf : X  Y , то бинарное отношение fной функцией вида f11 R f  X является биектив-: R f  X и называется обратной к f . Приэтом y  f ( x)  x, y  f  y, x  fУпражнение 2.4. Докажем, что f3411x f1( y) .– функция. Действительно,y  R f , x1 , x2  Xy, x1 , y, x 2  f1 x1 , y , x2 , y  f  f ( x1 )  y  f ( x2 )  x1  x2 .Упражнение 2.5. Докажем, что функция f1сюръективна. Оче-видно, что для любого бинарного отношения  выполняются равенства: D  R 1 , R  D 1 , а следовательно, R f 1  D f  X .Упражнение 2.6. Докажем, что функция fy1 , y 2  R f , f 1 ( y1 )  f 1 ( y 2 )  x  X . Тогда1инъективна. Пустьy1 , x , y2 , x  f 1  x, y1 , x, y 2  f , откуда, используя то, что f – функция,получаем y1  y 2 .Характеристическая функция множества.

Пусть U – непустоемножество. Для любого подмножества A множества U введем в рассмотрение характеристическую функцию множества A вида1, если x  A, UA : U  {0;1} , определяемую равенством  UA ( x )  0, если x  A.Упражнение 2.7. Докажем, что (a) UU ( x)  1 ; (б)  U ( x)  0 ; (в) UA ( x)  1   UA ( x) ; (г)  UAB ( x)   UA ( x)  BU ( x) ; (д)  UAB (x)   UA ( x)   BU ( x)   UA ( x)  BU ( x) ; (е)  UA\ B ( x)   UA ( x)   UA ( x)  BU ( x) .Решение.

Утверждения (а),(б) очевидны. Случай (в) обосновывается таблицей 2.1, в которой перечислены все возможные случаи относительно произвольного элемента x  U и во всех этих случаях леваячасть доказываемого равенства равна правой его части (см. совпадение двух последних столбцов):x Aданетx Aнетда UA (x)10Табл.

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

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