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

Filter by
Sorted by
Tagged with
22 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 ...
user avatar
21 votes
2 answers
762 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 ...
Wojowu's user avatar
  • 27.4k
19 votes
2 answers
2k 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 $...
Beau Madison Mount's user avatar
15 votes
1 answer
519 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, ...
Thomas Benjamin's user avatar
14 votes
3 answers
764 views

When is $A$ "$L$-ish" whenever $B$ is "$L$-ish"?

My question is about a variant of the usual notion of relative constructibility, $\le_c$ (which an earlier version of this question confusingly denoted "$\le_L$"), in set theory. Fix a ...
Noah Schweber's user avatar
14 votes
2 answers
415 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 ...
Todd Eisworth's user avatar
14 votes
1 answer
941 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 \...
jonasreitz's user avatar
  • 1,166
13 votes
1 answer
921 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 ...
user avatar
13 votes
1 answer
592 views

Can $L$ be defined without parameters?

If we omit parameters in the definition of $L$ would the result still be $L$? That is, we define a successor stage $L_{\alpha+1}$ in the constructible universe $L$, without including parameters; as: $...
Zuhair Al-Johar's user avatar
12 votes
2 answers
426 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 $\...
Mohammad Golshani's user avatar
12 votes
2 answers
927 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 $...
Ari Herman's user avatar
10 votes
2 answers
690 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$ ...
Nick Thomas's user avatar
10 votes
1 answer
431 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 = \...
Gro-Tsen's user avatar
  • 29.9k
10 votes
1 answer
846 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 ...
Mohammad Golshani's user avatar
10 votes
0 answers
344 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 ...
Asaf Karagila's user avatar
  • 38.1k
9 votes
2 answers
593 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 ...
Todd Eisworth's user avatar
9 votes
1 answer
337 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 ...
喻 良's user avatar
  • 4,191
8 votes
3 answers
689 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 ...
Mike Battaglia's user avatar
8 votes
3 answers
506 views

Elementary countable submodels in Gödel's universe

By the downward Lowenheim-Skölem theorem we can find two countable ordinals $\alpha < \beta$ such that $L_\alpha \prec L_{\omega_1}$ and $L_\beta \prec L_{\omega_1}$. That is, $L_\alpha$ and $L_\...
Johan's user avatar
  • 501
8 votes
1 answer
562 views

Is $\mathsf{ZFC+V=L}$ consistently $\omega$-complete?

This was previously asked and bountied on MSE: For brevity, let $T$ be $\mathsf{ZFC+V=L}$. Say that an extension of $\mathsf{ZFC}$ is $\omega$-complete iff it has exactly one $\omega$-model up to ...
Noah Schweber's user avatar
8 votes
1 answer
777 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 ...
Keith Millar's user avatar
  • 1,242
8 votes
1 answer
313 views

Forcing a unique $\Delta_3^1$ generic real

I know Jensen developed a forcing notions in $L$ that adds a unique, minimal and $\Delta_3^1$ $L$-generic real. In his paper Definable sets of minimal degree he says that Solovay had already shown the ...
Lorenzo's user avatar
  • 2,134
8 votes
1 answer
586 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 ...
Noah Schweber's user avatar
7 votes
1 answer
377 views

If $L_\alpha \vDash ZFC$, then do we have $L_{\alpha+1} \vDash \alpha\text{ is inaccessible}$?

Here we choose the definition of "is a cardinal" as there is no surjective map from a smaller ordinal to it. It's easy to prove that, if $L_{\alpha+1} \vDash\ \alpha\text{ is inaccessible}$, ...
Reflecting_Ordinal's user avatar
7 votes
2 answers
463 views

Can countable ordinals start gaps of every order in the constructible universe?

Define "$\alpha$ starts a gap of order $n+1$ and length $\beta$" iff $\mathcal P^n(\omega)\cap (L_{\alpha+\beta}\setminus L_\alpha)=\emptyset\land\forall\gamma\in\alpha: L_\alpha\setminus L_\...
Boris Dimitrov's user avatar
7 votes
1 answer
106 views

Why do $\pi$ and $\bigcup$ commute for Gödel-closed extensional classes?

Jech exercise 13.3 states: If $M$ is closed under Gödel operations and extensional, and $\pi$ is the transitive collapse of $M$, then $\pi(G_i(X,Y))=G_i(\pi X,\pi Y)$ for all $i=1,\ldots,10$ and all $...
Chad Groft's user avatar
  • 1,189
7 votes
1 answer
317 views

Which one of the following two ordinals is larger?

We say that $\alpha$ is $\Sigma_n$-extendable (to $\beta$), if there is $\beta>\alpha$ such that $L_\alpha$ is a $\Sigma_n$ elementary submodel of $L_\beta$. First ordinal: the least $\alpha_0$ ...
Reflecting_Ordinal's user avatar
7 votes
1 answer
406 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 ...
Johan's user avatar
  • 501
