Set Theory

Venn Diagram
Fields: Algebra, Number Theory, and Set Theory
Image Created By: Chengying Wang

Venn Diagram

At right is an example of a Venn diagram.
Some questions you might ask: What is contained in each colored area? What does the sign "∩" mean? What is a Venn diagram and what is it used for? Set theory can answer these questions.

Basic Description

Set theory is the study of sets (a term that we are going to define later). It is widely agreed that some knowledge of set theory is essential for people who want to study more advanced mathematics because many very complicated topics in modern mathematics are developed in terms of the notions of set theory.

Set theory has become a distinct branch of mathematics in its own right. Currently, there are four main research directions in set theory—inner models, independence proofs, large cardinals, and descriptive set theory.

The image you see on the right is a Venn diagram. Venn diagrams were devised by John Venn, a British philosopher and cleric, in 1880. They are often used to help people visualize elements, sets, and logical relationships. Items in each circle of a Venn diagram share certain common properties. For instance, in the main image, objects in the red circle share one characteristic, objects in the yellow circle share another, and those in the blue circle share a third. In many cases, circles in Venn diagrams overlap, which means that objects in the overlapping region share the properties of both circles. If three circles overlap, then objects in the overlapping area share the properties of all three circles.

History

Georg Cantor (1845-1918),a German mathematician

Set theory was founded in 1874 by Georg Cantor in his paper "On a Characteristic Property of All Real Algebraic Numbers", a work highly influenced by his friend Richard Dedekind. Though Cantorian set theory was initially opposed by many mathematicians led by Leopold Kronecker, Cantor continued his work and published a six part treatise on set theory from 1879 to 1884, in which he introduced well-ordered sets, ordinal numbers, multiplication and addition of transfinite numbers and various other mathematical concepts.

Around 1900, set theory brought another round of excitement because several paradoxes (contradictions, or antinomies) were discovered using set theory. In 1897, the first paradox was published by Cesare Burali-Forti, concerning the set of all ordinal numbers. In 1899, Cantor himself discovered another paradox which arises from the set of all sets. The most well-known paradox was found independently by Bertrand Russell and Ernst Zermelo in 1902. It is now called Russell's Paradox and its main idea is that the set of all sets that do not contain themselves has to be a member and not a member of itself at the same time.

In 1908, Ernst Zermelo published the first axiomatization of set theory. Later, in 1922, Abraham Fraenkel and others added the Axiom of Replacement to Zermelo's axioms, which led to the formation of Zermelo-Fraenkel set theory. The axioms will be introduced in A More Mathematical Explanation section.

What is a set?

A set is a collection, or ensemble, of objects. We call these objects elements, or members of the set. We can also say that they belong to that set. For example:

• In a library, all the books is a set, and each individual book is an element of this set.
• All the students in a school is a set.
• The English word "math" is a set of letters. "m", "a", "t", "h" are all elements of the set.

In set theory, we are mostly concerned with sets of mathematical objects. Therefore, we are not going to talk about sets of people or books much more, but focus on sets of numbers, functions, or sets.

Usually, we write a set by displaying its elements between two curly braces. For example, {1, 4, 6, 9} is a set whose elements are 1, 4, 6, 9. Note that the order in which the elements are written does not make the set different. In other words, {1, 4, 6, 9} and {6, 9, 1, 4} and {1, 6, 9, 4} all represent the same set.

Besides sets of numbers, we can also have sets of sets. For example, { {1, 2}, {2, 3} } is a set of two sets, namely {1, 2} and {2, 3}. Also, the elements of a set can be different types. For example, {1, 2, {1, 2} } is a set containing two numbers and one set.

It is important to point out the case where there is only one element in the set (e.g. {1}). The element 1 and the set {1} are different. We can understand this concept with an analogy: A library with only one book is different from a book.

Besides sets that only contain a single element, another special case is a set containing no objects. This set is called the empty set or the null set and is denoted Ø. There are several special symbols that mathematicians have agreed upon to represent certain sets:

