A note on basic set theory

This is a short note listing some basic facts on set theory and set theory notations, mostly about cardinality of sets. The discussion in this note is useful for proving theorems in topology and in many other areas. For more information on basic set theory, see [2].

Let A and B be sets. The cardinality of the set A is denoted by \lvert A \lvert. A function f:A \rightarrow B is said to be one-to-one (an injection) if for x,y \in A with x \ne y, f(x) \ne f(y). A function f:A \rightarrow B is said to map A onto B (a surjection) if B=\left\{f(x): x \in A\right\}, i.e. the range of the function f is B. If the function f:A \rightarrow B is both an injection and a surjection, then f is called a bijection, in which case, we say both sets have the same cardinality and we use the notation \lvert A \lvert = \lvert B \lvert. When the function f:A \rightarrow B, we denote this condition by \lvert A \lvert \le \lvert B \lvert. The Cantor–Bernstein–Schroeder theorem states that if \lvert A \lvert \le \lvert B \lvert and \lvert B \lvert \le \lvert A \lvert then \lvert A \lvert = \lvert B \lvert (see 1.12 in [2]).

For the functions f:X \rightarrow Y and g:Y \rightarrow Z, we define the function g \circ f by (g \circ f)(x)=g(f(x)) for each x \in X. The function g \circ f is denoted by g \circ f:X \rightarrow Z and is called the composition of g and f.

We use the notation B^A to denote the set of all functions f:A \rightarrow B. It follows that if \lvert A \lvert \le \lvert B \lvert then \lvert A^C \lvert \le \lvert B^C \lvert. To see this, suppose we have a one-to-one function f:A \rightarrow B. We define a one-to-one function H: A^C \rightarrow B^C by H(h)=f \circ h for each h \in A^C. Since f:A \rightarrow B, it follows that H is one-to-one.

By \omega, we mean the first infinite ordinal, which can be viewed as the set of all nonnegative intergers. By \omega_1 we mean the first uncountable ordinal. The notation 2^\omega has dual use. With 2=\left\{0,1\right\}, the set 2^\omega denotes all functions f:\omega \rightarrow 2. It can be shown that 2^\omega has the same cardinality as the real line \mathbb{R} and the unit interval [0,1] and the middle third Cantor set (see The Cantor set, I). Thus we also use 2^\omega to denote continuum, the cardinality of the real line.

If \lvert A \lvert=2^\omega, then the set \lvert A^{\omega} \lvert=2^\omega where A^{\omega} is the set of all functions from \omega into A. Since \omega_1 is the first uncountable ordinal, we have \omega_1 \le 2^\omega. The Continuum Hypothesis states that \omega_1 = 2^\omega, i.e. the cardinality of the real line is the first uncountable cardinal number.

The union of 2^\omega many sets, each of which has cardinality 2^\omega, has cardinality 2^\omega. Furthermore, the union of \le 2^\omega many sets, each of which has cardinality \le 2^\omega, has cardinality \le 2^\omega.

Reference

  1. Kunen, K. Set Theory, An Introduction to Independence Proofs, 1980, Elsevier Science Publishing, New York.
  2. Willard, S., General Topology, 1970, Addison-Wesley Publishing Company.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s