Relacje - podstawy.pdf - Matematyka - taizia

RELACJE I ODWZOROWANIA

Definicja 1.

Dwuargumentową relacją określoną w iloczynie kartezjańskim X × Y ,

X ≠∅ ∧ Y ≠∅ nazywamy uporządkowaną trójkę R = ( X, grR , Y ) , gdzie

grR ⊂ X × Y .

Zbiór X nazywamy naddziedziną relacji.

Zbiór Y nazywamy zapasem relacji.

grR to wykres relacji.

Mówimy, że dwa elementy x ∈ X ∧ y ∈ Y są w relacji R ⇔ ( x, y ) ∈ grR

Definicja 2.

R = ( X, grR, Y )

Dziedzinę relacji oznaczamy D R

D R : = { x ∈ X: ∃ y ∈ Y: xRy }

Przeciwdziedzinę relacji oznaczamy

R :={y ∈ Y: ∃ x ∈ X: xRy}

PRZYKŁAD 1.

X=[1,2] , Y=[1,2]

grR = {(x,y): x ≤ y }

Definicja 3.

R= (X, grR, Y)

Relacją odwrotną do relacji R nazywamy relację R -1 = (Y, grR -1 , X) ,

gdzie grR -1 = {(x,y) ∈ Y × X: (y,x) ∈ grR }

Wykład dr Magdaleny Sękowskiej

strona 1 z 9

Część 2 - Relacje i odwzorowania

Definicja 4.

Niech R i S to następujące relacje:

R= (X, grR, U)

S= (U, grS, Y)

Złożeniem relacji R z relacją S nazywamy relację

SR: ,grSR, , gdzie

(

)

( ) {

}

gr S R : ( , )

x yXY uy

∈

∈ × ∃

: :

∧

PRZYKŁAD 2.

(, , )

{(2,1), 3,1 , 4,2 , 4,5 , 5,3 }

(, , )

{(1,3),4,1,3,6,6,8,6,7}

{2, 3, 4, 5}

{1, 2, 3, 5}

(, ( ), )

( ) ( ) ( ) ( )

D ` D `

⊂

SR grSR

gr S R

RS grRS

gr R S

∧

(

) { 2,3 , 3,3 , 5,6 }

(, ( ), )

( ) ( ) ( )

D ` D `

∧

(

) ,}

( )

Definicja 5.

R = ( X, grR , Y ) ∧ X=Y ≠ ∅ relacje, czyli

R = ( X, grR , X )

Relacja jest relacją równoważności, gdy spełnione są warunki:

1 ° Relację nazywamy zwrotną: ⇔ ∀ x ∈ X: xRx

2 ° Relację nazywamy symetryczną: ⇔ ∀ x,y ∈ X: xRy ⇒ yRx

3 ° Relację nazywamy przechodnią: ⇔ ∀ x,y,z ∈ X: xRy ∧ yRz ⇒ xRz

Przyjmujemy oznaczenie (X,R)

Definicja 6.

Jeżeli (X,R) jest zbiorem z relacją równoważności i x ∈ X to klasą

równoważności elementu x nazywamy zbiór:

[x]:={y ∈ X: xRy }

Wykład dr Magdaleny Sękowskiej

strona 2 z 9

Część 2 - Relacje i odwzorowania

( ) ( )

R grR

grR

S grS

grS

PRZYKŁAD 3.

R jest relacją równości w zbiorze liczb rzeczywistych.

R=( R ,=), xRy ⇔ x=y

1 ° ∀ x ∈R x=x ⇒ xRx

2 ° ∀ x,y ∈R xRy ⇒ x=y ⇒ y=x ⇒ yRx

3 ° ∀ x,y,z ∈R xRy ∧ yRz ⇒ x=y ∧ y=z ⇒ x=z ⇒ xRz

PRZYKŁAD 4.

{}

JJJG

JJJG JJJG JJJG JJJG JJJG JJJG

AB CD AB CD AB CD

⇔= ∧

|| wektory są zgodnie równolegŁe

(

)

JJJG JJJG JJJG JJJG JJJG JJJG

ci wektorów

1° R , gdyż

AB AB AB AB

= ∧

ˆˆ

JJJG JJJG JJJG JJJG

AB CD CD AB

⇒

JJJG JJJG JJJG JJJG JJJG JJJG

3° R

AB CD CD EF AB CD

∧

⇒

JJJG JJJG JJJG JJJG

AB CD AB CD

{ : R }



JJJG

W tej relacji klasą równoważnoci jest wektor swobodny.

Definicja 7.

(X,R) – zbiór z relacją równoważności

