3
$\begingroup$

Let C(x) be a formula belonging to the language of ZFC in which the variable "x" and no other variable occurs free. Suppose that (a sentence of this language equivalent to) the following statement, is provable in ZFC but not in ZF.

"There exists a non-empty set Q such that every element x of Q satisfies the formula C(x)"

QUESTION: What is the smallest cardinal number that such a set Q can (be proved in ZFC) to have?

I know of no examples of such a set Q having a cardinal number less than 2^(2^k) where k is the cardinal number of the contnuum. Examples of such sets Q are the set of all uncountable sets of real numbers that are non-measurable in the sense of Lebesgue or that contain no perfect subset.

Improve this question
$\endgroup$
4
  • $\begingroup$ What about a set Q containing just one element which is a non-measurable subset of the reals? Do you mean the set of all x satisfying C(x)? $\endgroup$
    – Sergei Ivanov
    Commented Apr 22, 2010 at 20:14
  • $\begingroup$ Sergei, even if he does mean all x, then my answer still gives a one-element set. $\endgroup$
    – Joel David Hamkins
    Commented Apr 22, 2010 at 20:29
  • $\begingroup$ But your answer isn't sporting! $\endgroup$
    – Simon Thomas
    Commented Apr 22, 2010 at 20:42
  • $\begingroup$ But it is optimal...But seriously, I am interested in the projective version. $\endgroup$
    – Joel David Hamkins
    Commented Apr 22, 2010 at 20:54

2 Answers 2

Reset to default
18
$\begingroup$

You probably won't like this, but the answer is cardinality 1.

Let C(x) be the statement, "x=0 and the Axiom of Choice holds".

ZF doesn't prove that any x satisifes C(x), since it doesn't prove AC. If AC fails, then no x can have C(x). Thus, ZF+¬AC proves that no x has C(x).

But ZFC proves that C(0) holds, and so it proves that Q={0} is the desired set.

Addendum:

The set { x | C(x) } is an indicator set for AC, in the sense that it is either 0 or 1, depending exactly on whether AC holds. A similar trick works to construct indicator sets for any assertion.

I have suggested that the question be focused on the possibility of projective statements C(x). A projective statement is one expressible in the language of second order number theory, with quantifiers over real numbers and natural numbers. Thus, the question would be whether there is a specific projective statement C(x) such that ZFC proves that Q = { x | C(x) } is nonempty, but ZF does not.

This version of the question is exactly equivalent to the question of whether ZFC is not conservative over ZF for projective sentences, since if there is a counterexample C(X), then the assertion $\exists x C(x)$ is provable in ZFC but not ZF, and if $\sigma$ is provable in ZFC but not in ZF, then the set {x | $\sigma$} is ZFC provably all of the reals, but ZF is consistent with this set being empty.

Therefore, the question amounts to: Is ZFC not conservative over ZF for projective statements?

I think it is not, but I don't have a counterexample.

Meanwhile, I can say that if one replaces ZF here with ZF+DC, looking at the difference between the full Axiom of Choice and the Axiom of Dependent Choices, rather than at the difference between full AC and no AC at all, then the answer is that it IS conservative. In this MO answer, I explained that ZFC is conservative over ZF+DC for projective sentences, and so if one replaces ZF with ZF+DC in the question, the answer would be no. But without DC, weird things can happen in the reals, and I'm not yet quite sure about it.

Improve this answer
$\endgroup$
7
  • $\begingroup$ In this case, the formula asserting that there is such a nonempty Q is exactly equivalent to AC. You could replace AC in this argument with any statement whatsoever; what you get is a kind of indicator set for the truth of that statement. It is empty when the statement fails, and it is 1 when the statement holds. $\endgroup$
    – Joel David Hamkins
    Commented Apr 22, 2010 at 20:05
  • $\begingroup$ I take this answer to show that you will want to revise your question. Probably it is natural to restrict the complexity of the statement C(x). For example, can there be a projective such C(x)? $\endgroup$
    – Joel David Hamkins
    Commented Apr 22, 2010 at 20:22
  • $\begingroup$ This is a really cool answer. $\endgroup$
    – Harry Gindi
    Commented Apr 22, 2010 at 20:27
  • $\begingroup$ @Joel: I'm thinking about C(x) = "x is a minimal uncountable ordinal". Is it projective? $\endgroup$
    – Sergei Ivanov
    Commented Apr 22, 2010 at 20:55
  • 1
    $\begingroup$ Sergei, I don't think that statement works, since ZF and ZFC both prove that $\omega_1$ exists. It also isn't projective. A projective statement is a statement about real numbers, with quantification only over reals and natural numbers. If you allow real parameters, you can build up the projective hierarchy this way, with the Borel sets at the bottom, and then taking projections and complements. $\endgroup$
    – Joel David Hamkins
    Commented Apr 22, 2010 at 21:01
8
$\begingroup$

Wilfrid Hodges has shown that it is consistent with ZF that there is an algebraic closure $L$ of the rational field $\mathbb{Q}$ with no nontrivial automorphisms. Obviously $|Aut(L)\smallsetminus \{1\}| = 2^{\aleph_{0}}$.

See: W. Hodges, Läuchli's algebraic closure of $\mathbb{Q}$. Math. Proc. Cambridge Philos. Soc. 79 (1976), no. 2, 289--297

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ Is that rigidity due to the fact that there are less functions in his model than in the usual one? I imagine there is a bijection between his $L$ and the usual algebraic closure, if there is any sense one can talk about such a bijection... $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Apr 22, 2010 at 20:10
  • 4
    $\begingroup$ I find this shocking and disturbing...so much so that I dug up the paper. It is available at math.uga.edu/~pete/Hodges76.pdf $\endgroup$
    – Pete L. Clark
    Commented Apr 22, 2010 at 21:50
  • 11
    $\begingroup$ «The reader may well feel he could have bought Corollary 10 cheaper in another bazaar» Best comment in a paper EVAR. $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Apr 22, 2010 at 22:04
  • 4
    $\begingroup$ Yes, this is shocking! Joel is right: L is not countable in that model of ZF. The basic idea goes back to Plotkin who showed that given any countably categorical theory T you can find a model of ZF with an model M of T such that the only subsets of M that exist are the T-definable subsets of M. This doesn't directly apply to the algebraic closure of Q since ACF_0 is not countably categorical, but Hodges showed that ACF_0 is still nice enough for the basic idea to work... $\endgroup$
    – François G. Dorais
    Commented Apr 22, 2010 at 22:14
  • 1
    $\begingroup$ Mariano, François is talking about the completion L there, not Q, which is always countable. We know that L is a countable union of countable sets, since we can enumerate the polynomials in Q[x] in a countable sequence, and the corresponding finite sets of their roots. But I guess in that model, we cannot uniformly choose among the particular ways to list these root sets. Very strange. $\endgroup$
    – Joel David Hamkins
    Commented Apr 23, 2010 at 11:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .