Logika - Zadanie 204.

Że jest przechodnia, to już wiemy z poprzedniego zadania. Pozostaje pokazać:

• Q = Q^1 \subseteq \bigcup_{n=1}^{\infty} Q^n = { \over Q}
• Pokażmy, że jeśli S jest relacją przechodnią zawierającą Q, to { \over Q}\subseteq S.
  1. 

UWAGA! to rozwiązanie będzie brzydkie!
(ale nie mogę na razie wymyślić ładniejszego)
Pokażę tą drugą kropkę, do pierwszej nic dodać nic ująć.
Niech S \supseteq Q będzie przechodnia. Pokażemy że { \over Q} \subseteq S, skąd, dzięki uwadze iwana, wyniknie nam teza zadania.
Lecimy:
(a,b) \in LHS \Rightarrow (a,b) \in { \over Q} \Rightarrow (a,b) \in Q_n dla pewnego n \in \mathbb{N}. Ustalmy to n.
\ldots \Rightarrow \exists p_1 \in Q.(aQp_1 \wedge (p_1,b) \in Q^{n-1}) \Rightarrow \ldots \Rightarrow \exists p_1,p_2,\ldots,p_n \in Q.(aQp_1 \wedge p_{1}Qp_{2} \wedge \ldots \wedge p_{n-1}Qp_{n} \wedge p_{n}Qb). Skoro Q \subseteq S, to:
\ldots \Rightarrow \exists p_1,\ldots p_n.(aSp_1 \wedge p_{1}Sp_{2} \wedge \ldots \wedge p_{n}Sb) \Rightarrow (a,b) \in S \Rightarrow (a,b) \in RHS \heartsuit