2
votes
1answer
70 views
Is the equivalence between a $\Sigma^0_1$ and a $\Pi^0_1$ formula defining the same recursive set provable in a sufficiently strong arithmetic ?
Let $A$ be a recursive set. $A$ is recursively enumerable, so $A$ may be defined by a $\Sigma^0_1$ formula, i.e. by $\exists \overrightarrow{a} \phi (\overrightarrow{a}, n)$, where …
10
votes
1answer
338 views
Does any lower bound on proofs of FLT improve Shepherdson 1965?
In 1965 Shepherdson proved that FLT is independent of the fragment of PA that uses only open induction and signature $0,S,+\times$. Indeed $2x+1\neq 2y$ is independent of that fra …
6
votes
2answers
454 views
When does $ZFC \vdash\ ‘ ZFC \vdash \varphi\ ’$ imply $ZFC \vdash \varphi$?
Being a new member, I am not yet sure whether my question will be taken as a research level question (and thus, appropriate for MO). However, I have seen similar questions on MO, c …
9
votes
2answers
296 views
Reverse mathematics below RCA
I'm sure this is a fairly basic question, but I can't seem to find a solid answer:
My primary question is: Is there a reasonably nice subsystem of second-order arithmetic correspo …
4
votes
1answer
60 views
What metatheory proves $\mathsf{ACA}_0$ conservative over PA?
Simpson's book shows $\mathsf{ACA}_0$ is conservative over $\mathsf{PA}$ in the natural way by model theory using definable subsets. Of course, $\mathsf{ACA}_0$ being conservativ …
5
votes
1answer
113 views
Interpretability and consistency strength
I have heard there is some fairly recent result showing that whenever theories $T$ and $T'$ have the same consistency strength, then each can interpret the other. I suppose it ref …
13
votes
0answers
213 views
Godel on recursion-theoretic hierarchies
At the end of his excellent article, "The Emergence of Descriptive Set Theory" (http://math.bu.edu/people/aki/2.pdf), Kanamori writes:
"Another mathematical eternal return: To …
8
votes
6answers
752 views
Non-constructive proofs vs. efficient algorithms
My question concerns what is meant by "nonconstructive", and whether it has ever been defined in terms of computational complexity.
The wikipedia article on constructive proof beg …
0
votes
0answers
66 views
Beatty proof adaptation ?
If $m$ and $n$ are coprime integers, prove that each of these $m+n-2$ fractions: $$\frac{m+n}{m},\frac{2(m+n)}{m},\frac{3(m+n)}{m},...,\frac{(m-1)(m+n)}{m},$$ $$\frac{m+n}{n},\frac …
4
votes
1answer
143 views
ERA, PRA, PA, transfinite induction and equivalences
I'm quite sure I don't understand very well the links between proof theoretical ordinals of theories, the axioms of transfinite induction and the objects a theory can prove to exis …
4
votes
1answer
125 views
Notation for upperbound power sets.
There is a standard notation $\mathrm{ZF}[n]$ for Zermelo Fraenkel set theory with the power set axiom restricted to saying the set of natural numbers has $n$ successive power sets …
6
votes
5answers
527 views
Understanding the nature and structure of proofs; Reverse Mathematics and Proof Theory. Prerequisites? Good introductory texts?
I'm still studying maths at undergraduate level, but intend to continue exploring topics in pure maths after I have graduated, so am thinking already about what directions I'd like …
51
votes
28answers
5k views
Can infinity shorten proofs a lot?
I've just been asked for a good example of a situation in maths where using infinity can greatly shorten an argument. The person who wants the example wants it as part of a present …
8
votes
5answers
654 views
How many well orderings of $\aleph_0$ are there?
What is known about the set of well orderings of $\aleph_0$ in set theory without choice? I do not mean the set of countable well-order types, but the set of all subsets of $\alep …
12
votes
1answer
401 views
Does Taranovsky’s system of ordinal notations make sense?
Dmytro Taranovsky has a Web page on which he claims to define a system of ordinal notations strong enough to provide an ordinal analysis of full second-order arithmetic. I think ( …

