Student 539 — 2021-10-19 21:18 (442 days ago) — reply
Attachment (pdf)
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 539 — 2021-10-19 21:18 (442 days ago) — reply
Attachment (pdf)
Martin Koutecký — 2021-10-22 12:33 (440 days ago) — reply
Ahoj,
u té jedničky je tam zjevně správná myšlenka popsána na začátku, ale pak jsem se nějak zamotal v těch kvantifikátorech -- co znamená např. "existuje nekonečný počet relací $R^{n+1}$" - to je nesmysl, existuje právě jedna relace $R^{n+1}$; pak máme $\exists R^{n+1} = R^{n+1+k} \mid k \in \mathbb{N}$ -- toto vůbec neumím přečíst -- že existuje relace $R^{n+1}$ (tento kvantifikátor nedává smysl, $R^{n+1}$ je definována, takže ano, existuje, ale to asi není to, co myslíš) taková, že se rovná $R^{n+1+k}$ pro ... každé $k$? nějaké $k$? Pokud jsi chtěl říct "pro nějaké $k$", tak jsi měl říct $\exists k \dots$, například.
Tedy prosím ještě zkus závěr toho důkazu přepsat, klidně slovy, ale nějak srozumitelně.
Druhá část je správně, ale je to tedy na můj vkus až příliš stručné. Např. mě zkus přesvědčit, že pro takto definovanou $R$ neexistují $r\neq s$, t.ž. $R^s = R^r$ -- neboli, zkus mě přesvědčit, že pro každé dvě různé $r,s$ platí $R^r \neq R^s$.
Points: 3.00