# Questions tagged [constructibility]

This tag is for questions about Gödel's constructible universe $L$, and related constructions such as $L[X]$ and $L(X)$.

49
questions

**2**

votes

**1**answer

172 views

### On a particular proof of “if the sharp of every real exists and every club contains a club constructible from a real, then $\delta^1_2 = \omega_2$”

I am referring to the proof of (4) implies (1) in Theorem 3.16 of Woodin's The Axiom of Determinacy, Forcing Axioms, and the Nonstationary Ideal. His proof leverages on the fact that if the sharp of ...

**8**

votes

**1**answer

248 views

### On the utility of Silver machines

This question arises out of having Devlin's Constructibility [1] in my collection of books at home during the lockdown. Chapter IX of the book deals with Silver machines, which are presented as ...

**14**

votes

**2**answers

335 views

### Consequences of existence of a certain function from $\omega_1$ to $\omega_1$

In his book [1], Paul Larson remarks (Remark 1.1.22) that in L there is a function $h:\omega_1\rightarrow\omega_1$ such that for any countable elementary submodel $X$ of $V_\gamma$ (where $\gamma$ is ...

**1**

vote

**0**answers

142 views

### End-extension in Gödel's constructible universe

Given two ordinals $\alpha < \beta$, considering the subsets of Gödel's constructible universe, one say that $L_\beta$ is a $\Sigma_n$ end-extension of $L_\alpha$ (and $L_\alpha$ is an $\Sigma_n$ ...

**1**

vote

**2**answers

340 views

### Is the power set axiom essential for constructing L?

Take ZFC, remove axiom of Power set, and put instead of it the following axiom:
Axiom of Successor Cardinals: $\forall \kappa \exists x \forall \alpha ( \alpha \leq \kappa \to \alpha \in x)$
where "$...

**4**

votes

**1**answer

419 views

### Is ZFC interpretable in a kind of an extended form of second order arithmetic?

Informally the following theory is a kind of extension of second order arithmetic, where numbers are not limited to naturals, instead here we have formation of further numbers by setting limits on ...

**5**

votes

**1**answer

211 views

### Capturing the $\omega_1^{\mathrm{CK}}$-th stage of Gödel's constructible hierarchy

For an ordinal $\alpha$, let $L_\alpha$ be the $\alpha^{th}$ set of Gödel's constructible hierarchy and let $\omega_1^{\mathrm{CK}}$ be the first non-recursive ordinal or the first admissible ordinal ...

**2**

votes

**2**answers

293 views

### Question about Jech's proof of V = L implies GCH

On pg 190 of Jech's Set Theory, he proves V = L implies GCH. I understand it all except the following:
Thus let X ⊂ $ω_α$. There exists a limit ordinal δ>$ω_α$ such that X ∈ $L_δ$.
Let M be an ...

**4**

votes

**0**answers

131 views

### Can this reflective class theory interpret ZFC?

Reflective Set Theory $\mathsf{RfST}$ is formulated in first order predicate logic with extra-logical primitives of equality $``="$, membership $``\in"$, and a single primitive constant symbol $V$ ...

**0**

votes

**0**answers

141 views

### Is “ZF+ V=L” an upper limit theory for cardinal decidability (per its strength)?

{EDIT: this posting has been edited, the additional text is in italics}
If $\varphi, \psi$ are two parameter free formulas in the language of set theory $T$ such that there is a theorem of $T$ that ...

**1**

vote

**1**answer

158 views

### What is the strength of this strict constructible iterative hierarchy?

Begin with the empty set then construct the set of the empty set, then construct the set of all subsets of the latter set, then at each level of construction construct the next level as the set all ...

**5**

votes

**1**answer

311 views

### $\Delta^{1}_{2}$ and degrees of constructibility $\textbf{on sets}$

This is a follow-up to my question on $\Delta^{1}_{2}$ and degrees of constructibility of real numbers that was answered by the user "William", see here: Can $\Delta^{1}_{2}$ separate degrees of ...

**7**

votes

**1**answer

245 views

### Can $\Delta^{1}_{2}$ separate degrees of constructibility?

Suppose that $\phi(x)$ is a $\Delta^{1}_{2}$-formula (without parameters) and let $A:=\{x\subseteq\omega:\phi(x)\}$. It is clear that, e.g. if there are Cohen-generics over $L$, then $A$ cannot be the ...

**2**

votes

**1**answer

124 views

### Encoding sets in locally generic sets

Let $\alpha$ be an ordinal, and let $a\subseteq\alpha$ such that $\alpha$ is countable in $L[a]$. Moreover, let $\beta>\alpha$ be an ordinal such that, in $L[a]$, $\alpha$ and $\beta$ have the same ...

**7**

votes

**1**answer

408 views

### Is the smallest $L_\alpha$ with undefinable ordinals always countable?

Let $\mathfrak{t}$ be the least ordinal such that $L_{\mathfrak{t}}$ has undefinable ordinals; i.e. there is an $\alpha<\mathfrak{t}$ such that $L_{\mathfrak{t}}$ cannot define $\alpha$.
This ...

**18**

votes

**2**answers

1k views

### Does $V = \textit{Ultimate }L$ imply GCH?

In his Midrasha Mathematicae lectures ("In Search of Ultimate $L$", BSL 23 [2017]: 1–109), Woodin notes that $V = \textit{Ultimate }L$ implies $\textrm{CH}$ (Theorem 7.26, p.103). Is it known whether $...

**1**

vote

**1**answer

192 views

### Is there a 'Constructible Universe' that is a submodel of a non-transitive model of $ZF$?

In Barwise's book, Admissible Sets and Structures, the following statement is made (on pg. 8):
"...if $ZF$ is consistent, so is $ZF$ + "There is no transitive model of $ZF$"
He mentions this fact ...

**9**

votes

**1**answer

290 views

### Stability for the Gödel and Jensen hierarchies

Notations: Let $L_\alpha$ stand for the Gödel constructible hierarchy ($L_0=\varnothing$ and $L_{\alpha+1} = \mathrm{def}(L_\alpha)$ is the set of definable subsets of $L_\alpha$ and $L_\delta = \...

**-4**

votes

**2**answers

746 views

### Can only the constructible sets be proven to exist in $ZF$ without benefit of extra assumptions? [closed]

I am interested in asking the following question:
What sets can be proven to exist in $ZF$ without the benefit of extra assumptions? (Thanks to Toshiyasu Arai for inspiring me to ask this variation ...

**5**

votes

**0**answers

304 views

### Inaccessible cardinals and the perfect set property for coanalytic sets

I am wondering who proved the following fact:
($\ast$) If $\omega_1$ is not inaccessible in $L$, then there is an uncountable coanalytic set of reals without a perfect subset.
I have been unable to ...

**9**

votes

**1**answer

327 views

### Minimal cover v.s random reals

The following set theoretical question is inspired by a question from recursion theory:
Question: Is there an $L$-random real $r$ which is a minimal cover over another real $x$?
Where a minimal ...

**6**

votes

**1**answer

290 views

### Problem with definability in the constructible hierarchy

This is a rather technical question. I cannot find my mistake in a proof of the (obviously wrong) following sentence: Every countable ordinal is $\Sigma_2$-definable in $J_{\omega_1 + 1}$ by a formula ...

**14**

votes

**1**answer

457 views

### Category-theoretic characterization of $L$

Does there exist a characterization of Goedel's constructible universe $L$ in purely category-theoretic terms, or is constructibility an 'artifact' of material set theory? If, in fact, ...

**2**

votes

**2**answers

447 views

### What is the largest cardinal consistent with $ZFC$ + $V$=$L$?

What is the largest cardinal consistent with $ZFC$ + $V$=$L$? The reason for the question is this: under the assumption that all of 'ordinary mathematics' (as reverse mathematics understands the ...

**7**

votes

**1**answer

338 views

### How similar are large cardinals, over $L$?

EDIT: Joel's answer shows that no $\Sigma_2$ large cardinal property will do the job - however, $\Pi_2$ properties (such as unfoldability and its relatives) may still be useful.
Throughout this ...

**2**

votes

**1**answer

336 views

### Further research on $\mathrm L_{\infty}$

In the mathoverflow question , "Godel's Constructible Universe in Infinitary Logics (A Possible Solution to $HOD$ Problem), Prof Hamkins answered user46667's question 2
What is $\mathrm L_{\infty}$?...

**2**

votes

**0**answers

135 views

### When do wide initial segments ruin admissibility?

Suppose $\alpha$ is admissible and $\beta<\alpha$. We know that $L_\alpha$ is an admissible set (by definition), but adding subsets of $\beta$ to $L_\alpha$ might break admissibility: while set ...

**3**

votes

**1**answer

119 views

### Levels of L resembling each other, take 2

(Everything below is assuming $V=L$.)
Fix an uncountable regular cardinal $\kappa$, and let $$E_\kappa=\{\mu<\kappa: \mbox{there is an elementary substructure of $L_\kappa$ isomorphic to $L_\mu$}\}...

**6**

votes

**1**answer

238 views

### Fine structure question: when do levels of $L$ look “a lot” like each other?

(Everything is assuming $V=L$.)
Fix an uncountable regular cardinal $\kappa$, and let $$E_\kappa=\{\mu<\kappa: \mbox{there is an elementary substructure of $L_\kappa$ isomorphic to $L_\mu$}\},$$ ...

**7**

votes

**1**answer

463 views

### Is every ordinal potentially definable?

It is easy to see that, if $V\models\alpha>\omega_1^{CK}$, then $\alpha$ is not recursive in any forcing extension of $V$. The argument goes as follows:
The relation "$\Phi_e=r$" is $\Pi^0_2$.
The ...

**20**

votes

**2**answers

589 views

### Can $L$ be thin?

I have recently been wondering if the following is consistent with ZFC:
For every infinite ordinal $\alpha$: $|V_\alpha\cap L|=|\alpha|$.
Intuitively, this states that for $L$ is very "thin", in ...

**3**

votes

**0**answers

561 views

### Can there be ordinals larger than those contained in Ord, and if so, can they be used to extend the constructible universe $L$?

Can there be ordinals larger than those contained in Ord, the class of all ordinals,and if so, can these ordinals be used to extend the constructible universe $L$?
In a simplified form, my question ...

**5**

votes

**1**answer

342 views

### Simplest non-constructible set of integers compatible with the nonexistence of $0^\sharp$?

What is the simplest non-constructible set of integers (say, in the analytical hierarchy) that is compatible with the nonexistence of $0^\sharp$? In particular, can there still be a non-constructible $...

**10**

votes

**0**answers

319 views

### Is there a “hereditary” construction for $L$?

Recall that $L$, Godel's constructible universe is constructed by defining the following hierarchy:
$L_0=\varnothing$, for a limit ordinal $\delta$, $L_\delta=\bigcup_{\alpha<\delta}L_\alpha$, and ...

**10**

votes

**1**answer

791 views

### Harrington's unpublished note “The constructible reals can be anything”

Around 1974, Leo Harringto wrote an unpublished note entitled "The constructible reals can be anything", in which he proved that it is consistent that being $\Delta^1_n$ is the same as being ...

**12**

votes

**2**answers

704 views

### How necessary is Godel's Condensation Lemma

It seems that the Godel's Condensation Lemma is typically used to show that certain constructible sets will appear by some stage of the construction of $L$. For example in the proof that CH holds in $...

**2**

votes

**0**answers

120 views

### Does $\forall X \in L_{\kappa}: P(X) \subset L_{\kappa}$ hold in $L$

While working on an exercise in Jech's Set Theory, I tried to prove that if $V=L$, then $\forall X \in L_{\kappa}: P(X) \subset L_{\kappa}$, where $k$ is any cardinal. I was hoping someone could ...

**9**

votes

**2**answers

404 views

### When is $A$ “$L$-ish” whenever $B$ is “$L$-ish”?

My question is about a kind of relative constructibility in set theory.
Fix a countable transitive model $W\models ZFC$ which is much bigger than $L^W$. There is a natural way within $W$ to compare ...

**12**

votes

**2**answers

373 views

### Producing no non-constructible reals

The following is stated without proof in Shelah's book "Cardinal arithmetic" (page 276), and is attributed to Uri Abraham:
Suppose that $L[A], L[B]$ have no non-constructible reals and that $\...

**2**

votes

**1**answer

405 views

### Would a non-constructible set become constructible if we had oracles of arbitrarily high cardinality for the halting problems of ordinal computers?

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 ...

**21**

votes

**1**answer

2k views

### Gödel's Constructible Universe in Infinitary Logics (A Possible Approach to HOD Problem)

Gödel's constructible universe ($L$) is defined using definable power set operator in first order logic ($\mathcal{L}_{\omega ,\omega}$). One can produce such a universe in infinitary logics in ...

**7**

votes

**3**answers

472 views

### In $L$, does there exist a definable non-principal ultrafilter on $\mathbb{N}$

The axiom of constructibility $V=L$ leads to some very interesting consequences, one of which is that it becomes possible to give explicit constructions of some of the "weird" results of AC. For ...

**12**

votes

**1**answer

656 views

### V=HOD & The Height of the Large Cardinal Tree

As we know the assumption $V=L$ adds a restriction on the height of the large cardinal tree. Also there is a strict border like $0^{\sharp}$ exists such that all large cardinal axioms which are ...

**2**

votes

**1**answer

389 views

### What is the order type of $L$ with Godel's well ordering?

In some sense $Ord$ is a "proper class" ordinal. Unfortunately the notion of a proper class ordinal is not a straight forward generalization of the notion of "set" ordinals because the proper classes ...

**12**

votes

**0**answers

737 views

### Can a model of $V\neq L$ contain a class giving the $L$-ordering on all its sets?

This question is inspired by the excellent question by Douglas Ulrich When is $L$-Rank definable in inner models of $V=L$?
Suppose $M \in L$ is a countable model of $ZFC$, and furthermore suppose $M \...

**10**

votes

**2**answers

591 views

### Constructible models of New Foundations?

Hi all! Is there anything like Gödel's constructible universe for New Foundations?
More precisely, I would like a process for taking a model $M$ of NF, and using it to build a model $L \subseteq M$ ...

**5**

votes

**1**answer

370 views

### Higher computability : Constructive ordinal and $\Delta^1_1$ predicates

Everything I know on this subject comes from Sacks book : "Higher recursion theory"
Let $\mathcal{O^Y}$ be the set of codes for ordinals constructive in $Y$.
We should have the result that $A \...

**7**

votes

**1**answer

285 views

### Acceptability and Soundness of J-structures.

I would like an example of a J-structure $(J^A,B)$ which is not acceptable and one that is not 1-sound.
Edit:Let us recall that a structure $J^A_\alpha$ is acceptable if for every limit ordinal $ \xi&...

**4**

votes

**1**answer

284 views

### Sequences of projecta in the constructible hierarchy.

For $n$ a natural number, $\alpha$ an ordinal, let $p(n,\alpha)$ be the $n$-th projectum of $J_\alpha$, where $J$ is the Jensen hierarchy for $L$.
Call a finite sequence $s:=(x_1,\dots,x_m)$ of ...