I still have trouble to grasp the concept of a non-constructible set, my intuition is that we could "avoid" the non-constructibility of many of them if we assume we have "ordinal computers" extended with oracles for their halting problems, plus oracles for the new halting problems of these new extended machines, and all the oracles needed for the hierarchy of halting problems arising for the enhanced machines of the previous iteration. Assuming we can keep adding oracles for the new halting problems up to any arbitrarily high cardinal (actually I can imagine the halting oracle giving an answer for an ordinal machine that were able to run up to the entire class V). Assuming that were possible, the question is: There would be sets that will remain non-constructible even if we had such oracles? Wouldn't such oracles allow us to verify any non-constructible property in the same way that the hierarchy of halting Oracles for ordinary Turing machines empower them to "compute" incomputable reals?
-
$\begingroup$ Are you using the word "constructible" in the set-theorist's sense of Goedel's constructible universe (which is the sense of Koepke's and other's results on ordinal computation and the constructible universe) or in the sense of constructivism, the philosophy of mathematics concerned with non-classical logic? $\endgroup$– Joel David HamkinsCommented Mar 17, 2014 at 19:06
-
$\begingroup$ Constructibility of sets is not about making decisions. You cannot turn a set constructible by using more information. You probably want to know about relative constructibility as described on Wikipedia. $\endgroup$– Colin McLartyCommented Mar 17, 2014 at 19:08
-
$\begingroup$ Yes Joel, I was thinking about the set-theorist's sense of Goedel's constructible universe. I apologize to put this question on this forum because it seems too basic, actually I wanted to put it on Match exchange first but put it here by mistake, as I am still a "student" on these issues (I only come to this forum when I find that Math exchange people cannot give a satisfactory response because most of them (not all of course) are not familiar enough with these subjects. Should I migrate the question? Thanks $\endgroup$– Wolphram jonnyCommented Mar 17, 2014 at 19:16
-
$\begingroup$ The question reveals some sort of misunderstanding. Here is a suggestion, perhaps close to what you intend: Given a specific notion $T$ of ordinal computation, and an oracle $O$, we could define that a set is $(T,O)$-constructible iff it is "$T$-recursive in $O$". With Koepke's notion of ordinal computability, and $O=\emptyset$, the $(T,O)$-constructible sets are precisely the constructible sets in the sense of Gödel. We can call $L^{T,O}$ the collection of $(T,O)$-constructible sets, and your question appears to be how $L^{T,O}$ varies with $O$. You may want to add some details clarifying. $\endgroup$– Andrés E. CaicedoCommented Mar 17, 2014 at 19:39
1 Answer
I'm not sure exactly what you're asking, so maybe this is irrelevant, but let me give it a shot. When you're talking about "avoiding inconstructibility," it sounds like the picture of $L$ you have is roughly: the collection of all 'reasonably computable' sets. And you're asking, what happens if we alter the definition of 'reasonably computable'?
First of all, let me mention that different people may disagree about whether this is an accurate picture of $L$. The issue is that $L$ is really built hereditarily, at each stage throwing in all the definable subsets of the previous stage. There is no reference to computation anywhere here, unless you count first-order definability as a kind of computation. I do, but I'm not sure this is universal.
There is a natural way to 'strengthen' the construction of $L$: strengthen the logic used to pass from each layer to the next! That is, replace "first-order definable" with "$\mathcal{L}$-definable" for some stronger logic $\mathcal{L}$. For some interesting stuff along these lines, see Gödel's Constructible Universe in Infinitary Logics (A Possible Approach to HOD Problem).
(Another approach, less relevant I think but still worth mentioning, is via end extensions of the ground model $V$: it is a theorem of Barwise that any countable model of $ZFC$ has an end extension satisfying "$V=L$." So one can make every set constructible by 'strengthening' the construction of $L$ by making it longer, that is, by adding new ordinals. However, I would argue that you ought not to find this satisfying: the resulting end extension is not well-founded, so the new 'ordinals' added are not really ordinals, and so it's not clear that anything along the lines of what you're hoping for has really been accomplished.)
I think that what's going on is, you have an interesting picture of set-theoretic computations in your head, but a picture which does not jibe with what $L$ really is about. I recommend reading about the theory of $L$ in more detail; and in particular, try to phrase your intuitions (as in the OP) precisely, making clear exactly what you mean; this will help you understand, I think, what's going on with non-constructible sets.
