Пусть f: X à Y и g: Y à Z – отображения множеств. Поскольку f и g – отношения, то определена их композиция g ° f(x) = g(f(x)). Если h: Z à T – отображение множеств, то h ° (g ° f) = (h ° g) ° f. Отношения IdX и IdY – функции, стало быть, определены композиции IdY ° f = f ° Idx = f. При X = Y определим f2 = f ° f, f3 = f2 ° f, …, fn+1 = fn ° f.
Отображение f: X àY называется инъекцей, если для любых элементов x1 ¹ x2 множества X справедливо f(x1) ¹ f(x2). Отображение f называется сюръекцией, если для каждого y ÎY существует такой x Î X, что f(x) = y. Если f является и сюръекцией, и инъекцией, то f называется биекцией. Легко видеть, что f – биекция тогда и только тогда, когда обратное отношение f-1 Í Y ´ X является функцией.
Будем говорить, что справедливо равенство |X| = |Y|, если существует биекция между X и Y. Положим |X| £ |Y|, если существует инъекция f: X à Y.
Теорема Кантора-Шредера-Бернштейна. Если |X| £ |Y| и |Y| £ |X| , то |X| = |Y|.
Доказательство. По условию, существуют инъекции f: X à Y и g: Y à X. Пусть A = g¢¢Y = Img – образ множества Y относительно отображения g. Тогда
(X A) Ç (gf)¢¢(X A) = Æ,
(gf)¢¢(X A) Ç (gf)2¢¢(X A) = Æ, …,
(gf)n¢¢(X A) Ç (gf)n+1¢¢(X A) = Æ, …
Рассмотрим отображение j: X à A, заданное как j(x) = gf(x), при
x Î (X A) È (gf)¢¢(X A) È (gf)2¢¢(X A) È …, и j(x) = x в остальных случаях. Легко видеть, что j – биекция. Искомая биекция между X и Y будет равна g-1 ° j.