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
1answer
28 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
49 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
47 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 ...
0
votes
1answer
53 views

Prove that the sequence {an} does not converge by showing it is not Cauchy

Let an = {7 + 4/n if n is even, 8 - 1/n if n is odd}. Prove that the sequence {an} does not converge by showing that it's not a Cauchy sequence. This is what I have so far. Let $\epsilon$ > 0. For ...
0
votes
1answer
22 views

Left “ and” inference rule G3cp

If you are at the stage of $$((P\supset Q) \wedge (Q\supset \bot)) \Longrightarrow (P \supset \bot)$$ And then you apply an $L\wedge$ rule, Why do you get $$(P \supset Q),(Q\supset\bot)),P ...
0
votes
1answer
17 views

Example of an axioms in G3Cp

Would $$A,B,C \Longrightarrow C,A$$ be an axiom in G3Cp? I ask because B is not on both sides and I am not sure if that makes a difference or not?
1
vote
1answer
38 views

Proofs from the book: in Praise of inequality's

I am reading a book with nice proofs, but i struggle at a few points. 1) why is $\sum_{i=1}^{k} p_i \int_{a_i}^{G} (\frac{1}{t} - \frac{1}{G}) dt + \sum_{i=k+1}^{n} p_i \int_{G}^{a_i} (\frac{1}{G} - ...
0
votes
0answers
16 views

Proofs for PCA, LDA, ICA, HMM learning algorithms and other stuff

I was wondering if there is some kind of encyclopedia of website for all known math proofs. I'm more interested in statistics (PCA, ICA, LDA, Factor analysis, HMM learning, GMM learning) and algebra ...
0
votes
2answers
80 views

Proof of the Dirichlet–Dini Criterion for Pointwise convergence of Fourier series

I have tried and failed to prove the Dirichlet–Dini Criterion for Pointwise convergence of Fourier series which is as follows (and is described here: ...
1
vote
1answer
32 views

What is the proof-theoretic ordinal of $PA+TI(\epsilon_0)$?

what is the proof-theoretic ordinal for $PA+TI(\epsilon_0)$, where $PA+TI(\epsilon_0)$ is Peano arithmetic where transfinite induction up to $\epsilon_0$ was added? Is it known? Thank you
0
votes
2answers
44 views

How would one prove this flavour of the triangle inequality?

I have to prove $|z_1 - z_2| \leq |z_1|+|z_2|$ where $z_1,z_2$ are in $\mathbb{C}$. What I wrote down is: $$|z_1| = |z_1+z_2-z_2| \geq |z_1-z_2|-|z_2|\implies |z_1|+|z_2|\geq |z_1-z_2|,$$as desired. ...
1
vote
0answers
17 views

Independence of FLT over weak systems

It is known that Fermat's last theorem can be proven in finite-order arithmetic (e.g. accoridng to this site). This is still an extremely high upper bound on proof complexity (for example, compared to ...
0
votes
0answers
17 views

Is it decidable whether there are finitely or infinitely many positive integers n such that the (2^n)+1th last digit of 3^(2^n) in base 2 is 1.

It seems so obvious that there are infinitely many such n because using a probabilistic arguement, it seems like there's no chance of there only being finitely many of them. Yet, it seems impossible ...
2
votes
1answer
47 views

Next step to reach the contradiction?

This is a problem from Discrete Mathematics and its Applications Here are my notes and my current work so far for this problem. I started with an assumption that what i am trying to prove is ...
0
votes
2answers
38 views

What to use for r in proof by contradiction?

This is a problem from Discrete Mathematics and its applications To this proof, I am trying to use proof by contradiction. Here is how the book described the process of proof by contradiction. I ...
0
votes
0answers
24 views

Are proofs for many-sorted first order logic shorter than single sorted first order logic?

I understand that the expressive power of first order logic with one sort is the same as any many sorted first order logic, and that higher order logic with general semantics is the same as a many ...
3
votes
2answers
52 views

What is the fastest growing primitive-recursive-function?

Fast growing functions tend to be not primitive-recursive. So I wonder if there is a limit how fast a function can grow, if it is known that it is primitive recursive. What is the fastest growing ...
0
votes
1answer
41 views

What is the slowest growing function that cannot be proven to be total by PA?

I asked the question if PA can prove any function growing faster than $f_{\epsilon_0}(n)$ to be total. The answer was no. What about the converse : Can prove PA every function growing slower than ...
0
votes
1answer
44 views

Inference rule for Non-Empty Domains

I am currently experimenting with logic frameworks. I am basically using something along dependent types as in "Proof-assistants using Dependent Type Systems" by Henk Barendregt and Herman Geuvers. ...
4
votes
2answers
77 views

Is there any unreachable result?

I hope that this question is reasonable and make sense because I am not sure. Every theorem's proof is consisting of finite logical steps. Can a proof of the theorem require infinitely many ...
3
votes
0answers
61 views

Is the following derivation of Gödel's Paradox generalizable to an intuitionistic one using provability?

I will follow Goedel's original proof of Goedel's paradox located on pg. 264 of Hao Wang's A Logical Journey: From Gödel to Philosophy. With this in sight, and to also avoid confusion, I will also ...
5
votes
1answer
41 views

Can PA prove very fast growing functions to be total?

The Goodstein-sequence is a total function, but PA cannot prove this. Is this true for any other function with growth rate at least $f_{\epsilon_0}$ or are there functions growing at least as fast ...
1
vote
1answer
58 views

Proof in sequent calculus without cut

I met an exercise in Gaisi Takeuti, Proof Theory [Exercise 2.7, page 14]. How to construct a cut-free proof of$\ \forall xA(x)\rightarrow B\vdash \exists x(A(x)\rightarrow B)$, where A(a) and B are ...
1
vote
1answer
101 views

2 Questions regarding Relative Consistency Proofs

First Question: Let IC be the statement "There is an inaccessible cardinal." I have read that one cannot prove (in ZFC) the relative consistency of ZFC + IC w.r.t. ZFC. i.e. $ Con(ZFC) \rightarrow ...
-3
votes
1answer
57 views

fake proof of $\forall a. \forall b. a = b \to 1 = 0$

I saw a less formal version of this fake proof that claimed to prove $2=1$ but because it assumed $a=b$ from the start I knew why it was wrong. It does seem however that the proof can be used to prove ...
0
votes
1answer
53 views

Beginning Haskell - cannot understand proof

I've just started reading "Thinking Functionally with Haskell" by Richard Bird In the preface he states : And after stating the proof he also states the proof will be used throughout the book. ...
1
vote
2answers
29 views

What does this proposition mean?

$∀x ∈ P(\Bbb{N}), x \notin \{\} \Rightarrow ∃y ∈ x, ∀z ∈ x \ | \ y < z$ Where $P(x)$ is the power set. I'm interpreting it as "in all subsets of the natural numbers, there exists a value smaller ...
2
votes
0answers
52 views

How to check homeomorphic embedding relation programmatically?

This is a follow up to this question and Deedlit's answer. I'm looking for a precise definition of the "hem?" (tree A homeomorphically embeddable in tree B?) relation, preferably in terms of a ...
1
vote
2answers
50 views

Help with understanding this proof in discrete mathematics?

This is the question and solution: Q: Prove that for any integer $a$, $2a + 1$ and $4a^2$ + 1 are relatively prime. A: Since $4a^2 + 1 = (2a − 1)(2a + 1) + 2$, any common divisor of $2a + 1$ and ...
0
votes
1answer
49 views

Proof by induction of this formula? [duplicate]

$2^0+2^1+2^2+...+2^n$ for $n ∈ \mathbb{N}$ U ${0}$. I made a conjecture that this is $2^{n+1} - 1$. Now I have to prove it by induction. I tested the base case where it's equal to zero, and it ...
0
votes
0answers
25 views

prove corollary to the Universal Non-Euclidean Theorem?

For any line l and any point P not on l, there are infinitely many lines through P parallel to l. In the proof of the theorem, the choice of point X on m uniquely determines the line PS. Show that ...
0
votes
1answer
26 views

Z / 6Z being a set of well dedfined equivalence classes, and a congruent to b(mod 6)

why is this = [0],[1],[2],[3],[4],[5],[6] and how would I define f Z/6Z - Z/6Z by f([a]) = ([2a]). I have the proof but I don't understand it. Proof: Assume [a1] = [a2] in Z/6Z. then a1 congruent to ...
0
votes
1answer
43 views

Did I do this big-Omega proof correctly?

Prove or disprove: 6n^3 – 4n^2 + 3n +2 is in Ω (5n^3 – n^2 + n +1). So I'm not sure if I did this right or not, any pointers or the correct steps would be helpful Ǝc ∈ ℝ+, ƎB ∈ ℕ, ∀n ∈ ℕ, n ≥ B ⇒ ...
0
votes
1answer
23 views

Proving Theorem: subspace of polynomials of degree two or less?

How can I prove that the set $S$ of polynomials of degree $2$ or less, whose coefficients sum to zero, is a subspace of all polynomials with degree $2$ or less? I know I need to show that $a+b+c=0$ ...
0
votes
1answer
24 views

Define $f:\mathbb{Z}/4\mathbb{Z}\to \mathbb{Z}/4\mathbb{Z}$ by $f([a])=[3a+1]$.

Define $f:\mathbb{Z}/4\mathbb{Z}\to \mathbb{Z}/4\mathbb{Z}$ by $f([a])=[3a+1]$. Prove that $f$ is well-defined, surjective and injective I don't really have a problem with figuring out if it's ...
1
vote
4answers
54 views

Proof by Induction Divisibility.

$6^n-5n+4$ is divisible by 5 for all positive integers $n$. $n >=1$ Prove By Induction My attempt is as follows: $n=1$ $6^1-5(1) +4$ $=5$, Therefore 5 is divisible by 5 so $n=1$ is true ...
2
votes
3answers
49 views

How can I prove that the square of an even number ends in 0/4/6?

I am trying to prove that the last digit of the square of an even number is either 0, 4, or 6 but I'm completely lost and have no idea how to tackle this problem.
2
votes
1answer
91 views

Uncountable reals in the theory

The Question I'm looking for a possibility to somehow proof the "essence" of Cantor's diagonal argument within a recursive first-order theory which is satisfied by the reals (better: within a theory ...
2
votes
0answers
34 views

How far can-I rewrite in lambda functions?

I am quite new with the lambda calculus. I am experimenting lambda-calculus proofs through the coq proof assistant, but the question I have is not related to coq (I guess). However, I'm going to use ...
0
votes
1answer
38 views

Euclid's proof for infinitely many prime numbers

Prove that there are infinitely many primes congruent to 3mod4 using euclid's proof for infinitely many prime number. I guess I don't really know where to start because I don't understand euclid's ...
1
vote
1answer
50 views

Comparing Statements and predicates using Truth Tables

Consider the four statements: $∃x$ $∀y$ $p(x, y)$ $∃y$ $∀x$ $p(x, y)$ $∀x$ $∃y$ $p(x, y)$ $∀y$ $∃x$ $p(x, y)$ which we call S1, S2, S3 and S4 respectively. Does there exist a predicate p such ...
0
votes
3answers
53 views

Proving $f\colon S \to S$; $f(x) = 1/x$ is bijective

Hey I'm trying to figure out this proof. I don't know if anyone could help but I would really appreciate it! Let $S = \mathbb{R} \setminus \{0\}$. Prove that the function $f\colon S \to S$; $f(x) = ...
1
vote
1answer
45 views

Model-theoretic question about language of field theory.

Let $\mathscr{L}=\{+,·\}$ be the language of the theory of fields. Let $\phi$ be a sentence in this language. Show, using the compactness theorem of first-order logic, that if $\phi$ holds in finite ...
1
vote
1answer
56 views

Proof Strategy, Power sets, and Injections

Let $S$ and $T$ be sets and define the function $$f:\mathcal P(S) \times \mathcal P (T)\to \mathcal P(S \cup T)$$ by $f(A,B) = A \cup B$ for all $A \subseteq S$ and all $B \subseteq T$. Prove that ...
11
votes
2answers
922 views

How to find the shortest proof of a provable theorem?

Roughly speaking, there are some fundamental theorems in mathematics which have several proofs (e.g. Fundamental Theorem of Algebra), some short and some long. It is always an interesting question ...
1
vote
2answers
25 views

how to know when a particular proof is appropriate for the given problem?

The main trouble I am currently having in math is knowing when the use cases are appropriate in a proof. I see many videos where they seem to choose a strategy like proof by contrapositive or proof by ...
2
votes
2answers
56 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
46 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
42 views

Prove the 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 ...
0
votes
1answer
77 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)