Proof theory is an area of logic that studies proof as formal mathematical objects. For questions asking how to write proofs or for checking an informal proof, please use the proof-writing or proof-strategy tags instead.

learn more… | top users | synonyms

2
votes
1answer
19 views

Undecidability and truth

Are there undecidable problems for which a single truth exists? For example, the question about parallels is not decidable from Euclid axioms. But multiple answers are valid and give different kinds ...
1
vote
2answers
31 views

Proving $\forall x (A\to B) \to(A \to \forall x B):x\notin \mbox{free}(A)$ in a Hilbert system where it is not an axiom

I have no idea whether this question is way too specific or whether something similar has already been asked (we still need to work out a way to search for formulas I guess). Anyways here I go: I ...
-1
votes
2answers
29 views

prove cauchy-schwarz inequality (missing a step)

during lecture notes I only caught most of the proof and couldnt write a step down fast enough, and I'm having a touch trouble seeing how to get from the previous step to the next. Here is what i have ...
1
vote
0answers
35 views

Is the parallelogram law a theorem or an axiom?

I'm learning about inner product spaces and I am able to prove it within an inner product space. Is this a theorem or an axiom in euclidean geometry?(note: not the geometry of Descartes)
1
vote
2answers
32 views

Trouble understanding algebra in induction proof

I'm on hour 20 of studying for the discrete math midterm tomorrow, and I've got to be honest I'm a little panicked. In particular I'm having trouble with induction proofs, not because I don't ...
1
vote
0answers
15 views

Use induction and Pascal’s identity to prove that if n > 1, then 1 = n − 1 = n [on hold]

Use induction and Pascal’s identity to prove that if n > 1, then (n)C(1) = nC(n − 1) = n
1
vote
1answer
18 views

How can Goodstein's theorem be expressed in PA

I understand Goodstein's Theorem and its proof. I'm trying to understand the proof of why Goodstein's Theorem cannot be proved in PA. However, it's not immediately clear to me that Goodstein's Theorem ...
0
votes
2answers
18 views

Proof by contradiction how to show is properly

For every $x \in \left[\pi/2,\pi\right]\,,\ \sin\left(x\right) − \cos\left(x\right) \geq 1$. I have drawn the graph and can clearly see that A is true however how do I prove it correctly.
0
votes
2answers
30 views

If the sum of the digits of n is equal to the sum of the digits of 5n, then prove that 9|n.

Let $n\in\mathbb{N}$. So far I have: If the sum of the digits of $n$ is $k$, then $n = 9m + k$, where $m$ element of an integer (not sure why). Now consider $5n-n$. Help?
0
votes
1answer
8 views

Euclidean algorithm to provde gcd's and multiples

Suppose a, b, n ∈ N. Use the Euclidean algorithm to prove that gcd(na, nb) = n gcd(a, b). I was going to try setting it up, by literally doing: nb = rna + k and so forth, but something tells me this ...
1
vote
1answer
16 views

Proving the dimension of the intersection of 2 subspaces

Assume that $U$ and $W$ are distinct subspaces $( U ≠ W )$ of a four-dimensional vector space $V$ and $\dim(U) = \dim(W) = 3$. Prove that $\dim ( U ∩ W ) = 2$.
-1
votes
0answers
16 views

How Do I Show that Condensed Derivable Rules of Inference Yield the Same Formula as Using Condendensed Detachment Multiple Times?

If we look at condensed detachment of two formulas $\alpha$ and $\beta$, we can see that D$\alpha$.$\beta$, where $\alpha$ has form C$\alpha$$_a$$\alpha$$_b$ is equivalent to using the rule ...
6
votes
1answer
93 views

Why wouldn't someone accept Gentzen's consistency proof?

Reading the consistency section of the Peano Axioms wikipedia page, I came across this sentence: The vast majority of contemporary mathematicians believe that Peano's axioms are consistent, ...
0
votes
0answers
25 views

Proof of law of reflection using Fermat's principle : are we really proving the law of reflection?

Before you skip reading this, let me tell you that this isn't a "how to derive the law of reflection using Fermat's principle" question. Also, I asked it on MSE instead of the physics site because ...
0
votes
0answers
20 views

Prove that (√ 2)^(log(n)) + log^2(n) + n^10 = O(2^n) [duplicate]

This example question has me rather stumped. I'm not sure where to even start with the log(n) terms. The only clue it gives is "There is at least one non-trivial induction to do as part of the ...
1
vote
1answer
20 views

