Talk:Cantor-Bernstein-Schröder Theorem

From ProofWiki
Jump to navigation Jump to search

There seem to be some inconsistencies in Proof 3 which make it hard to understand this nice argument.

1. $C_S$ (and $C_T$) are defined by $C_S(A)=S\setminus A$ (and not by $P(S)\setminus A$)

2. $z:P(S)\to P(T)$ should by defined by $z(A)=C_S(g(C_T(f(A)))$

and the arguments which follow should be changed accordingly:

$A\subseteq B (\subseteq S) \implies f(A)\subseteq f(B) \implies C_T(f(A))\subseteq C_T (f(B))$ ...
Many thanks for that. You are quite correct. --prime mover 21:58, 1 November 2010 (UTC)

LEM

How appropriate is it to add the LEM template to this? It is used in Proof 5. Is it also used in the other proofs as well? (I'm not in a mindset to check.) --prime mover (talk) 21:23, 11 March 2013 (UTC)

Sometimes explicitly; sometimes implicitly. There's a discussion over on Math Overflow where some folks who know a lot more than I give reasons to believe the theorem is inherently non-constructive. --Dfeuer (talk) 21:30, 11 March 2013 (UTC)
Exercise for you then: identify the places where LEM is invoked in all 5 proofs of this theorem so we can justify putting LEM at the bottom. --prime mover (talk) 21:55, 11 March 2013 (UTC)
Proof 1 is sufficiently informal and incomplete that I have no idea what it's doing.
Proof 2 uses it explicitly.
Proof 3 uses Relative Complement of Relative Complement, whose proof is currently circular, but I'd bet a trout that it depends on LEM.
Proof 4 inspects the two cases of a repetition occurring or not occurring, which presumes LEM.
Proof 5 uses a lemma that uses it explicitly.

--Dfeuer (talk) 22:53, 11 March 2013 (UTC)

The proof of Relative Complement of Relative Complement is not circular as far as I can see (and I've traced proof 2 all the way). It probably hinges on Set Difference with Set Difference is Union of Set Difference with Intersection which appears to be some De Morgan law combined with LEM, in its core. — Lord_Farin (talk) 08:00, 12 March 2013 (UTC)
Sorry for coming in late. 't Had been resolved already (as this was the only one on my watchlist, I hadn't noticed the stuff on the other talk pages). — Lord_Farin (talk) 11:38, 12 March 2013 (UTC)

Merge?

I now see that the Proof 6 I just added is essentially the same as Proof 3, except that Proof 6 factors out the Knaster-Tarski Lemma/Power Set, uses different notation, and goes into somewhat more detail about why $h$ is a bijection. Should these proofs be merged? If so, how? --Dfeuer (talk) 18:01, 1 April 2013 (UTC)

My suggestion would be to add the invocation of Knaster-Tarski Lemma into Proof 3, leaving that notation the same, and then removing proof 6. Your hobbit proof might also be implementable. --prime mover (talk) 19:43, 1 April 2013 (UTC)
Considering it. I find said notation very hard to read, which is a bit of a barrier. There do seem to be a couple ways to go about defining $h$ once the fixed point is chosen; that could become a lemma with two proofs. I just added a (very WIPish) form of proof 3/6 as an alternative proof of the lemma of proof 5. That trims things down in a different direction, largely because the identity mapping is infinitely flexible in choice of domain. --Dfeuer (talk) 20:32, 1 April 2013 (UTC)
Your reading problems: a physical or psychological disability, or just a matter of practice or patience? --prime mover (talk) 21:06, 1 April 2013 (UTC)
It's probably largely a matter of being much less familiar with the relative complement notation than the set difference notation, But the former also seems annoyingly asymmetrical while the latter often allows a mental substitution of $-$ to aide intuition. --Dfeuer (talk) 21:22, 1 April 2013 (UTC)
Nothing we need to worry about, then - just a matter of personal preference. That's cool. --prime mover (talk) 21:38, 1 April 2013 (UTC)

No to the rename

Using non-standard characters in titles makes them difficult to find in a search. --prime mover (talk) 19:24, 2 April 2013 (UTC)

Merge again

As far as I can see proofs 3 and 6 as well as 1, 2 and 4 are essentially the same. (Possibly using other methods and notation but the ideas are the same.) Should we merge them?

Also in most of them sources are given but not cited. Does this mean the general idea of the proof is taken from there? --Inconsistency (talk) 13:11, 4 June 2015 (UTC)

If it can be demonstrated that the proofs are "essentially" the same, then maybe it would be a good idea to tidy up this area. It will take some considerable work, though.
What do you mean "sources are given but not cited"? --prime mover (talk) 15:58, 4 June 2015 (UTC)
I will try to merge them then. Should I publish the proposed new versions as proofs 7,8,... respectively or should I keep them in my sandbox?
Please keep them in your sandbox for now. --prime mover (talk) 17:50, 4 June 2015 (UTC)
e.g. in proof 4: A reference is given but it is nowhere cited. Nor is somewhere stated what was taken from this book. --Inconsistency (talk) 17:34, 4 June 2015 (UTC)
"A reference is given but it is nowhere cited." The reference given indicates that the material on that page can be found, at least in part, in the source given. I don't understand what you mean. --prime mover (talk) 17:49, 4 June 2015 (UTC)

Adding Elegant Proof

I'd like to add the proof here (https://artofproblemsolving.com/wiki/index.php/Schroeder-Bernstein_Theorem). It is similar to proof 2 but seems like a more elegant formalization. Think I should add it as a separate proof?