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

1
vote
2answers
50 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
54 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
12 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
37 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
46 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
1answer
35 views

Proof that polynom $P:\mathbb{R}^n\to\mathbb{R}$ is continuous

Could you tell me some webpages or books where I can find the proof that polynom $P:\mathbb{R}^n\to\mathbb{R}$ is continuous. I know how it can proof if $P:\mathbb{R}\to\mathbb{R}$, but I don't know ...
0
votes
2answers
27 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
60 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
26 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
0answers
20 views

proof calculus in math proofs

Proof theory, is in some way associated with the concept of proofs in mathematics, as proofs of geometric topics, topology, and so on?? And if the three best-known proof calculi (the Hilbert-style ...
0
votes
1answer
25 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
22 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
34 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
28 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
17 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
39 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
56 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
35 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
26 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
38 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
30 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
52 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
45 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
31 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
79 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
50 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
73 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
22 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
38 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$
19
votes
3answers
2k views

Why is Gödel's Second Incompleteness Theorem important?

Given that the consistency of a system can be proven outside of the given formal system, Gödel says, It must be noted that proposition XI... represents no contradiction to the formalities ...
-1
votes
1answer
46 views

How to prove the inductive step in this Mathematical induction problem?

Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 6, pg 342]. Problem: a) Determine which amounts of postage can be formed using just $3$-cent and $10$-cent ...
2
votes
2answers
34 views

How to come up with relation in induction hypothesis for strong induction

Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 2, page 341]. Problem: Let $P(n)$ be the statement that a postage of n cents can ...
0
votes
1answer
68 views

How to show the inductive step of the strong induction?

Note: This problem is from Discrete Mathematics and Its Applications [7th ed, prob 2, pg 341]. Problem: Use strong induction to show that all dominoes fall in an infinite arrangement of dominoes if ...
0
votes
2answers
44 views

How to get $k^{k + 1} + k^k$ to equate $(k+1)^{k+1}$?

This is a problem from Discrete Mathematics and its Applications Let $P(n)$ be the statement that $n!<n^n$, where $n$ is an integer greater than $1$. $\quad(a)$ What is the ...
0
votes
1answer
41 views

Perimeter problem involving different sized sticks?

Could you please help me find the answer to this question. I think it has something to do with grouping or pairing some numbers.I would appreciate easy-to-understand solutions. Thank you. There are ...
0
votes
0answers
59 views

How do I create this geometry proof? [duplicate]

I understand that a similar question like this has been asked before however, I did not understand the answers given. Thus, I would really appreciate it if you were to attempt to give an ...
0
votes
1answer
32 views

Prove every angle has a bisector.

Prove every angle has a bisector. I have successfully constructed a bisector and justified by construction. Now I need to put it in proof form. However, I technically do not know midpoints and ...
0
votes
1answer
32 views

What is the logic behind Jacobi iterative method?

The book I follow and on net also, all that I can find is the algorithm to find the solution, but I don't quite understand the physical significance or logic behind the algorithm. Can someone please ...
4
votes
6answers
132 views

Notable examples of “impossible” results ruled out by earlier barrier or no-go theorems or widespread beliefs

there is a certain style of type of proof in mathematics something like a "barrier theorem" but which also relates to widespread mathematical beliefs/ "conventional wisdom". an example would be the ...
0
votes
0answers
33 views

Law of one price theorem proof

There are two subparts to Fundamental Asset Pricing theorem. The LOOP (Law of one price) holds if and only if there exists a state price vector. In a market in which the LOOP (law of one price) ...
0
votes
1answer
24 views

Inversion lemma for G3ip

I'm following the book Structural Proof Theory by Negri and others. In it, they claim on page 32 about G3ip that if $⊢ _ n A \& B, Γ ⇒ C$, then $⊢ _ n A, B, Γ ⇒ C$. But, given that the only ...
0
votes
1answer
31 views

Set and Logic, Proving two quantifier the same

$(∃x∈A:P(x))∨(∃x∈B:P(x)) = ∃x∈(A∪B):P(x)$ I spent hours approaching this problem many different way By Definition: $(∃x∈A:P(x))∨(∃x∈B:P(x)) \\ ∃x:[(x∈A \to P(x) \vee (x∈B \to P(x)] \\ ∃x:[(¬x∈A ∨ ...
0
votes
1answer
66 views

Proof of subspaces of odd and even functions

$F^+(\mathbb{R})$, the set of even functions in $F(\mathbb{R}, \mathbb{R})=\{ f: \mathbb{R} \to \mathbb{R} \}$ and $F^−(\mathbb{R})$, the set of odd functions in $F(\mathbb{R}, \mathbb{R})$ are both ...
2
votes
1answer
64 views

What are 2-morphisms in the category of proofs?

After reading through "Categories for the practicing physicist" I came to learn there is a category whose objects are propositions $A,B,...$ and whose morphisms are proofs $f:A\rightarrow{B}$ that ...
0
votes
1answer
64 views

Mathematical Induction with Fermat's last theorem?

Question on Fermat's Last theorem: $\nexists a,b,c\in \mathbb N:a^n+b^n = c^n$ for all $n \in \mathbb N, n\ge 2$. Assume that we have shown a proof for the cases $n = 3$ and $n = 4$. Can we say ...
0
votes
0answers
39 views

Is the length of the proof of propositional tautology a PA-total function?

Suppose we have fix some interpretation of propositional (not first-order!) logic inside PA, and say $f(n) = $ {the maximum length of a proof of a tautology with $n$ propositional primitives} ...
1
vote
1answer
49 views

Proof of existence of “peaks” in The Sequential Compactness Theorem

According to Bolzano–Weierstrass theorem: How do we guarantee that EVERY sequence of real numbers has either infinitely or finitely many "peaks"? (Note that a subsequent is ordered in a way of ...
2
votes
1answer
56 views

Couple of questions from Takeuti's Proof Theory book

I am reading Gaisi Takeuti's Proof Theory (Second Edition, Dover), and I have a couple of questions: I) Right after the first (1.1.) definition, the author says that "In any case it is essential that ...
0
votes
0answers
53 views

Theorem of Lefschetz

If anyone has the book of James D. Lewis entitled: A survey of Hodge conjecture on page $58$, There are the famous theorem of Lefschetz $(1,1)$ "without proof it seems to me." Is that so? Could you ...