Talk:Cantor–Bernstein–Schroeder theorem

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Mid Priority  Field: Foundations, logic, and set theory

Contents

[edit] Translation of parts from german article

In the german article de:Cantor-Bernstein-Schröder-Theorem, which I translated from the english version, I added a visualization of the map h.

Someone might want to translate the image displayed at that article into english and look over this trial of a translation, and then integrate it into the english article.

Here comes my translation of the section "Veranschaulichung" in the german article.

(Before that, I added a little remark on the map h.)

Note, that this definition of h is nonconstructive, in the sense that there exists no general method to decide in finitely many steps for any given sets A, B and injections f, g, if an element x of A lies in C or not. For special sets and maps this might of course be possible.

Visualization

The definition of h can be visualized with the following diagram.

(Then the diagram) [1]

Displayed are parts of the (disjoint) sets A and B together with parts of the mappings f and g. If you interpret the set A union B together with the two maps as a directed graph, then this bipartite graph has several connected components.

These can be divided into four types: pathes extending infinitely to both directions, finite cycles of even length, infinite paths starting in the set A, and infinite paths starting in the set B (the path passing through the element a in the diagram is infinitely long into both directions, so the diagram contains one path of every type). In general it is not possible to decide in finitely many steps, what type of path a given element of A or B belongs to.

The set C defined above contains precisely the elements of A which are part of an infinite path starting in A. The map h is then defined in such a way, that for every path it yields a bijection of the elements of A onto the elements of B direct before or after it in the path. For the both-side infinite path and for the finite cycles, we choose to map every element to its predecessor in the path.

Hope this will be of use. --SirJective 10:54, 29 Oct 2003 (UTC)

Still hope someone might take a look at it... :-( --SirJective 19:36, 13 Jun 2004 (UTC)
I now copied this section into the article (and corrected some minor mistakes). The image still needs to be translated, and I will do it as soon as someone tells me the correct english words in the context of graph theory. --SirJective 15:45, 1 Aug 2004 (UTC)

imho, "One can then check that h : A → B is the desired bijection." is not really clear. Don't you think that more details may be necessary to understand this proof ? What do you think about the french article ?

[edit] Alternative presentation

The Cantor-Berstein-Schröder theorem is one that many people find difficult to understand intuitively. At present, I think the sketch proof is not quite as clear as it could be, and the helpful diagram is not used as effectively as it could be. How about this presentation, formalising the intuitive approach which provides a more complete proof that is well illustrated by the diagram?

Assume without loss of generality that A and B are disjoint. For any a in A or b in B we can form a unique two-sided sequence of elements that are alternatively in A and B, by repeatedly applying f and g to go right and g − 1 and f - 1 to go left (where defined).
\cdots \rightarrow f^{-1}(g^{-1}(a)) \rightarrow g^{-1}(a) \rightarrow a \rightarrow f(a) \rightarrow g(f(a)) \rightarrow \cdots
For any particular a, this sequence may terminate to the left or not, at a point where f - 1 or g − 1 is not defined.
Call such a sequence (and all its elements) an A-stopper, if it stops at an element of A, or a B-stopper if it stops at an element of B. Otherwise, call it doubly-infinite if all the elements are distinct or cyclic if it repeats.
By the fact that f and g are injective functions, each a in A and b in B is in exactly one such sequence to within identity, (as if an element occurs in two sequences, all elements to the left and to the right must be the same in both, by definition).
By the above observation, the sequences form a partition of the whole of the disjoint union of A and B, hence it suffices to produce a bijection between the elements of A and B in each of the sequences separately.
For an A-stopper, the function f is a bijection between its elements in A and its elements in B.
For a B-stopper, the function g is a bijection between its elements in B and its elements in A.
For a doubly infinite sequence or a cyclic sequence, either f or g will do. (unsigned post from User:Elroch circa Feb 2006).
Great presentation! Finally I understood this proof. 88.152.251.205 16:34, 18 March 2006 (UTC)
I've used your proof in the Hebrew Wikipedia. 88.152.251.205 12:29, 25 March 2006 (UTC)
I am very pleased that you found this of use, and appreciate your feedback. Elroch 01:22, 27 March 2006 (UTC)
this argument is actually from Julius König.Kope 16:06, 2 September 2006 (UTC)

[edit] A supershort proof hiding infinite steps

There is a supershort proof that goes like this:

Let A and B be sets and f:A->B and g:B->A be functions. Then there is a subset A0 of B such that g(B-f[A0])=A-A0. If f and g are injevtive, it follows immediatly that h(x)=f(x) for x in A0 and else h(x)=g−1(x) is a bijection.

This proof has the virtue of avoiding infinite steps. The infinite steps are needed though in proving the first assertion. (Sry bout my mathematical syntax. I have only notepad ;) —The preceding unsigned comment was added by YohanN7 (talk • contribs) 18:59, 30 March 2007 (UTC).

[edit] alternative proof

I have an alternative proof which does not involve the use of inverse functions. I don't know whether it is worth adding to the article. I'd also need some help attributing the proof to the right source. I think it is from Boolos and Jeffrey's Computability and Logic... —Preceding unsigned comment added by 137.205.8.2 (talk • contribs)