Deadline: 2021-10-19 23:59 (442 days ago)
Martin Koutecký — 2021-10-12 11:09 (450 days ago) — reply
Pro relaci $R$ na množině $X$ definujeme indukcí relaci $R^n: R^1 = R, R^{n+1} = R \circ R^n$.
1. Dokažte, že je-li $X$ konečná množina, potom existují $r,s \in \mathbb{N}, r < s$ takové, že $R^r = R^s$.
2. Nalezněte relaci na nekonečné množině takovou, že všechny $R^n$ jsou různé -- tedy předchozí bod pro nekonečné množiny neplatí.
Student 377 — modified 2021-10-19 23:17 (442 days ago) — reply
1. Je-li X konečná množina, pak jistě existují r,s z N, kde r<s, takové že R^r=R^s. Uvažujeme-li totiž zadanou relaci jako ekvivalenci, tak pak platí, že např. pro R1=R a R2= RoR1 = RoR, což se ale rovná samotnému R (protože skládání relací můžeme brát jako prodlouženou tranzitivitu, kterou ekvivalence splňuje sama o sobě, tedy dvě totožné ekvivalence se složí opět do té stejné).
Santa Claus — 2021-10-20 17:57 (441 days ago) — edit — reply
Ahoj, tvé řešení není správné, protože se nevztahuje k zadání, $R$ není zadáná jako ekvivalence, nýbrž obecná relace na množině $X$. Takhle to tedy řešit nepůjde. Zkus si to řešení opravit, můžu ti za to pořád přidělit až všechny body, zatím je to ale bez bodu.
Points: 0.00
Martin Koutecký — 2021-10-22 13:33 (440 days ago) — reply
Souhlas. Jen dodám, že zde se jednalo o chybu v kvantifikaci -- má se dokázat, že **pro každé** $R$ toto platí, ne že **pro nějaké** $R$ to platí.