Relacje i funkcje

Para uporządkowana –  to obiekt matematyczny o dwóch elementach (współrzędnych) umożliwiająca jednoznaczne wyróżnienie dowolnego z obiektów, z których jeden nazywany jest poprzednikiem (pierwszym elementem, pierwszą współrzędną) , a drugi następnikiem (drugim elementem, drugą współrzędną). Zwyczajowym zapisem pary uporządkowanej jest ( a , b ), gdzie a  jest pierwszą współrzędną, zaś b – drugą.  Istota pary „uporządkowanej” wyraża się w tym, że:                                         ( a , b )  oznacza coś innego niż ( b , a ), o ile a ≠ b.

Przykładem pary uporządkowanej mogą być współrzędne punktu na płaszczyźnie, a także, wynikające z odpowiedniego utożsamienia, liczby zespolone. Ogólnie elementami a i b  w parze nie muszą być liczby. Przykładem może być formalnie zdefiniowana grupa, która jest właśnie parą uporządkowaną – zbiór wraz z działaniem (patrz rozdz.  ).

O ile uznamy, w sposób naturalny, że pojęcie zbioru jest pojęciem pierwotnym, to parę uporządkowaną  można zdefiniować w sposób następujący:

            (a,b):={{a},{a.b}}

(tak właśnie w 1921 roku Kazimierz Kuratowski przedstawił do dzisiaj przyjmowaną definicję pary uporządkowanej).

Niech (a1,b1) oraz (a2,b2) będą dwiema parami uporządkowanymi. Własnością charakteryzującą (lub nawet definiującą) parę uporządkowaną jest tożsamość

(a1,b1) = (a2,b2)⇔ (a1= a2)∧ (b1= b2).

Pary uporządkowane mogą mieć za elementy inne pary uporządkowane. Z tego powodu para uporządkowana może służyć definicji rekurencyjnej krotek (n-tek) uporządkowanych.                    Na przykład trójka uporządkowana (a,b,c) może być zdefiniowana jako  ( a , ( b , c ) ), jedna para zagnieżdżona w innej. To podejście znajduje swoje odzwierciedlenie w językach programowania komputerowego. Zbiór wszystkich par uporządkowanych, których poprzednik x należy do zbioru X, a następnik y – do zbioru Y, nazywa się iloczynem kartezjańskim X  oraz Y, co zapisuje się jako X×Y. Mamy więc  (x,y) ∈  X×Y.

Relacja dwuargumentowa  ρ jako podzbiór iloczynu kartezjańskiego X i Y  jest zbiorem par uporządkowanych postaci (x,y) należących do zbioru X × Y . Czasami zamiast (x.y) ∈ ρ pisze się  x ρ y  i mówi, że element x  jest w relacji  ρ z elementem y, bądź między elementami x , y zachodzi relacja ϱ . Istnieje pewna rozbieżność względem nazewnictwa dotyczącego zbiorów; tutaj dziedziną i przeciwdziedziną nazywane będą odpowiednio zbiory X i Y. Z kolei zbiór

         DL(ρ)={x∈X:∃y∈Y (x,y)∈ ρ},    

tzn. zbiór złożony ze wszystkich poprzedników par należących do relacji ϱ ,  nazywany będzie dziedziną lewostronną (często nazywa się ją nieprecyzyjnie po prostu dziedziną), zaś zbiór 

     DP(ρ)={y∈Y:∃x∈X (x,y)∈ ρ},  

                                            

tzn. zbiór złożony ze wszystkich następników par należących do relacji ρ nazywany będzie dziedziną prawostronną lub obrazem tej relacji. Sumę dziedzin lewostronnej i prawostronnej (dziedziny i obrazu) nazywa się polem relacji

 

Wprowadzimy teraz pojęcie jednoznaczności relacji:

  • Mówimy, że relacja ma jednoznaczność lewostronną lub iniektywność, gdy

                 ∀x,z∈X∀y∈Y   x ρ y   ∧   z ρ y   ⇒  x = z

 

  • Mówimy, że relacja ma jednoznaczność prawostronną lub funkcyjność, gdy

                ∀x∈X∀y,z∈Y   x ρ y   ∧   x ρ z   ⇒  y = z

 

  • Mówimy, że relacja ma jednoznaczność obustronną bądź wzajemną (1-1), gdy ma

                 iniektywność i funkcyjność.

 

Wprowadzimy teraz pojęcie całkowitości relacji:

  • Mówimy, że relacja ma całkowitość lewostronną lub krótko całkowitość, gdy

          ∀x∈X∃y∈Y  x ρ y

  • Mówimy, że relacja ma całkowitość prawostronną lub surjektywność, gdy

                ∀y∈Y∃x∈X  x ρ y

  • Mówimy, że relacja ma odpowiedniość, gdy ma

            całkowitość i suriektywność.

Funkcją nazywa się dowolną relację funkcyjną całkowitą (lewostronnie), jeśli X = Y , to funkcję nazywa się zwykle działaniem jednoargumentowym; z kolei wzajemnie jednoznaczną odpowiedniość, nazywaną bijektywnością, nazywa się funkcją wzajemnie jednoznaczną lub bijekcją. W przypadku funkcji pojęcia dziedziny, przeciwdziedziny i obrazu pokrywają się z definicjami dla relacji; nazywanie wtedy dziedziną dziedziny lewostronnej nie prowadzi do niejasności, gdyż są one sobie równe.