RELACJE

Iloczynem kartezjańskim zbiorów A i B jest zbiór wszystkich par uporządkowanych, których pierwsze elementy należą do A, drugie zaś do B:

A × B = {( x, y): x ∈ A ∧ y ∈ B}

R jest relacją binarną określoną w zbiorze A wtedy i tylko wtedy, gdy R ⊆ A × A = A 2.

Dziedzina relacji R to zbiór pierwszych elementów par uporządkowanych należących do relacji R:

D( R) = { x ∈ A: ∃ y xRy}

Przeciwdziedzina relacji R to zbiór drugich elementów par uporządkowanych należących do relacji R:

Ď( R) = { x ∈ A: ∃ y yRx}

Pole relacji R to zbiór wszystkich elementów par uporządkowanych należących do relacji R: P( R) = D( R) ∪ Ď( R) Konwersem relacji R (relacją odwrotną do R) jest relacja Ř (inne oznaczenie R–1), która zachodzi między elementem pierwszym a drugim wtedy i tylko wtedy, gdy między drugim a pierwszym zachodzi relacja R:

( x, y) ∈ Ř ≡ ( y, x) ∈ R

Iloczyn względny relacji R i S to relacja, która zachodzi między elementem pierwszym a drugim wtedy i tylko wtedy, gdy istnieje taki element, do którego pierwszy jest w relacji R, i element ów jest w relacji S do drugiego:

xR○ Sy ≡ ∃ z [ xRz ∧ zSy]

Obraz zbioru A wedle relacji R, czyli R( A): y ∈ R( A) ≡ ∃ x [ x ∈ A ∧ xRy]

Przeciwobraz zbioru A wedle relacji R, czyli Ř( A): x ∈ R( A) ≡ ∃ y [ y ∈ A ∧ xRy]

Obcięcie R| B (lub RB) relacji R do podzbioru B zbioru A:

R| B = R ∩ B 2

Pewne rodzaje relacji na zbiorze A

relacja pusta:

R = ∅

relacja identyczności (tożsamości) na zbiorze A (oznaczamy: Id A): Id A = {( x, x): x ∈ A}

relacja totalna (pełna):

∀ x∀ y [( x ∈ A ∧ y ∈ A) → yRx]

inaczej: R = A × A

relacja spójna:

∀ x∀ y [( x ≠ y ∧ x ∈ A ∧ y ∈ A) → ( yRx ∨ xRy)]

relacja zwrotna (refleksywna):

∀ x ( x ∈ A → xRx)

inaczej: id P( R) ⊂ R

relacja przeciwzwrotna (antyrefleksywna):

∀ x ~ xRx

inaczej: id P( R) ∩ R = ∅

relacja symetryczna:

∀ x∀ y ( xRy → yRx)

inaczej: R ⊂ R–1

relacja antysymetryczna (niekiedy: słabo antysymetryczna):

∀ x∀ y [( xRy ∧ xRy) → x = y) inaczej: R ∩ R–1 ⊂ id A

relacja asymetryczna (niekiedy: przeciwsymetryczna, silnie antysymetryczna):

∀ x∀ y ( xRy → ~ yRx)

inaczej: R ∩ R–1 = ∅

relacja przechodnia:

∀ x∀ y∀ z [( xRy ∧ yRz) → xRz]

inaczej: R○ R ⊂ R

relacja tolerancji (podobieństwa) w zbiorze A:

relacja zwrotna & symetryczna w zbiorze A

relacja quasi-porządku w zbiorze A:

relacja zwrotna & przechodnia w zbiorze A

relacja częściowego (częściowego ostrego) porządku w zbiorze A:

relacja asymetryczna & przechodnia w zbiorze A

relacja liniowego (liniowego ostrego) porządku w zbiorze A:

relacja asymetryczna, przechodnia & spójna w zbiorze A

relacja równoważności (równościowa) w zbiorze A:

relacja zwrotna, symetryczna & przechodnia w zbiorze A

klasa abstrakcji (klasa równoważności) relacji R wyznaczona

(reprezentowana) przez element a:

x ∈ [ a] R ≡ x ∈ A ∧ xRa relacja (prawostronnie) jednoznaczna (funkcja w znaczeniu matematycznym,

odwzorowanie):

∀ x∀ y∀ z [( xRy ∧ xRz) → y = z]

inaczej: R–1○ R = id Ď( R)

relacja lewostronnie (odwrotnie) jednoznaczna:

∀ x∀ y∀ z [( xRy ∧ zRy) → x = z]

inaczej: R○ R–1 = id D( R)

relacja wzajemnie jednoznaczna (jedno-jednoznaczna, bijekcja):

relacja prawostronnie & lewostronnie jednoznaczna

inaczej: R jest różnowartościowa & „na” (por. niżej)

R odwzorowuje (przekształca) zbiór A w zbiór B: a. R jest odwzorowaniem

b. D( R) = A

c. Ď( R) ⊂ B

R jest odwzorowaniem różnowartościowym (injekcją, funkcją różnowartościową) ze zbioru A w zbiór B:

a. R jest odwzorowaniem

b. D( R) = A

c. Ď( R) ⊂ B

d. ∀ x∀ y∀ z [ xRz ∧ yRz → x = y]

R odwzorowuje (przekształca) zbiór A na zbiór B ( R jest surjekcją, odwzorowaniem

„na”):

a. R jest odwzorowaniem

b. D( R) = A

c. Ď( R) = B

relacje R i S, określone odpowiednio w zbiorach A i B są homomorficzne wtedy i tylko wtedy, gdy istnieje relacja T (ich homomorfizm):

a. T jest prawostronnie jednoznaczna (jest odwzorowaniem)

b. D( T) = P( R)

c. Ď( T) = P( S)

d. ∀ x∀ y∀ v∀ z [ xTy ∧ vTz → ( xRv ≡ ySz)]

relacje R i S są epimorficzne wtedy i tylko wtedy, gdy są homomorficzne i relacja T

ustalająca ich homomorfizm jest „na”

relacje R i S są monomorficzne wtedy i tylko wtedy, gdy są homomorficzne i relacja T

ustalająca ich homomorfizm jest różnowartościowa

relacje R i S są izomorficzne wtedy i tylko wtedy, gdy są homomorficzne i relacja T

ustalająca ich homomorfizm jest obustronnie jednoznaczna