Axioms of set theory: fast review

Reference: A Second Course in Analysis, M Ram Murty, Hindustan Book Agency.

Chapter 1 Background

Axioms of Set Theory

The concept of number lies at the heart of mathematics. The subject of mathematical analysis, in the formal sense of the word, began when mathematicians initiated the exploration of infinity as a precise mathematical idea. This perhaps is the greatest event of the nineteenth century, on par with the discovery of zero as a mathematical idea. Both zero and infinity are now essential to the understanding of limits and the related processes of real and complex analysis.

Because these two ideas were poorly understood, mathematicians in the nineteenth century introduced the axiomatic method with the theory of sets as the foundation for all mathematics. In this approach, Georg Cantor (1845-1918) was definitely the leading figure. Sadly, his work received considerable opposition at first, but is now universally accepted. It is not an exaggeration to say that research into the foundations of mathematics has given us a larger understanding of the nature of mathematical logic, both its strengths and limitations.

Set theory is the standard foundation of all mathematics. Mathematical proofs use set-theoretic ideas in one form or another. Below, we give a quick overview of the axioms of set theory so that the student is introduced to the relevant vocabulary. One need not become overly preoccupied with these formalities for otherwise a serious study of these axioms will take us into the realm of mathematical logic which is not the province of this short survey. Rather, we indicate the main themes, very much similar to a quick sight-seeing tour of an ancient city. There will undoubtedly be many side streets to explore and since time is of the essence, we need to be content with a one-hour tour highlighting the significant monuments. For a gentle introduction to mathematical logic, we refer the reader to the following text: Hilbert’s Tenth Problem, An introduction to logic, number theory and computing, Student Mathematical Library, Volume 88, American Mathematical Society, Providence, Rhode Island, 2019.

The basic objects of set theory are classes, some of which are sets. An informal definition of a set is an unordered collection of objects. The basic relationship between them is membership indicated by the symbol \epsilon. Thus, $x \in A$ means that x is a member of A. Its negation, x is not a member of A is written as $x \notin A$. Already, with the notion of a set and the relation of membership, we can easily run into logical contradictions if we do not formulate proper axioms for the construction of sets. The famous “Russell paradox” (named after the British philosopher and mathematician Bertrand Russell (1872-1970)) shows that the “set of all sets” is not a set. Indeed, if it were a set, it would be a proper member of itself by definition, which is a contradiction. The paradox is often posed as the following riddle: In the town of Seville lives a barber who shaves everyone who does not shave himself. Does the barber shave himself? The contradiction arises from self-reference and so it was quickly realized that to avoid logical contradictions in mathematics, one must formulate precise axioms for the construction of sets. In a formal system of axiomatic set theory, the notions of “class” and “\epsilon” are undefined terms. There are several well-developed axiomatic systems such as the Zermelo-Fraenkel system and the von Neumann-Godel-Bernays system. Our treatment below follows the latter.

The underlying idea of any these systems is that we construct new sets from old sets in a systematic manner, with the existence of the empty set as a basic axiom. This is how we avoid the Russell paradox.

The words “and” and “not’ are used as propositional connectives. We usually write these words out and do not use symbols for them, though some logicians do. To say that “Proposition P implies Proposition Q” we write “P \Longrightarrow Q“. If $P \Longrightarrow Q$ and $Q \Longrightarrow P$, we write P \Longleftrightarrow Q. The usual logical quantifiers are : \forall which means “for all” and \exists which means “there exists”. The first one is sometimes called the universal quantifier and the second one as the existential quantifier. The statement, “For all x, the proposition F(x) holds” is denoted $\forall (F(x))$ with the parentheses used to designate the proposition. Such a statement is called an existential proposition.Using class variables like x, y, A,B and so on, together with the basic relation of membership $\epsilon$, quantifiers, connectives and parentheses, we can construct “well-formed” formulas. If variables are quantified, they are called “bound” and should only appear after the quantifier. Variables without quantifiers are called “free”. For example,

\forall {x} \exists {y} ((x \in y) \Longrightarrow (x \in z))

is well-formed in which x and y are bound variables and z is free, whereas

\exists{x} ((x \in z) \Longrightarrow \forall{z}(z \in y))

is not well-formed since z precedes its quantifier.

