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

(е) Нумеруем элементы множества A   AiiNаналогично случаю (в), но пропуская встречающиеся ранее элементы.Тогда каждый элемент из A получит свой номер, а следовательно множество A является либо конечным (например, в случае Ai  A1 приi  2 ), либо бесконечным, а следовательно, счетным.Задача 5.6. Доказать, что если множество A бесконечно и B – конечное или счетное множество, то A  B ∼ A .Решение. Поскольку A бесконечно, то в A можно выделить последовательность { a n | n N} (см. задачу 5.3).

Обозначим B1  B \ A .Тогда A  B  A  B1 , A  B1   . Возможны два случая (см. задачу725.4): (а) B1  {b1 ,..., bm } – конечное множество; (б) B1  { bn | n N} –счетное множество. В случае (а) определим отображение  : A  A  B1  A  B следующим образом: x  A \ { a n | n N}  ( x)  x, идля каждого x  a n , n  N, отображение x   (x) осуществляется всоответствии с таблицей (верхний элемент отображается в нижний):a1…ama m1am 2…b1…bma1a2…Указанное отображение является биекцией вида  : A  A  B ,откуда A  B ∼ A .

В случае (б) определим отображение  : A  A  B1  A  B следующим образом: x  A \ { a n | n N}  ( x)  x,и для каждого x  a n , n  N, отображение x   (x) осуществляется всоответствии с таблицей (верхний элемент отображается в нижний):a1a2a3a4…a 2 n1a2n…a1b1a2b2…anbn…Указанное отображение является биекцией вида  : A  A  B ,откуда A  B ∼ A .Задача 5.7. Доказать, что если множество A бесконечно и несчетно, а B – конечное или счетное множество, то A \ B ∼ A .Решение. Заметим, что A \ B – бесконечное множество.

Действительно, предположив, что A \ B – конечное множество, получаем, чтоA  ( A \ B)  ( A  B) – конечное или счетное множество (см. задачи5.2(б),5.4,5.5(а)), что противоречит исходным условиям. ОбозначимB1  A  B, A1  A \ B. Тогда A1  B1  ( A \ B )  ( A  B)  A . Множество B1  A  B  B является конечным или счетным (см. задачи5.2(а),5.4), множество A1 является бесконечным, а следовательно (см.задачу 5.6), A  A1  B1 ∼ A1  A \ B .73Задача 5.8. Доказать, что если множества A1 ,..., An (n  1) – счетны, то множество A1      An счетно.Решение. Заметим, что достаточно рассмотреть случай, когдаn  2 , поскольку A1      An  (...(( A1  A2 )  A3 )      An ) .

ПустьA1  { a n | n N}. Покажем, что множество A1  A2 счетное. Заметим,что A1  A2   ({an }  A2 ) , откуда (см. задачу 5.5(г)) и следует счетnNность этого множества.Задача 5.9. Доказать, что (а) множество целых чисел Z счетное;(б) множество рациональных чисел Q счетное; (в) множество рациональных чисел сегмента [a, b] счетное при a  b .Решение. (а) Z = { a n | n N}, где a1  0, a2n  n, a2n1  n, n  N; (б) Q=   {m / n} (см. также задачи 5.9(а),5.5(г)); (в) МножествоnN mZQ [ a ,b ]  [a, b]  Q является подмножеством счетного множества Q и поэтому либо конечное, либо счетное (см.

задачу 5.4). Покажем его бесконечность. Пусть a1 ,b1 – рациональные числа такие, что a  a1  b1  b(укажите алгоритм выделения чисел a1 , b1 , используя десятичное разложение числа c  (a  b) / 2 ; см. решение задачи 5.14). Пустьan  a1  (b1  a1 ) / n, n  N. Тогда an  [a1 , b1 ]  [a, b], n  N, т.е.{an | n  N} является бесконечной последовательностью из Q [ a ,b ] .Задача 5.10.

Доказать, что множество всех конечных последовательностей, состоящих из элементов счетного множества A , счетно.Решение. Множество всех конечных последовательностей элементов из A есть  A n , которое является счетным (см. задачи 5.5(г), 5.8).nNЗадача 5.11.

