Class 9: Relations, Finite Set Cardinality

### Schedule

This week you should finish reading MCS Chapter 4 (section 4.5) and Section 5.1. We will discuss Induction (Section 5.1) next class.

**Problem Set 4** is due **Friday at 6:29pm**. The
original version of Problem Set 4, Question 6, asked for a *function*,
when we really meant to ask for a *total function* (as we defined it
in class today, and the book defines it). The problem set is updated
now to specify this. If you already answered the original question,
you do not need to update your answer, just indicate clearly for which
questions the function you defined is partial. Sorry for the
confusion!

**Problem Set 5** (not yet posted) will be due Friday, 29 September.

**Exam 1** will be in-class on Thursday, 5 October. It will cover
Classes 1 - 11, Problem Sets 1 - 5, and MCS Chapters 1 - 5.

## 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.)