Georg Cantor devoted much of his mathematical career to the development
of a new branch of mathematics, namely, Set Theory. Little did he know that
his pioneering work would eventually lead to a unifying theory for
mathematics. In his earlier work, Cantor took a set of real numbers 
and
then formed the derived set 
of all limit points of 
. After iterating this
operation, Cantor obtained further derived sets 
, 
. These
derived sets enabled him to prove an important theorem on trigonometric
series. This work led Cantor to investigate sets in a more general setting and
to develop an abstract theory of sets that would dramatically change the
course of mathematics.
The basic concepts in set theory are now applied in virtually every branch of mathematics. Furthermore, set theory serves as the basis for the definition and explanation of the most fundamental mathematical concepts: functions, relations, algebraic structures, function spaces, etc. Thus, it is often said that set theory provides a foundation for mathematics.
The set concept is one that pervades all of mathematics. We shall not attempt to give a precise definition of a set; however, we will give an informal description of a set and identify some important properties of sets.
A set is a collection of objects. The objects in such a collection are called
the elements of the set. We write 
to assert that 
is an element,
or a member, of the set 
. We write 
when 
is not an
element of the set 
. A set is merely the result of collecting objects of
interest, and it is usually identified by enclosing its elements with braces
(curly brackets). For example, the collection 
is
a set that contains the four elements 
. So 
, and
.
Sets are exceedingly important in mathematics; in fact, most mathematical objects (e.g., numbers, functions) can be defined in terms of sets. When one first learns about sets, it appears that one can naively define a set to be any collection of objects. In Section 1.4, we will see that such a naive approach can create serious problems.
Certain sets routinely appear in mathematics. In particular, the sets of natural numbers, integers, rational, and real numbers are regularly discussed. These sets are usually denoted by:
is the set of natural numbers.
is the set of integers.
is the set of rational numbers. Thus, 
.
is the set of real numbers, and so 
.In this section, we discuss the basic notation and concepts that are used in
set theory. An object 
may or may not belong to a given set 
; that is,
either 
or 
, but not both.
and 
be sets. We write 
when both sets have exactly
the same elements.
and 
we write 
to mean that the set 
is a
subset of the set 
, that is, every element of 
is also an element
of 
.
is a proper subset of the set 
, denoted
by 
, when 
and 
, that is, when every element
of 
is an element of 
but there is at least one element in 
that is not in 
.
for the empty set, or the null set. The set 
has no
elements.
and 
are disjoint if they have no elements in
common.It follows that 
and 
, for any set 
. To see why 
,
suppose that 
. Then there exists an 
such that 
. As
there is no 
such that 
, we arrive at a contradiction. Therefore, we
must have that 
.
A Venn diagram is a configuration of geometric shapes, which is commonly used to depict a particular relationship that holds between two or more sets. In Figure 1.1(a), we present a Venn diagram that illustrates the subset relation. Figure 1.1(b) portrays two sets that are disjoint.
A property is a statement that asserts something about one or more
variables (for more detail, see Section 1.3). For example, the two statements
“
is a real number” and “
and 
” are clearly properties that
assert something, respectively, about 
and 
. One way to construct a
subset is called the method of separation. Let 
be a set. Given a property
about the variable 
, one can construct the set of objects
that satisfy the property 
; namely, we can form the
truth set 
. Thus, we can separate the elements in 
that satisfy the property from those elements that do not satisfy the
property.
Solution. 
, 
, and
. 
An interval is a set consisting of all the real numbers that lie between two
given real numbers 
and 
, where 
:
is defined to be
.
is defined to be
.
is defined to be
.
is defined to be
.For each real number 
, we can also define intervals called rays or
half-lines:
is defined to be 
.
is defined to be 
.
is defined to be 
.
is defined to be 
.The symbol 
denotes “infinity” and this symbol does not represent a
number. The notation 
is often used to represent an interval “without a
right endpoint.” Similarly, the mathematical notation 
is used to
denote an interval “having no left endpoint.”
be a set. The power set of 
, denoted by
, is the set whose elements are all of the subsets of 
. That is,
.
Thus, 
if and only if 
. If 
is a finite set with 
elements, then one can show that the set 
has 
elements. The set
has three elements, and so 
has eight elements, namely,
For a pair of sets 
and 
, there are three fundamental operations that
we can perform on these sets. The union operation unites, into one set, the
elements that belong either to 
or to 
. The intersection operation
forms the set of elements that belong both to 
and to 
. The difference
between 
and 
(in that order) is the set of all elements that are in 
and not in 
.
and 
, we can build new sets using the
following set operations:
is the intersection of 
and
.
is the set difference of 
and
(also stated in English as 
“minus” 
).The set operations in Definition 1.1.3 are illustrated in Figures 1.2(a),
1.2(b), and 1.2(c). Shading is used to identify the result of a particular set
operation. For example, in Figure 1.2(c) the shaded area represents the set
.
When the elements of sets 
and 
are clearly presented, then
one can easily evaluate the operations of union, intersection, and
difference.
Let 
, 
, and 
be sets.
and 
, show that 
.
, then 
.
. Show that 
.
and 
. Show that 
.
and 
. Show that 
.
and 
, then 
.
be the property 
. Are the assertions 
,
, 
, 
true or false?
.
.
.
.
.
.
.Exercise Notes: For Exercise 6, 
means that 
or
.
Before introducing the fundamentals of set theory, it will be useful to identify some relevant aspects of language and logic. The importance of correct logical notation to set theory, and to mathematics, cannot be overstated. Formal logical notation has one important advantage: statements can be expressed much more concisely and much more precisely. Set theory often expresses many of its important concepts using logical notation. With this in mind, we now discuss the basics of logic.
A proposition is a declarative sentence that is either true or false, but not
both. When discussing the logic of propositional statements, we shall use
symbols to represent these statements. Capital letters, for instance, 
, 
,
, are used to symbolize propositional statements and are called
propositional components. Using the five logical connectives 
together with the components, we can form new logical sentences called
compound sentences. For example,
(means “
and 
” and is called conjunction).
(means “
or 
” and is called disjunction).
(means “not 
” and is called negation).
(means “if 
, then 
” and is called a conditional).
(means “
if and only if 
” and is called a biconditional).Using propositional components as building blocks and the logical connectives
as mortar, we can construct more complex compound sentences, for example,
. Parentheses ensure that our compound sentences
will be clear and readable; however, we shall be using the following
conventions:
to denote 
.
to denote 
.The truth value of a compound sentence in propositional logic can
be evaluated from the truth values of its components. The logical
connectives 
, 
, 
, 
, and 
yield the natural truth values
given in Table 1.1, where 
means “true” and 
means “false.”
Table 1.1(1) has four rows (not including the header). The columns
beneath 
and 
list all the possible pairs of truth values that can be
assigned to the components 
and 
. For each such pair, the
corresponding truth value for 
appears to the right. For example,
consider the third pair of truth values in this table, 
. Thus, if the
propositional components 
and 
are assigned the respective
truth values 
and 
, we see that the truth value of 
is
.
Table 1.1(2) shows that if 
and 
are assigned the respective truth
values 
and 
, then the truth value of 
is 
. Moreover, when
and 
are assigned the truth values 
and 
, then the truth value of
is also 
. In mathematics, the connective “or” has the same
meaning as “and/or”; that is, 
is true if and only if either 
is true or 
is true, or both 
and 
are true. Table 1.1(3)
shows that the negation of a statement reverses the truth value of the
statement.
Table 1.1(4) states that when 
and 
are assigned the respective
truth values 
and 
, then the truth value of 
is 
; otherwise,
it is 
. In particular, when 
is false, we shall say that 
is
vacuously true. Table 1.1(5) shows that 
is true when 
and 
are assigned the same truth value; when 
and 
have different truth
values, then the biconditional is false.
Using the truth tables for the sentences 
, 
, 
, 
,
and 
, we will now discuss how to build truth tables for more
complicated compound sentences. Given a compound sentence, we identify
the “outside” connective to be the “last connective that one needs to
evaluate.” Once the outside connective has been identified, one can break up
the sentence into its “parts.” For example, in the compound sentence
we see that 
is the outside connective with two parts 
and 
.
Solution. The components 
and 
will each need a column in our
truth table. Since there are two components, there are four possible
combinations of truth values for 
and 
. We will enter these
combinations in the two left most columns in the same order as that
in Table 1.1(1). The outside connective of the propositional sentence
is 
. We can break this sentence into the two parts
and 
. So these parts will also need a column in our truth
table. As we can break the sentences 
and 
only into
components (namely, 
and 
), we obtain the following truth table:
We will describe in steps how one obtains the truth values in the above
table. STEP 1: Specify all of the truth values that can be assigned to
the components. STEP 2: In each row, use the truth value assigned to
the component 
to obtain the corresponding truth value for 
,
using Table 1.1(3). STEP 3: In each row, use the truth values assigned
to 
and 
to determine the corresponding truth value in the column
under 
via Table 1.1(1). STEP 4: In each row, use the truth
values in the columns under 
and 
to evaluate the matching
truth value for the final column under the sentence 
,
employing Table 1.1(4). 
After constructing a truth table for a compound sentence, suppose that every entry in the final column is true. The sentence is thus true no matter what truth values are assigned to its components. Such a sentence is called a tautology.
Definition 1.2.1. A compound sentence is a tautology when its truth value is true regardless of the truth values of its components.
So a compound sentence is a tautology if it is always true. One can clearly
see from the following truth table that the sentence 
is a tautology:
Definition 1.2.2. A compound sentence is a contradiction when its truth value is false regardless of the truth values of its components.
Therefore, a compound sentence is a contradiction if it is always false. One
can easily show that the sentence 
is a contradiction.
A propositional sentence is either a compound sentence or just a component.
The next definition describes when two propositional sentences are logically
equivalent, that is, when they mean the same thing. Mathematicians
frequently take advantage of logical equivalence to simplify their proofs, and
we shall do the same in this book. In this section, we will use Greek letters
(e.g., 
, 
, 
, and 
; see page xiii) to represent propositional
sentences.
Definition 1.2.3. Let 
and 
be propositional sentences. We will say
that 
and 
are logically equivalent, denoted by 
,
whenever the following holds: For every truth assignment applied to the
components of 
and 
, the resulting truth values of 
and 
are
identical.
Solution. After constructing truth tables for the two statements 
and 
, we obtain the following:
 |  |
