# Discrete Mathematics Note Chapter 2

# Basic Structures: Sets, Functions, Sequences, and Sums

## Sets

Definition: A **set** is an unordered collection of objects. The objects in are called **elements**. It is said to **contain** its elements.

\(a \in A\): Element \(a\) belongs to set \(A\).

### Four ways to describe

- Roster method: listing elements between braces. $S = {1, 2, 3,} $
- Brace notation with ellipses \(S = \{1, 2, \ldots, 100\}\)
- Specification using set builder: \(S = \{x | P(x)\}\)
- Venn diagrams:
- \(U\) is represented in rectangle.
- Different sets represented in circles in the rectangle.

\(\emptyset\): Empty set, a set that contains nothing.

\(U\): Universal set, containing all objects.

### Relations between Two Sets

**Subset**: \(A \subseteq B\)

\(\emptyset \subseteq A, A\subseteq A\).

**Proper Subset**: \(A \subset B \Leftrightarrow (A \subseteq B\ \land\ A \neq B)\).

**Equal**: \(A = B \Leftrightarrow (A \subseteq B\ \land \ B\subseteq A)\).

**Size**: If there are exactly \(n\) elements in \(S\), we call \(S\) is **finite** and \(n\) is the **cardinality** of \(S\).

**Power Set**: The set containing all subsets of a given set. Attention, its elements are sets.

\(P(S) = \{X | X \subseteq S\}\).

\(|P| = 2^{|S|}\), so if \(S\) is finite, then \(P\) is finite.

Five rules: \(x \in P(S) \Rightarrow x \subseteq S\); $x S {x} P(S) $; \(S \in P(S)\).

\(P(A) \in P(B) \Rightarrow A \in B\); \(A \subseteq B \Rightarrow P(A) \subseteq P(B)\).

The **ordered n-tuple** \((a_1, a_2, \ldots, a_n)\). \((x, y) \neq (y, x)\).

The **Cartesian product** of two sets: \(A \times B = \{(a, b) | a \in A \land b \in B\}\)

**Truth Set** of predicate \(P\) in domain \(D\) is \(\{x | P(x)\}\).

## Set operations

### Operation Names

**Union**: \(A \bigcup B = \{x | x \in A \lor x\in B\}\).

**Intersection**: \(A \bigcap B = \{x | x\in A \land x \in B\}\). If \(A \bigcap B = \emptyset\), then we call they are **disjoint**.

\(|A \bigcup B| = |A| + |B| - |A \bigcap B|\).

**Difference**: $ A - B = {x | x A x B} = A B$.

**Complement**: \(\overline A = \{x | x \notin A \land x \in U\} = U - A\).

**Symmetric Difference**: $A B = (A B) - (A B) $.

### Set Identities

Four ways to prove:

- show that \(A \subseteq B\) and \(B \subseteq A\).
- Use logical equivalence to prove equivalent set definitions.
- Use membership tables (like truth table).
- Use previously proven identities.

Some proven identities:

- De Morgan's laws: \(\overline {(A \bigcup B)} = \overline{A} \bigcap \overline{B}\); \(\overline {(A \bigcap B)} = \overline{A} \bigcup \overline{B}\).
- Distributive laws: \(A \bigcup (B \bigcap C) = (A \bigcup B) \bigcap (A \bigcup C)\); \(A \bigcap (B \bigcup C) = (A \bigcap B) \bigcup (A \bigcap C)\).

### Computer Representations

Use bit strings to represent.

First we know \(U = {a_1, a_2, a_3 ,\ldots}\), and \(|U| = n\).

Then we can use a bit string \(s\) of length \(n\) to represent any set, \(s_i = 1\) if \(a_i\) is in this set.

## Functions

### Definition

A **function(mapping)** \(f\) from \(A\) to \(B\): \[
f : A \rightarrow B\\
\forall a \exists! b (a \in A \rightarrow b \in B \land f(a) = b )
\] \(A\) is called the **domain**, \(B\) is called **codomain**.

\(f(a) = b\), then \(b\) is called **image** of \(a\), \(a\) is called **preimage** of \(b\).

\(f(A) = \{f(a) | a \in A\}\) is called **range**, and it's a subset of \(B\).

If \(f\) is a function, we can call f **maps** \(A\) to \(B\).

\(f(\emptyset) = \emptyset\), \(f(\{ a \}) = \{ f(a) \}\).

\(f(A \bigcup B) = f(A) \bigcup f(B)\).

\(f(A \bigcap B) \subseteq f(A) \bigcap f(B)\).

### Graph of Functions

The **graph** of the function \(f\) is the set \(\{ (a, b) | a \in A \land b = f(a) \}\).

### Injective & Surjective Functions

**Injective** (One-to-one) functions hold that \[
\forall a \forall b (f(a) = f(b) \rightarrow a = b )
\] That is, every element in domain has a unique image.

**Surjective** (Onto) functions hold that \[
\forall b \in B \exists a \in A (f(a) = b)
\] That is, every element in codomain has at least one preimage.

**Bijection** (One-to-one correspondence) is both one-to-one and onto.

Bijection's domain and codomain must have the same **cardinality**.

### Monotonic Function

Monotonically (strictly) increasing: \(x < y \rightarrow f(x) < f(y)\).

Monotonically (strictly) decreasing: \(x < y \rightarrow f(x) > f(y)\).

### Inverse Functions

If \(f\) is a bijection, the **inverse function** of \(f\) can be defined as \(f^{-1}\), that \(f^{-1}(y) = x\ \mathrm{iff}\ f(x) = y\). \((f^{-1})^{-1} = f\).

