Timeline for Undecidability [sic] in set theory [per se]
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 15, 2011 at 21:56 | comment | added | Amit Kumar Gupta | @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. | |
| Dec 15, 2011 at 16:57 | comment | added | David Feldman | 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$. | |
| Dec 15, 2011 at 5:48 | comment | added | Amit Kumar Gupta |
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.
|
|
| Dec 15, 2011 at 5:45 | comment | added | Amit Kumar Gupta |
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]\}$?"
|
|
| Dec 15, 2011 at 3:46 | comment | added | David Feldman | 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. | |
| Dec 15, 2011 at 1:04 | history | answered | Andy Voellmer | CC BY-SA 3.0 |