Доказать, что множество всех конечных подмножествсчетного множества A  { a n | n N} счетно.74Решение. Обозначим Ak  {a1 ,..., ak }, k  N. Тогда множествовсех конечных подмножеств множества A есть  2 kNA k A k 1 A   2  k \   2   j , которое является счетным (см. задачу 5.5(в)).kN  j 1Задача 5.12. Доказать, что множество всех многочленов от однойпеременной с целыми коэффициентами счетно.Решение. Указанные многочлены являются выражениями видаa0  a1 x  a2 x 2  ...  an x n , где n  {0}  N , ai  Z, i  {0,1,..., n}, аследовательно, каждое такое выражение взаимно-однозначно задаетсяупорядоченным набором a0 , a1 ,..., an , т.е. множество этих многочленов эквивалентно счетному множеству  Z n (см.

задачи 5.5(г), 5.8,nN5.9(а)).Задача 5.13. Доказать счетность множества всех алгебраическихчисел, т.е. чисел, являющихся корнями многочленов от одной переменной с целыми коэффициентами.Решение. Заметим, что x  n, n N, – многочлены с целыми коэффициентами, а следовательно, множество алгебраических чиселвключает в себя множество натуральных чисел, а поэтому является бесконечным. С другой стороны, в силу задач 5.5 (е), 5.12, множество алгебраических чисел является либо конечным, либо счетным, а поэтому,в силу своей бесконечности, является счетным.Задача 5.14. Доказать, что любое множество попарно непересекающихся открытых интервалов на действительной прямой не болеечем счетное.Решение.

Заметим, что для любого интервала (a, b), где a  b,можно выделить рациональное число c( a ,b )  (a, b) , поэтому рассматриваемое множество интервалов эквивалентно подмножеству множества рациональных чисел, а следовательно, является счетным или конечным (см. задачи 5.4, 5.9(б)). Для выделения рационального числаc( a ,b )  (a, b) действуем следующим образом. Пусть c  (a  b) / 2,75c  c0 , c1c2 ...

– десятичное разложение числа c , где c 0 – целая частьэтого числа. Тогда последовательность рациональных чиселc(n)  c0 , c1c2 ...cn , n  N , сходится к c при n  , а следовательно,для некоторого n0  1 выполняется c(n0 )  (a, b).Задача 5.15. Доказать, что множество точек разрыва монотоннойфункции на действительной оси является конечным или счетным.Решение.

Пусть x p – точка разрыва монотонной функции ( x), x R . Рассмотрим a  lim  ( x), b  lim  ( x) . В силу моноx  x p 0x x p 0тонности  (x) эти пределы существуют и конечны, а в силу того, чтоx p – точка разрыва и  (x) – монотонная функция, имеем a  b.

Аналогично рассуждению из задачи 5.14 можно поместить между a и b рациональное число q( x p )  (a, b) и для разных точек разрыва эти рациональные числа будут различными. Множество выделенных такимобразом рациональных чисел {q( x p )} эквивалентно множеству точекразрыва {x p } и является подмножеством счетного множества Q , а следовательно, конечно или счетно (см. задачи 5.4, 5.9(б)).Задача 5.16. Доказать, что (0;1) ∼ [0;1] ∼ (0;1] ∼ [0;1) .Решение.

Докажем, что (0;1) ∼ [0;1] . Рассмотрение остальных случаев аналогично. Обозначим an  1 /( n  1), n  N . Заметим, чтоan  (0;1), n  N . Определим биективное отображение  : (0;1)  [0;1]следующим образом: (а) x  (0;1) \ {an | n  N}  ( x)  x; (б) дляx  an , n N, отображение  задается в соответствии с таблицей:xa1a2a3a4…an… (x)01a1a2…a n2…Задача 5.17.

Доказать, что (0;1) ∼ R.Решение. Положим  ( x)  ctgx, x  (0;1). Тогда отображение : (0;1)  R , очевидно, является биективным.76Задача 5.18. Доказать, что [0;1]2 ∼ [0;1] .Решение. В силу теоремы Кантора-Бернштейна достаточно описать инъективное отображение множества [0;1]2 в [0;1] (описание инъективного отображения [0;1] в [0;1]2 очевидно). Пусть  a, b  [0;1]2 ,a  0, a1a2 ...

, b  0, b1b2 ...(5.1)– десятичные разложения чисел a, b  [0;1] . При этом для однозначности десятичного разложения исключаем из рассмотрения конечные десятичные разложения вида 0, c1c2 ...ck , а также бесконечные разложениявида 0, c1c2 ...ck 00... . Единственно возможным для таких чисел оставляем разложение с бесконечной последовательностью числа 9 (можнопоступать и наоборот).

Например, вместо 0,25 (или 0,2500... ) используем разложение вида 0,24999… . Для числа 0 единственным десятичным разложением является 0,000… . Опишем инъективное отображение  : a, b  [0;1]2  [0;1] , где a, b удовлетворяют (5.1): (a, b)  0, a1b1a2 b2 ...an bn ...

.(5.2)Инъективность этого отображения очевидна (если  (a, b)   (c, d ), тоиз (5.2) следует, что a  c, b  d ).Задача 5.19. Доказать, что [0;1] ∼ [0;1]n , где n  N.Решение. Аналогично решению задачи 5.18.Задача 5.20. Доказать, что множество [0;1] несчетно.Решение. Предположим, что можно занумеровать числа из [0;1] ,т.е. [0;1]  {an | n  N} . Рассмотрим десятичные разложения чисел an(как и в задаче 5.18 делаем их однозначными):a1  0, a11a12 a13 ...