Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [proof-theory]

Proof theory is an area of logic that studies proof as formal mathematical objects. If you'd like advice on the presentation of a proof you have in draft, use proof-writing instead. If you'd like feedback on its validity, use proof-verification. If none of the above apply, you do not need a proof-* tag.

This tag is NOT intended for questions asking how to write proofs or for checking a proof posted in the question. If you'd like advice on the presentation of a proof you have in draft, use instead. If you'd like feedback on its validity, use . If none of the above apply, you do not need a proof-* tag.

Proof theory is an area of logic that studies proofs and deductive systems as formal mathematical objects. Formally, a proof is a sequence of symbols that obeys the rules of the deductive system.

984 questions
26
votes
6 answers

How to prove the mathematical induction is true?

I have no idea about the underlying theory from which the mathematical induction was derived. How to prove the mathematical induction is true?
Display Name
  • 2,715
11
votes
1 answer

Intutive explanation of the PCP Theorem

The PCP theorem states that: Every decision problem in NP has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity. Can anyone give an intuitive explanation of how this can be…
Casebash
  • 9,211
7
votes
4 answers

Justification of Proofs by Contradiction

Is there a validation for the technique of proof by contradiction? Or do those who use it take its validity as an axiom?
Ernest
  • 251
5
votes
1 answer

algorithmic checking of proofs

Is it possible to check if a proof is correct algorithmically(especially with computer aid)? I ask this question because I find that a lot of time is taken up during lectures going through the proof of the theorems, which is basically just checking…
picakhu
  • 4,906
4
votes
1 answer

Proving premises working on a proof of the conclusion

like very much this site. Let's consider the following rules of a deduction system (due to Sch\"{u}tte). I'll write them all, but some of them may not be useful. WEAK RULES Rule 1: \begin{equation} \frac{C \vee A \vee B \vee D}{C \vee B \vee A…
lie.teller
  • 43
3
votes
3 answers

Impossibility theorems

I've been wondering how you go about proving an impossibility e.g. when I looked up Abel's impossibility theorem it says nothing about the proof and only restates the theorem when I'd like to know how it's done. Is the way to prove an impossibility…
Niklas Rosencrantz
  • 2,265
3
votes
2 answers

Can a mathematical theorem be proved in infinite ways?

This is a question that I really think about. I wanted to develop my mind, and started trying to prove the Pythagorean theorem of a triangle, trying each day, and now its been a week. I wonder if theorems can be proved in infinite ways, or just a…
codetalker
  • 2,419
2
votes
0 answers

Relation between strong normalization (say, of Godel's T) and consistency of a proof system (say PA)

I'm studying proof theory and type theory, mostly from "Lectures on the Curry-Howard Isomorphism" and Girard's "Proofs and Types" but some things aren't quite clear. In particular, with the regards to Godel's T: I have seen the proof that uses…
Patrick Nicodemus
  • 1,245
2
votes
0 answers

Do we sometimes prove things based on the assumption that mathematics is self-consistent?

Do we sometimes prove things based on the assumption that mathematics is self-consistent? I recently started to be dubious about proofs by contradiction. It seems to me that it is somehow based on the assumption that whatever we do in mathematics…
Paul
  • 21
2
votes
2 answers

Number of proofs for a statement

On this site, people ask questions and then answers and proofs for those answers come from readers. Readers mark the best answer and then people focus on the next interesting topic. Sometimes, a question will have many answers with proofs from…
michael_timofeev
  • 211
2
votes
1 answer

Quasi-interactive proof on real numbers

[This is a cleaner and simpler restatement of a question I asked earlier on Theoretical CS forum. Please re-tag as appropriate.] Suppose you have two oracles (black boxes) that represent real numbers. Each oracle works like this: you give it integer…
malenkiy_scot
  • 517
1
vote
0 answers

Do all provable theorems have a finite number of proofs?

The Pythagorean Proposition states that there are 367 proofs of Pythagoras' theorem. Is there a limit for the number of proofs of this, or any, theorem? Are there provable theorems with infinitely many proofs, or do all theorems have a limit on the…
username
  • 41
1
vote
0 answers

A formal definition of circular proofs.

Suppose one were to prove that $\pi$ is irrational by claiming "because it is transcendental". This proof would be seen as circular. However, neither of "$\pi$ is irrational" and "$\pi$ is transcendental" is strictly stronger than the other, in…
user107952
  • 20,508
1
vote
0 answers

What are the assumptions of the logical/Mathematical proof-making system?

I know that axioms define a set of legal actions that we can perform on statements, by which those statements transform into other statements that are necessarily true. Suppose that $s_1$ is an statement that its truthfulness is to be determined…
caveman
  • 393
  • 1
  • 13
1
vote
0 answers

Is it possible to prove consistency of an axiomatic system without providing a model?

Providing concrete models is more-or-less impossible, since we are not sure about many things in real world. On the other side, abstract models are usually insufficient for proving consistency, since the consistency of the other axiomatic system…
Hamid Haghshenas
  • 11
1
2 3