• $\mathbb{N}$ denotes the set consisting of all natural numbers, which are 0,1,2,3,4...
• $\mathbb{Z}$ denotes the set consisting of all integers, which are ...-4,-3,-2,-1,0,1,2,3,...
• $\mathbb{Q}$ denotes the set consisting of all rational numbers
• $\mathbb{R}$ denotes the set consisting of all real numbers
• $\mathbb{C}$ denotes the set consisting of all complex numbers

If we want to write these letters by hand, add a small vertical bar to the left edge of the corresponding capital letter we normally write. For example, to represent real numbers, a little parallel bar would be written on the left side of the normal capital letter "R".

Some sets can also be written in the following form:

$\left\{x: (\text{statement involving } x) \right\}$

which means the set of x for which the statement involving x is true. For example,

$\left\{ x: x \text{ is an odd number} \right\} = \left\{...,-5,-3,-1,1,3,5,7...\right\}$

is the set of all odd numbers.

For a set A,

$\left\{x: x \in A \text{ and (statement involving } x) \right\}$ and

$\left\{ x \in A: (\text{statement involving } x) \right\}$

denote the same set, which is the set of elements in set A that satisfies the statement. (x ∈ A means the object x is in the set A. This notation is going to be explained down in the Basic Notations section.) For example,

$\left\{x \in \mathbb{R}: x^2 = 1 \right\} = \left\{x: x \in \mathbb{R} \text{ and } x^2 = 1 \right\} = \left\{-1,1\right\}$

is the set real numbers that satisfy the equation x² = 1.

We can also replace the colon with a vertical bar. For example, the sets above become:

$\left\{ x | x \text{ is odd} \right\} = \left\{...,-5,-3,-1,1,3,5,7...\right\}$

$\left\{x \in \mathbb{R} | x^2 = 1 \right\} = \left\{x | x \in \mathbb{R} \text{ and } x^2 = 1 \right\} = \left\{-1,1\right\}$

Basic Notations

Conventionally, sets are denoted by capital Roman letters and their elements denoted by small Roman letters.

Now, let A and B be sets and a be an object.

Notation	Read	Meaning	Equivalent Notation	Example
$a \in A$	a is an element of A, or a is in A"	a is an element of set A	$A \ni a$, read "A contains a (as an element)"	$1 \isin \left \{1,2,3,4 \right \}$
$a \notin A$	a is not an object of A, or a is not in A	a is not an element of set A	$a \not\ni A$, read "A does not contain a (as an element)"	$5 \notin \left \{1,2,3,4 \right \}$
$A \subseteq B$	A is contained in B	for every a, if a ∈ A then a ∈ B. In other words, every element of A is an element of B, but there can be elements that are in B but not in A	$B \supseteq A$, read "B contains A".	$\left \{1, 2, 3, 4\right \} \subseteq \left \{1,2,3,4,5,6\right \}$
$A \nsubseteq B$	A not contained in B	A is not contained in B. In other words, there exists an object that belongs to A but not to B.	$B \nsupseteq A$, read "B does not contain A".	$\left \{1,2,3,4\right \} \nsubseteq \left \{1,2,4,6\right \}$
$A = B$	A and B are equal	sets A and B consist of the same elements. Mathematically, a ∈ A implies a ∈ B; a ∈ B implies a ∈ A		$\left \{1,2,3,4 \right \} = \left \{1,2,3,4 \right \}$

Elementary Operations on Sets

In this section, we are going to define and discuss four set operations -- union, intersection, difference, and complement.

Union

---

Let A and B be two sets. The union of A and B is

$A \cup B = \left\{x: x \in A \text{ or } x \in B \right\}$

(Note that the word "or" used above is different from ordinary language. In everyday life, "or" is often exclusive: "A or B" would mean "A or B but not both". However, in mathematics, "A or B" always means "A or B or both A and B".) Therefore, A ∪ B is the set of all objects which are elements of at least one of the sets A and B. The notation is read "A union B".

In the Venn diagram on the right, the two circles represent sets A and B and the shaded part is the union of A and B.

Here are some examples:

$\left\{1,3\right\} \cup \left\{2,4\right\} = \left\{1,2,3,4\right\}$

$\left\{1,5\right\} \cup \left\{2,6,8\right\} = \left\{1,2,5,6,8\right\}$

