Functions

See also: Mathematical Analysis - index

---

A relational graph  [;F;]  is said to be functional (a functional graph)   [;\Leftarrow :\Rightarrow;]

[;\bullet\quad\quad\quad \forall_{\ x\ y\ z}\ \left(\ (x\ y)\ (x\ z)\ \in\ F\ \ \Rightarrow\ \ y=z\ \right);]

EXAMPLE 0  The diagonal  [;\Delta_X;]  of any set  [;X;]  is a functional graph.

EXAMPLE 1  The following relational graph

[;\bullet\quad\quad\quad C_{X\,c}\ :=\ X\times \{c\};]

is functional.

---

On the other hand, when set  [;A;]  is non-empty, and set  [;B;]  has more than one element, then their cartesian product  [;A\times B;]  is a relational graph which is not functional.

---

A relation  [;f := (X\ Y\ F);]  is said to be a function from  [;X;]  to  [;Y;]   [;\Leftarrow :\Rightarrow;]   [;F;]  is a functional graph such that

[;\bullet\quad\quad\quad\forall_{\ x\in X}\ \exists_{\ y\in Y}\ (x\ y) \in F;]

NOTATION:   When  [;f := (X\ Y\ F);]  is a function, and  [;(x\ y)\in F;]  then we write  [;y = f(x);].  (the value  [;f(x);]  is defined uniquely because graph  [;F;]  is functional). We also write  [;f : X \rightarrow Y;], and

[;\bullet\quad\quad\quad graph(f) := F;]

Thus


[;\bullet\quad\quad\quad graph(f)\ =\ \{ (x\ f(x)) : x\in X \};]

---

EXAMPLE 2 (compare with Example 0)  The identity relation

[;\bullet\quad\quad\quad I_X := (X\ X\ \Delta_X);]

is a function, called the identity function in  [;X;].  Now another way to define function  [;I_X : X \rightarrow X;]  is:

[;\bullet\quad\quad\quad \forall_{x \in X}\ I_X(x) := x;]

EXAMPLE 3 (compare with Example 1)  Let  [;c\in Y;].  The relation

[;\bullet\quad\quad\quad \gamma\ := (X\ Y\ C_{X\,c});]

is a function called the constant function on  [;X;]  (and into  [;Y;]), with constant value  [;c;].

---

We will see in a next post that general functions can be constructed using more special functions, namely canonical surjections, bijections, and canonical injections. The definitions of (arbitrary) surjections, bijections, and (arbitrary) injections are provided already below.

---

A function  [;f : X \rightarrow Y;]  is said to be surjective   [;\Leftrightarrow\quad \forall_{y\in Y}\exists_{x\in X}\ f(x)=y;].

---

A function  [;f : X \rightarrow Y;]  is said to be injective   [;\Leftrightarrow\quad \forall_{x'\,x"\in X}\ (f(x')=f(x")\ \Rightarrow\ x'=x");].

---

A function  [;f : X \rightarrow Y;]  is said to be bijective   [;\Leftrightarrow;]   [;f;]  is both surjective and injective.

---

Going back to surjections, let  [;\mathbf{T} := (X\ X\ T);]  be an equivalence relation. Let  [;X/\mathbf{T};]  be the set of the equivalence classes of  [;\mathbf{T};].  Then the canonical projection is defined as a function

[;\bullet\quad\quad\quad \pi : X \rightarrow X/\mathbf{T};]

defined by equality:

[;\bullet\quad\quad\quad \forall_{x\in X}\ \pi(x) := [x] ;]

where  [;[x];] is the equivalence class of  [;x;]  with respect to the equivalence relation  [;\mathbf{T};].

---

Going back to injections, let  [;A \subseteq X;].  Then the canonical embedding of  [;A;]  into  [;X;]  is defined as a function:


[;\bullet\quad\quad\quad i_A : A \rightarrow X;]

such that

[;\bullet\quad\quad\quad \forall_{x\in X}\ i_A(x) := x ;]

Transitivity reflexivity preorder

See also: Mathematical Analysis - index

---

A relational graph [;T;] is called transitive  [;\Leftarrow : \Rightarrow;] 

• 
  [; \forall_{x\ y\ z} (((x\ y) \in T\ \ \&\ \ (y\ z) \in T)\quad (x\ z) \in T) ;]
  

