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
1 vote
0 answers
108 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 $...
7 votes
1 answer
96 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 $...
  • 1,189
0 votes
0 answers
85 views

Can we have such an external function on some $L(A)$?

Working within $\sf ZF-Reg.$, is there anything that forbids having a set $A$ and a transitive model $M$ of $\sf ZF+ V=L(A)$, that admits an external bijection $j$ between two limit stages $L_\alpha(A)...
3 votes
1 answer
147 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{ ...
  • 1,361
2 votes
1 answer
105 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) = ...
  • 1,361
3 votes
0 answers
191 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$, ...
3 votes
0 answers
110 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 ...
1 vote
1 answer
123 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 ...
3 votes
1 answer
147 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}(\...
  • 401
2 votes
0 answers
130 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 ...
  • 401
4 votes
1 answer
192 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 ...
  • 1,361
1 vote
0 answers
118 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 ...
6 votes
2 answers
340 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_\...
4 votes
2 answers
250 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$?
0 votes
0 answers
91 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 ...
7 votes
1 answer
272 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}$, ...
4 votes
1 answer
757 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 \...
5 votes
1 answer
359 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?
6 votes
0 answers
167 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 $\...
4 votes
1 answer
258 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 ...
1 vote
0 answers
67 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,...
0 votes
0 answers
181 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)$: $\...
2 votes
0 answers
151 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$ ...
  • 295
-2 votes
1 answer
282 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$ ...
7 votes
1 answer
423 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 ...
3 votes
1 answer
292 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}^{\...
  • 4,316
3 votes
1 answer
210 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 ...
6 votes
1 answer
294 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 ...
2 votes
1 answer
248 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 ...
  • 915
9 votes
2 answers
542 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
388 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
161 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$ ...
  • 295
3 votes
2 answers
465 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 "$...
3 votes
1 answer
512 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
343 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 ...
  • 295
2 votes
2 answers
334 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
140 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
146 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
174 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
354 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 ...
  • 437
7 votes
1 answer
266 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 ...
  • 437
2 votes
1 answer
134 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 ...
  • 437
7 votes
1 answer
618 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 ...
  • 1,116
19 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
208 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
383 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 = \...
  • 23.9k
-4 votes
2 answers
813 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
372 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
335 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 ...
  • 3,791
6 votes
1 answer
386 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 ...