Otherwise, the inversion doesn't exist.

### Composition

Let \(g\) be a function from \(A\) to \(B\), and \(f\) be a function from \(B\) to \(C\). Then the **composition** of \(g\) and \(f\) is \[
f\ \circ\ g (a) = f(g(a))
\] The range of \(g\) must be a subset of the domain of \(f\).

### Simple Important Functions

Floor Function \(\lfloor x \rfloor\) (greatest integer below \(x\)) and Ceiling Function \(\lceil x \rceil\) (least integer above \(x\)) are commonly used.

#### Properties

## Sequence and Summations

### Definition

A **sequence** is a function from a subset of the set of integers \([N]\) to a set \(S\). We use the notation \(a_n\) to denote \(f(n)\).

Note that the order in a sequence matters.

### Geometric Progression

A sequence of the form \(a, aq, aq^2, \dots, aq^{n-1}\).

### Arithmetic Progression

A sequence of the form \(a, a + d, a + 2d, \ldots, a + (n - 1)d\).

### Summation

\[ \sum_{i=m} ^n a_i,\quad \sum _{x\in S} f(x) \]

\(m\): lower bound, \(n\): upper bound, \(i\): index of summation;

\(S\) should be a subset of the domain of \(f\).

#### Useful Closed Form

\(\large\sum\limits_{k = 0}^{n} ar^k = a \dfrac{r^{n + 1} - 1}{r - 1} (r \neq 0, 1)\).

\(\large\sum\limits_{k = 1}^n k^2 = \dfrac{n (n + 1) (2n + 1)}{6}\).

\(\large \sum \limits_{k = 1}^{n} k^3 = \dfrac{n^2 (n + 1)^2}{4} = \left(\dfrac{n (n + 1)}{2}\right)^2\).

## The cardinality of an infinite set

### Definition

The cardinality of a set \(A\) is **equal** to the cardinality of a set \(B\), denoted \(|A| = |B|\), \(\mathrm{iff}\) there exists a bijection from \(A\) to \(B\).

If there is an injection from \(A\) to \(B\), then we have \(|A| \le |B|\). And if they have different cardinality, we say \(|A| < |B|\).

Any real interval have the same cardinality, so they are equal. A bijection \(f\) from \((a, b)\) to \((c, d)\): \(\dfrac{f(x)-d}{c-d}=\dfrac{x-a}{b-a}\).

If a set is finite or has the same cardinality as \(N_{+}\), it is called **countable**. Otherwise it's called **uncountable**.

The cardinality of **countable infinite** set \(S\) is **aleph null** \(\aleph_0\).

### Amazing conclusions

\(|Z| = |N^+|, |Q^+| = |N^+|\).

To prove \(|Q^+| = |N^+|\), define \(S = \{ (p,q) | p, q \in N^+ \}\).

- \(Q^+ \subseteq S\), because \(r = \frac{p}{q} \in Q^+\), then \((p, q)\) must be in \(S\).
- \(|S| = |N^+|\), because \((p, q)\) can be put in the \(q\)-th column of \(p\)-th row in the table, and we can pick them up in the antidiagonal order \((1, 1), (2, 1), (1, 2), (3, 1), (2, 2) \ldots\).
- \(N^+ \subseteq Q^+\).

### Property

- No infinite set has a smaller cardinality than a countable set.
- The union of two countable set is countable.
- The union of finite number of countable sets is countable.
- The union of countable number of countable sets is countable.

### Cantor Diagonalization Argument

**Theorem**: The set of real number between \(0\) and \(1\) is uncountable.

Proof:

- \(|N^+| \le |A|\)
a function \(f(n) = \frac{1}{n+1}\) performs \(f : N^+ \rightarrow A\).

- \(| N^+ | \neq |A|\)
Assume \(A\) is countable, then let \(A = \{ r_1, r_2, \ldots, r_n \ldots \}\).

Then list

\(r_1 = 0.d_{11}d_{12}d_{13}\ldots\)

\(r_2 = 0.d_{21}d_{22}d_{23}\ldots\)

\(r_3 = 0.d_{31}d_{32}d_{33}\ldots\)

\(\ldots\)

Now construct \(x = 0.x_1x_2x_3\ldots\)

\(x_i = p\) if \(d_{ii} \neq p\), otherwise \(x_i = p + 1\).

\(x\) is not in \(A\) since it's not equal to any \(r_i\).

How to describe the cardinality of \((0, 1)\)? We can see that \(|(0, 1)| = |R|\).

Let \(f(x) = \tan x\).

There is an bijection from \(( -\frac{\pi}{2}, \frac{\pi}{2} )\) to \((- \infty, + \infty)\).

Then \(|(0, 1)| = |( -\frac{\pi}{2}, \frac{\pi}{2} )| = |R|\).

The cardinality of \(R\) is **aleph one** \(\aleph_1\).

In cantor diagonalization argument, we try to list the elements of the set \(S\) in a matrix.

Then we pick the them up in antidiagonal order, to form a sequence.

Finally if the sequence has the same cardinality as \(N^+\), we can prove \(|S| = |N^+|\).

### Computability

A function is **computable** is it can be computed by some programming language. Otherwise it's **incomputable**.

**Schrőder-Bernstein Theorem**: If \(|A| \leq |B|\) and \(|B| \leq |A|\), then \(|A| = |B|\).

To prove \(|A| = |B|\), find \(f : A \rightarrow B\) and \(g : B \rightarrow A\).

The **Continuum Hypothesis** asserts that there's no cardinal number \(a\) such that \(\aleph_0 < a < \aleph_1\).