Упорядоченные множества и универсальная алгебра (вводный курс). Гуров С.И. - 24 стр.

UptoLike

ВУЗ: 

МГУ | Москва

Составители: 

Рубрика: 

Теорема 1.17. Отображение f : X → Y — сюръекция если и только если для любых
двух отображений g
1
, g
2
из Y в некоторое множество Z
f ¦ g
1
= f ¦ g
2
⇔ g
1
= g
2
.
Доказательство. (⇒) Пусть f — сюръекция из множества X в Y и для любых двух
отображений g
1
, g
2
из Y в Z справедливо f ¦ g
1
= f ¦ g
2
. Из того, что f — наложение
следует непустота f
#
(y) для любого y ∈ Y . Пусть x ∈ f
#
(y).
10
Тогда
g
1
(y) = g
1
(f(x)) = g
2
(f(x)) = g
2
(y) ,
что в виду произвольности элемента y влечёт g
1
= g
2
.
(⇐) Пусть для любых двух отображений g
1
, g
2
из Y в Z справедлива равносиль-
ность f ¦ g
1
= f ¦ g
2
⇔ g
1
= g
2
, но f не является наложением. Тогда найдётся элемент
y из области Y r Im(f). Зафиксируем в Y элемент y
0
6= Y и рассмотрим отображение
g
2
: Y → Y , определяемое условием
g
1
(t) =
½
t, если t 6= y ,
y
0
, если t = y .
Ясно, что g
1
6= id
Y
, в силу чего f ¦ g
1
6= f ¦ id
Y
. Однако для всех x ∈ X имеем
g
1
(f(x)) = f(x) = id
Y
(f(x)) .
Противоречие.
Свойства биекции позволяют описывать фундаментальные свойства множеств.
Теорема 1.18 (Кантора-Шрёдера-Бернштейна
11
). Если для двух множеств A и B су-
ществуют биекции θ
1
между A и подмножеством B и θ
2
между B и подмноже-
ством A, то существует биекция между A и B.
Доказательство. Обозначим A
0
= A и Im(θ
2
) = A
1
. Ясно, что можно считать A
0
⊃ A
1
и Im(θ
1
) ⊂ B, иначе теорема тривиально справедлива. Также ясно, что в этом случае A
и B — бесконечные множества.
Последовательное применение отображений, указанных в формулировке теоремы, да-
ёт взаимно однозначное отображение θ = θ
1
∗ θ
2
множества A
0
на своё подмножество
A
2
и A
1
⊃ A
2
. Обозначим θ(A
i
) = A
i+2
, i = 0, 1, 2 . . .. Получим цепочку строго содер-
жащихся друг в друге подмножеств A: A = A
0
⊃ A
1
⊃ A
2
⊃ . . ..
Обозначим C
i
= A
i
r A
i+1
, i = 0, 1, 2 . . . и C =
T
i>0
A
i
. По построению между
множествами C
0
, C
2
, . . . существует взаимно однозначное соответствие θ; то же и для
множеств C
1
, C
3
, . . ..
Построим теперь взаимно однозначное отображение ϕ между A
0
и A
1
. Положим
ϕ(x) =
½
θ(x), если x ∈ C
2i
, i = 0, 1, . . . ,
x, иначе
(см. рис. 2).
Таким образом, имеем взаимно однозначные соответствия A
ϕ
→ A
1
θ
−1
2
→ B и ϕ ∗ θ
−1
2
—
искомая биекция.
10
Заметим, что возможность указания такого x эквивалентна принятию аксиомы выбора (см. п. 2.1.4).
11
Теорема была приведена без доказательства в работе Кантора 1883 г. и доказана позднее Шрёдером
и Бернштейном.
24
Теорема 1.17. Отображение f : X → Y — сюръекция если и только если для любых
двух отображений g1 , g2 из Y в некоторое множество Z

                                 f ¦ g1 = f ¦ g2 ⇔ g1 = g2 .

Доказательство. (⇒) Пусть f — сюръекция из множества X в Y и для любых двух
отображений g1 , g2 из Y в Z справедливо f ¦ g1 = f ¦ g2 . Из того, что f — наложение
следует непустота f # (y) для любого y ∈ Y . Пусть x ∈ f # (y).10 Тогда

                            g1 (y) = g1 (f (x)) = g2 (f (x)) = g2 (y) ,

что в виду произвольности элемента y влечёт g1 = g2 .
    (⇐) Пусть для любых двух отображений g1 , g2 из Y в Z справедлива равносиль-
ность f ¦ g1 = f ¦ g2 ⇔ g1 = g2 , но f не является наложением. Тогда найдётся элемент
y из области Y r Im(f ). Зафиксируем в Y элемент y0 6= Y и рассмотрим отображение
g2 : Y → Y , определяемое условием
                                      ½
                                        t,    если t 6= y ,
                             g1 (t) =
                                        y0 , если t = y .

Ясно, что g1 6= idY , в силу чего f ¦ g1 6= f ¦ idY . Однако для всех x ∈ X имеем

                                g1 (f (x)) = f (x) = idY (f (x)) .

Противоречие.
      Свойства биекции позволяют описывать фундаментальные свойства множеств.

Теорема 1.18 (Кантора-Шрёдера-Бернштейна11 ). Если для двух множеств A и B су-
ществуют биекции θ1 между A и подмножеством B и θ2 между B и подмноже-
ством A, то существует биекция между A и B.

Доказательство. Обозначим A0 = A и Im(θ2 ) = A1 . Ясно, что можно считать A0 ⊃ A1
и Im(θ1 ) ⊂ B, иначе теорема тривиально справедлива. Также ясно, что в этом случае A
и B — бесконечные множества.
   Последовательное применение отображений, указанных в формулировке теоремы, да-
ёт взаимно однозначное отображение θ = θ1 ∗ θ2 множества A0 на своё подмножество
A2 и A1 ⊃ A2 . Обозначим θ(Ai ) = Ai+2 , i = 0, 1, 2 . . .. Получим цепочку строго содер-
жащихся друг в друге подмножеств A: A = A0 ⊃ A1 ⊃ T             A2 ⊃ . . ..
   Обозначим Ci = Ai r Ai+1 , i = 0, 1, 2 . . . и C = i>0 Ai . По построению между
множествами C0 , C2 , . . . существует взаимно однозначное соответствие θ; то же и для
множеств C1 , C3 , . . ..
   Построим теперь взаимно однозначное отображение ϕ между A0 и A1 . Положим
                          ½
                            θ(x), если x ∈ C2i , i = 0, 1, . . . ,
               ϕ(x) =                                               (см. рис. 2).
                            x,    иначе

                                                                          ϕ   θ −1
                                                                2
   Таким образом, имеем взаимно однозначные соответствия A → A1 → B и ϕ ∗ θ2−1 —
искомая биекция.
 10
   Заметим, что возможность указания такого x эквивалентна принятию аксиомы выбора (см. п. 2.1.4).
 11
   Теорема была приведена без доказательства в работе Кантора 1883 г. и доказана позднее Шрёдером
и Бернштейном.


                                                24

Страницы