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
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