This is a possible answer, it is not mine, it is due to David Libert. So I'll quote it here and I'll present the link to it.

(Note: the restricted separation mentioned in the following quote is the same parameter free separation that I've presented here)

If I have not made a mistake, I can prove that there models of Z (Zermelo's)
set theory with separation replaced by your restricted form, satisfying that
there are countably many reals: that is there is a function from omega surjecting
onto all reals.

If that proof is correct, it does show there is indeed no proof of omega
uncountable using only your restricted separation axiom replacing the usual
separation axiom of Z.

I will begin by describing a construction of models of your restricted Z theory.
It is similar to the definition of Godel's L model, but weakened to correspond
to your weaker restricted separation axiom.

We begin at stage 0 (ordinal 0) with some initial transitive starting set T,
and consider the structure (T, epsilon) .

The next step of Godel's L would form all subsets of (T, epsilon) definable
in (T, epsilon) by formulas with parameters. Instead we throw in only subsets
of sets from the structure definable by pure formulas with only one variable
free: no side parameters. We also add explicitly pairs {x,y} and
the union axiom union(x) for all x,y since we lost these by restricting
the previous formulas.

At ordinal successor steps we do that same step to the last structure as
I just said on (T, epsilon). At limit ordinals take unions of all structures.

Iterate out to the successor ordinal of #T. This gives a stabilization,
where a formula on the resulting structure acting on the members of a set
has a uniform across that set relativization to a bounded stage which is
equivalent. This is like the proofs about Godel's L.

I want to find an instance of a construction as above producing a model of
restricted Z with P(omega) countable.

For simplicity of exposition, I will first do the easier case of explicitly
assuming Con(ZF), and then I will return to how to modify that argument
to be a proof in just ZF not assuming Con(ZF).

So to start, assume Con(ZF). So ZFC has a countable model M. (Godel's
L result to get ZFC model assuming Con(ZF)).

Use Cohen's forcing to produce M' model extending M making the original
reals^M countable.

Inside M', define T to be the transitive closure of the set of all
functions from omega onto reals^M. Do the construction I described above
inside M'.

This construction is purely definable in M'. Since I threw into T
all surjections and not merely a single generic surjection produced
by the forcing the definition of T does not depend on any parameters.

From the theory of forcing, when we collapse the reals to countable
as usual, any real definable in the resulting M' model in fact came
M the ground model.

Each successor step of my construction only added reals definable
from the previous structure, since the formulas doing separation
didn't use parameters. So in M', each real added at each successor
stage is definable in M' from the ordinal for that stage, since the
overall construction is M' definable.

The same forcing result, reals definable in M' from only an ordinal
parameter are in fact from M.

T put in only reals from M. And all later growth of my construction
only added M reals. So even though the construction went on in M',
since no parameters were used to define reals all the reals the
construction makes are from M.

T provided many surjections from omega to reals^M. So these are
in my construction. And since my construction never added any reals
from outside M, the Z model of my construction sees these as
surjecting onto its reals.

This concludes the Con(ZF) version of the argument.

Regarding arguing from just ZF. We only needed a fragemt of ZF,
out to some bounded (in the Levy hierarchy Sigma_n, n finite)
instances of replacement. ZF proves M models for such fragments,
specifically M models with enough ordinals to have the reflection
principal for all Levy level axioms from such a ZFC fragment.
This is enough to do a version of the theory of forcing for that
fragment.

So in meta theory ZF, you can have Levy-bounded ZF fragment models,
and forcing over them. So redo my argument above for M and M'
replaced by such fragments, and we can do everything in ZFC, without
needing Con(ZF).

So you can defeat Cantor's argument with your restricted separation.
But don't celebrate too much. This restricted separation theory is not
a reasonable system for set theory. It is too restricted.

Cantor's argument is so simple, and so broadly applicable. I think
it a lost cause to try to elude it. If you weaken things to avoid it,
you end up throwing out the baby with the bathwater.

Cantor's argument gives the diagonal real as a function from
{(n, n) | n in omega}.

To get the same diagonal real as an actual function from omega,
we would need to replace that index set by {n | n in omega}.

This trivial reindexing is defeated by the restriction on separation.
And that is the only way Cantor's argument fails.

10more comments