$\left\{1,3\right\} \cup \left\{ \left\{1,3\right\} \right\} = \left\{1,3, \left\{1,3\right\}\right\}$

Intersection

---

Let A and B be two sets. The intersection of A and B is

$A \cap B = \left\{x: x \in A \text{ and } x \in B \right\}$

That is, A ∩ B is the set of all objects that are in both set A and set B. The notation is read "A intersection B".

We can use a Venn diagram to illustrate this concept. In the image on the right, set A is the blue circle and set B is the red one. The green part is where the two circles overlay, and it is A ∩ B.

Here are some examples:

$\left\{1,2,3\right\} \cap \left\{2,3,5\right\} = \left\{2,3\right\}$

$\left\{1,5,8\right\} \cap \left\{3,9\right\} = \varnothing$

$\left\{ \left\{1,2\right\}, \left\{1,3\right\} \right\} \cap \left\{ \left\{1,2\right\}, \left\{2,3\right\} \right\} = \left\{ \left\{1,2\right\} \right\}$

Difference

---

Let A and B be two sets. The difference of A and B is

$A-B=\left\{x: x \in A \text{ and } x \notin B \right\}$

In words, A – B is the set of all objects that belong to set A but not to set B.

The symmetric difference of A and B is

$A \Delta B = (A-B) \cup (B-A)$

In words, A Δ B is the set of all objects that do not belong to both sets A and B. In the image on the right, the blue region is the symmetric difference.

Complement

---

Let A, S be two sets and A ⊆ S. The complement of A in S is

$\mathbf{C}_SA = \left\{ x \in S: x \notin A \right\}$

In words, C_SA is the set of all elements of S that are not in set A. The notation can also be called the complement of A with respect to S.

If S is explicitly stated, or very clear from the context, we can write CA instead and call it the complement of A.

In the Venn Diagram on the right, the rectangle represents set S and the white circle represents set A. The complement of A is the shaded region.

Some Properties About These Operations

---

Union and intersection are commutative:

$A \cup B = B \cup A$

$A \cap B = B \cap A$

Union and intersection are associative:

$A \cup (B \cup C) = (A \cup B) \cup C$

$A \cap (B \cap C) = (A \cap B) \cup C$

Union and intersection are distributive:

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

Besides the commutative, associative and distributive properties, we also have

$\mathbf{C}(A \cup B) = (\mathbf{C}A) \cap (\mathbf{C}B)$

$\mathbf{C}(A \cap B) = (\mathbf{C}A) \cup (\mathbf{C}B)$

$C - (A \cap B) = (C-A) \cup (C-B)$

$C - (A \cup B) = (C-A) \cap (C-B)$

We are not going to prove these properties here. You can visualize them through Venn diagrams, or try to prove them on your own as a good exercise. Also, there are many more properties and laws about operations on sets that we did not introduce in this page.

A More Mathematical Explanation

[Click to view A More Mathematical Explanation]

As described above, set theory provides a foundation for more advanced mathematics. After explaining [...]

[Click to hide A More Mathematical Explanation]

As described above, set theory provides a foundation for more advanced mathematics. After explaining the axioms, we will show how various mathematical concepts can be represented by sets, namely

• Orders where we will also introduce the another operation on sets -- the Cartesian product
• Functions and the relevant terms
• Natural Numbers, Cardinal Numbers, and Ordinal Numbers
• Finite, Infinite, Countable, and Uncountable Sets.

The Axioms

Russell's Paradox and various other similar examples tell us that defining a set does not mean the set actually exists. Sometimes, it is impossible to put all the objects that possess a certain property into one set, and so far, set theorists have not found a complete criteria for determining which properties can define sets without contradictions. Therefore, they decide to use some simple and intuitively true properties of sets as axioms and develop theorems that follow the axioms logically. Axiomatic set theory serves as a foundation for other branches of mathematics since practically all mathematical notions and properties can be defined and derived in this axiomatic system.

• The Axiom of Existence: There exists a set which has no elements.
• The Axiom of Extensionality: If every element of set A is an element of set B, and every element of B is an element of A, then A=B.

