All Questions
Tagged with computability-theory set-theory
172 questions
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,833
76
votes
6
answers
9k
views
Which graphs are Cayley graphs?
Every group presentation determines the corresponding Cayley graph, which has a node for each group element, and arrows labeled with the generators to get from one group element to another.
My main ...
- 236k
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
44
votes
3
answers
5k
views
"Simpler" statements equivalent to Con(PA) or Con(ZFC)?
Given any reasonable formal system F (e.g., Peano Arithmetic or ZFC), we all know that one can construct a Turing machine that runs forever iff F is consistent, by enumerating the theorems of F and ...
- 9,833
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 ...
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&...
31
votes
2
answers
2k
views
How (non-)computable is set theory?
Here is a naive outsiders perspective on set theory: A typical set-theoretical result involves constructing new models of set theory from given ones (typically with different theories for the original ...
- 4,727
27
votes
1
answer
2k
views
Why isn't this a computable description of the ordinal of ZF?
In a previous MO question, I was told by several commenters that
(a) it's known that there exists a computable ordinal $\alpha_{ZF}$ that "encodes the strength of ZF set theory" (i.e., a least ...
- 9,833
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 ...
- 20.5k
21
votes
1
answer
1k
views
About $\omega_1^{CK}$
Here we use $\omega_1^{CK}$ to denote the least nonrecursive ordinal. The following theorem is well known.
$\mathbf{Theorem}$ $\omega_1^{CK}$ is an admissible ordinal.
But its proof seems weird. ...
- 4,201
20
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,833
19
votes
1
answer
747
views
What non-standard model of arithmetic does Hofstadter reference in GEB?
Following some of the coolest bits of Hofstadter's Gödel, Escher, Bach, extensions of the standard model of arithmetic are described. A ways in, the paragraph "Supernatural Addition and Multiplication"...
- 1,288
18
votes
4
answers
2k
views
Theorems in set theory that use computability theory tools, and vice versa
I recently learnt that the proof of the classical theorem "$\mathsf{AD}$ $\implies$ $\aleph_1$ is measurable" uses computability theory tools (or at least one of its proofs does so). I'm ...
- 1,432
18
votes
3
answers
2k
views
Is Robinson Arithmetic biinterpretable with some theory in LST?
Let ZFC$^{\text{fin}}$ be ZFC minus the axiom of infinity plus the negation of the axiom of infinity. It is well-known that ZFC$^{\text{fin}}$ is biinterpretable with Peano Arithmetic. In this sense ...
- 3,267
18
votes
2
answers
1k
views
Is there a name for sets for which it is easier to test membership than to find members---and vice versa?
This is a question my son Bob asked me. For some sets it is relatively easy
to test for membership but a lot more difficult to find members, and for others
the reverse is true. Here is an elementary ...
- 15.3k
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
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
1
answer
720
views
Would an oracle for Rayo's function let you compute a model of $(V, \in)$?
Working in Kelly-morse set theory, let $R$ be an oracle that can compute Rayo's function. Can $R$ compute a countable model $M = (\mathbb N,\in_M)$ that is elementary equivalent to $(V, \in)$?
- 6,353
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
15
votes
1
answer
616
views
Does Kechris' conjecture contradict both parts of Martin's conjecture, or just part 1?
By Kechris' conjecture (KC) I mean the assertion that Turing equivalence $\equiv_T$ is a universal countable Borel equivalence relation.
On the other hand, Martin's conjecture (MC) is a long-lasting ...
- 151
14
votes
2
answers
719
views
Woodin on Posner-Robinson for the hyperjump and sharp
The Posner-Robinson theorem states that, if $X$ is noncomputable, there is some $G$ such that $X\oplus G=G'$; that is, even though genuine jump inversion only works above $0'$, every (nontrivial) $X$ ...
- 20.5k
14
votes
2
answers
1k
views
Does Turing determinacy imply full determinacy?
The axiom of Turing determinacy is a weakening of the full axiom of determinacy, $AD$, in which only games with payoff sets which are $\equiv_T$-invariant are demanded to be determined.
In "...
- 20.5k
14
votes
1
answer
1k
views
Descriptive set theory for computer scientists?
It seems to me that there are scattered references of deep relationships between descriptive set theory and computability theory. For one, the relationship between the Borel hierarchy and the ...
- 1,221
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
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
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
12
votes
1
answer
684
views
Continuous functions and 2-bushy trees
The following problem was asked by Joe Miller in the fall of 2010 at a bar in Madison.
A subtree $T \subseteq 4^{< \omega}$ is $2$-bushy if for some node $\sigma \in T$, every node above $\sigma$ ...
- 9,641
11
votes
2
answers
1k
views
Does ZF+AD have any unusual arithmetic consequences?
Motivation:
This question is motivated by wondering to what extent "natural" theories are linearly ordered (or at least ordered in a directed manner) by their (first-order) arithmetic consequences, ...
- 63.9k
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
11
votes
1
answer
400
views
What is the Turing degree of the monadic theory of the real line?
The monadic theory of the real line is the set of all sentences in the monadic second-order language of order which are true in $\mathbb{R}$. In this 1982 paper, Gurevich and Shelah show that true ...
- 4,597
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 ...
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 ...
- 20.5k
10
votes
2
answers
482
views
What subsets of a set of integers can compute it?
For $x, y \subseteq \omega$,
(a) We write $x \leq_T y$ if $x$ is Turing reducible to $y$.
(b) We write $x \leq_L y$ if $x \in L(y)$ where $L(y)$ is the smallest model of ZFC that contains all ...
- 101
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, ...
- 20.5k
9
votes
3
answers
2k
views
What set theoretical questions could never be answered by Turing machines of arbitrary cardinality?
Let us assume that there are Turing machines of arbitrary cardinality, by that I mean they can have input tapes of any arbitrarily high cardinality and compute for a number of steps also of ...
- 297
9
votes
2
answers
914
views
Non null Turing antichain
This interesting question resulted from a query of Mushfeq: In ZFC, can we find a non null set of pairwise Turing incomparable reals?
- 9,641
9
votes
1
answer
711
views
Computable models of the ordinal numbers
It's known, for example in the answer to this question: Is there a computable model of ZFC? that ZFC has no computable model. My questions is: is there a model of ZFC for which the order relation on ...
- 375
9
votes
1
answer
739
views
Can the Turing degrees be linearly ordered?
Assuming the axiom of choice, every set can be linearly (indeed, well-) ordered. However, without choice this can fail, as witnessed most drastically by the consistency of amorphous sets. More ...
- 20.5k
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
9
votes
1
answer
341
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 ...
- 4,201
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 ...
- 20.5k
9
votes
0
answers
279
views
What logic characterizes relative intrinsic complexity in set recursion?
Short version: Is there an analogue of the Ash-Knight-Manasse-Slaman/Chisholm theorem for $E$-recursion?
Long version: I'm interested in "$E$-recursive structure theory," but it's not ...
- 20.5k
9
votes
0
answers
305
views
Moschovakis' discovery of E-recursion
E-recursion is a notion of generalized computability theory which seeks to extend computations to allow arbitrary sets as inputs. In contrast with e.g. $\alpha$-recursion, it disallows unbounded ...
- 20.5k
9
votes
0
answers
471
views
(A little bit) Beyond the E-recursive
The E-recursive functions are a particular generalization of classical recursion theory to the entire set-theoretic universe, $V$. They are defined via a schemes: see Sacks' $E$-recursive intuitions. ...
- 20.5k
9
votes
0
answers
526
views
"Hard" separation results in reverse mathematics (or similar)
This is a fairly broad question. In particular, I specify 5 questions (Q1, Q2.1, Q2.2, Q3, Q4) which for me all fall under one umbrella. Since this is unreasonably broad, I'm really interested in an ...
- 20.5k
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 ...
- 20.5k
8
votes
1
answer
1k
views
Can a Hamkins infinite time Turing Machine with infinite Super Turing jumps (from higher type oracles) get the power to decide $\Sigma_1^2$ sets?
Hamkins showed that his infinite time Turing machine has the power to decide some $\Delta_2^1$ sets. I wonder if some modifications of the machine could be made to reach level $\Sigma_1^2$ sets, or, ...
- 297