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

Соответственно, в рассматриваемом случае m, n N  {1,2,... } выполняется:x1 ,..., xm ≺ y1 ,..., y n  либо x1  y1 ; либо x1  y1 , m  1, n  2 ;либо m, n  2, x1  y1 , x2  y 2 ; либо x1  y1 , x2  y 2 , m  2, n  2 ;либо m, n  3 , x1  y1 , x2  y 2 , x3  y3 и т.д. Для упражнения расположите в лексикографическом порядке последовательности натуральных чисел:  1, 2, 3, 1 ,  2, 2, 1 ,  1, 1 ,  1 ,  1, 2, 1  .Задача 4.7. Показать, что, если A, A1 – частично упорядоченныемножества с частичными порядками ≼, ≼ 1 , соответственно, функцияf : A  A1 (кратко пишем f : ( A, ≼)  ( A ,≼ 1 )) осуществляет взаим66но-однозначное соответствие между множествами A, A1 , функция fявляется монотонной (т.е. x1 , x2  A x1 ≼ x 2  f ( x1 ) ≼ 1 f ( x2 ) ), тофункция f1: A1  A может не быть монотонной.Решение.

Пусть A  A1  {a, b, c} . Частично упорядочим множество A двумя способами, заданными диаграммами Хассе, изображенными на рис.4.5. Левая диаграмма соответствует частичному порядку, а правая – линейному порядку ≼ 1 . Пусть x  A f ( x)  x . Тогдафункция f : ( A, ≼)  ( A ,≼ 1 ) является монотонной, а функцияf 1  f : ( A, ≼ 1 )  ( A ,≼) не является монотонной, поскольку b ≼ 1 c ,но b и c не сравнимы по ≼ (т.е.f 1 (b)  b ≼ c  f 1 (c) не выполня-ется).Рис.4.5Определение. Пусть A , A1 – частично упорядоченные множества с частичными порядками ≼, ≼ 1 , соответственно. Тогда, если существует биективная функция f : A  A1 такая, что функции f , f1являются монотонными, то говорят, что f является изоморфизмом частично упорядоченных множеств ( A ,≼), ( A1 ,≼ 1 ).Задача 4.8.

Доказать, что (N,  ), (N,  ), где N = {1,2,...} – натуральный ряд, не изоморфны.Решение. В случае изоморфизма образ минимального элементаочевидным образом снова будет минимальным, максимального – максимальным, наименьшего – наименьшим, наибольшего – наибольшим.Но тогда частичные порядки (N,  ), (N,  ) не изоморфны, поскольку в67(N,  ) существует наименьший элемент, но отсутствует наибольший, ав (N,  ) – наоборот.Задача 4.9. Рассмотрим частичный порядок ≼ на множестве натуральных чисел N = {1,2,...} : k, m N 2k  1 ≺ 2m , т.е. любое нечетноечисло меньше любого четного, а множества четных и нечетных чиселупорядочены «естественным» образом, т.е.

бинарным отношением  .Доказать, что (N,  ), (N, ≼) не изоморфны.Решение. Предположим противное. Пусть существует изоморфизмf :( N,  )  (N, ≼) , и a  f 1 (2) . Тогда k N f 1 (2k  1)  a , аэто противоречит конечности множества {1,2,..., a} .Задача 4.10. Доказать, что любое непустое частично упорядоченное множество A изоморфно некоторой системе подмножеств множества A , упорядоченной включением  .Решение.

Пусть ≼ – отношение частичного порядка на A . Длялюбого элемента a  A обозначим Aa  {x  A | x ≼ a} . Очевидно, чтоa  A a  Aa . Рассмотрим отображение f : A  2 A такое, чтоa  A f (a)  Aa . Докажем инъективность этого отображения (а следовательно, биективность отображения f : A  f ( A) ). Пустьa, b  A, f (a)  f (b) . Покажем, что a  b . Действительно,Aa  f (a)  f (b)  Ab  a  Aa  Ab , b  Ab  Aa  a ≼ b , b ≼ a  a  b . Докажем теперь изоморфизм ( A ,≼), ( f (A) ,  ). (а) Еслиa, b  A, a ≼ b , то x  A x ≼ a  x ≼ b , а следовательно, f (a)  {x  A | x ≼ a}  {x  A | x ≼ b}  f (b) . (б) Обратно, если a, b  A,f (a)  f (b) , то a  Aa  f (a)  f (b)  Ab  a  Ab  a ≼ b .Тема №5. Равномощность множеств.

Счетные, континуальныемножества.Множество A называется эквивалентным множеству B (символически A ∼ B ) , если между A и B можно установить взаимно одно68значное соответствие, т.е. существует биекция  : A  B. Если множество A эквивалентно множеству B , то эти множества называются равномощными. Обозначим N n  {1,2,..., n}, где n  N, N  {1,2,...} – натуральный ряд. Каждое множество A , эквивалентное N n для некоторогоn  N, либо пустое, называется конечным, а n – числом элементовмножества A, при этом пишем A  n. Множество, не являющееся конечным, называется бесконечным. Каждое множество A , эквивалентноенатуральному ряду N, называется счетным. Каждое множество A , эквивалентное множеству действительных чисел R, называется континуальным.

