User:IssaRice/Schröder–Bernstein theorem

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?
why does the wikipedia proof (and some of the other proofs) assume that A and B are disjoint? what does this buy us?
what is the point of having the set C in exercise 8.3.2? i don't see how we need this extra level of generality when applying this result in the following exercise, and the picture is simpler to draw in 8.3.2 itself.

In my proof at https://taoanalysis.wordpress.com/2020/09/01/exercise-8-3-2/ i think the proof of injectivity can be improved. consider dictinct x,y, and then split cases depending whether both are green, both are white, or one is green and the other is white. Also in the surjectivity proof, i am already doing this green/white split, so it would be good to mention those colors in the proof itself (just to help the reader).

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.)

Chain types

Type 1: Loop

Type 2: infinitely goes backwards without repeating

Type 3: Chain stops in A, with $g^{-1}$ eventually undefined.

3a: Elements of $C_{0}$ ( $g^{-1}$ immediately undefined)
3b: Elements of $\bigcup _{n=1}^{\infty }C_{n}$ ( $g^{-1}$ is defined, but eventually if you keep going $g^{-1}$ will be undefined)

Type 4: Chain stops in B, with $f^{-1}$ eventually undefined.

4a: Elements of $D_{0}$ ( $f^{-1}$ immediately undefined)
4b: Elements of $\bigcup _{n=1}^{\infty }D_{n}$ ( $f^{-1}$ is defined, but eventually if you keep going $f^{-1}$ will be undefined)

Definitions of the bijection in various books

Book of Proof: h(x) = f(x) if x is of type 3; $h(x)=g^{-1}(x)$ if x is of type 1,2,4.
Cornell page: h(x) = f(x) if x is of type 1,2,3; $h(x)=g^{-1}(x)$ if x is of type 4.
Tao: h(x) = f(x) if x is of type 1,2,3,4a (actually case 4a doesn't even exist in the Tao book since A is a subset of B); $h(x)=g^{-1}(x)$ if x is of type 4b
Wikipedia: h(x) = f(x) if x is of type 3; $h(x)=g^{-1}(x)$ if x is of type 4; h(x) can be defined either way if x is of type 1 or 2

Unified notation

Chain types

Definitions of the bijection in various books

References