A relation [;\mathbf{T} := (X\ X\ T);] is called transitive  [;\Leftarrow : \Rightarrow;]  the relational graph  [;T;]  is transitive.

REMARK 0  Transitivity is defined only for relations for which codomain coincides with the domain (we have  [;X=Y;]  so to speak). When codomain coincides with the domain, say  [;X=Y;],  then we say that the relation is in  [;X;]  (rather than in  [;X\ Y;]).

---

A relational graph  [;T;]  is called reflexive  [;\Leftarrow : \Rightarrow;] 

• [;\forall_{x\ y} ( (x\ y) \in T\quad\Rightarrow\quad ((x\ x)\in T\ \ \&\ \ (y\ y) \in T) ;]

---

Let  [;X;]  be an arbitrary set. Then the following set  [;\Delta_{X};]  is called the diagonal of  [;X;]:

[;: \quad\quad \Delta_{X} := \{ (x\ x) : x\in X \} ;]

We see that  [;\Delta_{X};]  is a relational graph, and that

[;: \quad\quad \mathbf{\Delta}_{X}\ \ :=\ \ (X\ X\ \Delta_{X}) ;]

is a relation in  [;X;].

A relation [;\mathbf{T} := (X\ X\ T);] is called reflexive  [;\Leftarrow : \Rightarrow;]  the relational graph  [;T;]  contains the diagonal:  [;\Delta_X \subseteq T;].

REMARK 1  Reflexivity is defined only for relations for which codomain coincides with the domain.

REMARK 2  The relational graph of any reflexive relation is reflexive, while the inverse claim fails: a relation may have a reflexive graph without being reflexive, as for instance the empty relation in a non-empty set  [;X;]:

[;:\quad\quad(X\ X\ \emptyset) ;]

THEOREM 0  Let  [;\mathbf{T} := (X\ X\ T);]  be a transitive relation. Then the relational graph

[; :\quad\quad\underline{T} := T\cup\Delta_X ;]

is both transitive and reflexive. Furthermore

[; :\quad\quad\underline{\mathbf{T}} := (X\ X\ \underline{T});]

is a transitive and reflexive relation

---

A relation which is both transitive and reflexive is called a preorder.

We saw that each transitive relation in  [;X;]  leads to a preorder by extending it by the diagonal  [; \Delta_X;].

Diagonal  [;\Delta_{X};]  itself is a preorder. And so is the complete relation in  [;X;],  which has  [;X\times X;]  for its relational graph.

Relational graphs and relations

See also: Mathematical Analysis — index

---

Let's start with three definitions:

• The Cartesian product  [;X\times Y;]  of two sets  [;X\ Y;]  is defined as the set of all ordered pairs such that their first and second terms belong respectively to  [;X\ Y;]:
  
  [;:\quad\quad X\times Y\ \ :=\ \ \{(x\ y)\ :\ x\in X\ \ \&\ \ y\in Y\};]
  
• 
  A set [;T;] is said to be a relational graph  [; \Leftarrow : \Rightarrow ;]  every element of [;T;] is an ordered pair.
  
• 
  An ordered triple  [;\mathbf{T} := (X\ Y\ T);]  is said to be a relation  [; \Leftarrow : \Rightarrow\ \ T ;]  is a relational graph such that [;T \subseteq X\times Y ;].  Such a relation  [;\mathbf{T};]  is said to be a relation in the sets  [;X\ \ Y;],  where  [;X;]  is called the domain of relation  [;\mathbf{T};],  and  [;Y;] is called the codomain or the target of [;\mathbf{T};].
  

REMARK  We could define a relation in fewer words: an ordered triple  [;\mathbf{T} := (X\ Y\ T);]  is said to be a relation  [; \Leftarrow : \Rightarrow\ \ T \subseteq X\times Y ;].

We see that a relation is an ordered triple of the form:

          (domain  codomain  rel_graph)

where rel_graph is a relational graph contained in the Cartesian product of the domain and codomain.

Observe that  [;(X \ Y\ X\times\ Y);]  is a relation in the sets  [;X\ \ Y;];  its relational graph contains the relational graph of any other relation in the sets  [;X\ \ Y;].  Also the empty set is a relational graph. It is contained in any other relational graph. Thus any relational graph of any relation in the sets  [;X\ \ Y;];  is contained between these two relational graphs.