Page 70 - Textos de Matemática Vol. 38

62 PETER KOEPKE
By symmetry we also have
∀wRx u∃vRx u(v,Rx)≡(w,Rx).
Together these imply (u,Rx) ≡ (u,Rx).
Symmetry. Consider points x = (x, Rx) and y = (y, Ry). We show by induction on the wellfounded relation Rx × Ry that
(u,Rx) ≡ (v,Ry) iff (v,Ry) ≡ (u,Rx).
Assume that the claim holds for all (u′, v′) with u′ Rx u and v′ Ry v. Assume that (u,Rx) ≡ (v,Ry). To show that (v,Ry) ≡ (u,Rx) consider v′ Ry v. By assump- tion take u′ Rx u such that (u′,Rx) ≡ (v′,Ry). By the inductive assumption on symmetry, (v′, Ry) ≡ (u′, Rx). Hence
Similarly
∀v′ Ry v∃u′ Rx u(v′, Ry) ≡ (u′, Rx). ∀u′ Rx u∃v′ Ry v(v′, Ry) ≡ (u′, Rx)
and thus (v,Ry) ≡ (u,Rx). This shows
(u,Rx) ≡ (v,Ry) → (v,Ry) ≡ (u,Rx).
By the symmetry of the situation the implication from right to left also holds and
(u,Rx) ≡ (v,Ry) ↔ (v,Ry) ≡ (u,Rx). In particular for x = (x, Rx) and y = (y, Ry)
x ≡ y ↔ y ≡ x.
Transitivity. Consider points x = (x, Rx), y = (y, Ry) and z = (z, Rz). We show
by induction on the wellfounded relation Rx × Ry × Rz that
(u,Rx) ≡ (v,Ry) ∧ (v,Ry) ≡ (w,Rz) → (u,Rx) ≡ (w,Rz).
Assume that the claim holds for all (u′, v′, w′) with u′ Rx u, v′ Ry v and w′ Rz w. Assume that
(u,Rx) ≡ (v,Ry) ∧ (v,Ry) ≡ (w,Rz).
To show that (u,Rx) ≡ (w,Rz) consider u′ Rx u. By (u,Rx) ≡ (v,Ry) take v′ Ry v such that (u′,Rx) ≡ (v′,Ry). By (v,Ry) ≡ (w,Rz) take w′ Rz w such that (v′, Ry) ≡ (w′, Rz). By the inductive assumption, (u′, Rx) ≡ (v′, Ry) and (v′,Ry) ≡ (w′,Rz) imply that (u′,Rx) ≡ (w′,Rz). Thus
∀u′ Rx u∃w′ Rz w(u′, Rx) ≡ (w′, Rz).