Tagged Questions

Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Questions which merely seek to apply logical or formal reasoning to other areas of mathematics should not use this tag. Consider using one of the ...

43 views

How is the set of all even numbers definable (from $\omega$)?

This Set Theory textbook (page 89) defines definable sets as follows: Definition 6.8. Given a set $a$ and a formula $\Phi$ we define the formula $\Phi^a$ to be the formula derived from $\Phi$ by ...
16 views

Semantic restrictions for $\forall$-introduction and $\exists$-elimination

I don't understand how the semantic restrictions for $\forall-$introduction and $\exists-$elimination work. These are $\dfrac{\Gamma \vdash \phi}{\Gamma\vdash \forall x\phi}, (x\notin FV(\Gamma))\quad$...
52 views

I am student and I'm studying linear logic. I saw a quote in a book: "I'm not a linear logician" - Jean-Yves Girard. Tokyo, April 1996. I searched on google but I did not find the context of why he ...
45 views

understanding a proof which uses induction on the length of a formula

This comes from Shoenfield's textbook Mathematical Logic. Here is the theorem and its proof: If $u_1,\dots,u_n, u_1',\dots,u_n'$ are designators and $u_1\dots u_n$ and $u_1'\dots u_n'$ are ...
14 views

Can I use negations in the rules of inference?

For example, modus ponens is $p \land (p → q) \therefore q$. If I had $¬p$ and $¬q$, could I do $¬p \land (¬p → ¬q) \therefore ¬q$?
8 views

Proving logic equivalences

How to prove elementary rules like $\phi\land\phi\iff\phi$ or $\phi\land\psi\iff\psi\land\phi$ without using truth tables? I want to show it using the rules for the connectives, for example the rules ...