Skip to main content

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\text{,}\) union \(A \cup B\text{,}\) complement \(A^c\text{,}\) difference \(A \ \backslash \ B\text{,}\) and Cartesian product \(A \times B\text{.}\)

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\text{.}\)

Definition 1.1.1. Set Inclusion and Equality.

If \(A\) and \(B\) are sets in some universe \(U\text{,}\) then we say \(A\) is a subset of \(B\text{,}\) denoted by \(A \subseteq B\text{,}\) if

\begin{equation*} (\forall x \in U)(x \in A \Rightarrow x \in B)\text{.} \end{equation*}

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

\begin{equation*} (\forall x \in U)(x \in A \Leftrightarrow x \in B)\text{.} \end{equation*}

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{align*} \mathbb{N} \amp = \{1,2,3,\ldots,\}\\ \mathbb{Z} \amp = \{\ldots,-2,-1,0,1,2,\ldots\}\\ \mathbb{Q} \amp = \left\{\dfrac{p}{q} : p,q \in \mathbb{Z}\right\}\\ \mathbb{R} \amp = (-\infty,\infty), \text{ the set of real numbers.} \end{align*}

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\}\text{,}\) or that \(\{0,1,2,3,\ldots\} = [0,\infty)\text{.}\) Watch your notation!

Definition 1.1.4. Function.

A function

\begin{equation*} f: A \rightarrow B \end{equation*}

is a rule that takes elements from its domain \(A\) and assigns to each one an element from the codomain \(B\text{.}\)

Definition 1.1.5. Injective, surjective, bijective.

A function \(f: A \rightarrow B\) is

  • injective if for every \(x_1 \ne x_2 \in A\text{,}\) \(f(x_1) \ne f(x_2)\text{.}\)
  • surjective if for every \(y \in B\text{,}\) there exists an \(x \in A\) so that \(f(x) = y\text{.}\)
  • bijective if it is both injective and surjective.

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

  1. \(f: \mathbb{R} \rightarrow (0,+\infty)\text{,}\) \(f(x) = \sqrt{x^2+1}\)
  2. \(g: \mathbb{N} \rightarrow \mathbb{N}\text{,}\) \(g(m) = 3m + 7m^2\)
  3. \(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 \rightarrow B\) and \(g: B \rightarrow C\text{,}\) the composition \(g \circ f: A \rightarrow C\) is defined as the function

\begin{equation*} (g \circ f)(x) = g(f(x)) \end{equation*}

for all \(x \in A\text{.}\)

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

\begin{equation*} |A| = |B|\text{,} \end{equation*}

if there exists a bijection between them.

We also say \(A\) has cardinality less than or equal to the cardinality of \(B\text{,}\) written as

\begin{equation*} |A| \leq |B|\text{,} \end{equation*}

if there exists an injective function from \(A\) to \(B\text{.}\)

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\text{,}\) denoted by \(P(A)\text{,}\) is the set

\begin{equation*} P(A) = \{X : X \subseteq A\}\text{,} \end{equation*}

that is, it contains all subsets of \(A\text{.}\)

Prove that if \(A\) is finite, then

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