Is there a proof for what I describe as the “recursive process of mathematical induction for testing divisibility”.

I was working on my homework for Discrete Math, and we were asked to "Prove: $6 | n^{3}+5n$,where $n\in \mathbb{N}$" my solution varied significantly from how I have seen it done by others. I noticed ...
1
vote
1answer
58 views

Question about the incompleteness proof (Theorem V)

Question in short: Where do I find a complete proof of Theorem V from Gödels incompleteness proof? If it does not exists, can someone provide it? Question in detail: I am trying to understand ...
0
votes
1answer
17 views

Proving Properties in Ordered Fields

Refer to Definition 1.3, which states, an ordered field is a field F that is ordered set with the following additional properties: ...
1
vote
2answers
45 views

Using logical Properties to prove a tautology

So I have to prove this as a tautology. I've been stuck on this forever and am not sure where to go. I experimented and got this far, and looking for some pointers on where to take it next. (p → q) ...
3
votes
1answer
70 views

Birkhoff's completeness theorem

I have two simple questions. A) Does Birkhoff's completeness theorem follow directly from Gödel's completeness theorem? B) Is Birkhoff's completeness theorem constructive in the following sense: ...
1
vote
0answers
25 views

Has the abc conjuncture been proved by Shinichi Mochizuki? [duplicate]

I'd like to know is his proof was reviewed, and what exactly happened.
0
votes
1answer
17 views

Cartesian product proof with counterexample

I was asked to disprove the following statement by counterexample: Let A, B and C be sets. If A x C = B x C then A = B I was under the impression that: (x1, y1) = (x2, y2) if and only if x1 = x2 and ...
0
votes
1answer
18 views

Proving order of magnitude

Generally how much proof must be given to prove a statement of order-of-magnitude? for example: $n^2 + 2 log (n) = O(n^2)$ $2 log (n)$ has a lower order of magnitude than $n^2$ so it can be argued ...
2
votes
2answers
115 views

Is constructive proof of non-existence possible

Constructive proof construct(indicates) object that satisfies given predicate. Question is whether one can give constructive proof of non-existence of an object with given property e.g. that every ...
1
vote
1answer
36 views

Weakening and Contraction

