2. Sequences, Strings

Sequence = enumerated or indexed collection of elements where repetition is allowed and order matters

1. Sequences are numbers
2. Sequences are infinite

Examples:

• $(1,1,1,1,...)$
• $(1,2,3,4,...)=(n+1{)}_{n\ge 0}$

If X is a set, then an X-string is an ordered sequence of elements in X with repetition allowed

$X=\{0,1\}$ $\text{X-string (of length 4)}=0110$

$X=\{D,E,H,L,O,R,W\}$ $\text{X-string (of length 10) can be HELLOWORLD}$

Given X and Y are sets, an ordered pair $(x,y)$ mapping $x\in X$ to $y\in Y$ means that $y$ is an image of $x$.

A function $f:x\to y$ is a set of ordered pairs st. each $x\in X$ has one ordered pair in $f$ - 1 input, 1 output

Example: $f(x)=x^2$ can also be represented as $\{(x,x^2)\mid x\in \mathbb{R}\}$

Domain = X Codomain = Y Range is a subset of the codomain such that $\{y\in Y\mid (x,y)\in f\text{ for some x}\}$ = the Y that exists in f for some x

A function is…

• Injective (one to one) if no element in its range is in more than 1 ordered pair of $f$
• Surjective (onto) if the codomain of $f$ is equal to its range
• Bijective if it is both injective and surjective

$X=\{1,2,3\}$, $Y=\{A,B,C,D\}$

injective $f=\{(1,A),(2,B)\}$ surjective $g=\{(1,A),(2,B),(3,B),(3,C),(3,D)\}$

Injective means every output has only one input Surjective means every possible output is in the function

Can apply the pigeonhole principle for injectivity/surjectivity

Pigeonhole Principle

If $n+1$ pigeons want to fit in $n$ holes, at least one pigeonhole contains 2 pigeons

To prove injection, show if $f(x)=f(w)\text{ for some }x,w\in X$, then $x=w$

To prove surjection, show for any $y\in Y$, there exists some x where $f(x)=y$

Do both for bijection

Example:

Let E be the set of even numbers and O for odd. Prove $|E|=|O|$. Odd is even + 1. $f(x)=x+1$. f is injective because if $x+1=w+1$ then $x=w$. f is surjective because pick any $y\in O$, then consider $y-1\in E$. put in f and get y

Bijective → $|E|=|O|$