This axiom can be used to prove that there only exists one empty set. Here is the proof: [show more][hide]

Assume A and B are both sets that have no elements. Because A has no elements, any statement about elements of set A is automatically correct. Similarly, B being an empty set means that every element of B is an element of A. By the Axiom of Extensionality, A=B. This proves the uniqueness of empty set.

• The Axiom (Schema) of Restricted Comprehension: Let P(x) be a property of x. For any set A, there is a set B such that x ∈ B if and only if x ∈ A and satisfies P(x).

This set B is unique. See the proof here: [show more][hide]

Here is the proof for the uniqueness of set B:

If set B′ is another set such that x ∈ B if and only if x ∈ A and satisfies P(x), then x ∈ B if and only if x ∈ B′. Therefore, according to the Axiom of Extensionality, B=B′.

• The Axiom of Pair: For any sets A and B, there is a set C such that x ∈ C if and only if x = A or x = B.

This means that set C has exactly A and B as its elements. This is called the unordered pair of A and B and is denoted as {A, B}. If A = A, we write {A} instead of {A, A}. For example, if A = B = {Ø}, then {Ø} = {Ø, Ø} is a set whose only element is Ø. Note that {Ø} ≠ Ø because Ø ∈ {Ø}, but Ø ∉ Ø.

• The Axiom of Union: For any set S, there exists a set U such that x ∈ U if and only if x ∈ A for some A ∈ S.

The set U is called the union of S and denoted by ∪S. We can stress the fact that the elements of S are sets by calling S a collection of sets. (Strictly speaking, all objects are sets. Numbers can be considered as sets as well. We will see why in the section about natural numbers.)

For example, let S={1, {1}, {1, 2} }. In this case, the set A in the axiom could be 1, {1}, and {1, 2}. Therefore, x ∈ ∪S if and only if x ∈ 1 or x ∈ {1} or x ∈ {1, 2}. Thus, ∪S = {1, 2}.

Instead of only having set S, we can have two sets A and B, and x ∈ ∪{A, B} if and only if x ∈ A or x ∈ B. ∪{A, B} is more commonly written as A ∪ B. (See Elementary Operations on Sets for examples).

• The Axiom of Power Set: For any set S, there exists a set P such that X ∈ P if and only if X ⊆ S.

The set of all the subsets of S (all the possible P) is called the power set of S and denoted $\mathcal{P}(S)$. For example,

$\mathcal{P}(\left\{1\right\}) = \left\{\varnothing, \left\{1\right\} \right\}$

$\mathcal{P}(\varnothing) = \left\{\varnothing \right\}$

$\mathcal{P}(\left\{1,2\right\})=\left\{\varnothing,\left\{1\right\},\left\{2\right\},\left\{1,2\right\} \right\}$

• The Axiom of Infinity: An inductive set exists.

The definition of inductive sets will be introduced in the Natural Numbers, Cardinal Numbers, and Ordinal Numbers section.

• The Axiom Schema of Replacement: Let P(x,y ) be a property such that for every x there is a unique y for which P(x,y ) holds. For every A there is a B such that for every x ∈ A there is y ∈ B for which P(x,y ) holds.
• The Axiom of Foundation: All sets are well-founded.
• The Axiom of Choice: Every system of sets has a choice function.

These axioms together constitute the Zermelo-Fraenkel set theory with Choice (ZFC). The last three axioms (the Axiom Schema of Replacement, the Axiom of Foundation, and the Axiom of Choice) are not going to be specifically explained in this page. If interested, you can refer to books on set theory (some of them can be found in the References section) or to the following Wikipedia webpages: Axiom Schema of Replacement,the Axiom of Foundation, and the Axiom of Choice.

Orders and the Cartesian Product

As mentioned previously in the Axiom of Pair, for objects a and b, {a,b} denotes the same set as {b,a}, and {a,b} is called unordered pair. However, in some cases, we want to be able to differentiate order. We can use (a,b ) to denote the ordered pair of a and b. a is the first coordinate of the pair, and b is the second coordinate. Thus, for objects a, b, c, and d, (a,b ) = (c,d ) if and only if a=c, b=d. In particular, (a,b ) ≠ (b,a ) unless a=b.
To satisfy the condition above, we can define (a,b ) in the following way:

