Bernstein-Schröder Theorem

  • #1
8
0
The theorem: Let ##X##, ##Y## be sets. If there exist injections ##X \to Y## and ##Y \to X##, then ##X## and ##Y## are equivalent sets.

Proof: Let ##f : X \rightarrow Y## and ##g : Y \rightarrow X## be injections. Each point ##x \in g(Y)⊆X## has a unique preimage ##y\in Y## under g; no ##x \in X-g(Y)## has one. Each point ##y \in f(X)⊆Y## has a unique preimage ##x \in X## under ##f##; no ##y \in Y-f(X)## has one.
Consider the two composition telescopes:
$$...\to X \to Y \to X \to Y \to X \to Y \to X$$
$$... \to Y \to X \to Y \to X \to Y \to X \to Y$$
Composed of alternating copies of ##f## and ##g##.
Peering through these telescopes from ##X## and ##Y##, we see that each ##x \in X## and each ##y \in Y## has a unique maximal sequence of preimages under alternating copies of the injections ##f## and ##g##, which we call their ancestry:

$$...\to y_{2k+1} \to x_{2k} \to ... \to x_5 \to y_4 \to x_3 \to y_2 \to x_1=x$$
and
$$...\to x_{2k+1} \to y_{2k} \to ... \to y_5 \to x_4 \to y_3 \to x_2 \to y_1=y$$

The ancestry of each ##x \in X## and each ##y \in Y## either has finite even length ##2k \geq 2##, finite odd length ##2k+1 \geq 1##, or infinite length. These properties give disjoint sets ##X_{even}, X_{odd},## and ##X_\infty## with union ##X##, and disjoint sets ##Y_{even}, Y_{odd},## and ##Y_\infty## with union Y.
And the injections restrict to the three injections:
$$f : X_{odd} \to Y_{even}$$
$$g : Y_{odd} \to X_{even}$$
and
$$f : X_\infty \to Y_\infty$$
that are surjective.
So they determine a bijection ##X \to Y##.
$$\blacksquare$$

At first I thought this might have meant that for every ##x \in g(Y)## there is either a finite composition of inverse images of ##x## and ##y##:
$$g^{-1}(f^{-1}(...g^{-1}(f^{-1}(y))...))=y$$
and
$$f^{-1}(g^{-1}(...f^{-1}(g^{-1}(x))...))=x$$
or there is no such finite composition, in which case ##x \in X_\infty## or ##y \in Y_\infty##
but such a sequence of preimages under f and g would always be of even length.
I am assuming by restricting f they mean ##f(x)## such that ##x \in X_{even}## etc., and similarly for g.
Why are they surjective though?
If some element ##x_n \in X## occurs in the sequence of preimages of ##x_1## under alternating copies of f and g, then it does not occur in any other sequence, so if we have another element ##x_2 \in X## (such that ##x_2 \ne x_1##, then ##x_2## is not in the first sequence at all.
I'm wondering why these restrictions are surjective.
What do they mean by maximal sequence of preimages/ancestry?
Perhaps it is the smallest sequence for no subsequence of which do we have an element of ##X## or an element of ##Y## being sent to itself?
Also ##f## and ##g## could be any injections, so why should their restrictions to the subsets ##X_{even},X_{odd},X_\infty⊆X## and ##Y_{even},Y_{odd},Y_{infty}⊆Y## be the functions
$$f : X_{odd} \to Y_{even}$$
$$g : Y_{odd} \to X_{even}$$
and
$$f : X_\infty \to Y_\infty$$
?
 

Answers and Replies

  • #2
stevendaryl
Staff Emeritus
Science Advisor
Insights Author
8,428
2,609
At first I thought this might have meant that for every ##x \in g(Y)## there is either a finite composition of inverse images of ##x## and ##y##:
$$g^{-1}(f^{-1}(...g^{-1}(f^{-1}(y))...))=y$$
and
$$f^{-1}(g^{-1}(...f^{-1}(g^{-1}(x))...))=x$$
or there is no such finite composition, in which case ##x \in X_\infty## or ##y \in Y_\infty##
If ##g^{-1}(f^{-1}(...g^{-1}(f^{-1}(y))...))=y##, then that means that ##y \in Y_\infty##. It means that you can keep going in either direction infinitely far (a cycle is a special case of an infinite chain). You only get a finite chain in the case where the last element in the chain (or first element, depending on how you are counting) has no pre-image.
 
Last edited:
  • Like
Likes Wendel

Related Threads on Bernstein-Schröder Theorem

Replies
23
Views
6K
  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
10
Views
4K
Replies
2
Views
1K
  • Last Post
Replies
1
Views
2K
Replies
8
Views
5K
Replies
9
Views
5K
Top