Total and Partial 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.

Relation Relationships

Definition review: 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$.

Relation Practice

The inverse of a relation $R: A \rightarrow B, G \subseteq A \times B$ is defined by reversing all the arrows: $$ R^{-1}: B \rightarrow A, G^{-1} \subseteq B \times A $$

$$ (b, a) \in G^{-1} \iff \fillin\fillin\fillin\fillin $$

What does it mean if $R \equiv R^{-1}$?

Set Cardinality

Finite Cardinality. The book’s definition is: ``If $A$ is a finite set, the cardinality of $A$, written $|A|$, is the number of elements in $A$.”

Does this definition require adding a new fundamental set operation, or is it meaningful with just the set operations we have defined?

Alternate definition: The cardinality of the set $$ N_k = { n | n \in \mathbb{N} \wedge n < k } $$ is $k$. (Next class, we’ll use this to define the cardinality of any set. You should be able to figure out how to do this on your own with what you know now.)