FOM: Refuting the Power Shift Axiom Scheme

[JoeShipman@aol.com]

Consider the following set-theoretic formula:

Phi(X): The largest integer n such that |X|=|P^n(Y)| for some set Y is even.

In ZC one can prove that such an integer exists (of all the cardinals <|X| 
who have an iterated powerset with cardinality = |X|, take the least).  
Whenever X satisfies Phi, P(X) fails to satisfy it, refuting the Power Shift 
Axiom Scheme.

This argument uses full Choice (since you're assuming sets of cardinals have 
least elements).  More interestingly, if you're willing to use Replacement 
rather than Comprehension (that is, go from Z to ZF) you only need (a Class 
version of) AC_2 (choice for collections of two-element sets).  Define two 
cardinals j and k to be equivalent if there exist integers m and n with 
|P^m(j)|=|P^n(k)|.  This partitions the Directed Graph (I'm using capitals to 
show this is a proper Class) whose vertices are cardinals and whose edges are 
given by the exponentiation operation into connected components.  Within each 
component, declare two cardinals to be equivalent if the number of times you 
have to exponentiate each one to reach their lub has the same parity.  Now 
select from each component one of the two equivalence classes.

If a choice function for collections of 2-element sets could be given by a 
formula, then the above could (within ZF) turned into a formula which refutes 
the Power Shift Axiom Scheme.

How much Choice is needed to refute NF over Z and ZF?  If you have 
Replacement can you get a weaker form of Choice to refute NF?

-- Joe Shipman