Topology/Basic Concepts Set Theory

From Wikibooks, open books for an open world
Jump to: navigation, search

This chapter concisely describes the basic set theory concepts used throughout this book—not as a comprehensive guide, but as a list of material the reader should be familiar with and the related notation. Readers desiring a more in-depth understanding of set theory should read the Set Theory Wikibook.

Basic Definitions[edit]

The empty set is denoted by symbol \varnothing. A finite set consisting of elements x_1, x_2, \ldots, x_n is denoted \{x_1, x_2, \ldots, x_n\}. Set theorists commonly, albeit sloppily, do not distinguish strictly between a singleton set \{x\} and its single element x.

For a more in depth understanding of how elements of sets relate to each other, we must first define a few terms. Let A and B denote two sets.

  • The union of A and B, denoted A\bigcup{B}, is the set of all x that belong to either A or B (or both).
  • The intersection of A and B, denoted A\bigcap{B}, is the set of all x that belong to both A and B.
  • The difference of A and B, denoted A\backslash B or A-B, is the set of all x\in A such that x\notin B.
    • In contexts where there is a set containing "everything," usually denoted U, the complement of A, denoted A^c, is U\backslash A.
  • The symmetric difference of A and B, denoted A\Delta B, is defined by A\Delta B=(A\backslash B)\bigcup{(B\backslash A)}.
  • A is a subset of B, denoted A\subseteq B, if and only if every element in A also belongs to B. In other words, when \forall x\in A:x\in B. A key property of these sets is that A=B if and only if A\subseteq B and B\subseteq A.
  • A is a proper subset of B, denoted A\subsetneq B, if and only if A\subseteq B and A \ne B. (We do not use the notation A\subset B, as the meaning is not always consistent.)
  • The cardinality of A, denoted \left|A\right|, is the number of elements in A.
    Examples
    • \left|\left\{1,2,3,4,5\right\}\right|=5
    • \left|\varnothing\right|=0
    • \left|\left\{\varnothing\right\}\right|=1
  • The power set of A, denoted P(A), is the set of all subsets of A.
    Examples
    • P(\varnothing)=\left\{\varnothing\right\}
    • P(\left\{x\right\})=\left\{\varnothing,\left\{x\right\}\right\}
    • P(\left\{x,y\right\})=\left\{\varnothing,\left\{x\right\},\left\{y\right\},\left\{x,y\right\}\right\}

Note that \left|P(A)\right|=2^{\left|A\right|}.

Ordered n-tuples are denoted (x_1,x_2,\ldots,x_n). For two ordered sets X=(x_1,x_2,\ldots,x_n) and Y=(y_1,y_2,\ldots,y_n), we have X=Y if and only if \forall i \in \mathbb{N}, 1 \le i \le n:x_i = y_i.

N-tuples can be defined in terms of sets. For example, the ordered pair \langle x,y\rangle  was defined by Kazimierz Kuratowski as \left(x,y\right):=\left\{\{x\},\{x,y\}\right\}. Now n-tuples are defined as

(x_1, x_2,\ldots, x_n)\ :=\ \{\langle 1,x_1\rangle ,\langle 2,x_2 \rangle ,\ldots,\langle n,x_n\rangle \}.

We now can use this notion of ordered pairs to discuss the Cartesian Product of two sets. The Cartesian Product of A and B, denoted A\otimes B, is the set of all possible ordered pairs where the first element comes from A and the second from B; that is,

A\otimes B=\left\{ (a,b)~\left| ~a\in A,~b\in B \right. \right\}.

Now that we have defined Cartesian Products, we can turn to the notions of binary relations and functions. We say a set R is a binary relation from A to B if R\subseteq A\otimes B. If (x,y)\in R, it is customary to write xRy. If R is a relation, then the set of all x which are in relation R with some y is called the domain of R, denoted domR. The set of all y such that, for some x, x is in relation R with y is called the range of R, denoted ranR. A binary relation F is called a function if every element x in its domain has exactly one element y in its range such that xFy. Also, if F is a function, the typical notation is F(x)=y instead of xFy.

There are a few special types of functions we should discuss. A function F:A\to B is said to be onto a set B, or a surjective function from A to B, if ranF=B. A function F is said to be one-to-one or injective if a_{1}\in \text{dom }F,~a_{2}\in \text{dom }F,\text{ and}~a_{1}\ne a_{2} implies F(a_{1})\ne F(a_{2}). A function that is both injective and surjective is called bijective.

Exercises[edit]

If you can successfully answer the following problems, you are ready to study topology! Please take the time to solve these problems.

  1. Prove that the empty set is a subset of every set.
  2. Consider the set A_n=(-n,n) for each n in the set of natural numbers. Does the union over all A_n (for n in the set of natural numbers) equal \mathbb R (the set of all real numbers)? Justify your answer.
  3. Using A_n from above, prove that no finite subset of A_n has the property that the union of this finite subset equals \mathbb R. Once you study topology, you will see that this constitutes a proof that \mathbb R is not compact.