As noted earlier, it is not our goal here to develop axiomatic set theory. On the other hand, the mature mathematician cannot ignore the need for foundations and must have some idea of the basic axioms and notation. So we content ourselves with a cursory overview of the basic axioms and set the stage for both notations and structure of logical proofs.

The essential idea of set theory is that sets are built up in a progressive hierarchy and there are precise rules as to how to form new sets from old sets. We begin with the axiom of extensionality which allows us to determine when two sets are equal.

Axiom I : (extensionality) For any classes A and B, A=B if and only if

\forall{x} (x \in A \Longleftrightarrow x \in B).

This axiom can be taken as the definition of equality.

Axiom 2: (existence of the empty set). There is a set \phi such that

\forall{x}(x \notin O)

The axiom of extensionality implies that the empty set \phi is unique.

Axiom 3: (unordered pairs) For all sets x, y there is a set (x,y) such that

u \in {x,y} \Longleftrightarrow (u =x \hspace{0.1in} or \hspace{0.1in} u=y)

If x=y we obtain the singleton \{ x\}, u \in \{ x \} if and only if u=x. Again this sets are unique by extensionality.

As defined earlier, a variable is free if there are no quantifiers defining it. Otherwise, the variable is said to be bounded. This concept isused in the next axiom and allows us to form new sets from old using well-formed formulas. In fact, the next axiom is more appropriately called an axiom schema or a collection of axioms.

Axiom 4: (selection): Given any well-formed formula P(x) containing one free variable x, there is a class A suchthat for any set x, we have $x \in A$ if and only if P(x) holds.

We often write

A = \{ x: P(x) \}

and read this as “A is the class of all (sets) x such that P(x) holds.”

The distinction between sets and classes in the last axiom is important as noted earlier. Without it, we fall into”Russell’s paradox.” Indeed, let R = \{x: x \notin x \}. If R were a set, then R \in R implies R \notin R and if R \notin R, then R \in R. a contradiction in both cases. Technically, R is not a set but a proper class containing all sets which we call the “universe” and the theory contains no logical contradictions. The previous axioms do allow us to construct new sets from old ones in a systematic manner. Thus, a set may consist of other sets that have already been well-defined.

Axiom 5 (union): For any set x, there is a set \bigcup {x} such that y \in \bigcup{x} if and only if y \in x for some x \in x.

We sometimes write \bigcup_{y \in x}y for \bigcup{x} in the last axiom. Thus,

x \bigcup y = \bigcup \{ x,y\} = \{ z: z \in x \hspace{0.1in} or \hspace{0.1in} z \in y\}.

For any well-formed formula Q(x) with a free variable x, (\forall x \in A)(Q(x)) means

(\forall x)(x \in A \Longrightarrow Q(x)).

The relation of A being a subset of B is defined by the symbol:

(\forall x \in A)(x \in B) and we write this as A \subset B, or equivalently B \supset A.

Axiom 6(power set axiom); For any set x, there is a set 2^{x} such that y \in 2^{x} if and only if y \in x.

The reader should understand that the symbol 2^{x}is pure symbology for the set of all subsets of x and that no exponentiation is meant since x is a set. It will always be clear from the context which meaning is indicated.

For any two classes A and B, we define the intersection as

A \bigcap B = \{ x: x \in A \hspace{0.1in}and \hspace{0.1in}x \in B\} .

If A is any set, then A \bigcap B is a set for any class B by Axiom 6 and the definition of a set. If x is a non-empty set, its intersection is defined by

\bigcap {x} = \{ y; (\forall u \in x) \Longrightarrow y \in u\}.

This is easily seen to be a set. We can also write \bigcap{x} as \bigcap_{y \in x}y.

We can use set theory to define an ordered pair (x,y) as the set of the form \{ \{ x\}, \{x.y\}\}.

Indeed, for any ordered pair Q, its first member is the unique x such that \{ x\} \in Q and its second member is the unique y such that Q = \{ \{x\}, \{ x,y\}\}, where x is the first member.

A relation is any set of ordered pairs. For any relation E, we define the inverse relation by

E^{-1} = \{ (y,x): (x,y) \in E\}.

From the definition of an ordered pair, we are led to the definition of a function as a set f of ordered pairs such that (x,y) \in f and (x,z) \in f implies y=z. We write f(x) =y to mean (x,y) \in f for any given function f. Thus, a function is a special kind of relation. In other words, all functions are relations, but not all relations are functions.

