wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Help: a direct proof of Independence of AC
        
(Message started by: beibeibee on Nov 2^nd, 2004, 1:49am)

Title: Help: a direct proof of Independence of AC
Post by beibeibee on Nov 2^nd, 2004, 1:49am

In Kunen’s Set Theory, P245, there is a famous problem (settled by Cohen):

show that consis(ZF) \to consis(ZF+\neg AC).

I know a proof of using symmetric model, which however is involved in the Boolean-valued models.

Kunen gives a hint to use p.o. straightforwardly to construct a submodel of generic model, in which ZF holds but AC fails. I have tried to handle this proof in these days, but I find it is out of my control ???. Is there anyone telling me that the main idea of such a proof. Many thanks!

Title: Re: Help: a direct proof of Independence of AC
Post by kiochi on Oct 31^st, 2006, 5:18pm

You can use cohen forcing to construct a model in which AC fails. Take a model R so that:

M is a submodel of R is a submodel of M[G]

where M is a (countable) transitive model of ZFC and M[G] is a generic extension of M.

Many suitable models exist. For example, take M=L and extend M by adding countably many Cohen generic reals. Then it's fairly easy to construct a model R so that R is a transitive model of ZF in which the reals are not well-orderable.

Title: Re: Help: a direct proof of Independence of AC
Post by Michael_Dagg on Nov 1^st, 2006, 5:37pm

Example?

Title: Re: Help: a direct proof of Independence of AC
Post by kiochi on Dec 24^th, 2006, 4:59am

Sorry, was gone for a while. I'll use a bit (but try to limit the use) of TeX markup, hope that's OK.

So we w.t.s con(ZF) ==> con(ZF+¬AC).

Assuming con(ZF) we can take c.t.m. M of ZFC (given a model of ZF, theory of constructibility implies there also exists model of ZFC).

Now define a poset B := {f:f is a finite fcn, f\subseteq \omega_1 \times 2} ordered by \supseteq (with largest element \emptyset).

Let G be B-generic over M.

define a fcn * by recursion, setting x*={(y*,1):y \in x}

Constructible Heirarchy (let D is the definable powerset operation, tc is the transitive closure):

L_{0}^{AB} = tc(A)

L_{a+1}^{AB}= D(L_{a}^{AB}, C)

L_{a}^{AB} = \bigcup_{b <a} L_{b}^{AB} for limit ordinals a

L_{a}(A) = L_{a}^[B}\emptyset}

lL(A) = \bigcup_{a an ordinal} L_{a}(A)

It's straightforward (if tedious) to show that lL will be a model of ZF.

Now let N = lL(Pwrst(\omega))^{rel M[G]}

(that is, relativized to the model M[G])

So N is a model of ZF, and in fact AC fails in N.

Suppose to the contrary that AC holds in N. Let k = |Pwrst(\omgea)|.

(again the ^{rel __} means relativized to __).

Ok, so the statement (k*=|Pwrst(\omega)|)^{rel lL(Pwrst(\omega)} holds in M[G], so let p \in G be s.t. p forces (|k*|=|Pwrset(\omega)|)^{rel lL(Pwrst(\omega)}.

So 1 forces (|k*|=|Pwrst(\omega)|)^{rel lL(Pwrst(\omega)} with respect to our poset B.
OK, so this really takes some proof :P, but I haven't let details get in my way so far, so let's not start ;)

Now define a new poset. Let j be the least cardinal greater than |k|, now set D := {f:f is a finite fcn, f\subseteq \j \times 2} (ordered like B)

Now 1 forces (|k*|=|Pwrst(\omega)|)^{rel lL(Pwrst(\omega)} with respect to D.

Let H be D-Generic over M. Then (|k*|=|Pwrst(\omega)|)^{rel lL(Pwrst(\omega)} holds in M[H]. So a bijection exists in M[H] from Pwrst(\omega) to k. But |Pwrst(\omega)| ? j, contra.

whew. Yea I left out a bunch of details let me know if you need any in particular ... but that's the rough sketch.

--k