Будем писать, что (а) A  B , если A ∼ B ; (б) A  B , еслиA ∼ B1  B ; (в) A  B , если | A || B | и A не эквивалентно B . Изсвойств биективных функций (см. тему №2 ) следует, что для любыхмножеств A, B, C A ∼ A (рефлексивность ∼); если A ∼ B , то B ∼ A(симметричность ∼); если A ∼ B , B ∼ C , то A ∼ C (транзитивность ∼).Для установления равномощности множеств часто используетсяТеорема Кантора-Бернштейна. Если A  B , B  A , то A ∼ B(см. задачу 5.35).ЗадачиЗадача 5.1. Доказать, что если существует сюръективная функция : A  B, то B  A .Решение. В силу сюръективности  каждому элементу b  Bможно поставить в соответствие произвольный элемент ab   1 ({b}).Обозначим A1  {ab | b  B}. Отображение  : B  A1 такое, чтоb  B  (b)  ab , будет, очевидно, биекцией (т.е.

B ∼ A1  A ), откуда и следует доказываемое утверждение.Задача 5.2. Доказать, что (а) всякое подмножество B конечногомножества A конечно; (б) объединение конечного числа конечныхмножеств конечно; (в) прямое произведение конечного числа конечныхмножеств конечно.69Решение. (а) Случаи A   или B   очевидны. Пусть A  n,где n  N. Тогда из B  A следует, что | B || A | n.(б) Пусть A1  n1  N,…, Ak  nk  N.

Тогда A1  ...  Ak  n1  ...  nk . (в) Пусть A1  n1  N,…, Ak  nk  N. Тогда (см. упkражнение 2.2)A1      Ak   ni .i 1Задача 5.3. Доказать, что из всякого бесконечного множества Aможно выделить счетное подмножество.Решение. Поскольку A бесконечно, то A    a1  A . ЕслиA \ {a1}  , то A  {a1} ∼ N1 , что противоречит бесконечности A ,следовательно, A \ {a1}  , откуда a2  A \ {a1} . Если A \ {a1 , a2 }  , то A  {a1 , a2 } ∼ N 2 , что противоречит бесконечности A , следовательно, A \ {a1 , a2 }  , откуда a3  A \ {a1 , a2 } и т.д. Таким образом, в результате описанного процесса мы выделим бесконечную последовательность попарно различных элементов a n , n  N, а следовательно, A  {an | n  N } ∼ N.Задача 5.4.

Доказать, что всякое подмножество B счетного множества A счетно или конечно.Решение. Пусть A  {an | n N } , B  A. Покажем, что B счетноили конечно. Пусть B не является конечным. Докажем, что B счетно.Заметим, что b  B b  A  i(b)  N: b  ai (b ) , т.е. B  {ai (b ) |b  B}.

Пусть b1  ai1 , где i1  min{i(b) | b  B}, b2  ai2 , где i2  min{i(b) | b  B \ {b1}}, b3  ai3 , где i3  min{i(b) | b  B \ {b1 , b2 }}, иk N bk  aik , где ik  min{i(b) | b  B \ {b1 ,..., bk 1}}. Заметим, что1  i1  i2  ...  ik  ... (где k  3 ), а следовательно, k  N k  ik .Покажем, что B  {bk | k  N } . Действительно, b  B b  ai (b ) , апоэтому при некотором k  i(b) b  aik  bk .70Задача 5.5. Доказать, что (а) если множество A является конечным, а множество B – счетным, то множество A  B является счетным; (б) если множества A и B являются счетными, то множествоA  B также является счетным; (в) если множества Ai , i  N, являютсяконечными, непустыми и попарно не пересекающимися, то множество Ai является счетным; (г) если множества A, i  N, являются счетiNными, то множество  Ai также является счетным; (д) если множестваiNAi , i  N, являются счетными или конечными и хотя бы одно из них является счетным, то множество  Ai – счетное; (е) если множества Ai ,iNi  N, являются конечными, то множество  Ai является счетным илиiNконечным.Решение.

(а) Производим нумерацию элементов множества A  Bследующим образом. Сначала нумеруем элементы множества A , затемпереходим к нумерации элементов множества B . Если очередной элемент множества B принадлежит A , то пропускаем его, в противномслучае присваиваем ему очередной номер. Тогда каждый элемент изA  B получит свой номер и множество A  B будет бесконечным(см.

задачу 5.2(а)), а следовательно, счетным.(б) Пусть A  {a1 , a2 ,...}, B  {b1 , b2 ,...} . Осуществляем обход (нумерацию) элементов множества A  B согласно рис.5.1. Если очередной элемент встречался ранее, то пропускаем его, в противном случае,присваиваем ему очередной номер. Тогда каждый элемент из A  Bполучит свой номер и множество A  B будет бесконечным (см.

задачу 5.2 (а)), а следовательно, счетным.Рис.5.171(в) Множество  Ai является бесконечным, поскольку содержитiNпоследовательность {an | n  N } , где a n – произвольный элемент из An .Покажем его счетность. Последовательно нумеруем элементы первогомножества, затем второго, затем третьего и т.д. В результате каждыйэлемент из  Ai получит свой номер.

(г) Пусть Ai  {ai1 , ai 2 ,...}, i  N.iNОсуществляем обход бесконечного множества  Ai (см. задачу 5.2(а))iNсогласно рис. 5.2. Если очередной элемент встречался ранее, то пропускаем его, в противном случае присваиваем ему очередной номер. Тогдакаждый элемент из  Ai получит свой номер.iNРис.5.2(д) Действуем, как и в случае (г). При этом, если некоторое множество конечно, то добавляем бесконечное множество пустых элементов.Соответственно при назначении очередного номера не учитываем проход по пустым элементам.