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

0
votes
1answer
15 views

How to show that the displaying numbers of a onto function is k!S(n,k)?

Let it be $A$,$B$ sets that $|A|$=$n$, $|B|$=$k$ and $|A|>|B|$. How to show that the displaying numbers of an onto function $f$:$A$ $\rightarrow$ $B$ is: $\begin{Bmatrix} n \\ k\end{Bmatrix}$$k!$ ...
2
votes
1answer
63 views

prove that this number contains two equal digits

We delete the first digit from the number $7^{1996}$ and then we add it to the remaining number, repeat this until we get a number consisting of $10$ digits, prove that, this number contains two equal ...
-2
votes
2answers
49 views

Prove that to any three numbers positive integers [on hold]

Prove that for any three positive integers, following equality holds $$\operatorname{lcm}(ab , bc , ca ) \cdot \gcd(a , b, c )=abc$$
3
votes
1answer
63 views

Proving a trigonometric identity with tangents [on hold]

Prove that: $$\tan^227^\circ +2 \tan27^\circ \tan36^\circ=1$$ any help, I appreciate it.
2
votes
5answers
142 views

Rigorous proof of '${\{A \Rightarrow B}\} \iff {\{\neg B \Rightarrow \neg A}\}$' for a high school student

One method to prove the statement 'If A, then B' is to prove that 'If not B, then not A'. First time that I saw this method it was not (and still isn't) obvious. So I used a more obvious example to ...
2
votes
4answers
222 views

How do I know which of these are mathematical statements?

While reading this book called "How to Read and do Proofs" by Daniel Solow(Google) I found the following exercise at the end of the first chapter. So how do I know if something is a mathematical ...
1
vote
2answers
122 views

Is Fermat's Last theorem equivalent to $1 + 1 = 2$?

I got into a debate with someone concerning whether FLT is equivalent to $1 + 1 =2$. He said common sense tells us it isn't equivalent. However, I disagreed. Since both are provable statements, they ...
2
votes
1answer
41 views

Can we see natural deduction rules as functions or even as formal grammars?

Is there a way of seeing natural deduction rules as functions or even as formal grammars, maybe context-free grammars or Lambek grammars? It seems quite "easy" to see the rules as functions which take ...
0
votes
1answer
61 views

Using Sequent Calculus to prove $\exists x_1 x_2 [ B ( x_1 , x_2 ) \rightarrow \forall y_1 y_2 B ( y_1 , y_2 ) ]$

I need to prove the validity of the following formula using the sequent calculus LK: $$ \exists x_1 x_2 [ B ( x_1 , x_2 ) \rightarrow \forall y_1 y_2 B ( y_1 , y_2 ) ] \text{.} $$ I already had a look ...
2
votes
2answers
57 views

Explanation on the symmetry between identity axiom and cut rule

In Proofs And Types at the beginning of 5.1.4 Girard says that the identity axiom is somewhat complementary to the cut rule, more specifically 'The identity axiom says that $C$ (on the left) is ...
6
votes
2answers
110 views

What does “rigorous proof” mean?

I have heard several times that some mathematician has given another and more rigorous for an established theorem, but I don't know what does it really mean and what differences makes it to be more ...
0
votes
1answer
22 views

Problem with a step in a proof in predictive control

I'm trying to follow a demontration written in an optimal control paper. In one of the steps, it states What I'm having troubles with is the last step, it states that because of the convexity of ...
5
votes
0answers
59 views

What are some arguments/counterarguments for Zeilberger's “proof certificates”?

Here is the quote I wish to ask about: "I speculate that similar developments will occur elsewhere in mathematics, and will 'trivialize' large parts of mathematics, by reducing mathematical ...
3
votes
1answer
54 views

Encyclopedia of Mathematical Proofs with no English

I was wondering if anyone is aware of a modern book that builds a subset of elementary number theory from Peano axioms preferably in a Principia Mathematica fashion? Or similarly an encyclopedia of ...
0
votes
0answers
27 views

Is it always possible to algebraically express a function defined by a set of rules?

Let's say you have an arbitrary function defined by a set of rules such that for example: Domain $\hspace{9mm}$ Range $\hspace{5mm}$ 1 $\hspace{23mm}$ 2 $\hspace{5mm}$ 2 $\hspace{23mm}$ 2 ...
3
votes
1answer
79 views

Consistent, complete axiom system that proves its own consistency

Is there a consistent, complete axiom system that proves its own consistency? I know that this question isn't exact and I haven't defined when an axiom system proves its own consistency because ...
0
votes
1answer
36 views

What kind of trivial statement still needs to be proven?

There are many statements that seem to be needless of a proof since they are ‘evident’ mainly because of our intuition. But some of them have proofs. For example, in C. Adams’ Introduction to ...
2
votes
0answers
28 views

Clever proofs that prove one identity is equal to another, without going through the original identity?

In a previous question I attempted to formalize the argument of going from one proof of an identity to another, which turned out to be harder than I thought. The thing is, while it may be impossible ...
2
votes
0answers
25 views

Is it always possible to go from one identity to another?

This question was inspired by this Quora question. I'm sure lots of you are familiar with the fact that we have many different representations of $\pi$, things like $$ \begin{align} \pi & = ...
0
votes
7answers
108 views

Prove $ \{(p \lor q) \land (p \implies r) \land (q \implies r) \} \implies r$ is a tautology using logical properties

I spent quite a bit of time on this and have little to no ideas on how to proceed. Using the conditional laws and De Morgan's law, I got to $$( \sim p \land \sim q) \lor (p \land \sim r) \lor(q ...
1
vote
1answer
32 views

Isomorphic: Properties Proved for A are True for B?

To make this a little more concrete, consider vector spaces. An isomorphism between two spaces is an invertible linear transformation. It seems to then be commonly asserted or assumed that if A and ...
1
vote
1answer
57 views

Using the notion of provability only, how to show that $\Gamma \nvdash \varphi$?

For a practical example, suppose I want to show that $\{ P\} \nvdash Q$. From completeness, this is trivial: just find a model where $P$ is true and $Q$ false. But suppose I am stubborn and I don't ...
3
votes
2answers
68 views

Proving that $\sum_{i=2}^n(5i-4)=\frac{n(5n-3)-2}{2}$ for all $n\geq 1$ by mathematical induction

I have this question: Show, using mathematical induction, that for all natural numbers $n$, $$6 + 11 + 16 + 21 + \cdots + (5n-4) = \frac{n(5n-3)-2}{2}$$ I am confused in that that question states ...
4
votes
4answers
79 views

If $T$ a consistent set of sentences and $a,b$ sentences such that $T\vdash (a\rightarrow b)$and $T\vdash (\lnot a\rightarrow b)$ Then $T\vdash b$ [closed]

I am stucked at this problem for a long time: Let $T$ be a consistent set of first-order sentences and let $\alpha,\beta$ be sentences. Prove that if $T\vdash( \alpha\rightarrow \beta)$ and ...
1
vote
1answer
54 views

Prove by Natural deduction that $\lnot\exists xP(x)\rightarrow\forall x\lnot P(x)$

I got this problem: Prove by Natural deduction in First Order Logic that $\lnot\exists xP(x)\rightarrow\forall x \lnot P(x)$ I tried to prove it using the Contradiction Theorem but I got ...
2
votes
0answers
35 views

What exactly is wrong with this argument (Lucas-Penrose fallacy)

Argument "For every computer system, there is a sentence which is undecidable for the computer, but the human sees that it is true, therefore proving the sentence via some non-algorithmic method." ...
0
votes
1answer
71 views

Mathematical Induction. Horses made me question my understanding

I recently read about the false inductive proof that all horses are the same colour. There are some mathSE threads about this already (MathSE_thread_1, MathSE_thread_2). After reading this, I now ...
9
votes
0answers
160 views

The ethics of Borel determinacy

I was speaking with a friend the other day, and I happened to say "morally, Borel determinacy is as strong as ZF." I was riffing on the well-known result of Harvey Friedman, that we need ...
2
votes
1answer
49 views

Left and Right hand associativity equivalent first order logic

Say we are in a first order theory, and one of our inference rules is the associative rule saying that we can infer $(A \vee B) \vee C$ from $A \vee (B \vee C)$. Using the other logical inference ...
1
vote
0answers
18 views

Showing that language $L^{'}$ is regular given $L$ is regular [duplicate]

Say $L \subseteq \{a,b\}^*$ is a regular language with words whose length is divisible by 3. Each word $w \in L$ has the form $w=xyz$ with $|x|=|y|=|z|$, where $y$ is then called the middle third of ...
1
vote
0answers
27 views

Series Proof Question [duplicate]

By considering the partial sums for S, that is Sn =1+2+3+···n show that the infinite series S does not converge. However in this video http://www.numberphile.com/videos/analytical_continuation1.html ...
1
vote
1answer
20 views

Proof for equalities remaining

Imagine the relation x@y = z, where @ is some operation (and so is #). We often use the property that (x@y)# = z# to solve for variables. For example, $$2x = 9/2$$ We say that it will still be equal ...
1
vote
2answers
64 views

Josephine problem

So the problem is Suppose there are 2n people in a circle; the first n are “good guys” and the last n are “bad guys.” Show that there is always an integer m (depending on n) such that, if we go ...
1
vote
1answer
37 views

proof by contradiction

I have the following theorem: and I want to prove it by contradiction. I have started by negating the consequence, so I will have that so if I rearrange these terms I will have that: which ...
1
vote
0answers
47 views

Show that if A and B are strictly convex, then A + B is strictly convex or provide a counter example.

We have: If A is open: $\exists x,y \in A,$ $x \neq y$ such that $\lambda x+(1-\lambda y)\in \dot A $ (the interior) and $\exists u,v \in B,$ $x \neq y$ such that $\lambda u+(1-\lambda v)\in ...
1
vote
1answer
21 views

Clarification when using Mean Value Property to prove Fundamental Theorem of Algebra

We say that $f$ satisfies the Mean Value Property (MVP) on a ball $B(a,R) = \{z; |z-a| <R \}$ if $$ f(a) = \frac{1}{2 \pi} {\int_0}^{2\pi} f(a + te^{i \phi}) d \phi$$ for $0 < t <R.$ It is ...
2
votes
1answer
61 views

What is meant by “constant” in Liouville's Theorem?

Liouville's Theorem states that: Every holomorphic* function for which there exists a positive number M such that $|f(z)| \le M$ for all $z \in \mathbb C$ is constant. I'm using this to prove ...
1
vote
2answers
49 views

Discrete Math Informal Proofs Using Mathematical Induction

Need to do a proof by mathematical induction using 4 steps to show that the following statement is true for every positive integer n and to help use the weak principle of mathematical induction. $2 + ...
6
votes
8answers
206 views

Why is $n^2+4$ never divisible by $3$?

Can somebody please explain why $n^2+4$ is never divisible by $3$? I know there is an example with $n^2+1$, however a $4$ can be broken down to $3+1$, and factor out a three, which would be divisible ...
0
votes
1answer
35 views

How to go about a “not divisible by..” proof

I need to show the following proof: For any integer x, x^2 + 4 is not divisible by 3. I was trying proof by contraposition, but I do not believe that is the most efficient way to go about this. ...
9
votes
3answers
108 views

role of definitions in proofs

Definitions are needed to define objects and such, however I am confused as to where definitions come from. I feel that they cannot be something that we arbitrarily define because simply saying ...
1
vote
2answers
36 views

Prove using PMI that if $A$ is denumerable and $B$ is finite, then $A \cup B$ is denumerable.

This is what I have thus far: Claim: If $A$ is denumerable and $B$ is finite, then $A \cup B$ is denumerable. Proof. Suppose $A$ is denumerable and $B$ has $n$ elements and $B = \{b_1, b_2, b_3, ...
0
votes
1answer
73 views

Proof of infinite monkey theorem. [duplicate]

I was just wondering, does the infinte monkey theorem also has a proof? And why is this called a theorem? It is sheer common sense. And what are its applications. I have heard about PHP and IEP and I ...
34
votes
2answers
351 views

When are two proofs “the same”?

Often, we find different proofs for certain theorems that, on the surface, seem to be very different but actually use the same fundamental ideas. For example, the topological proof of the infinitude ...
1
vote
2answers
82 views

How can I start to learn proof theory?

I'm studying computer science and I realized that I have problems in working with mathematical proofs. They are for example part of my class Formal Systems and Automata. I'm really interested in ...
0
votes
0answers
60 views

A provability puzzle

This is a problem I came up with on my own, and it has me stumped, so I am going to pose it as a kind of puzzle. Let $F$ be a formal proof system, recursively axiomatizable, with an acceptable ...
1
vote
1answer
42 views

Proof by Strong Induction

$a_0 = 1, a_1 = 1, a_k = 2a_{k-1} + 2a_{k_2}$ for $k≥2$ For all integers $n≥0$, $a_n= \frac{1}2[3^{n}+(-1)^n$] Proof By Strong Induction: Basis: $F(0), F(1), F(2), F(3), F(4), F(5)$ Inductive ...
3
votes
3answers
48 views

Proof by Strong Induction for $a_k = 2~a_{k-1} + 3~a_{k-2}$

$$\begin{align} a_0 &= 1 \\ a_1 &= 1 \\ a_k &= 2~a_{k-1} + 3~a_{k-2} \quad \text{ for } k \ge 2 \end{align}$$ Proof by Strong Induction: For all non-negative integers $n$, $a_n$ is an ...
0
votes
2answers
30 views

Proof of L'Hospital with power series

I'm having a bit of problem with this question. I feel like I have to prove the l'hospital's rule but I don't know where to start especially because I have to use the power series. Suppose that the ...
1
vote
1answer
72 views

What does it mean by Proving false

With respect to the recent finding of a bug in a Coq theorem prover in which false was proved, I'm asking this question. As a hobbyist studying maths, I'm ...