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∩B, union A∪B, complement Ac, difference A ∖ B, and Cartesian product A×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⊆B, if

(∀x∈U)(x∈A⇒x∈B).

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

(∀x∈U)(x∈A⇔x∈B).

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:

N={1,2,3,…,}Z={…,−2,−1,0,1,2,…}Q={pq:p,q∈Z}R=(−∞,∞), the set of real numbers.

🔗
Intervals of real numbers are denoted by (a,b),[a,b], and other combinations, with −∞ or ∞ 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,…}=[0,∞). Watch your notation!

🔗
Definition 1.1.4. Function.

A function

f:A→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→B is

  • injective if for every x1≠x2∈A, f(x1)≠f(x2).
  • surjective if for every y∈B, there exists an x∈A so that f(x)=y.
  • 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→B and g:B→C, the composition g∘f:A→C is defined as the function

(g∘f)(x)=g(f(x))

for all x∈A.

🔗
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|≤|B|,

if there exists an injective function from A to B.

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⊆A},

that is, it contains all subsets of A.

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

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