[FOM] Hume's principle and the axiom of choice

[Harvey Friedman]

Reply to Shapiro 8:01 PM 5/14/03.
>
>First, a reminder on what Hume's principle (HP) is.  Let F and G be 
>monadic, second-order variables and let # be a name of a function 
>from items of type F,G to objects (i.e., items in the range of the 
>first-order variables).  HP is the following sentence
>
>(F)(G)[#F=#G iff EQU(F,G)],
>
>where EQU is the second-order statement that there is a function 
>mapping the F's one to one onto the G's.  It is abbreviated, "F is 
>equinumerous with G".
>
>George Boolos observed that HP is satisfiable on any infinite set. 
>His proof makes use of the axiom of choice, however.  What George 
>noted is that HP is satisfiable on any infinite, well-ordered set. 
>The number of sizes of subsets of aleph-l is the maximum of aleph-0 
>and l, which is less than or equal to aleph-l.  So we can interpret 
>the #-function symbol.
>
>I wondered if this use of choice is necessary.  For example, is it 
>consistent with ZF that HP is not satisfiable on the continuum.
>

THEOREM 1. If ZF is consistent then there is a model M of ZF such 
that the number of internal subsets of omega of M is externally 
countable, and the number of internal sets of subsets of omega of M 
has externally continuumly many equivalence classes under the 
equivalence relation "being of the same internal cardinality in M". 
Furthermore, if there is a countable transitive model of ZF then 
there is a countable transitive model of ZF with these properties.

Here is a more detailed statement.

THEOREM 2. Let M be a countable model of ZF. There is a model M' of 
ZF such that
i) M is a submodel of M';
ii) M,M' have the same internal ordinals;
iii) the number of internal subsets of omega in M' is externally countable;
iv) there is an internal set of subsets of omega, S, in M', which is 
closed under internally finite symmetric differences, such that all 
external subsets of S that are closed under internally finite 
symmetric differences, lie in M' (see remark);
v) furthermore, if two such external subsets of S are of the same 
internal cardinality in M', then there symmetric difference must have 
only internally finitely many elements under internally finite 
symmetric difference.

REMARK: Since we are being more general than countable transitive 
models, "lie in M'" means "has a representative in M'" in the obvious 
sense.

To give an idea of how this is done, let us simplify matters a little 
by assuming that we are dealing with countable transitive models of 
ZF only.

We start with a ctm M of ZF. The idea is to first Cohen generically 
add to M, the closure under finite symmetric difference of a new 
(externally countable) set of subsets of internal omega that is 
closed under symmetric difference. Call this S and the model M[S]. 
Then using Cohen generic technology, one can then add absolutely all 
subsets of S that are fixed under finite symmetric differences, 
yielding the desired model M'. Then using more Cohen generic 
technology, one can verify that the internal partial one-one maps 
from S mod finite symmetric differences, into S mod finite symmetric 
differences, are rather trivial. They are all the identity modulo 
finite symmetric differences, with finitely many exceptions modulo 
internal finite symmetric differences.

>
>Second question.  What happens to HP when it is interpreted on V (so 
>that F and G range over proper classes)?  (n.b., anybody who finds 
>talk of proper classes incoherent or silly should stop reading.)

THEOREM 3. If ZF is consistent then there is a model M of NBG such 
that the number of internal sets of M is externally countable, and 
the number of internal classes of M has externally continuumly many 
equivalence classes under the equivalence relation "being of the same 
internal cardinality in M". Furthermore, if there is a countable 
transitive model of ZF then there is a countable transitive model of 
NBG with these properties.

We can easily modify the earlier construction, although it is a bit 
safer to start with a countable model M of ZF + V = L (much less is 
needed, but so what?). We will even arrange that no new sets are 
added when we pass to M'.

First add a generic class S of classes, closed under internally set 
symmetric differences, without adding any new sets, and take the 
model of NBG so generated over M. This is done by using set 
conditions. Then show that one can add absolutely all subclasses of 
this S that are closed under internally set symmetric differences, 
again not adding any new sets, and still preserving NBG. Finally, one 
has to verify that the internal partial one-one maps from S mod 
internal set symmetric differences, into S mod internal set symmetric 
differences, are all the identity modulo internal set symmetric 
differences, with an internally set number of exceptions modulo 
internal set symmetric differences.