Functions and Relations

fnr.md

$$ \newcommand{\NOT}{{\sim}} \newcommand{\R}{\textbf{ R }} $$

• (f) is one-to-one ( \Leftrightarrow ) ( \forall a,b \in X, f(a) = f(b) \rightarrow a = b )

• (f) is onto ( \Leftrightarrow ) ( \forall y \in Y, \exists x \in X \text{ such that } f(x) = y )

• (f) has one-to-one correspondence ( \Leftrightarrow ) (f) is both one-to-one AND onto.

• (f^{-1}(x)) is the inverse of (f(x)) ( \Leftrightarrow ) ( \forall x \in X, f^{-1}(f(x)) = x )

• (\R) is reflexive ( \Leftrightarrow ) ( \forall x \in S, x \R x )

• (\R) is irreflexive ( \Leftrightarrow ) ( \NOT \exists x \in S, x \R x )

• (\R) is symmetric ( \Leftrightarrow ) ( \forall a, b \in S, a \R b \rightarrow b \R a )

• (\R) is asymmetric ( \Leftrightarrow ) ( \NOT \exists a, b \in S, a \R b \rightarrow b \R a )

• (\R) is antisymmetric ( \Leftrightarrow ) ( \forall a, b \in S, (a \R b \wedge b \R a) \rightarrow a = b )

• (\R) is transitive ( \Leftrightarrow ) ( \forall a, b, c \in S (a \R b \wedge b \R c) \rightarrow a \R c )

• (\R) is an equivalence relation ( \Leftrightarrow ) (\R) is reflexive, symmetric AND transitive

• (\R) is a partial order relation ( \Leftrightarrow ) (\R) is reflexive, antisymmetric AND transitive

• (\R) is a total order relation ( \Leftrightarrow ) (\R) is a partial order relation AND (\forall a,b \in S, a \R b \vee b \R a )