All Questions
Tagged with forcing computability-theory
16 questions
2
votes
1
answer
161
views
Are Cohen Generics Minimal Covers?
Are Cohen generics (in $2^\omega$) minimal covers?
I'm ultimately interested in this question for some more effective notion of forcing but I realized I wasn't sure how to show this even assuming full ...
- 3,029
4
votes
0
answers
182
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 $\...
- 2,286
2
votes
1
answer
123
views
Arithmetically-hyperimmune-free degrees are comeager
I think proposition XIII.1.22 of Odifreddi is false but I wanted to check I wasn't being dumb. Here's the claim.
Definition: The set$^1$ $A$ is arithmetically-hyperimmune-free if every function $f$ ...
- 3,029
6
votes
1
answer
227
views
How often are forcing extensions of countable computably saturated models of $\mathsf{ZFC}$ computably saturated?
Recall that given a finite language $\mathcal{L}$, we say that an $\mathcal{L}$-structure is computably saturated (or recursively saturated) if for any computable set $\Sigma(\bar{x},y)$ of $\mathcal{...
- 12.5k
7
votes
0
answers
313
views
An uncountable structure with unusual "relatively-computable shadow"
Below, all structures are infinite and in a finite language. Given a structure $\mathcal{A}$ with domain $\omega$, we conflate $\mathcal{A}$ with some reasonable encoding of its atomic diagram for ...
- 21.2k
7
votes
0
answers
468
views
"Relative plausibility" of some infinitary theories
We work in $\mathsf{ZFC+V=L}$.
Define a plausible theory to be a theory $T\subseteq\mathcal{L}_{\omega_1,\omega}$ in an $\omega_1$-finite language which is $\omega_1$-c.e. and $\omega_1$-finitely ...
- 21.2k
8
votes
2
answers
752
views
Paul Cohen on genesis of method of forcing and mathematical similarities
We have on record Paul Cohen's comments on being inspired by issues of formalizing algorithms in number theory (this needs to be verified as per comment) as well as related remarks on computability. ...
- 16.6k
8
votes
2
answers
518
views
History of forcing over admissible sets
In his paper "Forcing in admissible sets", Ershov writes
In unpublished lectures given at Novosibirsk State University in 1976-1977 on the theory of admissible sets, the author
showed that it is ...
- 21.2k
1
vote
1
answer
362
views
How are Koepke's ordinal computability and E-recursion related?
In Koepke's paper, "Turing Computations On Ordinals", one has the following (well-known) result:
A set $x$ is ordinal computable from a finite set of ordinal parameters if and only if it is ...
- 6,132
3
votes
0
answers
203
views
Class forcing over E-closed sets
Short version: does anyone know of any good sources on class-forcing over E-closed, non-admissible sets?
Longer version: A problem I'm working on has reached an interesting conclusion - I've managed ...
- 21.2k
10
votes
1
answer
411
views
The least admissible above a dominating real
Let $\mathbb{P}$ be the usual forcing which adds a dominating real: conditions in $\mathbb{P}$ are pairs $(p, f)$ with $p:\omega\rightarrow\omega$ finite partial and $f:\omega\rightarrow\omega$ total, ...
- 21.2k
13
votes
1
answer
742
views
Is forcing computable?
By results similar to Tennenbaum's theorem we know that there exist no computable models of $ZF$. But suppose we are given, as a sort of oracle, access to some model of $ZF$ (e.g. we can make oracle ...
- 28.2k
4
votes
0
answers
262
views
Recursively Pointed Sacks Forcing and Preserving $\omega_1$
Let $\mathbb{P}$ denote recursively pointed Sacks forcing. This is forcing with recursively pointed perfect trees ordered by inclusion. A tree $T \subseteq {}^{<\omega}2$ is recursively pointed if ...
- 1,750
8
votes
2
answers
473
views
Does forcing with recursively pointed perfect trees add a Turing degree that is minimal over $V$?
A tree $T$ on $\omega$ is recursively pointed if it is recursive in each of its branches. We can consider a variant of Sacks forcing where the conditions are recursively pointed perfect trees ordered ...
- 5,471
8
votes
3
answers
745
views
Natural statements independent from true $\Pi^0_2$ sentences
I am looking for sentences in the language of first order arithmetic ($0,1,+,\cdot,\leq$) which are independent from $\Pi^0_2$ consequences of true arithmetic $\Pi^0_2\text{-}\mathsf{Th}(\mathbb{N})$. ...
- 5,502
6
votes
1
answer
416
views
An eventually different function adding no Solovay real nor dominating function?
Definitions
I believe set theorists have studied all of the following three notions in the context of forcing extensions of a model of ZFC, $M$ (hopefully the terminology is the standard one).
A ...
- 24.8k