$(a,b) = \left\{ \left\{a\right\}, \left\{a,b\right\} \right\}$

If a ≠ b, then we find the first coordinate in the first set({a}) by just taking element a, and the second coordinate in {a,b } by taking the other element. If a=b, then (a,a ) = {{a}, {a, a}} = {{a }, {a}} = { {a} } by the Axiom of Pair. There is only one element. In both cases, we can easily tell the order in which a and b is.

Does this definition satisfy the theorem (a,b ) = (c,d ) if and only if a=c, b=d? [show more][hide]

Theorem: (a,b ) = (c,d ) if and only if a=c, b=d First, let's prove the "if" part. If a=c, b=d, it is very obvious that (a,b )={{a}, {a, b}} = {{c}, {c, d}} = (c,d ).

To prove the "only if" part, assume (a,b ) = (c,d ), which means {{a}, {a, b}} = {{c}, {c, d}}.

• If a=b, (a,b ) = { {a} }. Therefore, {a} = {c} = {c, d}. Then we get a = b = c = d, which satisfies the theorem.
• If a ≠ b, either {a} = {c} or {a} = {c, d} must be true.

Suppose {a} = {c, d}, then a = c = d. As a result, (c,d ) = { {a} }, which means the (a,b ) has to equal { {a} } as well. This contradicts a ≠ b.

If {a} = {c}, then a=c. We would have {a, b} = {c, d} next. This implies that b=d.

Through both cases, we can see that the theorem is satisfied.

With the concept of ordered pairs in mind, we can defined ordered triples

$(a,b,c) = ( (a,b),c )$

and ordered quadruples

$(a,b,c,d) = ((a,b,c),d)$

and so on.

Similar to ordered pairs, two ordered triples, quadruples or n-tuples are equal if and only if the corresponding coordinates are the same. For example, (a,b,c ) = (d,e,f ) if and only if a=d, b=e, and c=f.

Next, we can define the product of two sets, A × B, by

$A \times B = \left\{z: z = (x,y) \text{ with } x \in A \text{ and } y \in B \right\}$

Therefore, A × B is the set of all possible ordered pairs (x,y ) where x is in set A and y is in set B.

For example:

$\left\{1\right\} \times \left\{2\right\} = \left\{(1,2)\right\}$

$\left\{1,2\right\} \times \left\{2,3,4\right\} = \left\{(1,2),(1,3),(1,4),(2,2),(2,3),(2,4) \right\}$

$\left\{1,2,3\right\} \times \varnothing = \varnothing$

Functions

A function is an ordered triple f = (A,B,G) where

1. A,B,G are sets
2. G ⊆ A × B
3. for every x ∈ A there is exactly one y ∈ B such that (x,y ) ∈ G

Set A is called the domain of function f, sometimes written as dom f; set B is called the range of f, sometimes written as ran f; set G is called the graph of f. f is called a function from A to B. Sometimes, "mapping", "map" or "correspondence" is used instead of "function".

Let f = (A,B,G) be a function. Suppose we have an element x ∈ A. By the third condition, we can denote the unique y value f(x) and call it the value of f at x. Therefore, we have

$G=\left\{ (x,f(x)) | x \in A \right\}$

For example, let A = {1, 2, 3}, B = {2, 3}, G = A × B. We can tell that (A,B,G ) is not a function, because (2,2) and (2,3) are both in G. Thus, the y value such that (2,y ) ∈ G is not unique and it breaks the third rule.

On the other hand, let A = R, B = R and G = {(x,x² )|x ∈ R}, then (R, R, G) is a function, because for each x ∈ A, we have a unique x² ∈ B.

Let f and g be two functions and define

