Logical snippets

For a number of  years now, I’ve been a sporadic visitor to the very useful question-and-answer site, math.stackexchange.com — this is a student-orientated forum, not to be confused with the truly wonderful mathoverflow.net which is its research-level counterpart. OK, you can think of these visits as (hopefully) constructive procrastination on my part …

Of course, many of the questions on the site, including many I’ve found myself answering, are very ephemeral or very localized or based on very specific confusions. But a proportion of the exchanges to which I’ve contributed might, for one reason or another, be of some interest/use to other students — or at least, to beginners and near beginners in logic.

Do read other people’s answers of course, which are sometimes more interesting than mine! I’ve included a few exchanges where all I contribute is a reference to something interesting in the literature. Do explore other logic and related questions on the math.stackexchange site too. And why not register so you can occasionally “vote up” answers you get something out of, as the feedback encourages good authors — and there are a significant number there — to keep posting to the general benefit.

Beginning logic

• Why bother to study deductive systems for propositional logic?
• Introductions to logic talk about sets of atomic formulae, etc. But doesn’t set theory in turn depend on logic? Isn’t this circular?
• Elementary logic, formal logic, metalogic — what are they?
• How are different approaches to logic related?
• Sermon: Questions of the form ‘How do I prove X by natural deduction?’ are ill-posed
• Disjunction: why did the inclusive “or” become the convention?
• Is natural language “or” ambiguous?
• More on inclusive/exclusive “or”
• What does “contradiction” mean in logic?
• What is the “correct” reading of ⊥?
• What does “classical logic” mean?
• Why do we prefer classical logic over e.g. relevant logic?
• Why is “traditional logic” inadequate?
• Does  All A are B imply Some A are B?
• Why not allow empty domains?
• What is the role of free variables in first-order logic?
• Why do the clauses in a semantics for quantifiers mention free variables?
• Should we prefer to use  first-order theories with multiple sorts?
• Can we replace the identity sign in first-order logic by the convention that different variables get assigned different values?
• What’s the best method to determine whether a first order formula is logically valid or not?
• What is a zero-place predicate? a 0-adic function, etc.?
• Do tableaux proofs show syntactic or semantic entailment?
• How do we prove for a tableaux system that if and that ?
• How about marrying the axiomatic approach and natural deduction as Kleene does
• How does the meta-language relate to the object-language?
• What are the rules for the use of dots rather than parentheses in logical formulae?
• Some definitions of the idea of a wff make unique readability trivial: why not use such a definition?

Explaining the material conditional, etc.

• Why do we use the material conditional in logic?
• When does material implication supposedly not “work?”
• Do the usual natural deduction rules for the conditional determine its truth-table?
• Why is if P then Q equivalent to ?
• Why is if P then Q not equivalent to ?
• Can we replace the  modus ponens rule with a conditional proposition?
• What’s the sense of ‘implies’ in logic?
• What is the difference between “if ⊢P, then ⊢Q” and “⊢(P⇒Q)”?
• What is the difference between etc. (i)?
• What is the difference between etc. (ii)?

Help for beginners with translation into first-order logic

• How to translate “Any A who is B is C”
• Translate “Every person who dislikes all vegetarians is smart”
• Translate “There is exactly one person whom everybody can fool”
• Translate “Anyone who knows everyone Alma knows knows Alma”
• Can we translate ‘Everyone loves themself” as ?
• When regimenting an argument with a definite description in first-order logic, when must we use Russell’s theory of descriptions?

Help for beginners with natural deduction proofs etc.: how to think strategically!

• How to show
• How to show
• How to show  and  are equivalent
• How to show
• How to show
• How to show , and another problem
• How to show
• How to show
• How to show
• How to show
• How to show
• How to show
• How to show
• How to show entails
• How to show is a theorem.
• How to show
• How to show
• How to prove in FOL
• How to show
• Strategy for another tricky proof with multiple quantifiers!
• How to derive in the sequent calculus

Paradoxes

• What makes something a paradox?
• A: B  is true. B: A is false. Nonsense? Paradox?
• Is the Barber’s paradox a paradox?
• Why is Russell’s Paradox a paradox?

Theories

• Why are we interested in models as well as formal axioms for theories?
• What’s the difference between an interpretation and a model of a theory?
• What is the relationship between the consistency, axiomatizability, and decidability of a theory?
• What is the use of identifying objects in different mathematical theories?
• How is it legitimate to add non-standard elements to a model of arithmetic?

Arithmetic and computability

