All Questions
Tagged with computability-theory set-theory
28 questions
40
votes
3
answers
5k
views
Is there a computable model of ZFC?
Background
Assuming ZFC is consistent, then by downward Löwenheim–Skolem, there is a countable model (M,$\in$) of ZFC. Since the universe M is countable, we may as well think of it as actually being ...
19
votes
3
answers
5k
views
Pi1-sentence independent of ZF, ZF+Con(ZF), ZF+Con(ZF)+Con(ZF+Con(ZF)), etc.?
Let
ZF1 = ZF,
ZFk+1 = ZF + the assumption that ZF1,...,ZFk are consistent,
ZFω = ZF + the assumption that ZFk is consistent for every positive integer k,
... and similarly define ZFα ...
- 9,823
77
votes
8
answers
12k
views
Succinctly naming big numbers: ZFC versus Busy-Beaver
Years ago, I wrote an essay called Who Can Name the Bigger Number?, which posed the following challenge:
You have fifteen seconds. Using standard math notation, English words, or both, name a single ...
- 9,823
46
votes
3
answers
3k
views
Does an existence of large cardinals have implications in number theory or combinatorics?
Does an existence of large cardinals have implications in more down-to-earth fields like number theory, finite combinatorics, graph theory, Ramsey theory or computability theory? Are there any ...
- 1,699
45
votes
5
answers
64k
views
How large is TREE(3)?
Friedman, in _Lectures notes on enormous integers shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman function and exponentiation ...
- 3,630
4
votes
2
answers
489
views
Mapping between Notations
$\DeclareMathOperator{\address}{address}$
As in my other question, it is assumed that the (total) function describing a given notation is denoted as $\address:p \rightarrow \Bbb{N}$ and assumed to be ...
- 881
13
votes
1
answer
650
views
About primitively recursively recognizable ordinals
Preliminary: I believe the notion of primitive recursive functions on ordinals is standard and unproblematic (the main difference with the finite case is that one needs to introduce a $\sup$ or $\...
- 32.5k
11
votes
0
answers
556
views
Various definitions of recursion from ordinal machines
Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available ...
9
votes
2
answers
1k
views
Martin's cone theorem and recursion theory
Martin's remarkable cone theorem in the theory of determinacy says the following:
Suppose $A\subseteq \omega^\omega$ is Turing invariant and determined. If $\forall x\exists y(x\le_T y\& y\in ...
- 32.5k
34
votes
1
answer
3k
views
Does "every" first-order theory have a finitely axiomatizable conservative extension?
I originally asked this question on math.stackexchange.com here.
There's a famous theorem (due to Montague) that states that if $\sf ZFC$ is consistent then it cannot be finitely axiomatized. ...
- 3,137
33
votes
15
answers
7k
views
What's a magical theorem in logic?
Some theorems are magical: their hypotheses are easy to meet, and when invoked (as lemmas) in the midst of an otherwise routine proof, they deliver the desired conclusion more or less straightaway&...
21
votes
2
answers
1k
views
Antirandom reals
This is a crossposting of https://math.stackexchange.com/questions/1446602/anti-random-reals, which has not gotten any answers; after thinking about the problem, I've become more convinced that it ...
- 21.2k
17
votes
1
answer
1k
views
Is there a stronger form of recursion?
I'm wondering if there are any recursion principles more general than the following, first given by Montague, Tarski and Scott (1956):
Let $\mathbb{V}$ be the universe, and $\mathcal{R}$ be a well-...
- 10.1k
17
votes
7
answers
2k
views
Finding the largest integer describable with a string of symbols of predefined length
(This question is motivated by the reading of the article Large numbers and unprovable theorems by Joel Spencer, which can be found at http://mathdl.maa.org/images/upload_library/22/Ford/Spencer669-...
- 2,992
17
votes
1
answer
960
views
Polynomial-time algorithm to compare numbers in Conway chained arrow notation
I am looking for a polynomial-time algorithm which, given a character string containing two numbers in Conway's chained arrow notation for large numbers, indicates whether the first number is less ...
- 171
15
votes
2
answers
918
views
Which are the hereditarily computably enumerable sets?
My question is about sets that are computably enumerable with respect to their hereditary membership structure. Specifically, let me define that a hereditarily computably enumerable (h.c.e.) set is ...
- 236k
12
votes
1
answer
780
views
Does every countable set of Turing degrees have an upper bound, without AC?
It is easy to see that every countable collection of sets $A_n\subseteq\mathbb{N}$ has an upper bound in the Turing degrees, since we can just take a copy of their disjoint sum $\oplus_n A_n=\{\langle ...
- 236k
11
votes
1
answer
441
views
Concerning Silver's result
Jack Silver proved that if $x$ is a real so that every $x$-admissible ordinal is a cardinal in $L$, then $0^{\sharp}$ exists.
I wonder whether various weaker or stronger versions of Silver's result ...
- 4,201
10
votes
2
answers
470
views
Is the set of permissible numbers of models of various cardinalities computable?
This question arose in the comments to this question.
Let $X$ be the set of pairs $(m,k)$ such that there is some (consistent complete countable first-order) theory $T$ with exactly $m$ models of size ...
- 21.2k
9
votes
1
answer
495
views
Can two versions of $\omega_1^{CK}(\mathsf{Ord})$ ever coincide?
The goal of this question is to fill in the gap in this old answer of mine.
For a transitive set $M$, thought of as an $\{\in\}$-structure, we define the following ordinals (this is not the notation ...
- 21.2k
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
1
answer
514
views
How big is the least non-$\Sigma^1_1$-pointwise-definable ordinal?
There's a large countable ordinal which has cropped up (as a lower bound!) in a computable structure theory problem I'm playing with. At present I don't really understand how big it is, and I'm ...
- 21.2k
7
votes
1
answer
490
views
"Robinson arithmetic" for (some) levels of $L$?
I'll write "$\mathcal{L}_\alpha$" for the fragment $\mathcal{L}_{\infty,\omega}\cap L_\alpha$.
Say that a countable admissible $\alpha$ is Robinsonian if there is some sentence $\varphi\in\mathcal{L}...
- 21.2k
6
votes
0
answers
241
views
ITTMs with higher types
What is the complexity of Infinite Time Turing Machines (ITTMs) augmented with an initially empty set of real numbers, with the ability to add, remove, and test presence of a real number in the set?
...
- 7,545
6
votes
1
answer
571
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 ...
- 1,490
5
votes
1
answer
286
views
Is there an oracle that can compute something iff it is computable in every countable model that is equivalent to $(V, \in)$?
Let us work in Kelly-morse set theory, so we can talk about $V$. For some model $M=(\mathbb N, \in_M)$ that is elementary equivalent $(V, \in)$, we can have an oracle that corresponds to $(\mathbb N, \...
- 6,353
4
votes
1
answer
572
views
Definition of HYP in $L_{\omega_1^{CK}}[a]$?
The structure $L_{\omega_1^{CK}}$ consists of only HYP sets (I believe) and HYP in this structure is the same as the actual hyperaritmetic sets. Now if I move to the structure $L_{\omega_1^{CK}}[a]$ ...
- 3,029
2
votes
1
answer
298
views
A question about computability and Turing machines
For any recursively enumerable set theory $T$ (of consistency strength at least superior to KP), if we want to calculate $F(n)=\{F(m)：m∈ω∧mEn\}$ and can determine each $F(n)$ for a Henkin model $(ω,E)$...
- 127