$f = (A',B',G')$ and $g = (A'',B'',G'')$

As explained in Orders and the Cartesian Product section, f = g if and only if X′ = X′′ and Y′ = Y′′ and G′ = G′′. Therefore, two functions are equal if and only if their domains, ranges and graphs are the same. Therefore, f = g if and only if f(x) = g(x) for all x ∈ A.

A function f = (A,B,G) can also be written as f : A → B. Here are some terms to describe types of functions:

• f is called onto or surjective if for every b ∈ B, there exists an a ∈ A such that b = f(a). In other words, each element of set B has a corresponding element in set A.
• f is called into or injective or one-to-one if different elements in A correspond to different elements in B. In other words, f(a₁) = f(a₂) only if a₁ = a₂.
• f is called bijective or one-one onto or a one-one correspondence between A and B if it is both injective and bijective. For any set A, the identity function f : A → A given by f(x) = x is bijective.

We can visualize these terms in the following way: Suppose we have function f : A → B. In the images below, the arrows represent correspondence between elements from sets A and B.

Bijective	Not surjective, since b1 does not have a corresponding element in set A	Not injective, since a3 and a4 both correspond to b3

Natural Numbers, Cardinal Numbers, and Ordinal Numbers

Natural Numbers

---

Intuitively, we know the natural numbers are 0,1,2,3,... In set theory, natural numbers can be defined in the following way:

First, we define 0 = Ø, the only set that has no elements.

Since 0 is defined, we can choose {0} as the representative of sets that have one element. So we can define 1 = {0} = {Ø}

Since 0 and 1 are defined and 0 ≠ 1, we can define 2 = {0,1} = {Ø,{Ø} }

As this process continues, we have

$3 = \left\{0,1,2\right\} = \left\{ \varnothing, \left\{\varnothing\right\},\left\{\varnothing, \left\{\varnothing\right\}\right\} \right\}$

$4 = \left\{0,1,2,3\right\} = \left\{ \varnothing, \left\{\varnothing\right\},\left\{\varnothing, \left\{\varnothing\right\}\right\},\left\{\varnothing, \left\{\varnothing\right\},\left\{\varnothing, \left\{\varnothing\right\}\right\}\right\} \right\}$

As shown above, we can define a natural number n as the set of all the natural numbers that are smaller than n: n = {0, 1, 2, ..., n – 1}.

However, this way of defining natural numbers is not perfect, because the general definition above (a natural number n is the set of all the natural numbers that are smaller than n) uses the concept of natural numbers to define natural numbers. Is there a more rigorous way to define natural numbers?

After defining 2 = {0,1}, we can get 3 by adjoining 2 itself to the set {2}:

$3 = 2 \cup \left\{2\right\} = \left\{0,1\right\} \cup \left\{2\right\}$

Similarly,

$4 = 3 \cup \left\{3\right\} = \left\{0,1,2\right\} \cup \left\{3\right\}$

$5 = 4 \cup \left\{4\right\} = \left\{0,1,2,3\right\} \cup \left\{4\right\}$

We define the successor of a set n as the set S(n)=n ∪ {n}. Given a natural number n, its successor, S(n), or n+1, is also a natural number. Starting at 0, if we take the successor repeatedly (0, 0+1=1,1+1=2,2+1=3,etc.) we can get all the natural numbers.

For a set I, if

1. 0 ∈ I
2. if n∈ I, then (n+1) ∈ I

then, it is called inductive.

We can easily see that the set of natural numbers fits the properties above. It is an inductive set that contains nothing other than the natural numbers. Therefore, we call this set the smallest inductive set. Then, we can define the set of natural numbers in the following way:

$\mathbb{N} = \left\{x | x \in I \text{ for every inductive set } I \right\}$

In other words, a number is a natural number if and only if it is a member of every inductive set.

As we mentioned above, being able to define a set does not mean such a set exists. How do we prove that N exists? [show more][hide]

To prove the existence of N, we can have an inductive set A, and by the Axiom of ComprehensionLet P(x) be a property of x. For any set A, there is a set B such that x ∈ B if and only if x ∈ A and satisfy P(x). (The Axioms section), it is easy to see that there exists a subset of A that fits the property x ∈ I for every inductive set I. Lastly, since the Axiom of Infinity tells us that an inductive set exists, the existence of set A is proved. Therefore, we conclude the set N exists.

Cardinal Numbers

---

Let A and B be two sets. We say the two sets are equipotent (or have the same cardinalityThe cardinality, or cardinal number, of a set is the number of elements in the set. It is usually represented by putting a vertical bar on each side of the set. For example, the cardinality of set A is |A|) if there exists a bijection f: A → B. For example,

A = {1, 2, 3} and B = {3, 9, 12}. Define f: A → B by f (1) = 3, f (2) = 9, and f (3) = 12. Then, function f is a one-one correspondence between set A and set B. Therefore, A and B are equipotent. (This concept is related to Equivalence Relation)

Below are some basic theorems about equipotent sets:

• A is equipotent to A.
• If A is equipotent to B, then B is equipotent to A.
• If A and B are equipotent and B and C are equipotent, then A and C are equipotent.

Ordinal Numbers

---

One very important usage of the natural numbers is to count. Now, imagine we have an infinite number ω that is bigger than all the natural numbers and continues the counting process into transfinite. "Transfinite" means that the number is greater than all finite numbers, but not absolutely infinite . After ω there comes ω+1, (ω+1)+1, and so on. These numbers are called ordinal numbers. They can be considered the generalization of natural numbers, therefore sharing many properties of natural numbers.

Similar to how we approached the definition of natural numbers, we can define the least transfinite number, ω as the set of all natural numbers:

$\omega = \mathbb{N} = \left\{0,1,2,3,...\right\}$

Then, the successor of ω and its successor can be produced in the following way:

$S(\omega) = \omega \cup \left\{\omega\right\} = \left\{0,1,2,3,...,\omega\right\}$

$S(S(\omega))=S(\omega) \cup \left\{S(\omega)\right\} = \left\{0,1,2,3,...,\omega,S(\omega)\right\}$

We can use the notation ω+1 to represent S(ω) and ω+2 to represent S(S(ω)) and so on. In this way, we can generate more and more ordinal numbers.

Ordinal numbers are representatives of all well-ordered sets since every well-ordered set is isomorphic to an ordinal number. Therefore, ordinal numbers can be considered order types of well-ordered sets. We did not introduce the concept of orderings, or well-ordered sets in this page. Thus, we are not going to expand any more on this topic. If you are interested in learning more about ordinal numbers, you can refer to the Wikipedia page on ordinal numbers or set theory books (some of them are listed in the References section).

Finite, Infinite, Countable, and Uncountable Sets

A set A is finite if A = Ø or it is equipotent to {1, 2, 3,..., p} where p ∈ N. In other words, A is finite if it is equipotent to some natural number. If |A |=n ∈ N, we can say set A has n elements. Set A is infinite if it is not finite. Though we will not go through the proofs, here are some theorems and corollaries related to what we introduced in this page:

• If set A is finite and set B ⊆ A, then B is also finite and |B | ≤ |A |.
• If sets A and B are finite, so is A ∪ B. In addition, |A ∪ B | ≤ |A | + |B |.
• If A is a finite set, its power set is also finite.
• If A is infinite, then |A | ≥ n for all n ∈ N

...

A set S is countable if |S | = |N |. S is at most countable if |S | ≤ |N |. Therefore, a set S is countable if there is a one-one correspondence between N and S. Here are some theorems:

• An infinite subset of a countable set is countable.
• A set is at most countable if and only if it is either finite or countable.
• The union of two countable sets are countable.

...

Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.

References

Many of the mathematical definitions, theorems and explanations come from the following books:
Hrbacek, K., Jech T. (1999). Introduction to Set Theory (Third Edition, Revised and Expanded). Taylor & Francis Group. ISBN 978-0-8247-7915-3
Fairchild, W.W., Ionescu Tulcea, C. (1970). Sets. W. B. Saunders Company.
Rosenlicht M. (1968). Introduction to Analysis. Dover Publications, INC. ISBN 0-486-65038-3.

Future Directions for this Page

• Expand more on orders and relations: introduce terms such as reflexive, symmetric, transitive, equivalence, modulo, and etc; define ≤ orderings, linear orderings, well-ordered sets, and etc.
• Explain what ordinal numbers are after defining well-ordered types and give examples.
• I find the book by Hrbacek, K., Jech T. very useful for this page. The order this page introduces concepts is highly influenced by the book. I strongly recommend it to future editors of this page.
• If possible, add more images?
  

---

If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.