# Tagged Questions

Proof theory is an area of logic that studies proof as formal mathematical objects. If you'd like advice on the presentation of a proof you have in draft, use proof-writing instead. If you'd like feedback on its validity, use proof-verification. If none of the above apply, you do not need a proof-* ...

31 views

### Non model-theoretic, constructive proof that it is valid to introduce new unique constants in a first order theory with equality

I'm currently reading through Mendelson's `Introduction to Mathematical Logic', and one of the proofs has left me dissatisfied. In general, I am fine with seeing metamathematical results proven ...
108 views

### natural deduction: introduction of universal quantifier and elimination of existential quantifier explained

Currently, I am dealing with the calculus of natural deduction by Gentzen. This calculus gives us rules to manipulate so-called sequents. Definition. If $\phi_1,\dots, \phi_n,\phi$ are formulas, then ...
98 views
+50

### Does PA prove that Con(PA) implies Con(ZF-I) and Con(NFU)?

I read from many sources that PA and ZF-I (a suitable axiomatization of ZF minus Infinity plus its negation) are bi-interpretable, but is PA enough to prove that they are equiconsistent? Specifically ...
51 views

### What is the intutition behind the negative exponential ? in linear logic?

The positive exponential ! has a very satisfying interpretation in terms of the standard resource interpretation of linear logic. Given a resource $a$, we know that $!a$ means an infinite supply of $a$...
59 views

### Basic: Sequent definition, and-introduction, and iff

I am reading through "Mathematical Logic by Ian Chiswell & Wilfred Hodges"(amazon, and publisher) So far have it has covered $\land$-Introduction and $\land$-Elimination Sadly this text only has ...
52 views

### Elementary proof of Fermats Last Theorem [on hold]

Considering the number of possible combinations of 5 pages of elementary algebra, isnt it exceedingly likely that there exists an elementary proof of FLT using only elementary algebra and a couple of ...
47 views

61 views

### Number of proofs for a statement

On this site, people ask questions and then answers and proofs for those answers come from readers. Readers mark the best answer and then people focus on the next interesting topic. Sometimes, a ...
131 views

### Are geometric proofs less reliable than others?

When I submit a homework with a proof that uses a graph, ball, shape etc., most of the time the professors are not happy with them. They respond with a statement like: "The proof you made seems very ...
79 views

### easy proof of the completeness theorem [closed]

The completeness theorem of first-order logic states: If $\Phi\models\phi$, then $\Phi\vdash\phi$. Assume that I have a calculus $\vdash$ in mind for which I want to prove this completeness theorem. ...
198 views

### Calculus of Natural Deduction That Works for Empty Structures

Currently, I am dealing with the calculus of natural deduction by Gentzen. This calculus gives us rules to manipulate so-called sequents. Definition. If $\Gamma$ is a set of formulas and $\phi$ a ...
25 views

### Set-Theoretic Probability

Consider $\{B_i | i \in I\}$ be a collection of events where $I$ is an arbitrary index set. I would like to show that $$\left(\bigcup_{i \in I} B_i\right)^c = \bigcap_{i \in I} B_i^c.$$ My friend ...
56 views

### A question regarding contrapositive for implications

I am slightly confused about the negation for an implication after encountering two questions as follows: "Let P be the statement: If 3 is even, then 6 is even or divisible by 5. Write the negation ...
79 views

### Changing Hilbert-style axioms

Consider the following system for Hilbert-style deduction: Axioms: $A \rightarrow (B \rightarrow A)$ $(A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C))$ ...
17 views

### Proof of the lack of existence of a Hamiltonian Cycle

Consider a graph of $|V| = 2k+1$ vertices with $k+1$ of those vertices having exactly degree $2$ such that none of those degree $2$ vertices are adjacent to each other. I want to go about proving that ...
43 views

### How to generalize the principle of mathematical induction for proving statements about more than one natural number?

Suppose that $P(n_1, n_2, \ldots, n_N)$ be a proposition function involving $N >1$ positive integral variables $n_1, n_2, \ldots, n_N$. Then how to generalise the familiar induction to prove this ...
2k views

### What is the difference between ⊢ and ⊨?

I want to know the difference between ⊢ and ⊨. http://en.wikipedia.org/wiki/List_of_logic_symbols ⊢ means ”provable” But ⊨ is used exactly the same: ...
43 views

### How is the entropy of the normal distribution derived?

Wikipedia says the entropy of the normal distribution is $\frac{1}2 \ln(2\pi e\sigma^2)$ I could not find any proof for that, though. I found some proofs that show that the maximum entropy resembles ...
85 views

### Examples of provably${}^n$ unprovable statements

Given any statement $A$ and a classical theory $T$ which we assume is at least as strong as Peano Arithmetic ($\sf PA$), we have that $T\vdash A$ implies $T\vdash T\vdash A$ (that is, if a statement ...
54 views

### Using induction to prove for $n ≥ 1,$ $1 \times 5+2\times6+3\times7 +\cdots +n(n + 4) = \frac 16n(n+1)(2n+13).$

This is a very interesting problem that I came across in an old textbook of mine. So I know its got something to do with mathematical induction, which yields the shortest, simplest proofs, but other ...
167 views

72 views

### Logical limitations of Proofs by Contradiction

In general proofs by contradiction go as follows: Given an arbitrary hypothesis, $\ p \implies q$, we assume $\left(p\implies q\right) = T$, and then we show that by assuming the hypothesis to be ...
48 views

### Recursion Proof by Induction

Given: f(1) = 2 f(n) = f(n-1) + 3, for all n>1 It can be evaluated to: ...
440 views

### Proof that SAT is NPC

I am not really sure I understand the idea behind Cook theorem (it says that SAT is a NP-complete problem). I read the proof with all its parts corresponding to the Turing machine TM solving it (TM ...
144 views

### On “why” questions in mathematics

In response to the question How would one be able to prove mathematically that $1+1 = 2$?, Asaf Karagila explains: In a more general setting, one needs to remember that $0,1,2,3,…$ are just ...
54 views

### Gödel number for contradicting modus ponens?

When Gödel numbered statements, for instance modus ponens and connectives got their own numbers, does it matter which number each connective gets as long as they are different? Sometimes I'm not ...
30 views

### What are some active areas of research in proof theory?

Is there any research activity going on in the field of proof theory today? If so, what are some of the most active areas, what types of questions do they deal with, and where can I go to find out ...
44 views

### How to prove facts regarding sentential logic

Recently I have been very fascinated by the claim and impact of Godel's incompleteness theorem. To understand the proof given by Godel, I felt the need to read an introductory book in logic to begin ...
25 views

### Why don't the quantifiers split in linear logic?

Every presentation of linear logic I've seen seems to either omit or treat quantifiers as an after-thought. Even Girard says that there is "little to say" about them. However, if we view universal (...
21 views

### Proof that the union of rational and irrational numbers sets is a set of real numbers [duplicate]

I see it all the time but is there a nice way to show that this is true? Or is this just a definition? I know that $\mathbb{Q} \subset \mathbb{R}$ and $\mathbb{I} \subset \mathbb{R}$, but how do we ...
27 views

50 views

### Weak Representability and Derivability Condition 1

Can someone point out the error in the following reasoning? Let K be an axiomatizable, consistent extension of Peano Arithmetic. Let P' denote the Gödel number for P. K is axiomatizable, thus Thm(k)...
20 views

### proof by induction of a graph theorem

I would like to proof the following theorem by induction: Theorem: If G is a graph that is not complete, then it is possible to add at least one edge to it. Inductive proof: Base case: Assume we ...
29 views

### Proof for: Let A and B be sets s.t $A \cap B = A$ iff $A \subseteq B$

I am practicing some proofs involving sets and I would like to see if what I did was a valid proof because it seemed to be different from the one provided in the textbook I am using given that it did ...
103 views

### Can we prove that induction is impossible for some proofs?

I read in a book that Andrew Wiles first attempted proof by induction to prove Fermat's last theorem and that he gave up proving it with induction. Instead as far as I understand, Wiles proved some ...
155 views

### In which order should I learn the foundations of mathematics? [closed]

I know from Wikipedia that those are the four pillars of the foundations of mathematics: Proof theory Aximatic Set theory Model Theory Recursion Theory and I want to learn all of them, the problem ...
27 views

### What to call a term-in-context whose context contains exactly the variables occurring in the term?

In type theory, a term-in-context $\Gamma \vdash t : \tau$ is only well-formed when $\Gamma$ contains all the variables occurring in $t:\tau$. Is there a name for when it contains exactly the ...