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
0 votes
0 answers
138 views

How does the cardinality of a set and its powerset compare in the hereditarily rank-concordant constructible world?

Working in the constructible universe "$L$", if we define two kinds of ranks for any constructible set $x$, one being the ordinal index of the first $L_\alpha$ where $x$ appears as a subset ...
Zuhair Al-Johar's user avatar
5 votes
2 answers
402 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
2 votes
1 answer
243 views

Inner model for KP and a Well-Ordering of the Reals

It is well known that Gödel proved the following theorem: $\mathsf{ZFC + V=L}$ has a $\mathit{\Delta}^1_2$-good well-ordering of $\mathbb{R}$. (Gödel, Addison) So: Is there an inner model for KP/Z/....
Ember Edison's user avatar
1 vote
0 answers
161 views

Can the Constructible Universe be built in absence of Unions and Power?

Can $L$ be built in $\sf ZF$ $\sf-Regularity-Union-Power+ Boolean \ Union$? We know that $L$ can be built in $\sf KP$, but here we don't have Set Union. If the answer is to the negative, then would ...
Zuhair Al-Johar's user avatar
1 vote
0 answers
135 views

Must models of the following theory satisfying opposing infinitary sentences, satisfy opposing finitary sentences?

This is a follow-up to posting titled "Is this theory finitary first order complete?" Recall the theory presented at that posting. Replace the size axiom by the following: $\textbf{...
Zuhair Al-Johar's user avatar
2 votes
1 answer
145 views

Is this theory finitary first order complete?

If we coin a theory in $\mathcal L_{\omega_1, \omega}$ that begins with constructing pure true well founded finite sets, then the set of all true well founded hereditarily finite sets, then builds up ...
Zuhair Al-Johar's user avatar
12 votes
1 answer
586 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
6 votes
1 answer
499 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
2 votes
1 answer
203 views

Is stable ordinals in non-well-founded model the same as well founded models?

Let $BST$ be the axiom system $KP$ - $\Delta_0$ collection. For an ordinal $\alpha$, we say that $\alpha$ is $\varphi$-$\Sigma_n$-stable, if there is a $\beta>\alpha$ satisfies the formula $φ$ such ...
Reflecting_Ordinal's user avatar
2 votes
0 answers
118 views

Higher-order oracle computation of reals and axiom of constructibility

Certain real numbers can be approximated arbitrarily well by computable functions. If we introduce halting oracles, then more real numbers can be "computed", like Chaitin's constant or the ...
Darren Li's user avatar
3 votes
1 answer
494 views

Are all constructible from below sets parameter free definable?

Lets take the intersection of the theory of $L_{\omega_1^{CK}}$ and $\sf ZF + [V=L]$, this is equivalent to the theory of constructability from below + limit stages. Can this theory prove the ...
Zuhair Al-Johar's user avatar
4 votes
0 answers
173 views

Some questions on a paper of Gerald Sacks

I've been reading Sacks' Countable admissible ordinals and hyperdegrees as I'm interested in Theorem 5.3 of the paper: Let $M$ be a countable standard model of $\mathsf{ZF}$ and $V=L$. Suppose $\...
Lorenzo's user avatar
  • 2,134
7 votes
1 answer
315 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
2 votes
0 answers
157 views

End elementary extension in infinitary logic of some $L_\alpha$ producing a $L_\beta$

Let $L_\alpha$ be some admissible level of the constructible hierarchy and $M \supseteq L_\alpha$ an extension of $L_\alpha$. I am looking for conditions under which $M \simeq L_\beta$. It is not ...
Johan's user avatar
  • 491
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
2 answers
366 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
  • 491
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
1 vote
0 answers
257 views

Is Jensen's covering lemma meaningful in a platonist's view?

The typical applications of fine structure theory are finding out the lower bounds of consistency strength of axiom systems. In such a proccess, we also constructs many combinatorial objects in core ...
Reflecting_Ordinal's user avatar
0 votes
0 answers
66 views

A weak version of Shoenfield absoluteness theorem

In my studies I found the following exercise ``Let $\phi\in \boldsymbol{\Delta}_{1}$ and $A,B\in L$, so $$V\models \exists f\in {B}^{A}\,\forall x\in A\, \phi(x,f(x))$$ if and only if $$L\models \...
Ândson josé's user avatar
1 vote
1 answer
190 views

Recursively inaccessible ordinals and non locally countable ordinals

This answer seems to imply that: for an ordinal $\alpha$, to be recursively inaccessible (i.e. $\alpha$ is admissible and limit of admissible) implies to be not locally countable (i.e. $L_\alpha \...
Johan's user avatar
  • 491
8 votes
3 answers
503 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
  • 491
2 votes
1 answer
303 views

What's the order type of the following set?

Fix a positive integer n. Assume $Lan=\{R_0,R_1,...,R_n\}$ be a language of first order logic, where every $R_i$ is a 2-ary relation symbol. Assume $M$ is an Lan-model, where the underlying set is $...
Reflecting_Ordinal's user avatar
4 votes
0 answers
141 views

Slicing large countable ordinal properties, from $\Pi_3$-reflection to $\Sigma_2$-admissibility

Edit 2024: This post was based on an incorrect premise, as can be seen by my conversation with Farmer S in the comments. However the mistake I made and the conversation in comments may be instructive (...
C7X's user avatar
  • 1,176
7 votes
1 answer
105 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
3 votes
1 answer
162 views

Weak form of $\text{CH}$ in $L(\mathbb{R})$

I was wandering whether this weak form of $\text{CH}$ holds in $L(\mathbb{R})$ provably in $\text{ZF}+\text{DC}$ $(\text{ZF}+\text{DC}) \ L(\mathbb{R})\vDash \forall X\subseteq\mathbb{R} ( X \text{ ...
Lorenzo's user avatar
  • 2,134
2 votes
1 answer
120 views

A continuous map relating co-constructible reals

My question is the following: Given $x,y \in \omega^\omega$ such that $x\equiv_c y$ is there an $L$-definable continuous map $\varphi: \omega^\omega\rightarrow \omega^\omega$ such that $\varphi(x) = ...
Lorenzo's user avatar
  • 2,134
3 votes
0 answers
242 views

Is this recursion theoretic analogue of a criterion of weakly compact cardinal accurate?

Jensen proved that, if V=L, and $\kappa$ is a regular cardinal, then if for any stationary $A\subseteq \kappa$, the set $\{\alpha\mid A \text{ is stationary below }\alpha\}$ is stationary in $\kappa$, ...
Reflecting_Ordinal's user avatar
3 votes
0 answers
120 views

At which large cardinal property this second order ordinal arithmetic stops?

Language: Second order logic, with as usual predicates written in upper case, and objects in lower case. Let $<$ be a primitive constant binary relation symbol. Equality between objects is ...
Zuhair Al-Johar's user avatar
0 votes
1 answer
166 views

At which large cardinal, the theory of the minimal transitive model of ZFC starts proving its absence?

Let's take the minimal transitive model of $\sf ZFC$ which, I came to know, is some minimal $L_\kappa$ for a countable $\kappa$, that models $\sf ZFC$, and since its minimal so no subset of it can be ...
Zuhair Al-Johar's user avatar
3 votes
1 answer
211 views

Do all limit $\alpha \in \omega_1^L$ satisfy $L_\alpha \models V=HC$?

In Gaps in the constructible universe, Marek and Srebrny, 1973 a gap ordinal and the start of a gap are defined as follows $\alpha$ is a gap ordinal iff $(L_{\alpha+1}-L_\alpha)\bigcap \mathcal{P}(\...
Martín S's user avatar
  • 421
2 votes
0 answers
160 views

Why can't $L_\beta$ contain a real coding a well-ordering of order-type $\beta$, when $\beta$ is a gap ordinal?

In Gaps in the constructible universe, Marek and Srebrny, 1973 a gap ordinal is defined as follows $\alpha$ is a gap ordinal iff $(L_{\alpha+1}-L_\alpha)\cap \mathcal{P}(\omega) = \emptyset$ Their ...
Martín S's user avatar
  • 421
4 votes
1 answer
225 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
3 votes
1 answer
270 views

When does $\Pi_2$-reflection on $X$ fail to imply iterated $\Pi_1$-reflection on $X$?

Let lowercase Greek letters denote ordinals. Recall from Richter and Aczel's "Inductive definitions and reflecting properties of admissible ordinals", for a set of formulae $\Gamma$ and a ...
C7X's user avatar
  • 1,176
1 vote
0 answers
149 views

Can Jensen's covering lemma be proven easier in generic extensions of L?

Jensen's covering lemma, stating that if there is no $0^\#$ in V, then some covering property holds true, has a very complex proof. In any generic extension L[G] of L, $0^\#$ don't exist, so the ...
Reflecting_Ordinal's user avatar
7 votes
2 answers
461 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
4 votes
2 answers
284 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
0 votes
0 answers
141 views

How to define BHO alternatives below admissible ordinals?

Bachmann-Howard ordinal is a recursive ordinal. It's not that large compared to those proof-theoretic ordinals of stronger theories, but the definition of BHO is sufficient to illustrate how ...
Reflecting_Ordinal'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
4 votes
1 answer
895 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
5 votes
1 answer
399 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
6 votes
0 answers
195 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
5 votes
1 answer
394 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
1 vote
0 answers
70 views

Can all sets in stratified L above some stage be proximate?

Define stratified $L$, denoted by $^S L$, as: Let $S$ be the set of all stratified formulas in first order language of set theory. Define: ${ }^S Def (X) = \{\{y \in X \mid (X, \in) \models \phi(y,z_1,...
Zuhair Al-Johar's user avatar
0 votes
0 answers
190 views

Does the following characterization of the elements of $\mathscr P$($\omega$) fail for ITTM's?

Hartley Rogers Jr., on pg. 120 of his text, Theory of Recursive Functions and Effective Computability, presents and discusses the following characterization of the sets in $\mathscr P(\omega)$: $\...
Thomas Benjamin's user avatar
2 votes
0 answers
205 views

When is a $\Sigma_n$ Skolem hull a proper submodel?

For $M$ an amenable structure and $X \subset M$, the $\Sigma_n$ Skolem hull of $X$ is a $\Sigma_n$-elementary submodel of $M$. That is, as presentend in Devlin, Constructibility, pp. 85-88, for $h_n$ ...
Johan's user avatar
  • 491
-2 votes
1 answer
291 views

What does the Concordant constructible universe model?

Define a ranking function $\cal R$ as: $\mathcal{R}: V \to ON; \,\mathcal {R}(x)= \min \alpha \, \forall y \in x: \alpha > \mathcal {R}(y) $ Now the constructible rank $\mathcal R^c$ of a set $X$ ...
Zuhair Al-Johar's user avatar
8 votes
1 answer
561 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
3 votes
1 answer
310 views

If we have a class like $L$ but allowing a set number of unbounded quantifiers, is it strict superset of $L$?

The definition of $L$ only permits bounded quantifiers. If we allow a certain number of unbounded quantifiers, does this result in a strict superset of $L$? For example: $$ \operatorname{Def}^{\...
Christopher King's user avatar
3 votes
1 answer
222 views

smallest ordinal $\alpha$ such that $L \cap P(L_\alpha)$ is uncountable

Let $V$ denote the von Neumann universe and $L$ Gödel's constructible universe. For any set $X$, let $P(X)$ denote the power set of $X$. Assume that $0^\sharp$ exists (and ZFC). What is the smallest ...
Jesse Elliott's user avatar
6 votes
1 answer
356 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