Математичка логика, скупови, релације и функције

Функције

Ако су $A$ и $B$ два непразна скупа, функција или пресликавање скупа $A$ у скуп $B$ је сваки подскуп $f$ скупа $A \times B$, у којем се свако $x \in A$ појављује тачно једанпут као прва компонента.

Ово се записује:

$f:A \to B$

Дакле, функција $f:A \to B$ је таква бинарна релација између елемената скупова $A$ и $B$, тј. $f \subset A \times B$, која задовољава следећа два услова:

  1. скуп свих првих елемената уређених парова релације $f$ је скуп $A$,
  2. важи импликација $\left( {\left( {x,y} \right) \in f \wedge \left( {x,z} \right) \in f} \right) \Rightarrow y = z$

Ако је $\left( {x,y} \right) \in f$, онда се $x$ (прва компонента) назива оригинал, , а  (друга $y$ компонента) слика. Пише се $y = f\left( x \right)$.

 

Домен и кодомен

Скуп свих оригинала у кодомену функције $f$ зове се домен и означава се са $D\left( f \right)$, а скуп свих слика зове се кодомен функције и озачава се са ${C_D}\left( f \right)$.

Функција $f:A \to B$ је

"на" или сурјекција ако $\left( {\forall y \in B} \right)\left( {\exists x \in A} \right)\left( {y = f\left( x \right)} \right)$ 
"1-1" или инјекција ако  $\left( {\forall {x_1},{x_2} \in A} \right)\left( {f\left( {{x_1}} \right) = f\left( {{x_2}} \right) \Rightarrow {x_1} = {x_2}} \right)$
бијекција ако је истивремено и "на" и "1-1"


Пермутација

Пермутација скупа $A$ је бијекција скупа $A$ на самог себе.

 

Инверзна функција

Ако је инверзна релација ${f^{ - 1}}$ функције $f$ такође функција, онда се каже да је ${f^{ - 1}}$ инверзна функција функције $f$.

 

Композиција функција

Ако су $f:A \to B$ и $q:B \to C$ дате функције, функција $q \circ f:A \to C$, дефинисана са

 

$\left( {q \circ f} \right)\left( x \right) = q\left( {f\left( x \right)} \right)$

 

назива се производ или композиција функција $f$ и $q$.

Ако је $f:D\left( f \right) \to {C_D}\left( f \right)$ бијекција, онда постоји ${f^{ - 1}}$ и за свако $x \in D\left( f \right)$ и свако $y \in {C_D}\left( f \right)$ важи

$\left( {{f^{ - 1}} \circ f} \right)\left( x \right) = x$, $\left( {f \circ {f^{ - 1}}} \right)\left( y \right) = y$

Задавање функције

Функција се задаје:

  1. навођењем свих уређених парова
    $f = \left\{ {\left( {{x_1},{y_1}} \right),\left( {{x_2},{y_2}} \right),....,\left( {{x_n},{y_n}} \right)} \right\}$
    или
    $f = \left( {\begin{array}{*{20}{c}}
    {{x_1}{\text{ }}{x_2}{\text{ }}...{\text{ }}{x_3}} \\
    {{y_1}{\text{ }}{y_2}{\text{ }}...{\text{ }}{y_3}}
    \end{array}} \right)$
  2. навођењем правила (формуле) по којем се за дати оригинал добија слика
    $f = \left\{ {\left( {x,y} \right)|y = R\left( x \right)} \right\}$

Пише се $x \mapsto f\left( x \right) = R\left( x \right)$ или само $f\left( x \right) = R\left( x \right)$, односно $y = R\left( x \right)$


Коначан и бесконачан скуп

Скуп је бесконачан ако постоји бијекција која га пресликава на неки његов прави подскуп. У противном, скуп је коначан.

 

Кардиналност скупа

За скупове $A$ и $B$ каже се да имају једнаке кардиналне бројеве (такође се каже да су еквивалентни или да имају једнаку моћ), ако постоји бијекција $f:A \to B$, што се пише $card\left( B \right)$ или $|A| = |B|$.
Кардинални број скупа $A$ је $n \in N$, тј. $card\left( A \right) = n$, ако и само ако постоји бијекција $f:A \to \left\{ {1,2,....,n} \right\}$.


Пребројив и непреброив скуп

Бесконачан скуп је пребројив, ако постоји бијекција која га пресликава на скуп природних бројева. У противном скуп је непребројив.