- A set is an unordered collection of unique elements. Examples are natural numbers, integers, rational numbers, and real numbers
- Cartesian product of
$A$ and$B$ is$A \times B = \lbrace(a, b) : a \in A, b \in B\rbrace$ - 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$ - Set
$A$ is called the domain of$f$ - Set
$B$ is the codomain of$f$ - The set
$f(A) = \lbrace(x) : x \in A\rbrace$ is called the range of$f$ - Althought
$D(f) = A$ , we only have$R(f) \subseteq B$
-
$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. -
$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. - If 1. and 2. are met, then
$f$ is BIJECTIVE
- 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))$
Every nonempty set
Suppose
$1 \in S$ $k \in S \rightarrow k+1 \in S$ $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$
$1 \in S$ - for every
$k \in \mathbb{N}$ , if$\lbrace1, 2, \cdots, k\rbrace \subseteq S$ , then$k+1 \in S$ - Then
$S = \mathbb{n}$
- 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
If set
- 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
- if
- 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
- if
- 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