3
$\begingroup$

I'd like to know of any natural undecidable (not independent!) families of questions in the theory of ZF or ZFC where the questions seem naturally to belong to set theory qua set theory.

(This follows up on my question The purview or scope of set theory qua set theory which didn't get much traction.)

I don't know how to formalize the distinction here-- I'd appreciate help there too -- but I wouldn't accept, say, "the word problem in finitely presented groups" because that has nothing directly to do with the sort of things set theorists usually talk about: higher cardinalities, ordinals, filters, elementary embeddings, etc.,

On the other hand, something like an undecidable family of cardinal arithmetic questions would suit me fine (but not if we know the independence of all of them from ZF(C) - that decides their status within the theory).

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ What is the motivation for this question? $\endgroup$
    – user9072
    Commented Dec 14, 2011 at 21:10
  • 2
    $\begingroup$ I'm confused about what precisely you're looking for: would, for instance, the problem "Is a given notion of forcing proper?" qualify? How about "does the singular cardinal hypothesis fail for all singular strong limit cardinals of cofinality $<\kappa$ but $>\lambda$?" as $\kappa, \lambda$ vary through the ordinals? I don't understand, in particular, your distinction between "undecidable" and "independent." $\endgroup$
    – Noah Schweber
    Commented Dec 14, 2011 at 21:41
  • 1
    $\begingroup$ Would, for instance, the problem "Is a given notion of forcing proper?" qualify? At very least, you would need to specify for me some natural recursive family of notions of forcing. (Natural means that, say, you don't by fiat attach proper forcing notions to halting Turing machines and inversely.) And then tell me what makes the question of properness undecidable. $\endgroup$
    – David Feldman
    Commented Dec 14, 2011 at 22:24
  • 2
    $\begingroup$ @quid A partial answer that probably won't satisfy you. I'm collecting materials for a set theory course. Students often confuse undecidability with independence, so I want examples, preferably characteristic of set theory per se. More generally, I'd like to know to what extent modern set theory naturally raises its own characteristic algorithmic questions. $\endgroup$
    – David Feldman
    Commented Dec 14, 2011 at 22:32
  • 1
    $\begingroup$ Thank you for the elaboration; seems like a fine motivation. $\endgroup$
    – user9072
    Commented Dec 15, 2011 at 1:27

2 Answers 2

Reset to default
2
$\begingroup$

There can be no examples like you are asking for. If a family of statements indexed by natural numbers is 'undecidable' in the sense that there is no recursive procedure for deciding whether the $n$-th statement is true ('true' in whatever model of ZFC we are working in), then infinitely many of those questions must be independent of ZFC. For, if only finitely many were independent, then the following would be a decision procedure for all the others: Run through all ZFC-proofs until you prove the statement or its negation.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I have no problem with: "If a family of statements indexed by natural numbers is 'undecidable' in the sense that there is no recursive procedure for deciding whether the n-th statement is true ('true' in whatever model of ZFC we are working in), then infinitely many of those questions must be independent of ZFC." But that's equally true of Diophantine equations or words in finitely presented groups. I just want an example like those, except that the individual questions should seem, at least prima facie, like purely set-theoretic issues. $\endgroup$
    – David Feldman
    Commented Dec 15, 2011 at 3:46
  • 2
    $\begingroup$ What Andy's saying is that independence is unavoidable. This is even the case in the word problem for groups. The word problem for a finite presentation $\langle x_1,\dots,x_n \ |\ R_1,\dots,R_m\rangle$ can be formalized as follows: First, fix an (effective) enumeration $w_1, w_2, \dots$ of words in the generators. Let $\mathrm{GA}$ be the group axioms. The question becomes, "Is the following set recursive: $\{i\ :\ \mathrm{GA}\mbox{ decides the formula }[R_1 \wedge \dots \wedge R_m \rightarrow w_i = e]\}$?" $\endgroup$
    – Amit Kumar Gupta
    Commented Dec 15, 2011 at 5:45
  • 1
    $\begingroup$ For the answer to be "No" it's trivially necessary that said set is not all of $\mathbb{N}$, so in particular, for some $i$, $[R1 \wedge \dots \wedge R_m \rightarrow w_i = e]$ must be independent of $\mathrm{GA}$. The right interpretation of your question is: Find natural, effective list of genuinely set-theoretic statements $\phi_1, \phi_2, \dots$ such that $\{i\ :\ \mathrm{ZFC}\mbox{ decides }\phi_i\}$ is not recusrive. $\endgroup$
    – Amit Kumar Gupta
    Commented Dec 15, 2011 at 5:48
  • $\begingroup$ I don't understand why you think that's better than, or even essentially different from my (implicit) formulation (see my last paragraph): Find natural, effective list of genuinely set-theoretic statements $ϕ_1,ϕ_2,…$ such that $i:ϕ_i$ is a theorem of $ZFC$ is not recursive. Sure, if a certain $ϕ_i$ does not occur as a theorem, that will leave two possibilities: 1) theoremhood for the negation of ϕ_i; 2) independence of $ϕ_i$. $\endgroup$
    – David Feldman
    Commented Dec 15, 2011 at 16:57
  • $\begingroup$ @David, it's essentially the same as the question in your comment here. Indeed, if you had a procedure to compute independence, then you could combine that with the (partially computable) procedure for determining provability vs. disprovability of decidable sentences (the "run through all proofs" procedure) to get a procedure that computes theoremhood. My formulation is no different from what your intended question was, but I think my formulation is harder to misinterpret. $\endgroup$
    – Amit Kumar Gupta
    Commented Dec 15, 2011 at 21:56
0
$\begingroup$

If you look at "families" in a more general sense there are many examples. For example, the set of $x \in 2^\omega$ that are the graph of a well ordering of $\omega$. This set is well known to be $\Pi^1_1$ complete, and in particular is not decidable (i.e. lightface $\Delta^0_1$). I think that being well ordered is a purely set-theoretic problem.

This can also be put into a countable setting by replacing the set above with a slightly less natural set, Kleene's $\mathcal{O}$, of all natural numbers that are indices of computable well-orderings of $\omega$.

There are many similar examples in descriptive set theory.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Now that I've gotten up to speed a little concerning Kleene's {\em O}, I guess I don't agree yet that "being well ordered is a purely set-theoretic problem." (On the other hand, being well-orderable, yes.) Your example seems to belong directly to the theory of computation, as distinct from set theory. Whatever the importance of Kleene's {\em O} to mathematicians (proof theorists, right?), the question whether some specific $n$ belongs to Kleene's {\em O} doesn't strike me as "natural," if for no other reason, because of dependence on the particular coding. $\endgroup$
    – David Feldman
    Commented Dec 15, 2011 at 6:52
  • $\begingroup$ Kleene's $\mathcal{O}$ is of the same Turing degree as the set of ''e'' such that $\phi_e$ is a computable well-ordering of $\omega$. In the latter case there is not the same explicit coding. However, in the example from my first paragraph there is essentially no coding at all, it is literally the set of graphs of well-orderings of $\omega$. $\endgroup$
    – Carl Mummert
    Commented Dec 15, 2011 at 12:41

You must log in to answer this question.

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