Functions

A function is a mathematical datatype that associates elements from one set, called the domain, with elements from another set, called a codomain.

$$ f: \textrm{\em domain} \rightarrow \textrm{\em codomain} $$

If the function is total, every element of the domain has one associated codomain element; if the function is partial, there may be elements of the domain that do not have an associated codomain element.

Defining a function. To define a function, we need to describe how elements in the domain are associated with elements in the codomain.

Set Products. A Cartesian product of sets $S_1, S_2, \cdots, S_n$ is a set consisting of all possible sequences of $n$ elements where the $i$\textsuperscript{th} element is chosen from $S_i$.

$$ S_1 \times S_2 \times \cdots \times S_n = { (s_1, s_2, \cdots, s_n) | s_i \in S_i } $$

How many elements are in $A \times B$?

#

What are the (sensible) domains and codomains of each function below:

$$ f(n) ::= |n| \qquad \qquad f(x) ::= x^2 \qquad\qquad f(n) ::= n + 1 \qquad\qquad f(a, b) ::= a / b $$

$$ f(x) ::= \sqrt{x} \qquad \qquad \qquad f(S) ::= \textrm{minimum}_{<}(S) $$

##

For which of them is the function total?

How are functions in your favorite programming language like and unlike mathematical functions?

#

Relations

A binary relation, $R$, consists of a domain set, $A$, and a codomain set, $B$, and a subset of $A \times B$ called the graph of $R$.

For each statement below, give the name and at least one example.

• A binary relation where no element of $A$ has more than one outgoing edge:

##

• A binary relation where every element of $A$ has exactly one outgoing edge:

##

• A binary relation where every element of $B$ has exactly one incoming edge:

##

• A binary relation where every element of $A$ has exactly one outgoing edge and every element of $B$ has exactly one incoming edge:

##

If there exists a bijective relation between $S$ and $T$ defined by the graph $G$ which of these must be true:

a. there exists some injective relation between $S$ and $T$. b. there exists some bijective relation between $T$ and $S$. c. there exists a total function, $f: S \rightarrow T$. d. $S - T = \emptyset$. e. the number of elements of $S$ is equal to the number of elements of $T$. f. $G - (S \times T) = \emptyset$. g. $(S \times T) - G = \emptyset$. h. $(S \times T) - G \neq \emptyset$.