Sets and Functions

Section 1.1 Sets and Functions

A set is is just a collection of objects (where the order in which the objects are listed does not matter). The following set operations should be familiar to you: intersection $A \cap B,$ union $A \cup B,$ complement $A^{c},$ difference $A ∖ B,$ and Cartesian product $A \times B .$

We also recall that proving the set $A$ is a subset of the set $B$ simply necessitates showing that any element of $A$ can also be found in $B .$

Definition 1.1.1. Set Inclusion and Equality.

If $A$ and $B$ are sets in some universe $U,$ then we say $A$ is a subset of $B,$ denoted by $A \subseteq B,$ if

(\forall x \in U) (x \in A \Rightarrow x \in B) .

We say that $A$ and $B$ are equal as sets if $A \subseteq B$ and $B \subseteq A$ both hold. This means that

(\forall x \in U) (x \in A \Leftrightarrow x \in B) .

Checkpoint 1.1.2. Prove Set Inclusion.

Define

\begin{equation*} A = \{k \in \mathbb{Z} : k = 6s + 3 \text{ for some } s \in \mathbb{Z}\} \end{equation*}

and

\begin{equation*} B = \{m \in \mathbb{Z} : m = 3t \text{ for some } t \in \mathbb{Z}\}\text{.} \end{equation*}

Prove that $A \subseteq B$ holds.

Hint

Pick an arbitrary element in $A\text{,}$ call it $x\text{.}$ Then you know $x = 6s + 3$ for some integer $s\text{.}$ Can you express $x$ in the form $3t$ where $t$ is an integer?

We will use the standard notation for these sets of numbers:

\begin{aligned} N & = {1, 2, 3, \dots,} \\ Z & = {\dots, - 2, - 1, 0, 1, 2, \dots} \\ Q & = {\frac{p}{q} : p, q \in Z} \\ R & = (- \infty, \infty), the set of real numbers. \end{aligned}

Intervals of real numbers are denoted by $(a, b), [a, b],$ and other combinations, with $- \infty$ or $\infty$ as one of both of the endpoints.

Remark 1.1.3.

Interval notation is used to refer to sets of real numbers. It is incorrect, for instance, to say that $(- 2, 4) = {- 1, 0, 1, 2, 3},$ or that ${0, 1, 2, 3, \dots} = [0, \infty) .$ Watch your notation!

Definition 1.1.4. Function.

A function

f : A \to B

is a rule that takes elements from its domain $A$ and assigns to each one an element from the codomain $B .$

Definition 1.1.5. Injective, surjective, bijective.

A function $f : A \to B$ is

injective if for every $x_{1} \neq x_{2} \in A,$ $f (x_{1}) \neq f (x_{2}) .$
surjective if for every $y \in B,$ there exists an $x \in A$ so that $f (x) = y .$
bijective if it is both injective and surjective.

Checkpoint 1.1.6. Injective, surjective, bijective, or none?

For each function, determine if it is injective, surjective, bijective, or none of these:

$f: \mathbb{R} \rightarrow (0,+\infty)\text{,}$ $f(x) = \sqrt{x^2+1}$
$g: \mathbb{N} \rightarrow \mathbb{N}\text{,}$ $g(m) = 3m + 7m^2$
$h: \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}\text{,}$ $h(a,b) = \dfrac{ab(b-1)}{2}$

Answer

1. none, 2. injective, 3. surjective.

Definition 1.1.7. Composition.

Given two functions $f : A \to B$ and $g : B \to C,$ the composition $g \circ f : A \to C$ is defined as the function

(g \circ f) (x) = g (f (x))

for all $x \in A .$

Theorem 1.1.8. Properties of Compositions.

The composition of two (injections, surjections, bijections) is a(n) (injection, surjection, bijection).

Checkpoint 1.1.9. Prove Theorem 1.1.8.

Prove Theorem 1.1.8.

Later in the course we will learn techniques for counting objects and proving that two sets have the same number of elements; the notion of cardinality will be a useful tool to remember.

Definition 1.1.10. Cardinality Relations.

Two sets $A$ and $B$ are said to have the same cardinality, written as

| A | = | B |,

if there exists a bijection between them.

We also say $A$ has cardinality less than or equal to the cardinality of $B,$ written as

| A | \leq | B |,

if there exists an injective function from $A$ to $B .$

Checkpoint 1.1.11. There are as many natural numbers as odd integers.

Prove that the set of odd integers

\begin{equation*} O = \{\ldots,-3,-1,1,3,\ldots\} \end{equation*}

has the same cardinality as $\mathbb{N}\text{.}$

Hint

Construct a bijection from $O$ to $\mathbb{N}\text{.}$

Definition 1.1.12. Power Set.

Let $A$ be a set. The power set of $A,$ denoted by $P (A),$ is the set

P (A) = {X : X \subseteq A},

that is, it contains all subsets of $A .$

Checkpoint 1.1.13. Cardinality of a Power Set.

Prove that if $A$ is finite, then

\begin{equation*} |P(A)| = 2^{|A|}\text{.} \end{equation*}