Forum studentĂłw informatyki UE WrocĹaw :: Zobacz temat

pit3r · Wysłany: 2009-10-13, 16:42 **[2010L]Relacje**

ZdajÄ sobie sprawÄ, Ĺźe informacje te moĹźna odszukaÄ w internecie, ale chyba nikt nie bÄdzie narzekaÄ, gdy znajdÄ siÄ one w jednym miejscu. Wiedza ta przyda siÄ na pewno w rozwiÄzaniach zadaĹ 5,9 i 10 z listy 2 ;)

Definicja relacji
Dowolny podzbiĂłr $R \subseteq A \times B$ produktu kartezjaĹskiego zbiorĂłw A i B nazywamy relacjÄ dwuargumentowÄ(binarnÄ). JeĹli para $<a,b> \in R$ to mĂłwimy, Ĺźe elementy $a \in A, b \in B$ sÄ ze sobÄ w relacji $R$ .
Zamiast pisaÄ $<a,b> \in R$ , piszemy teĹź niekiedy $aRb$ lub $R(a,b)$ . Podzbiory $A \times A$ sÄ binarnymi relacjami na zbiorze A.

Binarnymi relacjami sÄ np:
1) identycznoĹÄ(rĂłwnoĹÄ, przekÄtna) na zbiorze liczb naturalnych: $\{ <x,x> \in \mathbb{N}} | x \in \mathbb{N} \}$
2) relacja mniejszoĹci na zbiorze liczb rzeczywistych: $\{ <x,y> \in \mathbb{N}^{2} | x <= y \}$

Cechy relacji

Relacja $R \subseteq A \time A$ jest:

1) zwrotna, jeĹli $\bigwedge\limits_{a\in A}$ zachodzi $aRa$
2) symetryczna, gdy $\bigwedge\limits_{a,b \in A}$ $aRb \Rightarrow bRa$
3) przechodnia, jeĹli $\bigwedge\limits_{a,b,c \in A}$ $(aRb \ \wedge \ bRc) \Rightarrow aRc$
4) antyzwrotna, gdy $\bigwedge\limits_{a\in A}$ $\sim aRa$
5) antysymetryczna, jeĹli $\bigwedge\limits_{a,b \in A}$ $aRb \Rightarrow \sim bRa$
6) sĹabo antysymetryczna, gdy $\bigwedge\limits_{a,b \in A}$ $(aRb \ \wedge \ bRa) \Rightarrow a=b$

RelacjÄ zwrotnÄ, symetrycznÄ i przechodniÄ nazywamy relacjÄ rĂłwnowaĹźnoĹci.
RelacjÄ zwrotnÄ, przechodniÄ i sĹabo antysymetrycznÄ nazywamy relacjÄ czÄĹciowego porzÄdku.

shawnzy · Wysłany: 2009-10-22, 18:13

1) JeĹli $\leq$ jest czÄĹciowym porzÄdkiem na A, to a < b oznacza
$a \ \leq \ b \ \wedge \ a \ \neq \ b$

2) zbiĂłr czÄĹciowo uporzÄdkowany, to zbiĂłr A z relacjÄ czÄĹciowego porzÄdku $\leq$ . ZbiĂłr czÄĹciowo uporzÄdkowany oznaczamy $\langle A,\leq \rangle$

PrzykĹady zbiorĂłw uporzÄdkowanych:
- $\langle P(A), \subseteq \rangle$ (zbiĂłr potÄgowy zbioru A z relacjÄ inkluzji)
- $\langle N, \leq \rangle$ (zbiĂłr liczb naturalnych ze zwykĹym porzÄdkiem)
- $\langle N,| \rangle$ ,gdzie a|b $<=> \ \exist \ x \ (ax \ = \ b)$

3) PorzÄdek czÄĹciowy $\leq$ w zbiorze A jest liniowy, jeĹli
dla dowolnych $a,b \ \in \ A$ zachodzi $a \leq b \ lub \ b \leq a$

4) PorzÄdek $\leq$ na zbiorze A jest gÄsty, gdy dla dowolnych takich $a,b \in A$ , Ĺźe a < b, istnieje taki $c \in A$ , Ĺźe $a \ < \ c \ < \ b$

5) PorzÄdek $\leq$ na zbiorze A jest bez koĹcĂłw, jeĹli dla dowolnego elementu zbioru A istnieje element od niego wiÄkszy i element od niego mniejszy, tj. gdy dla kaĹźdego $a \ \in \ A$ istniejÄ takie $b,c \ \in \ A$ , Ĺźe b < a < c

ELEMENTY WYRĂĹťNIONE

1) Niech $\langle P(A), \leq \rangle$ bÄdzie porzÄdkiem czÄĹciowym i niech $X \ \subseteq \ P$ . Element $x \in X$ jest elementem najwiÄkszym (odpowiednio najmniejszym) w X, jeĹli dla kaĹźdego $y \ \in \ X$ zachodzi $y \ \leq \ x$ (odpowiednio $x \ \leq \ y$ ). Element najmniejszy zbioru P oznacza siÄ $\perp$ , zaĹ najwiÄkszy T.

2) Element $x \ \in \ X$ jest elementem maksymalnym (odpowiednio minimalnym) w X, jeĹli dla kaĹźdego $y \ \in \ X$ z warunku $x \ \leq \ y$ (odpowiednio $y \ \leq \ x$ ) wynika $x \ = \ y$ .

Elementy minimalne, maksymalne, najmniejsze i najwiÄksze w zbiorze uporzÄdkowanym nazywamy elementami wyrĂłĹźnionymi

--------------------------------------------------------------------------------------------------
Niech $\langle P(A), \leq \rangle$ bÄdzie czÄĹciowym porzÄdkiem i niech $X \ \subseteq \ P$ . Wtedy elementem najwiÄkszym w X jest elementem maksymalnym w X.

Niech $\langle P(A), \leq \rangle$ bÄdzie zbiorem uporzÄdkowanym. Dla dowolnego zbioru $X \ \subseteq \ P$ istnieje co najwyĹźej jeden element najwiÄkszy tego zbioru.

KaĹźdy zbiĂłr posiada teĹź co najwyĹźÄj jeden element najmniejszy. ElementĂłw maksymalnych i minimalnych moĹźe byÄ natomiast wiele.

PrzykĹad: Niech X bÄdzie zbiorem niepustym i niech P = $P(X) \ \ {\emptyset}$ . Wtedy w zbiorze uporzÄdkowanym $\langle P(A), \leq \rangle$ jest |X| elementĂłw minimalnych.
|X| - liczba elementĂłw zbioru X
${\emptyset}$ - zbiĂłr pusty
---------------------------------------------------------------------------------------------------

PorzÄdek czÄĹciowy $\langle P(A), \leq \rangle$ jest regularny(dobrze ufundowany), jeĹli w kaĹźdym niepustym zbiorze $X \ \subseteq \ P$ istnieje element minimalny.
MĂłwimy, Ĺźe porzÄdek jest dobry, jeĹli jest liniowy i regularny.

Cytat:

PrzykĹadem porzÄdku liniowego, ktĂłry nie jest dobrym porzÄdkiem, jest standardowo uporzÄdkowany zbiĂłr liczb caĹkowitych (podobnie liczb rzeczywistych), gdyĹź w zbiorze tym nie ma najmniejszego elementu.