Sets and Functions

Finite, Countable, and Uncountable Sets

Preliminary Definitions Related to Functions and Cardinality

Note

• Function: For two non-empty sets \(A\) and \(B\), if each element \(x\) of \(A\) is associated with an element of \(B\), then this association is a function (or a mapping) from \(A\) to \(B\), written as \(f : A \to B\).

Tip

Imagine packing when relocating, putting items inside boxes before moving all those boxes inside your truck. A function is a rule which says which item goes inside which box. You can put two items in the same box but cannot put the same item into two different boxes. Your truck may have some leftover space when you’re done packing.

Note

The following definitions are for a function \(f : A \to B\). * Domain: The set \(A\) is the domain of \(f\). * Values: The element in \(B\) associated with \(x \in A\) is the value of \(x\), written as \(f(x)\). * Co-Domain: The set \(B\) is the co-domain of \(f\). * Range: The set of all values,

\[f(A) := \{ f(x) \mid x \in A \},\]

is the range of \(f\).

Note

• Remark: \(f(A) \subseteq B\).

• Onto Mapping/Surjection: If \(f(A) = B\), then \(f\) is a mapping of \(A\) onto \(B\) (instead of into) or a surjection.

• Image: For \(E \subseteq A\),

  \[f(E) := \{ f(x) \mid x \in E \}\]

  is the image of \(E\) under \(f\).

• Pre-Image: For \(E \subseteq B\),

  \[f^{-1}(E) := \{ x \mid f(x) \in E \}\]

  is the pre-image of \(E\) under \(f\).

• 1-1 Mapping/Injection: If \(\forall y \in f(A)\), the pre-image of \(\{y\}\),

  \[f^{-1}(\{y\}) := \{ x \mid f(x) = y \},\]

  consists of just one element (a singleton), then \(f\) is a 1-1 mapping or injection of \(A\) into \(B\).

• 1-1 Correspondence/Bijection: If there exists a 1-1 mapping of \(A\) onto \(B\), then \(A\) and \(B\) are in 1-1 correspondence and \(f\) is a bijection. \(A\) and \(B\) are called equivalent and written as \(A \sim B\).

Note

• Remark: If \(A \sim B\), then \(A\) and \(B\) have the same cardinal number.

• Remark: The relation \(A \sim B\) has the following properties:

  • \(A \sim A\) [Reflexive]

  • \(A \sim B \Rightarrow B \sim A\) [Symmetric]

  • \(A \sim B \wedge A \sim C \Rightarrow A \sim C\) [Transitive]

Finite, Countable, Uncountable Sets and Sequences

Note

From now on, for some positive integer \(n\), let

\[J_n := \{1, \cdots, n\} \quad \text{and} \quad J := \{1, \cdots\} \ \text{(set of all positive integers)}.\]

• Finite Set: \(A\) is finite iff (a) \(A = \varnothing\) or (b) \(A \sim J_n\) for some \(n\).

• Infinite Set: If \(A\) is not finite, it is infinite.

• Countable Set: If \(A \sim J\), then \(A\) is countable.

• Remark: Countable sets are also called enumerable or denumerable.

• Uncountable Set: If \(A\) is neither finite nor countable, it is uncountable.

• At-most Countable Set: If \(A\) is either finite or countable, it is at-most countable.

• Remark: \(\mathbb{Z} \sim J\).

• Remark: A set \(A\) is infinite if \(A\) is equivalent to one of its proper subsets.

• Sequence: A function \(f : J \to X\) is a sequence. If \(f(n) = x_n\), the sequence is written as \(\{x_n\}\).

• Insight: A sequence is a never-ending labelling of items in a set in an orderly fashion.

• Remark: If \(\forall n \in J\), \(x_n \in A\), then \(\{x_n\}\) is a sequence in \(A\).

• Remark: Every countable set can be arranged in a sequence.

Properties involving Finite, Countable, and Uncountable Sets

Note

• Theorem: Every infinite subset of a countable set is countable.

• Remark: Countable sets represent the smallest kind of infinity.

• Theorem: Countable union of countable sets are countable. Let \(\{E_n\}\) be a sequence of countable sets. Then

  \[\bigcup_{n=1}^{\infty} E_n\]

  is countable.

• Theorem: Set of tuples whose elements are taken from a countable set is countable. For \(A\), a countable set, let

  \[B_n := \{(a_1, \cdots, a_n)\}\]

  where every \(a_k \in A\), not necessarily distinct. Then \(B_n\) is countable.

• Remark: \(\mathbb{Q}\) is countable.

• Theorem: Set of sequences whose elements are taken from a finite set is uncountable. For \(A\), a finite set, let

  \[B := \bigl\{ \{x_n\} \mid \{x_n\} \text{ is a sequence in } A \bigr\}\]

  (i.e. \(B\) is the set of all sequences whose elements are chosen, with repetition, from \(A\)). \(B\) is uncountable.