7 votes
1 answer
381 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 ...
Noah Schweber's user avatar
7 votes
1 answer
280 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 ...
M Carl's user avatar
  • 437
7 votes
1 answer
307 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&...
azarel's user avatar
  • 173
6 votes
1 answer
360 views

For which ordinals do we have $V_\alpha = L_\alpha$?

Some elements of $L$ become constructible only in levels higher than its rank level. So I ask: Let $V$ be such that $V = L$. For which ordinals $\alpha$ do we have $V_\alpha = L_\alpha$? Indeed, we ...
Alfredo Roque Freire's user avatar
6 votes
1 answer
254 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$}\},$$ ...
Noah Schweber's user avatar
6 votes
1 answer
501 views

Parameter-free effective cardinals

In the paper "Effective cardinals and determinacy in third order arithmetic" by Juan Aguilera, effective cardinals is defined. I'm curious about its little variation, parameter-free ...
Reflecting_Ordinal's user avatar
6 votes
1 answer
455 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 ...
Archimondain's user avatar
6 votes
0 answers
196 views

Consistency strength of Sy Friedman's result about admissibility spectrum

A result by Sy Friedman in his book "fine structure and class forcing", is that, assume $0^\sharp$ exists, there exists a real number R such that the ordinals admissible in R (called $\...
Reflecting_Ordinal's user avatar
6 votes
0 answers
427 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 ...
Trevor Wilson's user avatar
5 votes
3 answers
772 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)$ ...
Zuhair Al-Johar's user avatar
5 votes
2 answers
403 views

Models of second-order arithmetic closed under relative constructibility

I know little to nothing about second-order arithmetic and its subsystems. However, I would like to understand when a model of (a subsystem of) second-order arithmetic ($\mathsf{Z}_2$) is downward ...
Lorenzo's user avatar
  • 2,134
5 votes
1 answer
401 views

Is this relation about elementary embedding transitive?

For ordinals $\alpha<\beta$, we say $\alpha<_{el}\beta$, if there is an elementary embedding with domain $L_\beta$ and critical point $\alpha$. Is $<_{el}$ transitive?
Reflecting_Ordinal's user avatar
5 votes
1 answer
362 views

Sequences of projecta in the constructible hierarchy

For $n$ a natural number, $\alpha$ an ordinal, let $\rho(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 ...
M Carl's user avatar
  • 521
5 votes
1 answer
222 views

Inner model with a $\mathit{\Delta}^1_3$-good well-ordering of the reals

The constructible universe $L$ has some nice properties: $L$ has a $\mathit{\Delta}^1_2$-good well-ordering of $\mathbb{R}$. (Gödel, Addison) For any $\mathit{\Sigma}^1_2$ formula $\varphi(x)$ and a ...
Lorenzo's user avatar
  • 2,134
5 votes
1 answer
395 views

Height of diamond

Assume $V=L$. Let $\alpha$ be the least ordinal such that there is a $\Diamond_{\omega_1}$-sequence in $L_\alpha$. It's obvious that $\omega_1 < \alpha < \omega_2$. Do we have some better ...
Reflecting_Ordinal's user avatar
5 votes
1 answer
470 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 $...
Jesse Elliott's user avatar
5 votes
2 answers
367 views

Terminology for ordinals whose constructible level is the least one satisfying some formula

An ordinal $\alpha$ is "meta-definable" by some formula $\varphi$ without free variables if: $$ \begin{cases} L_\alpha \models\varphi \\ \forall\beta < \alpha \, L_\beta \not\models \...
Johan's user avatar
  • 501
5 votes
1 answer
378 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 ...
M Carl's user avatar
  • 437
5 votes
1 answer
404 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 \...
Archimondain's user avatar
4 votes
2 answers
285 views

Can local $0^\#$ exists in L?

Assume $0^\#$ exists and there is an inaccessible cardinal. Are there two transitive sets $M,N$ s.t. $M\in N,M\vDash ZF+V=L[0^\#],N\vDash ZF+V=L$?
Reflecting_Ordinal's user avatar
4 votes
1 answer
897 views

A doubt about the Gödel condensation lemma

To simplify the notation, assume $V=L$. We have $\lvert V_{\omega_{1}} \rvert=\aleph_{\omega_{1}}$ and $\lvert H(\aleph_{1})\rvert=\aleph_{1}$, so in particular $V_{\omega_{1}} \models \exists x \...
Ândson josé's user avatar
4 votes
1 answer
226 views

Existence of a non-$Q$-set without the perfect set property

We have the following theorem: Suppose $\omega_1^L=\omega_1$ then there exists a $\Pi_1^1$ subset of reals without the perfect set property Moreover, under the same hypotheses, we can prove actually ...
Lorenzo's user avatar
  • 2,134