Theory of Equivalence Relations (A, R) (E1) For all x : xRx. (E2) For all x, y : If xRy then yRx. (E3) For all x, y, z : If xRy and yRz then xRz. Logic in Computer Science – p.2/16
Axiom Schemata for F Axiom Schema 1 A ∨ A ⊃ A Axiom Schema 2 A ⊃ (B ∨ A) Axiom Schema 3 A ⊃ B ⊃ (C ∨ A ⊃ (B ∨ C)) Axiom Schema 4 ∀xA ⊃ Sxt A where t is a term free for the individual variable x in A Axiom Schema 5 ∀x(A ∨ B) ⊃ (A ∨ ∀xB) provided that x is not free in A
F= = F + “ = ” + 2 Axiom Schemata Axiom Schema 6 x = x. Axiom Schema 7 x = y ⊃ (SzxA ⊃ SzyA) where A is an atomic wff. A first order theory is a first-order theory with equality if it has a binary predicate = such that the wffs above are theorem of the theory
Interpretation An interpretation I of F is , where D is a non-empty set called the domain of individuals. I0 is a mapping defined on the constants of F satisfying 1. If c is an individual constant, then I0(c) ∈ D. 2. If f n is an n-ary function constant, then I0(f n) : Dn → D