For question in Proof Theory, where "proofs" themselves are the object of mathematical investigation. It is not to be used to request a proof of some result.
-1
votes
1answer
96 views
notable inductive proofs relating to fractals
what are notable/ prominent inductive proofs relating to fractals?
the motivation for this question is:
fractals are very difficult mathematical objects to work with, and many ...
4
votes
0answers
64 views
$n$th order arithmetic with predicates for orders
Two papers I have looked at lately axiomatize $n$-th order arithmetic in a single sorted language with predicates $Z_1,\dots,Z_n$ and axioms like $\forall x(Z_1(x)\vee\dots\vee Z_n(x))$ to say ...
6
votes
1answer
162 views
Does the totality of Ackermann's function prove the consistency of $\Sigma_1$-induction?
It is well known that Ackermann's function is not primitive recursive. Therefore, the theories of primitive recursive arithmetic (PRA) and of $\Sigma_1$-induction ($I\Sigma_1$) cannot prove the ...
23
votes
2answers
419 views
Why is there no connection between fast-growing functions and complex analysis
I found myself wondering the other day whether the fast-growing functions from natural to naturals that are studied by people like proof theorists are the restriction to the naturals of analytic ...
2
votes
1answer
110 views
what are the proof-theoretic ordinals of second-order arithmetic and ZFC? [duplicate]
are they still smaller than omega-1-CK?what are the notations of them?
12
votes
1answer
171 views
Nontrivial upper bounds on proof-theoretic ordinals of strong theories: do we have any?
Motivated by Consistency of Analysis (second order arithmetic) and Proof-Theoretic Ordinal of ZFC or Consistent ZFC Extensions?, I have the following question:
Are there any examples of strong ...
7
votes
3answers
513 views
Consistency of Analysis (second order arithmetic)
Is there a proof of the consistency of Analysis (second order arithmetic), which is similar to Gentzen's proof of the consistency of arithmetic?
Update:
Which (different) methods can be used to ...
9
votes
4answers
1k views
Are there non-diagonal proofs for Cantor's continuum and Godel's incompletness theorems?
There is a formal definition for the notion of a formal proof.
Question 1. Is there any formal definition for the notion of a diagonal formal proof?
Consider the following theorems both proved by ...
9
votes
0answers
144 views
Reverse mathematics of meromorphic functions on Riemann surfaces
Various sources touch briefly on the reverse mathematics of measure theory and complex analysis. But I have found none on the uniformization theorem for Riemann surfaces or the existence of ...
6
votes
0answers
153 views
When is a reduction not a reduction?
Every mathematician understands the concept of reducing a complicated problem to a simpler problem. "Without loss of generality, we may assume…" However, I've noticed that some kinds of ...
1
vote
1answer
103 views
A question about consistent fragments of formalized mathematical theories with Natural Deduction
Ref to : Sara Negri & Jan von Plato, Structural Proof Theory (2001).
In Ch.6 : Structural Proof Analysis of Axiomatic Theories [page 126-on], they
give a method of adding axioms to sequent ...
4
votes
0answers
78 views
Stabilization of recursive approximation in $PA^-+I\Sigma_1^0$
Over any model M of $PA^-+I\Sigma_1^0$. Suppose $A\in [T]$ where $T$ is a $\Delta_2^0$-tree and $A$ is one isolated path. Further, $A$ is regular, i.e. $\forall n A\upharpoonright n$ has a code in ...
2
votes
3answers
327 views
Show that Z2 is not conservative over PA
It is well-known that $\mathsf{ACA}_0$ is a conservative extension of PA. I assume this theorem gets a lot of attention because $\mathsf{Z}_2$ is not conservative over PA. Thus there ought to be ...
5
votes
1answer
263 views
Is Kolmogorov complexity (KC) relevant for proof theory? [closed]
Note. The title was modified. Previous title was
"Every theorem t has a proof no more complex than~|t|. Is this right?"
The question ("Is Kolmogorov complexity (KC) relevant for proof theory?") ...
8
votes
1answer
236 views
What is the proof-theoretic ordinal of PA + Con(PA), PA + Con(PA + Con(PA)) etc., and why?
I seem to remember having read that the proof-theoretic ordinal (sup of ordinals the theory can prove well-ordered) of $\mathsf{PA} + \mathsf{Con}(\mathsf{PA})$ is the same as that of $\mathsf{PA}$, ...
2
votes
1answer
217 views
Elementary proof of bounds on factor polynomials
The question Getting a bound on the coefficients of the factor polynomial got very nice answers on Gelfond's theorem. But for work on proof theory of arithmetic I want a proof in arithmetic. The ...
7
votes
0answers
271 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 ...
0
votes
0answers
97 views
What references cover finitary systems of Ramified Analysis with transfinite levels?
The ramified theory of types, invented by Bertrand Russell, is a way of dealing with impredicativity by breaking the comprehension schema of second-order logic into levels. The comprehension schema ...
4
votes
0answers
107 views
cut-elimination for infinitary logic
Takeuti (1987, 223) deduces a cut-elimination theorem for infinitary logic from the corresponding soundness-and-completeness theorems. However, is there a way to adapt the basic Gentzen-style ...
1
vote
0answers
191 views
What is the role of the (formalized) omega rule in Ramified Analysis?
In the 1960's, Feferman and Schutte did groundbreaking proof-theoretic work to find out the strength of predicative systems of second-order arithmetic. They used the ramified theory of types, a ...
3
votes
2answers
216 views
What is the proof-theoretic ordinal of Hyperarithmetical Comprehension?
As I discuss in my answer here, it seems to me that Solomon Feferman shows, on pages 10-11 of his seminal 1964 paper "Systems of Predicative Analysis", that if you consider predicative second-order ...
1
vote
0answers
142 views
Has the Ramified Theory of Types been applied to Predicative Set Theories?
Questions of predicativity are well-studied in the context of arithmetic. We have a base theory, first-order Peano arithmetic. Some people, like Edward Nelson (in chapter 1 of his book) and Charles ...
4
votes
2answers
337 views
Did Gödel prove that the Ramified Theory of Types collapses at $\omega_1$?
Second-Order Arithmetic is considered impredicative, because the comprehension scheme allows formulas with bound second-order variables that range over all sets of natural numbers, including the set ...
4
votes
1answer
201 views
Can the Burgess-Hazen analysis of Predicative Arithmetic be extended to Transfinite Types?
Around page 300 of his book "Mathematical Thought and its Objects", Charles Parsons discusses the work of Edward Nelson, who believes that mathematical induction is impredicative, because it can be ...
0
votes
1answer
642 views
Is there any danger far from home? (Edited & Revised Version) [closed]
The notion of formal proof is defined by finite sequences ($<\omega$ - sequences) of sentences. In some sense if a sentence $\sigma$ is (finitely) provable from the theory $T$ it is very "near" to ...
1
vote
1answer
195 views
Does this algorithm terminate in all scenarios?
Let $x \in \mathbb{R}^p$ denote a $p$-dimensional data point (a vector). I have two sets $A = \{x_1, \dots, x_n\}$ and $B = \{x_{n+1}, \dots, x_{n+m}\}$, so $|A| = n$, and $|B| = m$. Given $k \in ...
17
votes
2answers
760 views
Deep theorems and long proofs
I ran across this discussion by Daniel Shanks,
"Is the quadratic reciprocity law a deep theorem?."
Solved and Unsolved Problems in Number Theory. Vol. 297. AMS, 2001. p.64ff.
which made me ...
6
votes
1answer
206 views
the choice of representing formulas and Gödel's second incompleteness theorem
In Rautenberg's book (A Concise Introduction to Mathematical Logic, Universitext, Springer 2006), Gödel's second incompleteness theorem is stated:
Theorem 3.2 (Second incompleteness theorem). PA ...
10
votes
1answer
257 views
Proof-Theoretic Ordinal of ZFC or Consistent ZFC Extensions?
Let the proof theoretic ordinal $\alpha$ of a theory $T$ be the least recursive ordinal such that $T$ does not prove that $\alpha$ is well-founded. This ordinal is intended to quantify in some sense ...
9
votes
2answers
235 views
Cut elimination algorithms
Gentzen's Hauptsatz in first order logic includes an algorithm taking any proof in the sequent calculus with cut rule, and delivering a proof without cut rule (and with the subformula property). So ...
3
votes
0answers
180 views
The substitution theorem in first order logic (finitely many variables)
We consider the language ${\cal L}=\{\in\}$ with an arbitrary set of variables $V$. Specifically we define ${\bf P}(V)$ as the free algebra of type $\{\bot,\to\}\cup\{\forall x:x\in V\}$ (with the ...
2
votes
1answer
343 views
Hilbert style axiomatic proof or sequent Calculus?
I am puzzling with the question which of the two proof systems (Hilbert style axiomatic proofs or substructural Sequent Calculi) is the most discriminatory?
With discriminatory I mean is which proof ...
8
votes
1answer
182 views
The Hasse Minkowski theorem in Peano arithmetic
Harvey Friedman's "Concrete Mathematical Incompleteness" at http://www.math.osu.edu/~friedman.8/pdf/0.Intro061311.pdf cites the Hasse Minkowski theorem saying quadratic forms over a number field are ...
1
vote
1answer
229 views
Ordinal Exponentiation in Genzen's Sequent Calculus
For Genzen's sequent calculus with PA axioms, why is the proof-theoretic ordinal $\epsilon_0$? This seems to hinge on what exactly it means for the level of a cut or CJ inference figure to be higher ...
5
votes
1answer
396 views
Axiomatization of first order logic (finitely many variables)
Standard textbooks in mathematical logic will assume an infinite supply of variables. Their axiomatization of first order logic will typically contain an axiom of the form $\forall ...
1
vote
2answers
259 views
Embedding of consistent subset in first order logic (finitely many variables)
I am looking at FOL with no equality, no constant, no function symbol and the unique binary predicate $\in$ with variables in arbitrary sets $V$ or $W$. Specifically we define ${\bf P}(V)$ as the free ...
12
votes
1answer
654 views
Reverse mathematics of Hilbert's Theorem 90
What is known, and what is published, on the reverse mathematics of the nest of results called Hilbert's Theorem 90?
5
votes
6answers
215 views
Strength of Bishop style constructive mathematics vs $\mathsf{RCA}_0$
This question came out of this other MO question of mine. My question is
Is there a formal comparison between $\mathsf{RCA}_0$ and $\mathsf{BISH}$ (Bishop style constructive mathematics as used ...
14
votes
1answer
504 views
Goodstein's theorem without transfinite induction
Goodstein's theorem is an example of a theorem that is not provable from first order arithmetic. All proofs of the theorem seem to deploy transfinite induction and I've wondered if one could prove the ...
1
vote
3answers
258 views
Is there an recursively axiomatized system with infinitely many proofs for some propositions or a proposition [closed]
Is there any recursively axiomized system with infinitely many proofs for some propositions or a proposition? So we will have at least one proposition which is deduced from the recursively axiomatic ...
10
votes
4answers
872 views
5
votes
1answer
213 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 $\phi$ contains no ...
11
votes
1answer
389 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 fragment. Schmerl ...
7
votes
2answers
750 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, couple of which led ...
12
votes
1answer
220 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 conservative over PA is ...
0
votes
0answers
76 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},$$ ...
5
votes
1answer
182 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 refers to first order ...
9
votes
2answers
375 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 corresponding essentially to ...
20
votes
0answers
770 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: Toward the end of his ...
4
votes
1answer
208 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 exist.
For instance I'm ...
