User:IssaRice/Schröder–Bernstein theorem: Difference between revisions

Revision as of 04:56, 30 August 2020

questions:

are the ancestor proof and the iterated partition proof actually different, or do they just look different on the surface? btw this is a very nice writeup of the ancestor proof (much clearer than wikipedia's version); HT Satira. UPDATE: these are actually basically the same proof, just written in different notation.
what is the proof that uses axiom of choice, and how does choice simplify the proof?
is the result a fixed point result? (if so how can we phrase it as such?) or is it just that some of the proofs makes use of the fixed point ideas?

Unified notation

Let $A,B$ be sets. (In Tao's book we assume $A\subseteq B$ but this isn't the case in the other proofs.)

$f:A\to B$ (In Tao's book we assume that $f=\iota _{A\to B}$ is the inclusion map that sends each $x\in A$ to itself.)

$g:B\to A$

$C_{0}=A\setminus g(B)$

$C_{n+1}=(g\circ f)(C_{n})$ for all $n\geq 0$

$D_{0}=B\setminus f(A)$

$D_{n+1}=(f\circ g)(D_{n})$ for all $n\geq 0$ (In Tao's book, since $f$ is just the inclusion map and $g$ maps into $A$ , we have $f\circ g=g$ which is why Tao can write $D_{n+1}=g(D_{n})$ . Note that Tao uses "f" instead of "g" because his notation is different from everybody else's.)

@@ Line 7: / Line 7: @@
 ==Unified notation==
-<math>f : A \to B</math>
+Let <math>A,B</math> be sets. (In Tao's book we assume <math>A \subseteq B</math> but this isn't the case in the other proofs.)
+<math>f : A \to B</math> (In Tao's book we assume that <math>f = \iota_{A \to B}</math> is the inclusion map that sends each <math>x \in A</math> to itself.)
 <math>g : B \to A</math>
@@ Line 17: / Line 19: @@
 <math>D_0 = B \setminus f(A)</math>
-<math>D_{n+1} = (f \circ g)(D_n)</math> for all <math>n \geq 0</math>
+<math>D_{n+1} = (f \circ g)(D_n)</math> for all <math>n \geq 0</math> (In Tao's book, since <math>f</math> is just the inclusion map and <math>g</math> maps into <math>A</math>, we have <math>f \circ g = g</math> which is why Tao can write <math>D_{n+1} = g(D_n)</math>. Note that Tao uses "f" instead of "g" because his notation is different from everybody else's.)
 ==References==