I saw this site saying weakening is a structural rule where the hypotheses or conclusion of a sequent may be extended with additional members and that contraction is a rule where two equal (or ...
0
votes
1answer
54 views

What is really a “complete” deductive system for first-order theories.

Given some first-order language and a set of axioms therefrom one still needs to specify a deductive system to turn it into a full-fledged first-order theory. Currently I'm under the following ...
1
vote
0answers
57 views

Is a sentence in $\Pi_1$ true given $Q \vdash \lnot\varphi$?

If $Q \vdash \lnot\varphi$ (Q is the Robinson arithmetic), and if I assume that $\varphi \in \Pi_1$; Can I say that $\varphi$ is a true sentence? My thoughts are that, given that Q is $\Sigma_1$- ...
1
vote
1answer
68 views

A simple question on Gödel's functional interpretation

I've been recently reading the Gödel's functional interpretation (or Dialectica). It is generally defined inductively, as could be found here: http://www.andrew.cmu.edu/user/avigad/Papers/dialect.pdf ...
3
votes
1answer
168 views

Problems with nesting proof predicates in first order logic.

Whenever I start nesting proof predicates, I always seems to run into these bizarre situations. I was wondering if anyone knows about this and could shed some light on it or provide me with some ...
4
votes
2answers
165 views

Is there a minimal axiomatization of ZFC?

Working in ZFC, does there exist a set $\Sigma$ of sentences which axiomatizes ZFC (i.e. every sentence in $\Sigma$ is provable from your favorite axiomatization of ZFC, and vice versa) and is minimal ...
4
votes
1answer
48 views

Sufficient and necessary conditions

Is it correct to say that sufficiency and necessity of a condition is like saying "if and only if"?
7
votes
2answers
170 views

Theorems with one-line proofs [closed]

Inspired by this very concise answer, which proves that $$\sin^2(\theta)+\cos^2(\theta) \equiv 1 $$ as follows: $f(\theta)=\cos^2\theta+\sin^2\theta \quad;$ then it's simple to see that ...
15
votes
16answers
1k views

Beautiful, simple proofs worthy of writing on this beautiful glass door [closed]

What are some of the more beautiful proofs you know? I am measuring beauty in two dimensions -- first, how conceptually elegant is it and second, how aesthetically pleasing is it. Context: I work ...
9
votes
3answers
139 views

The category of theorems and proofs

On a philosophy website, it said that you could have a category with theorems as objects and proofs as arrows. This sounds awesome, but I couldn't find anything on the web that has both "category" and ...
4
votes
2answers
129 views

What if a conjecture were provably unprovable?

Suppose we found a proof that "The Twin Prime Conjecture cannot be proven", without any conclusion as to the conjecture itself being true or false. Is it then possible for the conjecture to be true? ...
6
votes
1answer
95 views

Is there a way to tell how many different ways you can prove a theorem?

Consider the question. Given the nature of a sentence $S$, it there any way to tell how many different ways you can prove this sentence? Proofs are not distinct if we have a situation such as: $P ...
0
votes
2answers
34 views

Prove that the set $C = \{x \in\Bbb R : ax\le b\}$ is convex

Prove that if a and b are real numbers, then the set $C = \{x \in\Bbb R : ax\le b\}$ is a convex set. My solution so far: To show that a set $C$ is convex it needs to be shown that for for every ...
0
votes
2answers
35 views

Trying to disprove a statement - some partial working included

I am trying to find a counter example to show that the statement below is false, but I am having difficulty in trying to find a reasonable argument. Here is the statement: $n^2-12n + 35 \geq 0$ for ...
1
vote
2answers
94 views

Is it possible to prove that the encoding of existentials in System F is valid?

In Girard's Proofs and Types, under item 11.3.5, second-order existential quantification is encoded in System F using universal quantification as follows: $$ \Sigma X.V \equiv \Pi Y. (\Pi X.(V \to ...
1
vote
0answers
87 views

Do we know that if $\pi$ is normal then there is a proof of it?

We do not know whether $\pi$ is normal or it is not and many other weaker statements, e.g. (*) $\pi$ contains infinitely many $0$s. Inspired by the Godel's incompleteness theorem that there are some ...
2
votes
1answer
140 views

What if 'proof by contradiction' is not a valid method of proof?

I've just been reading this question about the existence (or lack thereof) of contradictions in maths. I've been wondering: What if 'proof by contradiction' is not a valid method to (dis)prove a ...
2
votes
1answer
57 views

Use a proposition to prove another proposition

I'd like to ask for help with an exercise from Solow - How to Read and Do Proofs(3.16). I've tried to get through it but I can't make the proper connection between the two properties. I figured that ...
4
votes
3answers
118 views

Deriving $A \rightarrow ( B \rightarrow C ) \rightarrow ( ( A \rightarrow B ) \rightarrow ( A \rightarrow C ) )$ in the sequent calculus

I need to prove the following theorem: $A\to (B\to C) \to ((A\to B) \to (A\to C))$ using the sequent calculus method. Using the rules: $$ G, A \Rightarrow B,D \over G \Rightarrow A \to B , D ...
0
votes
2answers
43 views

Proof exercise: finding hypothesis and conclusion in a statement

I am starting learn mathematical proofs and I was doing some exercise that needed to identify the hypothesis and the conclusion in a given statement. And I'm having trouble trying to figure it out in ...
1
vote
2answers
196 views

Mathematical statements that cannot be proved or disproved [closed]

I've recently been reading about the continuum hypothesis and am fascinated by the fact that it cannot be proved or disproved, despite the fact that the statement itself is either true or false. What ...
0
votes
3answers
115 views

Proof by contradiction using counterexample

Why can't we use one counter example as the contradiction to the contradicting statement? Example: Let a statement be A where a-->b. We can prove A is not true by finding a counter example. Now, in ...
2
votes
0answers
63 views

Can we always give a direct proof? [duplicate]

This is something I was wondering about for quite a while. Is it possible to construct a statement that can only be proven by using 'proof by contradicition' or contraposition? Or to put it ...
4
votes
2answers
53 views

Biconditional statements with an “easy” direction.

I was reading through Lax's Functional Analysis, when I came across the following statement: Theorem: X is a normed linear space over $\mathbb{R}$, $M$ a bounded subset of $X$. A point $z$ of $X$ ...
-1
votes
3answers
96 views

Examples of revisited proofs after new theorems are discovered… [closed]

Are there any nice examples of "old" complicated proofs that become much simpler after new math is discovered years later? For instance, we know now that Pn+16< Pn+1 occurs infinitely often (where ...
0
votes
1answer
61 views

Existential introduction - required or not?

Consider a theory $T$ in first order logic, and a formula $C$. If there exist a proof of $C$, and that all formulas in $T$ and $C$, none of them contains $\exists$. The question is: does there always ...