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.
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
Dyskusja
Co to znaczy, że Jasio jest najniższym chłopcem w klasie? To znaczy, że Jasio istotnie jest chłopcem i należy do klasy (pierwsza kropka), no i że dla każdego chłopca z tej klasy Jasio jest od niego niższy (druga kropka). Gdybym miał czas…
A to nie jest tak, że mamy pokazać, że { \over Q} jest najmniejszą możliwą relacją przechodnią zawierającą Q? Mogę się mylić ale chyba nigdzie nie pisze, że te 3 warunki, które mieliśmy udowodnić w 202 są równoważne z definicją R+.