MA2108 Note 1

ma2108_note1.md

MA2108 Note 1

Definitions

1. A set is an unordered collection of unique elements. Examples are natural numbers, integers, rational numbers, and real numbers
2. Cartesian product of $A$ and $B$ is $A \times B = \lbrace(a, b) : a \in A, b \in B\rbrace$
3. A function from set $A$ to set $B$ is a rule of correspondence that assigns each element $x \in A$ to uniquely determined element $f(x) \in B$
4. Set $A$ is called the domain of $f$
5. Set $B$ is the codomain of $f$
6. The set $f(A) = \lbrace(x) : x \in A\rbrace$ is called the range of $f$
7. Althought $D(f) = A$, we only have $R(f) \subseteq B$

Fuction Types

1. $f : A \rightarrow B$ is called INJECTIVE (one-one) if whenever $x_1 \neq x_2$, then $f(x_1) \neq f(x_2)$. It shows uniqueness of the mapping.
2. $f : A \rightarrow B$ is called SURJECTIVE ($A$ onto $B$) if whenever $f(A) = B$ ie. $R(f) = B$. It shows existence of the mapping.
3. If 1. and 2. are met, then $f$ is BIJECTIVE

Notes

• If $f$ is bijective, the inverse function $f^{-1}$ exists and is defined as $f^{-1}(f(x)) = x~\forall x \in A$ AND $f(f^{-1}(y)) = y~\forall y \in B$
• Composition is the mising of two functions $f : A \rightarrow B$ and $g : B \rightarrow C$. A function from $A$ to $C$ is defined as $g \circ f = g(f(x))$

Mathematical Induction

Well-Ordering Principle

Every nonempty set $S \in \mathbb{N}$ has a least (first) element ie. there exists a $m \in S$ such that $m \leq k$ for all $k \in S$. The WOP does not hold for $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$.

Suppose $S \subseteq \mathbb{N}$. If

1. $1 \in S$
2. $k \in S \rightarrow k+1 \in S$
3. $S = \mathbb{N}$

Proof of Principle of MI:

• Suppose $S \neq \mathbb{N}$.
• Then $\mathbb{N} - S$ is not empty (has leftovers).
• By WOP, $\mathbb{N} - S$ has a least element $p$.
• Since $1 \in S$, we must have $p > 1$.
• By point 2. above on MI, $p = (p-1) + 1 \in S$.
• This contradicts the fact that $p \in \mathbb{N} - S$

Strong MI

1. $1 \in S$
2. for every $k \in \mathbb{N}$, if $\lbrace1, 2, \cdots, k\rbrace \subseteq S$ , then $k+1 \in S$
3. Then $S = \mathbb{n}$

Finite and Infinite Sets

• Empty set has 0 elements
• If $n \in \mathbb{n}$, a set $S$ is said to have $n$ elements if there exists a bijection from the set $\mathbb{N}_n = 1, 2, \cdots, n$ onto $S$
• $S$ is finite if is neither empty or it has $n$ elements for some $n \in \mathbb{N}$
• $S$ is infinite if it is not finite

Uniqueness Theorem

If set $S$ is finite, then the number of elements is $S$ is a unique number in $\mathbb{N}$. The set $\mathbb{R}$ is infinite.

Theorems on Sets

• If $A$ has $m$ elements and $B$ has $n$ elements and $A \cap B = \emptyset$, then $|A \cup B| = m+n$.
• if $C$ is infinite and $B$ is finite, $C - B$ is infinite
• If $S$ and $T$ are sets such that $T \subseteq S$,
  • if $S$ is finite, $T$ is finite
  • if $T$ is infinite, $S$ is infinite
• The set $\mathbb{N} \times \mathbb{N}$ is countably infinite
• If $S$ and $T$ are sets such that $T \subseteq S$,
  • if $S$ is countable, $T$ is countable
  • if $T$ is uncountable, $S$ is uncountable
• The following statements are equivalent:
  • S is a countable set
  • There exists a surjection (existence) of $\mathbb{N}$ onto $S$
  • These exists an injection (one-one) of $S$ into $\mathbb{N}$
• The set $\mathbb{Q}$ is denumerable
• If $A_m$ is countable for each $m \in mathbb{N}$, then union $A = \cup_{m=1}^\infty A_m$ is countable