Wednesday, 16 August 2006

set theory - Does Cantor-Bernstein hold for classes?

This is an interesting question. I think there are some issues which the others did not mention yet. But I'm not an expert at all, I might be wrong. Please leave me a comment!



In the following, I work in $ZF$. Thus, a class is just a formula. There are some constructions and relations of sets which directly carry over to classes. For example $A=B$ means that the formulas of $A,B$ are equivalent.



Let's sketch the proof for classes. Let $A,B$ classes, $f : A to B$, $g : B to A$ injective maps. Define the classes $A_n subseteq A, B_n subseteq B$ recursively by $A_0=A, B_0 = B, A_{n+1} = g[B_n], B_{n+1}=f[A_n]$. Then $h : A to B$, defined by $f$ on $cap_n A_n cup (cup_n A_{2n} setminus A_{2n+1})$ and by $g^{-1}$ in the rest, is well-defined and a bijection.



Unions, cuts, images of functions etc. are not the problem. But what about the recursion? What we really need here is a recursion scheme for classes. Actually there is a theorem which might be called the transfinite recursion scheme for classes:




Let $R$ be a well-founded and set-like relation of the class $A$ and $F : A times V to V$ a function. Then there is a function $G : A to V$, such that for all $x in A$



$G(x)=F(x,G|_{{y in A : y R x}})$.




However, note that the images of $G$ are sets, not proper classes. We can't use that theorem here.



I think we need a meta-theorem stating that the above also holds when $V$ is replaced by the set of formulas and $R=mathbb{N}$. Also, the meta-world should be able to talk about functions. But this is not plausible at all, since the resulting formula won't have to be finite, right?



For example, try to define a formula $G(n)$ recursively by $G(0)=phi_0$ (doesn't matter what $phi_n$ is) and $G(n)=G(n-1) wedge phi_n$. Why should there be a formula $psi(n,x)$ such that $psi(n,x) Leftrightarrow wedge_{i=0}^{n} phi_i$? I think we need a rather mighty logical calculus for that.



Also note that Francois' great answer here (proving Schröder-Bernstein without the existence of the set $omega$) also causes problems when you want to write down the formula for the part "...$exists s : {0,...,n} to A$ ...". Perhaps there is really no bijection between the two classes mentioned above (class of all singletons, and class of all 2-element sets)?

No comments:

Post a Comment