Matematické Fórum

kotja · 07. 12. 2010 22:42

Nechť relace R na konečné množině M je taková, že neexistuje konečná posloupnost prvků x1, x2,...,xk splňující (xi, xi+1) náleží R pro i z [k-1] a (xk, xi) náleží R. Tedy nemá něco jako cyklus. Dokažte, že existuje uspořádání U množiny M takové, že R je pod U (neboli - kdykoli (a,b) náleží R potom také (a,b) náleží U, ne nutně naopak)

Bohužel nevím, jak na tuto úlohu jít. Prosím o pomoc s řešením. Děkuji

FailED · 08. 12. 2010 00:09 — Editoval FailED (08. 12. 2010 00:22)

R je pod U znamená $R\subseteq U$ ?

Klasicky musíš dokázat, že lze R doplnit tak aby byla tranzitivní a reflexivní, antisymetrie je zaručená tou podmínkou pro dvojice různých x1, x2 a k=2.

Edit: omyl

kotja · 08. 12. 2010 00:11

Dík moc, R je pod U jsi napsal tak, co to znamená. Můžu se prosím zeptat, jak to je s tím doplněním?

FailED · 08. 12. 2010 00:19 — Editoval FailED (08. 12. 2010 00:19)

↑ kotja:

Stačí přidat dvojice $(x,x)$ pro dosažení reflexivity a pro x,y,z takové, že $xRy, yRz, x\cancel{R}z$ přidat $(x,z)$ aby byla relace tranzitivní a tedy uspořádání.

Matematické Fórum

#1 07. 12. 2010 22:42

Speciální relace a uspořádání na množině

#2 08. 12. 2010 00:09 — Editoval FailED (08. 12. 2010 00:22)

Re: Speciální relace a uspořádání na množině

#3 08. 12. 2010 00:11

Re: Speciální relace a uspořádání na množině

#4 08. 12. 2010 00:19 — Editoval FailED (08. 12. 2010 00:19)

Re: Speciální relace a uspořádání na množině

Zápatí