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 591 — 2021-10-19 18:06 (442 days ago) — reply
1. Je zřejmé že na konečné množině existuje konečné množství relací (obecných šípek). Je pak zřejmé že můžeme najít takové relace a takové r a s že Rr=Rs. Například relace rovností, v takové relaci je jedno kolikrát budeme relace skládat, výsledek zůstane stejný. 2. Např. ostrá nerovnost na N. Každé další složení bude posouvat prvky dále (1<2<3 -> 1<3)
Santa Claus — 2021-10-20 18:33 (441 days ago) — edit — reply
Ahoj, druhý bod máš správně, u prvního bodu bys to podle mě měl trochu rozvést. Formulace "je zřejmé, že na konečné množině existuje konečně množství relaci" není ideální, podle mě to není úplně zřejmé, spíš je to to tvrzení, které chceš dokázat. Zkus více rozvést to "obecných šipek", co máš v závorce, zatím nevím, jak to pochopit. Zatím ti dám 75% bodů, plný počet za druhou část a polovinu bodů za první část, když si to doplníš, přidělím zbytek bodů.
Points: 3.75
Martin Koutecký — 2021-10-22 12:37 (440 days ago) — reply
Ahoj, souhlas s korektorem; já bych řekl, že je vidět, že těch relací bude konečně mnoho, ale pak se autor trochu zamotal v tom, že říká "třeba relace rovnosti" -- najednou to zní, jako by chtěl dokázat "existuje relace t.ž. $R^r = R^s$", ale ve skutečnosti má dokázat "PRO KAŽDOU relaci t.ž. $R^r = R^s$". Takže bych poprosil ten první bod zkusit napsat trochu podrobněji.