Zbiór klas równoważności relacji nazywamy zbiorem ilorazowym i

oznaczamy X/ R :={[x]: x ∈ X }

TWIERDZENIE 1.

Z: (X,R) – zbiór z relacją równoważności

1 ° ∀ x ∈ X: [x] ≠∅

2 ° ∀ [x], [y] ∈ X / R : [x] ≠ [y] ⇒ [x] ∩ [y]= ∅

3 ° ∀ [x] ∈ X / R : x = X

Wykład dr Magdaleny Sękowskiej

strona 3 z 9

Część 2 - Relacje i odwzorowania

ˆˆ

Z wasnos

AB AB

2° R

 =

WNIOSEK

Relacja równoważności w zbiorze X dzieli ten zbiór na podzbiory niepuste,

rozłączne, dające w sumie cały zbiór X.

Definicja 8.

(X,R) – zbiór z relacją równoważności

Definicja 9.

1 ° Relację nazywamy antysymetryczną: ⇔ ∀ x,y ∈ X: xRy ∧ yRx ⇒ x=y

2 ° Relacja nazywamy asymetryczną: ⇔ ∀ x,y ∈ X: xRy ⇒ ¬ (yRx)

3 ° Relacja nazywamy spójną: ⇔ ∀ x,y ∈ X: xRy ∨ yRx ∨ x=y

A) Jeśli dwuelementowa relacja (X,R) jest zwrotna, antysymetryczna i

przechodnia to nazywamy ją relacją słabego porządku częściowego.

Jeżeli dodatkowo jest spójna to nazywamy ją relacją słabego

porządku totalnego albo liniowego.

B) Jeżeli dwuelementowa relacja (X,R) jest asymetryczna i

przechodnia to nazywamy ją relacją silnego porządku częściowego,

jeżeli ponadto jest spójna to jest to relacja silnego porządku

liniowego lub totalnego.

C) Jeżeli w zbiorze X określona jest którakolwiek z powyższych relacji,

to zbiór nazywamy uporządkowanym

• Częściowo, jeżeli R jest relacją porządku częściowego,

• Totalnie, jeżeli R jest relacją porządku liniowego.

PRZYKŁAD 5.

( )

, , xRy: x y

⇔≤

Sprawdzamy, czy relacja , jest relacją porządku.

Z własnosci liczb rzeczywistych

1°

( )

≤

∀≤

∈

2°

x,y

∀≤∧≤⇒=

∈

xyyxxy

3°

x,y,z

∀≤∧≤⇒≤

∈

xyyzxz

4°

x,y

∀≤∨≤∨=

∈

xyyxxy

lacja

jest relacją słabego porz

ądku liniowego.

Wykład dr Magdaleny Sękowskiej

strona 4 z 9

Część 2 - Relacje i odwzorowania

PRZYKŁAD 6.

2, A R B

⇔⊂

A B

1° A A

∀⊂

2°

∀⊂∧⊂⇒=

BBA AB

∈

3°

∀⊂∧ ⊂⇒⊂

BBC AB

A,B,c 2

∈

Jest to relacja slabego porządku częsciowego.

Relacja nie jest spójna na przykład dla zbiorów z

ELEMENTY WYRÓŻNIONE ZBIORU UPORZĄDKOWANEGO

Definicja 10.

(X,R) –zbiór uporządkowany

1 ° M ∈ X , M nazywamy elementem największym zbioru

słabouporządkowanego: ⇔ ∀ x ∈ X xRM (dla silnego porządku M ≠ x)

2 ° m ∈ X, m nazywamy elementem najmniejszym zbioru

słabouporządkowanego: ⇔ ∀ x ∈ X mRx (dla silnego porządku m ≠ x)

TWIERDZENIE 2.

(X,R) – zbiór uporządkowany

Jeżeli w zbiorze X istnieje element największy (najmniejszy) to jest on

jedyny.

Definicja 11.

(X,R) – zbiór uporządkowany

1 ° ξ∈ X ∧ ξ≠ x, ξ nazywamy elementem maksymalnym zbioru

słabouporządkowanego: ⇔ ¬ ( ∃ x ∈ X: ξ Rx) (dla silnego porządku ξ≠ x)

2 ° η∈ X ∧ η≠ x, η nazywamy elementem minimalnym zbioru

uporządkowanego: ⇔ ¬ ( ∃ x ∈ X: xR η ) (dla silnego porządku η≠ x)

Wykład dr Magdaleny Sękowskiej

strona 5 z 9

Część 2 - Relacje i odwzorowania

( )

E R

∈

A,B 2

Relacje - podstawy.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: