[FOM] Hume's principle and the axiom of choice
Harvey Friedman
friedman at math.ohio-state.edu
Thu May 15 02:21:37 EDT 2003
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.
More information about the FOM
mailing list