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
Some Properties 1. ∆n is consistent. 2. Γ ⊆ ∆n ⊆ ∆n+1 ⊆ ∆Γ 3. ∆Γ is complete. 4. If ∆Γ ` A then there exists n ∈ N such that ∆n ` A. 5. A ∈ ∆Γ iff ∆Γ ` A 6. ∆Γ is consistent
The need for a richer language In P, it is not possible to express assertions about elements of a structure. First Order Logic is a considerably richer logic than propositional logic, but yet enjoys many nice mathematical properties
The primitive symbols of E are those of F, plus the symbol ∃. The formation Rules of E are those of F, plus the following If B is a wff of E and x is an individual variable, then ∃xB is a wff of E. The axiom schemata of E are those of F plus
Interpretation over a singleton Let I be , and σ ∈ ΣI. 1. I(A)(σ) = I(∀xA)(σ). 2. I(t)(σ) = a. 3. I(Sx1,···,xn t1,···,tn A)(σ) = I(A)(σ). 4. I0(P), σ(P) ∈ {I(n), Ψ(n)} for every n-ary predicate constant (variable), where
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
