Class 8: Sequences, Relations, Functions

### Schedule

**Problem Set 3** is due **Friday at 6:29pm**.

# Sequences

A **sequence** is a mathematical datatype that bears similarities to sets. A sequence $S$ also contains some elements, but we usually refer to them as *components*. There are two major differences between sets and sequences:

Components of a sequence are

**ordered**. There is either $0$, or $1$ or $2$, or … $n$ components, when the sequence if*finite*or it could be an infinite sequence that has an $i$‘th component for any non-zero natural number $i$.Different components of a sequence could be equal. For example $(a,b,a)$ has $a$ repeating, and this is a different sequence compared to $(a,b,b)$ even though they both have 3 componetns. If we interprete them as

*sets*, then they will be equal sets with $2$ elements each.

# Cartesian Product

We can use set products to get new sets whose elements are sequences. Cartesian product is a very useful way of doing it.

**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$?

# Relations and Binary Relations

A *relation* between some elements from set $A$ and some elements from set $B$ could be represented by putting all such pairs $(a,b)$ in a set $P$. As you can see, this way, $P$ would be a subset of the cartesian product $A \times B$, namely $P \subseteq A \times B$. More formally we have the following definition.

A **binary relation**, $P$, is defined with respect to a *domain* set, $A$, and a
*codomain* set, $B$, and it holds that $P$ is $P \subseteq A \times B$. When we draw $P$ by connecting elements of $A$ to $B$ based on their membership in $P$, we call this the *graph* of
$R$.

The notion of relations could be generalized to having relations
between elements coming from multiple sets $A,B,C$, and we can also
talk about relations of the form $P \subseteq A \times B \times C$,
but the binary relation remains a very important data type as it
allows us to define *functions*.

# Functions

The concept of a function $F$ models is a special form of a binary
relation $R$ between $A$ and $B$ where for every element $a \in A$
there is *at most one* element in $b \in B$ that is in relation with
$a$ (i.e. $(a,b) \in R$). More formally, we use a direct new notation
just reserved for working with 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} $$

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

#

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) $$