As the final columns in the truth tables for 
and 
are
identical, we can conclude from Definition 1.2.3 that they are logically
equivalent. 
Whenever 
and 
are logically equivalent, we shall say that 
is a logic law. We will now present two important logic laws that are often
used in mathematical proofs. These laws were first identified by Augustus De
Morgan.
.
.Let 
and 
be propositional sentences. If one can apply a truth
assignment to the components of 
and 
such that the resulting truth
values of 
and 
disagree, then 
and 
are not logically equivalent.
We will use this fact in our next problem, which shows that the placement of
parentheses in a compound sentence is very important. Note: A regrouping
can change the meaning of the sentence.
Solution. We shall use the truth table
 |
Since their final columns are not identical, we conclude that the propositional
sentences 
and 
are not equivalent. 
If a propositional component appears in a logic law and each occurrence of this component is replaced with a specific propositional sentence, then the result is also a logic law. Thus, in the above De Morgan’s Law
if we replace 
and 
, respectively, with propositional sentences 
and
, then we obtain the logic law
which is also referred to as De Morgan’s Law.
Listed below are some important laws of logic, where 
, 
, and 
represent any propositional sentences. These particular logic laws are
frequently applied in mathematical proofs. They will also allow us to derive
theorems concerning certain set operations.
.
.Commutative Laws
.
.Associative Laws
.
.Idempotent Laws
.
.Distributive Laws
.
.
.
.Double Negation Law (DNL)
.Tautology Law
.Contradiction Law
.Conditional Laws (CL)
Contrapositive Law
.Biconditional Law
.The Tautology Law and Contradiction Law can be easily illustrated. Observe
that 
is a tautology. From the Tautology Law we obtain the following
logical equivalence: 
. On the other hand, because 
is
a contradiction, it follows that 
by the Contradiction
Law.
Let 
and 
be two propositional sentences that are logically
equivalent. Now, suppose that 
appears in a given propositional sentence
. If we replace occurrences of 
in 
with 
, then the resulting
new sentence will be logically equivalent to 
. To illustrate this
substitution principle, suppose that we have the propositional sentence
and we also know that 
. Then we can conclude that
. Now, using this substitution principle and the
propositional logic laws, we will establish a new logic law without the use of
truth tables.
Solution. We first start with the more complicated side 
and derive the simpler side as follows:
Therefore, 
. 
Using a list of propositional components, say 
, and the
logical connectives 
, we can form a variety of propositional
sentences. For example,
The logical connectives are also used to tie together a variety of mathematical statements. A good understanding of these connectives and propositional logic will allow us to more easily understand and define set-theoretic concepts. The following problem and solution illustrate this observation.
.
.
, using logic laws.
, using logic laws.
.
and 
are not logically
equivalent.Variables, for instance, 
and 
, are used throughout mathematics to
represent unspecified values. They are employed when we are interested in
“properties” that may be true or false, depending on the values represented
by the variables. A predicate is simply a statement that proclaims that
certain variables satisfy a property. For example, “
is a number” is a
predicate, and we can symbolize this predicate by 
. Of course, the
truth or falsity of the expression 
can be determined only when a value
for 
is given. For example, the expression 
, which means “
is a
number,” is clearly true.
When our attention is to be focused on just the elements in a particular
set, we shall then refer to that set as our universe of discourse. For
example, if we were just talking about real numbers, then our universe of
discourse would be the set of real numbers 
. Furthermore, every statement
made in a specific universe of discourse applies to just the elements in that
universe.
Given a statement 
, which says something about the variable 
, we
often want to assert that every element 
in the universe of discourse
satisfies 
. Moreover, there will be times when we want to express the
fact that at least one element 
in the universe makes 
true. We will
thus form sentences using the quantifiers 
and 
. The quantifier 
means “for all” and is called the universal quantifier. The quantifier 
means “there exists,” and it is identified as the existential quantifier. For
example, we can form the sentences
[means “for all 
, 
”].
[means “there exists an 
such that 
”].Any statement of the form 
is called a universal statement. A
statement having the form 
is called an existential statement.
Quantifiers offer us a valuable tool for clear thinking in mathematics, where
many concepts begin with the expression “for every” or “there exists.” Of
course, the truth or falsity of a quantified statement depends on the universe
of discourse.
Suppose that a variable 
appears in an assertion 
. In the two
statements 
and 
, we say that 
is a bound variable
because 
is bound by a quantifier. In other words, when a variable in a
statement is immediately used by a quantifier, then that variable is
referred to as being a bound variable. If a variable in a statement is
not bound by a quantifier, then we shall say that the variable is a
free variable. When a variable is free, then substitution may take
place, that is, one can replace a free variable with any particular value
from the universe of discourse–perhaps 
or 
. For example, the
assertion 
has the one free variable 
. Therefore, we
can perform a substitution to obtain 
. In a given
context, if all of the free variables in a statement are replaced with
values, then one can determine the truth or falsity of the resulting
statement.
There are times in mathematics when one is required to prove that
there is exactly one value that satisfies a property. There is another
quantifier that is sometimes used, though not very often. It is called the
uniqueness quantifier. This quantifier is written as 
, and it means
that “there exists a unique 
satisfying 
.” This is in contrast
with 
, which simply means that “at least one 
satisfies
.”
As already noted, the quantifier 
is rarely used. One reason for this is
that the assertion 
can be expressed in terms of the other
quantifiers 
and 
. In particular, the statement 
is equivalent to
The above statement is equivalent to 
because it means that “there
is an 
such that 
holds, and any individuals 
and 
that satisfy
and 
must be the same individual.”
In addition to the quantifiers 
and 
, bounded set quantifiers are often
used when one wants to restrict a quantifier to a specific set of values.
For example, to state that every real number 
satisfies a property
, we can simply write 
. Similarly, to say that
some real number 
satisfies 
, we can write 
.
, we shall
write 
to mean that for every 
in 
, 
is true.
Similarly, we will write 
to signify that for some 
in 
,
is true.
The assertion 
means that for every 
, if 
, then
is true. Similarly, the statement 
means that there is
an 
such that 
and 
is true. Thus, we have the logical
equivalences:
.
.We now introduce logic laws that involve the negation of a quantified
assertion. Let 
be any predicate. The statement 
means that
“for every 
, 
is true.” Thus, the assertion 
means that “it
is not the case that every 
makes 
true.” Therefore, 
means there is an 
that does not make 
true, which can be expressed
as 
. This reasoning is reversible as we will now show. The
assertion 
means that “there is an 
that makes 
false.”
Hence, 
is not true for every 
; that is, 
. Therefore,
and 
are logically equivalent. Similar reasoning will
show that 
and 
are also equivalent. We now
formally state these important logic laws that connect quantifiers with
negation.
The above reasoning used to justify the quantifier negation laws can also
be used to verify two negation laws for bounded set quantifiers. Thus, given a
set 
and predicate 
, the following two logic laws show us how
statements of the form 
and 
interact with
negation. Notice that when you push the negation symbol through a
bounded set quantifier, the quantifier changes and the negation symbol
passes over “
.”
Bounded Quantifier Negation Laws 1.3.3. For every predicate 
, we
have the logical equivalences:
.
.Adjacent quantifiers have the form 
, 
, 
, and 
. In
this section, we will see how to interpret statements that contain adjacent
quantifiers. When a statement contains adjacent quantifiers, one should
address the quantifiers, one at a time, in the order in which they are
presented.
Problem 1. Let the universe of discourse be a group of people and
let 
mean “
likes 
.” What do the following formulas
mean?
.
.
Solution. Note that “
likes 
” also means that “
is liked by 
.”
We will now translate each of these formulas from “left to right” as
follows:
means “there is a person 
such that 
,”
that is, “there is a person 
who likes some person 
.” Therefore,
means that “someone likes someone.”
states that “there is a person 
such that 
,”
that is, “there is a person 
who is liked by some person 
.” Thus,
means that “someone is liked by someone.”Hence, the statements 
and 
mean the same
thing. 
Problem 2. Let the universe be a group of people and 
mean “
likes 
.” What do the following formulas mean in English?
.
.Solution. We will work again from “left to right” as follows:
means “for every person 
, we have that 
,”
that is, “for every person 
, we have that 
likes every person 
.”
Hence, 
means that “everyone likes everyone.”
So the statements 
and 
mean the same thing. 
Adjacent quantifiers of a different type are referred to as mixed quantifiers.
Problem 3. Let the universe be a group of people and 
mean “
likes 
.” What do the following mixed quantifier formulas mean in
English?
.
.Solution. We will translate the formulas as follows:
asserts that “for every person 
we have that
,” that is, “for every person 
there is a person 
such
that 
likes 
.” Thus, 
means that “everyone likes
someone.”
states that “there is a person 
such that 
,”
that is, “there is a person 
who is liked by every person 
.” In
other words, 
means “someone is liked by everyone.”We conclude that the mixed quantifier statements 
and
are not logically equivalent, that is, they do not mean the
same thing. 
To clarify the conclusion obtained in our solution of Problem 3, consider
the universe 
consisting of just four individuals with names
as given. For this universe, Figure 1.3 identifies a world where 
is true, where we portray the property 
using the “arrow notation”
. Figure 1.3 illustrates a world where there is an individual who
is very popular because everyone likes this person; that is, “someone is liked
by everyone.”
Figure 1.4 presents a slightly different world in which 
is
true. So, in this new world, “everyone likes someone.”
Let us focus our attention on Figure 1.4. Clearly, the statement
is true in the world depicted in this figure. Moreover, notice
that 
is actually false in this world. Thus, 
is true
and 
is false in the world presented in Figure 1.4. We can now
conclude that 
and 
do not mean the same
thing.
Our solution to Problem 1 shows that 
and 
both mean “someone likes someone.” This supports the true logical
equivalence:
Similarly, Problem 2 confirms the true logical equivalence:
Therefore, interchanging adjacent quantifiers of the same kind does
not change the meaning. Problem 3, however, verifies that the two
statements 
and 
are not logically equivalent. We
conclude this discussion with a summary of the above observations:
We offer another example, involving the real numbers, which shows that the interchange of mixed quantifiers can change the meaning of a statement.
Example 4. Let the universe of discourse be 
, the set of real numbers.
means that for every real number 
there is a
real number 
such that 
. We see that the sentence
is true.
states there is a 
such that 
.
This is false.
Quantifier Interchange Laws 1.3.4. For every predicate 
, the
following three statements are valid:
.
.
.We will be using the arrow 
as an abbreviation for the word “implies.”
The conditional connective 
shall be reserved for formal logical formulas.
It should be noted that the implication in item 3 cannot, in general, be
reversed.
The quantifier interchange laws also hold for bounded set quantifiers; for example, we have that
A quantifier can sometimes “distribute” over a particular logical connective.
The quantifier distribution laws, given below, capture relationships that hold
between a quantifier and the two logical connectives 
and 
. In
particular, the existential quantifier distributes over disjunction (see
1.3.5(1)), and the universal quantifier distributes over conjunction (see
1.3.6(1)). The following quantifier distribution laws can be useful when
proving certain set identities.
Existential Quantifier Distribution Laws 1.3.5. For any predicates 
and 
we have the following distribution laws:
.
.
.
.If 
is a statement that does not involve the variable 
, then we
have:
.
.
Universal Quantifier Distribution Laws 1.3.6. For any predicates 
and 
we have the following equivalences:
.
.
.If 
is a statement that does not involve the variable 
, then we
have:
.
.Cantor employed an informal approach in his development of set
theory. For example, Cantor regularly used the Comprehension
Principle: The collection of all objects that share a property forms a set.
Thus, given a property 
, the comprehension principle asserts
that the collection 
is a set. Using this principle, one can
construct the intersection of two sets 
and 
via the property
“
and 
”; namely, the intersection of 
and 
is the set
. Similarly, we can form the union of 
and 
to
be the set 
. In addition, we obtain the power set of 
,
denoted by 
, which is the set whose elements are all of the subsets of
; that is, 
. The comprehension principle
allowed Cantor to establish the existence of many important sets.
Today Cantor’s approach to set theory is referred to as naive set
theory.
Cantor’s set theory soon became an indispensable tool for the development of new mathematics. For example, using fundamental set theoretic concepts, the mathematicians Émile Borel, René-Louis Baire, and Henri Lebesgue in the early 1900s created modern measure theory and function theory. The work of these mathematicians (and others) demonstrated the great mathematical utility of set theory.
Relying on Cantor’s naive set theory, mathematicians discovered and
proved many significant theorems. Then a devastating contradiction was
announced by Bertrand Russell. This contradiction is now called Russell’s
paradox. Consider the property 
, where 
is understood to represent
a set. The comprehension principle would allow us to conclude that
is a set. Therefore,
Clearly, either 
or 
. Suppose 
. Then, as noted in 
,
must satisfy the property 
, which is a contradiction. Suppose
. Since 
satisfies 
, we infer from 
that 
, which
is also a contradiction.
Russell’s paradox thus threatened the very foundations of mathematics
and set theory. If one can deduce a contradiction from the comprehension
principle, then one can derive anything; in particular, one can prove that
. Cantor’s set theory is therefore inconsistent, and the validity of the
very important work of Borel and Lebesgue then became questionable. It
soon became clear that the comprehension principle needed to be restricted
in some way and the following question needed to be addressed: How can one
correctly construct a set?
Ernst Zermelo resolved the problems discovered with the comprehension principle by producing a collection of axioms for set theory. Shortly afterward, Abraham Fraenkel amended Zermelo’s axioms to obtain the Zermelo–Fraenkel axioms that have now become the accepted formulation of Cantor’s ideas about the nature of sets. In particular, these axioms will allow us to construct a power set and to form the intersection and union of two sets. These axioms also offer a highly versatile tool for exploring deeper topics in mathematics, such as infinity and the nature of infinite sets.
Before presenting the axioms of set theory, we must first describe a formal
language for set theory. This formal language involves the logical connectives
, 
, 
, 
, 
together with the quantifier symbols 
and 
. In
addition, this formal language uses the relation symbols 
and 
(also
and 
).
What is a formula in the language of set theory? An atomic formula is
one that has the form 
or 
, where 
can be replaced with
any other variables, say, 
. We say that 
is
a formula (in the language of set theory) if 
is an atomic formula, or it
can be constructed from atomic formulas by repeatedly applying the
following recursive rule: If 
and 
are formulas, then the next seven
items are also formulas:
Hence, 
is a formula in the language of set
theory because it can be constructed from the atomic formulas 
,
, 
and repeated applications of the above recursive rule.
Figure 1.5 illustrates this construction, where the statement 
is used
to abbreviate 
.
Formulas are viewed as “grammatically correct” statements in the
language of set theory. Moreover, the expression 
is not a formula
because it cannot be constructed from the atomic formulas and the above
recursive rule. In practice, we shall use parentheses so that our formulas are
clear and readable. We will also be using, for any formulas 
and 
, the
following three conventions:
to denote 
.
to denote 
.
We will also use symbols that are designed to make things easier to understand.
For example, we may write 
rather than 
.
Throughout the book, we will be using the notation 
to
identify 
as being free variables (see page 14) that appear in the
formula 
. If the variables 
are free, then substitution may take
place. Thus, we can replace all occurrences of 
, appearing in 
, with a
particular set 
and obtain 
. Moreover, a formula
may contain parameters, that is, free variables other than
that represent unspecified (arbitrary) sets. Parameters denote
“unassigned fixed sets.” For an example, let 
be the formula
So, 
has 
as an identified free variable, 
as a constant, and a
parameter 
(an unassigned set). To replace a parameter 
in a formula
with an specific set 
means that every occurrence of 
, in
, is replaced with 
.
We will now explore the expressive power of this set theoretic language.
For example, the formula 
asserts that the set 
is nonempty.
Moreover, 
states that “it is not the case that there is a set
that contains all sets as elements.” In addition, one can translate statements
in English, which concern sets, into the language of set theory. Consider
the English sentence “the set 
contains at least two elements.”
This sentence can be translated into the language of set theory by
.
Let 
be a formula with free variable 
and let 
be a set.
The sentence “there is a set 
whose members are just those 
’s
that satisfy 
and 
,” is represented by the formula
.
Let 
and 
be formulas. Now consider the relationship
This relationship can be translated into the language of set theory by
Let 
be the formula in (1.2). One can verify that 
holds if
and only if (1.1) holds. Note that for all 
there is a unique 
such that
.
say in English?
say in English?
say in English?
say in English?
say in English?
be a formula. What does 
assert?
is the union of 
and 
.
is not a subset of 
.
is the intersection of 
and 
.
and 
have no elements in common.
, 
, 
, and 
be sets. Show that the relationship
can be translated into the language of set theory.
The axiomatic approach to mathematics was pioneered by the Greeks well over 2000 years ago. The Greek mathematician Euclid formally introduced, in the Elements, an axiomatic system for proving theorems in plane geometry. Ever since Euclid’s success, mathematicians have developed a variety of axiomatic systems. The axiomatic method has now been applied in virtually every branch of mathematics. In this book, we will show how the axiomatic method can be applied to prove theorems in set theory.
We shall now present the Zermelo–Fraenkel axioms. Each of these
axioms is first stated in English and then written in logical form.
After the presentation, we will then discuss these axioms and some
of their consequences; however, throughout the book we shall more
carefully examine each of these axioms, beginning in Chapter 2. While
reading these axioms, keep in mind that in set theory everything is a
set, including the elements of a set. Also, recall that the notation
means that 
are free variables in the formula 
and
that 
is allowed to contain parameters (free variables other than
).
be a formula. For every set 
there is a
set 
that consists of all the elements 
such that 
holds.
2
and 
there is a set that consists of just 
and 
. 
there exists a set 
that consists
of all the elements that belong to at least one set in 
. 
there is a set 
that consists
of all the sets that are subsets of 
. 
that contains the empty set as an
element and whenever 
, then 
. 
be a formula. For every set 
,
if for each 
there is a unique 
such that 
, then there
is a set 
that consists of all the elements 
such that 
for
some 
. (See endnote 2.) 
has an element that is
disjoint from 
. 
The extensionality axiom simply states that two sets are equal if and only
if they have exactly the same elements (see Definition 1.1.1(1)). The empty
set axiom asserts that there exists a set with no elements. Since the
extensionality axiom implies that this set is unique, we let 
denote the
empty set.
The subset axiom proclaims that any definable subcollection of a set is
itself a set. In other words, whenever we have a formula 
and a set 
,
we can then conclude that 
is a set. Clearly, the subset axiom
is a restricted form of the comprehension principle, but it does not lead to
the contradiction that we encountered in Russell’s paradox. The subset
axiom, also called the axiom of separation (see page 3), is described as an
axiom schema, because it yields infinitely many axioms–one for each formula
. Similarly, the replacement axiom is also referred to as an axiom
schema.
The pairing axiom states that for any two given sets, there is a set
consisting of just those two sets. Therefore, for all sets 
and 
, the set
exists. Since 
, it follows that the set 
also exists
for each 
.
The union axiom asserts that for any set 
, there is a set 
whose
elements are precisely those elements that belong to at least one member of
. More specifically, the union axiom proclaims that the union of any set
exists; that is, there is a set 
so that 
if and only if
for some 
. As we will see, the set 
is denoted by
.
The infinity axiom declares that there is a set 
such that 
and
whenever 
, then 
. Since 
, we thus conclude
that 
. Now, as 
, we also have that
. Continuing in this manner, we see that the
set 
must contain all of the following sets:
Observe, by the extensionality axiom, that 
. One can also show
that any two of the sets in the above list are distinct. Therefore, the set 
contains an infinite number of elements; that is, 
is an infinite
set.
The replacement axiom plays a crucial role in modern set theory (see [8]).
Let 
be a set and let 
be a formula. Suppose that for each
, there is a unique 
such that 
. Thus, we shall say that 
is “uniquely connected” to 
. The replacement axiom can now be
interpreted as asserting the following: If for each 
there is an element
that is uniquely connected to 
, then we can replace each 
with
its unique connection 
and the result forms a new set. In the words of Paul
Halmos [7], “anything intelligent that one can do to the elements of a set
yields a set.”
Given any nonempty set 
, the regularity axiom asserts the 
for some 
. Can a set belong to itself? The regularity axiom rules out
this possibility (see Exercise 3).
The formulas in the subset and replacement axioms may contain
parameters. We will soon be proving theorems about formulas that may
possess parameters. Because parameters represent arbitrary sets, any
axiom/theorem that concerns a generic formula with parameters is
applicable whenever the parameters are replaced with identified sets.
As a result, such an axiom/theorem can be applied when a formula
contains fixed sets, as these sets can be viewed as ones that have
replaced parameters. For example, the subset axiom concerns a generic
formula 
. So this axiom can be applied when specific sets appear
in 
.
This completes our preliminary examination of the set-theoretic axioms that were first introduced by Ernst Zermelo and Abraham Fraenkel; however, we will more fully examine each of these axioms in the remainder of the book. Furthermore, before we make our first appeal to a particular axiom, it shall be reintroduced prior to its initial application. In addition, we will not invoke an axiom before its time; that is, if we are able to prove a theorem without appealing to a specific axiom, then we shall do so. Accordingly, we will not be using the regularity axiom to prove a theorem until the last section of Chapter 8.
It is a most remarkable fact that essentially all mathematical objects can be defined as sets. For example, the natural numbers and the real numbers can be constructed within set theory. Consequently, the theorems of mathematics can be viewed as statements about sets. These theorems can also be proven using the axioms of set theory. Thus, “mathematics can be embedded into set theory.”
, 
, and 
be sets. By the pairing axiom, the sets 
and 
exist. Using the pairing and union axioms, show that
the set 
exists.
3. Let 
be a set. The pairing axiom implies that the set 
exists.
Using the regularity axiom, show that 
. Conclude that
.
and 
, the set 
exists by the pairing axiom. Let
. Using the regularity axiom, show that 
,
and thus 
.
, 
, and 
be sets. Suppose that 
and 
.
Using the regularity axiom, show that 
. [Hint: Consider the
set 
.]
and 
be sets. Using the subset axiom, show that the set
exists.
9. Let 
be a set with no elements. Show that for all 
, we have
that 
if and only if 
. Using the extensionality axiom,
conclude that 
.
be the formula 
which asserts
that 
. As noted on page 25, for all 
the set 
exists. So 
. Let 
be a set. Show that the collection
is a set.
.
.
.
is the 
and
.
and 
. Then
and 
. 
and 
.
.
.
.
.
.
.
.
.
.
and 
are not logically equivalent.
.
.
, using
logic laws.
and 
be any two sets. Show that 
is
equivalent to the statement 
or 
.
as follows:
is equivalent to the assertion 
. 
.
.
, we have the
logical equivalences:
.
.
proclaims
, we have that
,” that is, “for each person 
, we have that 
is liked by
every person 
.” Thus, 
means “everyone is liked by
everyone.”
is true, since someone is
liked by everyone.
is true, because everyone
likes someone.
by the more readable 
.
be a set. Show that the pairing axiom implies that the set
exists. 
and 
be sets. Using the subset and power set axioms,
show that the set 
exists.
, 
, 
are equal to
each other.