Matematické Fórum

eminich · 26. 10. 2011 10:33

Zdravim, neviem si rady s touto ulohou:
Kolko je moznych reflexivnych relacii pre nosnu mnozinu velkosti n?
Prosim o nejake rady

vanok · 26. 10. 2011 11:38

Ahoj ↑ eminich:,

Odpoved je jednoducha ak poznas trochu kombinatoriku.

ALE JE NEVYHNUTE VEDIET CO ZNAMENA ZE RELACIA JE REFLEXIVNA

Mozes na tu napisat ako ste definovali reflexivnu relaciu?

Srdecne Vanok

eminich

reflexivna relacie je ked x je v relacii samo zo sebou tj xRx

a prvky relacie tvoria diagonalu ak si relaciu znazornime maticou

vanok · 26. 10. 2011 12:51 — Editoval vanok (27. 10. 2011 16:59)

↑ eminich:
Ano, ak si uvedomis ze relacia sa reprezentuje ako cast nejakej mnoziny co ma $n^2$ prvkov
Reflexivita ti fifovala $n$ prvkov a tak mas <<volny vyber pre $n^2-n$ prvkov>>
aby si vytvoril vsetki reflexivne relacie na tvojej mnozine
a na to staci na mnozine zostavajucych prvkov zobrat hociktoru podmnozinu

A vieme ze nejaka mnozina co ma $n^2-n$ prvkov ma $2^{n^2-n}$ podmnozin

upresnene 26/10/2011 o 13:23
Opravil som maly preklep 27/10 16:58

eminich · 26. 10. 2011 14:10

asi nerozumiem, ked ma byt relacia reflexivna znamena to ze vsetky jej prvky maju byt reflexivne takze reflexivna relacia tvori diagonalu a teda vsetky reflexivne relacie budu tvorene prave tymito prvkami na diagonale, prvkov na diagonale je $n$ takze z tychto prvkov vyberam postupne jednoprvkove, dvoj, troj, ... n prvkovu podmnozinu ale to je $2^n$ podmnozin

konkretne teda nechapem toto:

<<volny vyber pre $n^2-n$ prvkov>>

toto je predsa pocet prvkov ktore niesu na diagonale teda niesu reflexivne

vanok · 27. 10. 2011 17:02 — Editoval vanok (27. 10. 2011 17:07)

↑ eminich:,
Vseobecne graf jednej relacie na $M$ je podmnozina $M^2$
Moja poznamka znamena ze reklexivna relacia musi mat diagonalu ku ktorej pridas nejaku podmnozinu z M^2 \ diagonala a ktora

Autor skryl část textu. Zobrazit/skrýt!

ma pocet prvkov $n^2-n$
Srdecne Vanok

Rumburak

↑ eminich:
Snad Ti pomůže alternativní vyjádření definice reflexivní relace:

Relace $R$ definovaná na množině $A$ je reflexivní, právě když $\{[x, y] \in A \times A ; x = y \} \subseteq R$ .
(Rozmysli si, že tato definice je ekvivalentní s tou, kterou jste probírali.)

Tu množinu figurující na levé straně předchozího zápisu - můžeme ji vyjádřit v ekvivalentním tvaru $I := \{[x, x] ; x \in A \}$ -
nazýváme identitou na množině $A$ (je to právě ona "diagonála" v kartéském čtverci $A \times A$ ). Zároveň je to - ve smyslu inkluse -
nejmenší reflexivní relace na množině $A$ (a také jediná reflexivní relace na $A$ , která je funkcí).
Spočítat všechny reflexivní relace na množině $A$ tedy znamená spočítat všechny takové podmnožiny kartéského součinu $A \times A$ ,
jejichž částí je diagonála. Nakresli si situaci pro tříprvkovou množinu $A$ a bude Ti to snad jasné.