(Predicate Logic and Mathematical Theories)

A signature that has only one binary predicate R: ∀𝑥 𝑅 𝑥, 𝑥 specifies all structures where 𝑅 is reflexive. Symmetry: ∀𝑥 ∀𝑦 (𝑅 (𝑥, 𝑦 )→ 𝑅 (𝑦, 𝑥). Transitivity: ∀𝑥 ∀𝑦 ∀𝑧 𝑅 𝑥, 𝑦 ∧ 𝑅 𝑦, 𝑧 → 𝑅 𝑥, 𝑧. Anti-symmetry: ∀𝑥 ∀𝑦 ( 𝑅 (𝑥, 𝑦) ∧ 𝑅 (𝑦, 𝑥) → 𝑥 = 𝑦)

A signature with a unary function 𝑓 and a binary predicate = One-to-one (injective) functions ∀𝑥 ∀𝑦 (𝑓 (𝑥) = 𝑓( 𝑦) → 𝑥 = 𝑦). Onto (surjective) functions ∀𝑥 ∃𝑦 (𝑓 (𝑦) = x)

Example: 𝑥 is a prime number: 𝑥 > 1 ∧ ∀𝑦 (𝐷𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒(𝑥, 𝑦) → (𝑦 = 1 ∨ 𝑦 = 𝑥))

Example: All even numbers greater than two are the sum of two primes (Goldbach's Conjecture) ∀𝑥(( 𝑥 > 2 ∧ 𝐸𝑣𝑒𝑛 (𝑥)) → ∃𝑦∃𝑧 ((𝑥 = 𝑦 + 𝑧) ∧ 𝑃𝑟𝑖𝑚𝑒 (𝑦) ∧ 𝑃𝑟𝑖𝑚𝑒 (𝑧) )

What Cannot be Expressed in Predicate Logic?: Reachability

Reachability theorem: Assume there is 𝜙 that is true if and only if 𝑣1 is reachable from 𝑣2. A sentence 𝐹 with 𝑣1 and 𝑣2 replaced with constants 𝑐1 and 𝑐2 𝐹 = 𝜙 ∧ ¬𝜙1 ∧ ¬𝜙2 ∧ ⋯ 𝐹 is a contradiction. Every finite subset of 𝐹 is satisfiable, and therefore it is satisfiable! (Compactness). There is no 𝜙!

A sentence 𝜙 (or a set of sentences) specifies: a set of models 𝑴(𝝓), i.e., the structures that satisfy 𝜙. 𝑴 𝝓 = 𝓢 | 𝓢 ⊨ 𝝓}. 𝑀(𝜙) is like a set of possible worlds in which 𝜙 is true

What Is Closure Under an Operator?: A set 𝐴 ⊆ 𝑈 and an operator 𝑓: 𝑈 ↦ 𝑈. 𝐴 is closed under 𝑓 if 𝑓 maps elements of 𝐴 to the elements in the same set 𝐴. ∀𝑎 ∈ 𝐴, 𝑓 𝑎 ∈ A. E.g. 𝐴 = {1,2,3} is not closed under addition . ℕ is closed under addition. What about multiplication and subtraction? Is 𝐵 = { 𝑎 , 𝑏 ,{𝑎, 𝑏}} closed under union?

Theory: a set of sentences that is closed under logical entailment. 𝐹 = {𝜙1,𝜙2, … } is a theory if any sentence 𝜙 that is entailed from 𝐹 is also in 𝐹, i.e., if 𝐹 ⊨ 𝜙 then 𝜙 ∈ F

Theory structure: The theory of a structure 𝒮, denoted by 𝑇ℎ(𝒮), is the set of all sentences 𝜙 such that 𝒮 ⊨ 𝜙

Axiomatic system:Using a set of sentences called axioms • For an axiom 𝜙 (or a set of axioms), 𝑪𝒐𝒏𝒔(𝝓) is the set of all sentences 𝜓 that are logical consequence of (or entailed from) 𝜙, i.e., 𝜙 ⊨ 𝜓

Inconsistent theories: a theory 𝑇 is inconsistent if ⊥∈ T

An inconsistent theory consists of: all the possible sentences with the given signature

𝐶𝑜𝑛𝑠(∅): the set of all valid sentences, a subset of every theory

A theory 𝑇 is complete if: for every sentence 𝜙 of the same signature either 𝜙 ∈ 𝑇 or ¬𝜙 ∈ T

The set of valid sentences is an: incomplete theory

For any structure 𝒮, 𝑇ℎ(𝒮) is: complete or every sentence 𝜙, either 𝒮 ⊨ 𝜙 or 𝒮 ⊨ ¬𝜙

𝑇ℎ( ℕ) , 𝑇ℎ (ℝ) , and 𝑇ℎ (ℤ) are : complete theories

A theory is decidable if: it is possible to decide if any sentence is in the theory

Church’s Theorem: The theory of valid sentences in First Order (FO) predicate logic is undecidable.

The proof of Church’s theorem: Reducing an undecidable problem called Post’s Correspondence Problem (PCP) to checking validity

Reduction means: transforming problem 𝑃₁ into problem 𝑃₂ in such a way that a solution to 𝑃₂ also solves 𝑃₁. Reduction can show one problem is at least as hard (difficult) as another. For example, if solving 𝑃₂ requires solving 𝑃₁, 𝑃₂ is as hard as 𝑃₁. To prove a problem 𝑃 is undecidable, show that solving an undecidable problem, like the halting problem, is necessary to solve P

The answer to the correspondence problem 𝐾 = ( 𝑥1, 𝑦1 , 𝑥2, 𝑦2 , 𝑥3, 𝑦3 ) = (( 1,101)) , (10,00) , (011,11)): a sequence 𝒙𝟏𝒙𝟑𝒙𝟐𝒙𝟑 = 𝟏𝟎𝟏𝟏𝟏𝟎𝟎𝟏𝟏 = 𝒚𝟏𝒚𝟑𝒚𝟐𝒚𝟑

A consequence of Church’s theorem is that: a correct (sound and complete) proof system for first-order predicate logic does not exist

A theory 𝑇 is (finitely) axiomatizable if: 𝑇 = 𝐶𝑜𝑛𝑠(𝐹) for some finite set of axioms F

The theory of valid sentences (tautologies): is axiomatizable

An inconsistent theory is: also axiomatizable

A structure 𝒮1 with 𝑈𝒮1 = {𝑎, 𝑏, 𝑐} .An acceptable interpretation, An unacceptable interpretation: { 𝑎, 𝑎 , 𝑏, 𝑏 , (𝑐, 𝑐)} , { 𝑎, 𝑏 , 𝑎, 𝑐 }

Axioms of equality: A set of sentences that any structure satisfies iff it interprets “=” as the equality relation

Ax1 Reflexivity: ∀𝑥 (𝑥 = 𝑥)

Ax2 Symmetry: ∀𝑥∀𝑦 ( 𝑥 = 𝑦 → 𝑦 = 𝑥 )

Ax 3 Transitivity: ∀𝑥∀𝑦∀𝑧 ( 𝑥 = 𝑦 ∧ 𝑦 = 𝑧 → (𝑥 = 𝑧))