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

3
votes
2answers
47 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 ...
3
votes
4answers
53 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$

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
47 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
54 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 ...
8
votes
0answers
132 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 ...
1
vote
1answer
40 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
17 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
57 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
35 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
46 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
20 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
58 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
48 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
200 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
107 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
33 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
68 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
346 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
73 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
58 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 ...
0
votes
0answers
15 views

Legendre polynomial related simple proof question

Given the set of orthogonal polynomials {Qi(x)}i=0 to n , a polynomial Pn(x) of degree ≤ n, can be written as: Pn(x) = a0*Q0(x) + a1*Q1(x) + · · · + an*Qn(x) for some a0, a1, . . . , an. Please help ...
1
vote
1answer
40 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 ...
4
votes
3answers
47 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
65 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 ...
1
vote
0answers
27 views

Is the full strength of first-order logic needed for dealing with equational theories?

More specifically, if we have an equational theory $T$ (a set of equations understood as being implicitly universally quantified), are the (equational) consequences of $T$ that can be proved with ...
0
votes
1answer
34 views

Coplanar Vectors Proof

I came across this question in a math textbook: Prove that the vectors a=3i+j-4k, b= 5i-3j-2k, c= 4i-j-3k, are coplanar. This was my attempt at a solution: If (a x b) x c = 0, then c is orthogonal ...
0
votes
1answer
24 views

Ellipses Conics Proof

We are covering conics in our school and we just finished the ellipse section. An ellipse, by definition, is the "set of points such that the sum of the distances from any point on the ellipse to two ...
2
votes
2answers
17 views

Proving or Disproving statements using sets

I just don't seem to get proofs or set theory so hopefully my question makes sense. I'm not sure when I should or shouldn't use an example to prove or disprove a statement? One example question is, ...
0
votes
1answer
38 views

Prove by contradiction that a circle chord is no longer than its diameter

Can anyone help me with this homework question of mine? I'm actually new to discrete mathematics and to be specific, with proofs. Here's the question, "Prove, by contradiction, that no chord of a ...
2
votes
1answer
30 views

Proving Roots by Theorems

Prove that the polynomial $p(x)=x^3-x+\frac{1}{4}$ has at least one root on the interval $[0,1]$, by using the Mean Value Theorem. Since we know that polynomials are continuous every where, $p(x)$ ...
1
vote
2answers
28 views

DAG proof by numbering nodes

Prove that a directed graph is acyclic if and only if there is a way to number the nodes such that every edge goes from a lower number node to a higher numbered node. I know this is true and that ...
3
votes
1answer
44 views

What is the least ordinal $\beta$ for which the function $f_\beta(n)$ in fast-growing hierarchy is incomputable?

Fast-growing hierarchy consists of a transfinite succession of faster growing functions $f_\alpha$: $f_0(n) := n+1$, $f_{\alpha+1}(n) := f^n_\alpha(n)$, $f_{\alpha}(n) := f_{\alpha[n]}(n)$ if ...
1
vote
0answers
57 views

Disproving $\neg Q$ proves Q in all cases?

Does disproving the negation of a claim prove the claim in all scenarios and sufficient enough to say Q is true? Even if Q is an implication, or an equality, or etc? What about vacuous truths? Can ...
0
votes
0answers
42 views

Prove that the following Horn satisfiability problem is P-complete

Show that the following Horn satisfiability problem is P-complete: given a set of Horn clauses, is there a variable assignment which satisfies them? This is P's version of the Boolean satisfiability ...
0
votes
0answers
31 views

Proof the Restricted Case of CVP is P-complete

Show that the following Restricted Case of CVP is P-complete: Like CVP, except the input circuit satisfying the following conditions: All gates are placed int layers; the inputs of a gate come from ...
0
votes
2answers
40 views

How do I complete a proof with intersection and complements?

For all sets $A$ and $B$, $(A \cap B)^c = A^c \cup B^c$ I am confused how complements play a role in the proof. Can somebody explain that please. Thank you!
0
votes
2answers
42 views

How to prove the relation is transitive?

Problem: Consider the relation R on $N$ defined by $x$R$y$ iff $2$ divides $x + y$. Prove that R is an equivalent relation My work: I know that to prove that a relation is an equivalent relation, ...
1
vote
5answers
56 views

How to conclude 4 + 4k is divisible by 8 in proof by induction?

Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 35, pg 330]. Problem: a) Use mathematical induction to prove that $n^2$ - 1 is divisible by 8 whenever n is an odd ...
1
vote
2answers
58 views

Prove that if a|b and b|c then a|c using a column proof that has steps in the first column and the reason for the step in the second column.

Let $a$, $b$, and $c$ be integers, where a $\ne$ 0. Then $$ $$ (i) if $a$ | $b$ and $a$ | $c$, then $a$ | ($b+c$) $$ $$ (ii) if $a$ | $b$ and $a$|$bc$ for all integers $c$; $$ $$ (iii) if $a$ |$b$ and ...
2
votes
1answer
44 views

Rearranging an equation to form the limit definition of derivative

I am following a proof which starts with the following inequalities: $$S_{i}(v) \geq S_{i}(v+dv) + (-dv)P_{i}(v+dv)$$ $$S_{i}(v+dv) \geq S_{i}(v) + (dv)P_{i}(v)$$ From this, we rearrange to form: ...
3
votes
1answer
82 views

Certain Geometry proofs seem not rigorous at all.

For example, this proof from Kiselev's "Planimetry": Theorem: The diameter (here, AB), perpendicular to a chord (here, CD), bisects the chord and each of the two arcs subtended by it. The proof: ...
0
votes
1answer
53 views

More details of the “Standard View og Proof” with three points are needed.

I have a Danish book about the theory of knowledge for mathematicians which I have tried my best to translate some parts into English. According to the lecturer, we can with "certain reasonability" ...
2
votes
1answer
74 views

Maximal Principle: Why using the new transition matrix $\tilde{P}$?

First some notation: Let $(X,E,P)$ denote a finite, irreducible Markov chain with finite state space $E$ and transition matrix $P$. Choose and fix a subset $E^°$ of $E$, which will be called ...
1
vote
1answer
24 views

I have a problem understanding conceptually > using natural numbers

I am learning proofs with $\mathbb N $. I don't have significant problems using the axioms to prove propositions, I have a problem understanding certain axioms and the definition of >. 1) If $m,n ...
0
votes
3answers
39 views

Prove that if $n \in \Bbb{N}$ and $n > 1$ is not prime, then $\exists p$ prime such that $p \mid n$ and $p \leq \sqrt{n}$

Not really sure how to do this question this is what I have so far $n = a \cdot b$ $(a \leq b)$ $a > \sqrt{n}$ $b > \sqrt{n}$ $ab > n$