• Natural numbers, real numbers, complex numbers, p-adic numbers …. what makes them all numbers?
• We allow “imaginary” numbers such ; why not other imaginary numbers such that ?
• Can we define the usual arithmetic operations in terms of a single operator?
• Are partial functions interesting (outside recursion theory)?
• How is the standard model of number theory specified?
• How do you prove that proof by induction is a proof?
• Do we just have to take proofs by induction on faith?
• If you prove Goldbach’s conjecture is independent of ZFC, that proves Goldbach’s conjecture is true: why?
• What is the relationship between the idea of a “recursive” set and the concept of recursion in the sense of a function calling itself?
• ‘I would like a proof that first order logic is undecidable, but without using arithmetic’
• Why is the set of truths of arithmetic not effectively enumerable?
• Why do we believe the Church-Turing Thesis?
• Can every partially computable function be extended to a total computable function?
• Is the inverse of a primitive recursive bijection on the natural numbers primitive recursive?
• Do recursive definitions and impredicative definitions both involve self-reference? 
• What is the link between Church’s theorem and the undecidability of predicate logic?

Gödel’s incompleteness theorem(s)

• What background knowledge do you need for understanding Godel’s Theorem?
• Can someone explain Gödel’s incompleteness theorems in layman terms? [Notable for other people’s answers!]
• Don’t Gödel’s completeness and incompleteness theorems contradict each other? (i)
• Don’t Gödel’s completeness and incompleteness theorems contradict each other? (ii)
• What axioms is Gödel using to prove his theorem?
• What’s so great about showing that Peano Arithmetic is incomplete?
• What’s so great about Gödel’s Theorem, since incompleteness is pervasive?
• Are Gödel sentences always true?
• Is there an algorithm for producing undecidable sentences for any given theory?
• Is there a proof of Gödel’s  Theorem without self-referential statements?
• Is the negation of the Gödel sentence always unprovable too?
• Are the proofs of incompleteness theorems valid for an intuitionist?
• Does Gödel’s Theorem also show that are non-standard models of second-order arithmetic?
• Does Gödel’s Theorem say anything about the limitations of theoretical physics?
• What is the relation between the original proofs of Gödel’s two incompleteness theorems?
• What is the relation between Turing’s theorem about the halting problem and Gödelian  incompleteness?
• Are the axioms of arithmetic consistent? [Gödel’s second theorem]
• Is there more than one Rosser sentence?

Sets and functions

• What’s so special about set theory?
• Do we need to use set-theoretic concepts in theorizing about first order logic? 1
• Do we need to use set-theoretic concepts in theorising about first order logic? 2
• How much set theory is needed for serious logic?
• Why suppose there is such a set as the empty set?
• Why is the empty set is a subset of any set?
• Is a function a relation?
• Is a function a set? (i)
• Is a function a set? (ii)
• Must functions be single-valued?
• Should we allow individuals (urlemente) in set theory?
• How is Cantor’s diagonal argument related to Russell’s paradox in naive set theory?
• Does Cantor’s diagonal argument take an infinite number of steps?
• Is the domain of discourse of set theory also a set?
• What does it mean to say that a set is equipped with a function?
• How do we formalize the idea of set together with some other operations?
• Are there sets A and B such that A ∈ B and B ∈ A?
• What is the neatest proof that the set of finite subsets of a countable set is countable?
• What is the purpose of the Axiom of Infinity
• Why use ZF over NFU?
• Should we be realists about set theory?
• Why doesn’t the independence of the continuum hypothesis immediately imply that ZFC is unsatisfactory?

History of Logic

• Why did the later Frege appeal to geometry to found arithmetic?
• What does Russell mean when he defines the “Posterity… with respect to the immediate predecessor”?
• Where, specifically, did Principia Mathematica fail?
• Who first defined the notion of a wff?
• When and where was the concept of valid logic formula first defined?
• Was Hilbert trying to eliminate the infinite from maths? [On Hilbert’s Programme]
• How does Gödel’s theorem impact on Hilbert’s Programme? [Short version!]

Varia

• How does logic-for-philosophers relate to mathematical logic?
• What are some good maths/logic study-habits?
• How much maths is needed to understand logic and set theory?
• What are fun but serious mathematics books?
• How much math does one need to know to do philosophy of math?
• Is mathematics a formal game with symbols? [see esp. Henning Makholm’s answer]
• Should we look to Bourbaki for rigorous foundations of mathematics?
• What is there to read on the relation between category theory and logic?
• How might we think about quantification in category-theoretic terms?
• What’s an example of a sentence valid in standard second-order logic but not in Henkin semantics? [see esp. Carl Mummert’s answer]
• What is the minimal difference between classical and intuitionistic sequent calculus