If f is a function, f^{-1} is not necessarily a function. A function f is called one-to-one if and only if f^{-1} is a function.

This now allows us to construct the Cartesian product of two sets X and Y denoted X \times Y, which consists of ordered pairs (x,y) with x \in X and y \in Y.

With the axioms listed so far, we cannot prove the existence of an infinite set. The next axiom allows us to do this along with our earlier axioms.

Axiom 7 (axiom of infinity) There is a set X \neq \phi such that for all x \in N, x \bigcup \{ x\} \in N.

This axiom allows us to construct the natural numbers using the empty set because we now define inductively the sequence of sets

\phi, \{ \phi\}, \{ \phi, \{ \phi\}\}, \ldots

and define the non-negative integers using the “zero-symbol” 0 to designate the empty set and define

1 = \{ \phi\}, 2 = \{ 0,1\}, 3=\{ 0,1,2\}, \ldots

We could also have stated Axiom 7 in logical notation as \exists {N} such that \phi \in N and \forall{x}\in N,

x \bigcup \{ x\} \in N

To prevent x \bigcup {x} from being equal to x, and in general to keep order among sets and prevent unwanted closed cycles for the membership relation, we need a further axiom:

Axiom 8: (axiom of regularity) For any set A \neq \phi, (\exists X \in A) X \bigcup A = \phi. This allows us to prove :

Theorem 1.1: for all x and y, x \notin x and if x \in y, then y \notin x.

Proof 1.1: by Axiom 8, x \bigcap \{ x\} = \phi since x \bigcap \{ x\} = x \bigcap_{y \in x}y. If x \in x, then clearly x \in x \bigcap \{ x\} which implies x \in \phi, a contradiction. This proves the first half of our assertion. For the second half, if x \in y, then by Axiom 8, the set \{ x,y\} has a member disjoint from it. This member cannot be x for otherwise x \in x, a contradiction by the first half of the theorem. If the member is y, then y\bigcap \{ x,y\}= \phi is also a contradiction since x \in y. QED.

Exercises:

  1. Recall that an ordered pair (a,b) can be defined as the set \{ \{ a\}, \{ a,b\}\}. Show that (a,b) = (c,d) if and only if a=c and b=d.

Solution 1: This is clear by definition of equality and definition of ordered pair.

2. Define the ordered triple (a,b,c) to be the ordered pair ((a,b),c) where the ordered pair is defined a usual. Show that

(a,b,c) = (a^{'}, b^{'}, c^{'}) if and only if a=a^{'}, b=b^{'}, c=c^{'}.

Solution: If (a,b,c) = (a^{'}, b^{'}, c^{'}), then by definition of triple,

((a,b), c) = ((a^{'}, b^{'}), c^{'}), which in turn by equality of ordered pairs means that

c = c^{'} and (a,b) = (a^{'}, b^{'}) that is ({a}, \{ a,b\})= (\{ a^{'}\}, \{ a^{'}. b^{'}\}) that is a=a^{'} and b=b^{'}.

3. If x \in y \in z \in w, prove that w \notin x.

Solution: x \in w need not mean w \in x unless w=x.

4. Which of the following are functions and why?

4. (a) ((1,2), (2,3), (3,1)). yes.

4. (b) ((1,2), (2,3), (2,1)). No.

4 (c). ((2,1),(3,1),(1,2)). yes.

4 (d) ((x,y) \in \Re^{2}: x = y^{2}). No.

4 (e) ((x,y) \in \Re^{2}: y = x^{2}). yes.

5. For any relation V (that is, any set of ordered pairs), define the domain of V as

\{ x: (x,y) \in V \hspace{0.1in} for \hspace{0.1in} some \hspace{0.1in} y\}

and the range of V as

\{ y: (x,y) \in V for some x\}

Find the domain and range for each relation in the previous question whether or not it is a function.

4a. Domain is (1,2,3), and same range.

4b. Domain is (1,2) and range is (1,2,3).

4c. Domain is (x: x \geq 0), range is y  \in \Re.

4d. Domain is (x: x \in \Re) and range is y \geq 0/

Cheers,

Nalin Pithwa

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.