Wolfgang Schwarz

Gödel, Mechanism, Paradox

A famous argument, first proposed in (Lucas 1961), supposedly shows that the human mind has capabilities that go beyond those of any Turing machine. In its basic form, the argument goes like this.

Let S be the set of mathematical sentences that I accept as true. S includes the axioms of Peano Arithmetic. Let S+ be the set of sentences entailed by S. Suppose for reductio that my mind is equivalent to a Turing machine. Then S is computably enumerable, and S+ is a computably axiomatizable extension of Peano Arithmetic. So Gödel's First Incompleteness Theorem applies: there is a true sentence G that is unprovable in S+. By going through Gödel's reasoning, I can see that G is true. So G is in S and thereby in S+. Contradiction!

Teaching logic: Tarski vs Mates vs "logical constants"

I'm teaching an intermediate/advanced logic course this semester. So I had to ask myself how to introduce the semantics of quantifiers, with an eye on proving soundness and completeness. The standard approach, going back to Tarski, defines a satisfaction relation between a formula, a model, and an assignment function, and then defines truth by supervaluating over all assignments. The main alternative, often found in intro logic textbooks, is Mates' approach, where ∀xA(x) is defined as true in a model M iff A(c) is true in every c-variant of M, where c is a constant not occurring in A.