. 76
( 107 .)


1. a © b
2. b © a
3. a ∪ b
4. b © c
5. b ∪ c
6. (a © b) ∪ c
7. a © (b ∪ c)

15.16 Give an informal proof of Proposi- 15.17 Use Fitch to give a formal proof of
tion 6.2. Proposition 6.2. You will ¬nd the prob-
lem set up in the ¬le Exercise 15.17. You
may use Taut Con, since a completely
formal proof would be quite tedious.

Chapter 15
Sets of sets / 419

15.18 Give an informal proof of Proposi- 15.19 Use Fitch to give a formal proof of
tion 6.4. Proposition 6.4. You will ¬nd the prob-
lem set up in the ¬le Exercise 15.19. You
may use Taut Con in your proof.

15.20 Give an informal proof of Proposi- 15.21 Give an informal proof of Proposi-
tion 6.5. tion 6.6.

15.22 Give an informal proof that for every set a there is a unique set c such that for all x, x ∈ c
 i¬ x ∈ a. This set c is called the absolute complement of a, and is denoted by a. (This result
will not follow from the axioms we eventually adopt. In fact, it will follow that no set has
an absolute complement.) If you were to formalize this proof, what instance of the Axiom of
Comprehension would you need? Write it out explicitly.

Section 15.4
Sets of sets

The Axiom of Comprehension applies quite generally. In particular, it allows
us to form sets of sets. For example, suppose we form the sets {0} and {0, 1}.
These sets can themselves be collected together into a set a = {{0}, {0, 1}}.
More generally, we can prove the following:

Proposition 7. (Unordered Pairs) For any objects x and y there is a (unique)
set a = {x, y}. In symbols: unordered pairs

∀x ∀y ∃!a ∀w(w ∈ a ” (w = x ∨ w = y))

Proof: Let x and y be arbitrary objects, and let

a = {w | w = x ∨ w = y}

The existence of a is guaranteed by Comprehension, and its unique-
ness follows from the Axiom of Extensionality. Clearly a has x and
y and nothing else as elements.

It is worth noting that our previous observation about the existence of
singletons, which we did not prove then, follows from this result. Thus:

Section 15.4
420 / First-order Set Theory

Proposition 8. (Singletons) For any object x there is a singleton set {x}.
singleton sets

Proof: To prove this, apply the previous proposition in the case
where x = y.

In order for set theory to be a useful framework for modeling structures of
various sorts, it is important to ¬nd a way to represent order. For example, in
modeling order
high school you learned about the representation of lines and curves as sets of
“ordered pairs” of real numbers. A circle of radius one, centered at the origin,
is represented as the following set of ordered pairs:

{ x, y | x2 + y 2 = 1}

But sets themselves are unordered. For example {1, 0} = {0, 1} by Extension-
ality. So how are we to represent ordered pairs and other ordered objects?
What we need is some way of modeling ordered pairs that allows us to
prove the following:

x, y = u, v ” (x = u § y = v)

If we can prove that this holds of our representation of ordered pairs, then we
know that the representation allows us to determine which is the ¬rst element
of the ordered pair and which is the second.
It turns out that there are many ways to do this. The simplest and most
widely used is to model the ordered pair x, y by means of the unlikely set
{{x}, {x, y}}.
De¬nition For any objects x and y, we take the ordered pair x, y to be the
ordered pair
set {{x}, {x, y}}. In symbols:

∀x ∀y x, y = {{x}, {x, y}}

Later, we will ask you to prove that the fundamental property of ordered
pairs displayed above holds when we represent them this way. Here we simply
point out that the set {{x}, {x, y}} exists and is unique, using the previous
two results.
Once we have ¬gured out how to represent ordered pairs, the way is open
for us to represent ordered triples, quadruples, etc. For example, we will repre-
sent the ordered triple x, y, z as x, y, z . More generally, we will represent
ordered n-tuples
ordered n-tuples as x1 , x2, . . . xn .
By the way, as with brace notation for sets, the ordered pair notation
x, y is not part of the o¬cial language of set theory. It can be eliminated
from formulas without di¬culty, though the formulas get rather long.

Chapter 15
Sets of sets / 421


15.23 Using the previous two propositions, let a = {2, 3} and let b = {a}. How many members does
 a have? How many members does b have? Does a = b? That is, is {2, 3} = {{2, 3}}?

15.24 How many sets are members of the set described below?

{{}, {{}, 3, {}}, {}}

[Hint: First rewrite this using “…” as a notation for the empty set. Then delete from each
description of a set any redundancies.]

15.25 Apply the Unordered Pair theorem to x = y = …. What set is obtained? Call this set c. Now
 apply the theorem to x = …, y = c. Do you obtain the same set or a di¬erent set?

15.26 This exercise and the one to follow lead you through the basic properties of ordered pairs.
 1. How many members does the set {{x}, {x, y}} contain if x = y? How many if x = y?
2. Recall that we de¬ned x, y = {{x}, {x, y}}. How do we know that for any x and y
there is a unique set x, y ?
3. Give an informal proof that the easy half of the fundamental property of ordered pairs
holds with this de¬nition:

(x = u § y = v) ’ x, y = u, v

4. ( ) Finally, prove the harder half of the fundamental property:

x, y = u, v ’ (x = u § y = v)

[Hint: Break into two cases, depending on whether or not x = y.]

15.27 Building on Problem 15.26, prove that for any two sets a and b, there is a set of all ordered
 pairs x, y such that x ∈ a and y ∈ b. This set is called the Cartesian Product of a and b, and
is denoted by a — b.

15.28 Suppose that a has three elements and b has ¬ve. What can you say about the size of a ∪ b,
 a © b, and a — b? (a — b is de¬ned in Exercise 15.27.) [Hint: in some of these cases, all you can
do is give upper and lower bounds on the size of the resulting set. In other words, you™ll have
to say the set contains at least such and such members and at most so and so.]

Section 15.4
422 / First-order Set Theory

Section 15.5
Modeling relations in set theory
Intuitively, a binary predicate like Larger expresses a binary relation between
objects in a domain D. In set theory, we model this relation by means of a
set of ordered pairs, speci¬cally the set

{ x, y | x ∈ D, y ∈ D, and x is larger than y}

This set is sometimes called the extension of the predicate or relation. More
generally, given some set D, we call any set of pairs x, y , where x and y are
in D, a binary relation on D. We model ternary relations similarly, as sets of
relation in set theory
ordered triples, and so forth for higher arities.
It is important to remember that the extension of a predicate can depend
on the circumstances that hold in the domain of discourse. For example, if we
rotate a world 90 degrees clockwise in Tarski™s World, the domain of objects
remains unchanged but the extension of left of becomes the new extension of
back of. Similarly, if someone in the domain of discourse sits down, then the ex-
tension of is sitting changes. The binary predicates themselves do not change,
nor does what they express, but the things that stand in these relations do,
that is, their extensions change.
There are a few special kinds of binary relations that it is useful to have
properties of relations
names for. In fact, we have already talked about some of these informally in
Chapter 2. A relation R is said to be transitive if it satis¬es the following:

Transitivity: ∀x∀y∀z[(R(x, y) § R(y, z)) ’ R(x, z)]

As examples, we mention that the relation larger than is transitive, whereas
the relation adjoins is not. Since we are modeling relations by sets of ordered
pairs, this condition becomes the following condition on a set R of ordered
pairs: if x, y ∈ R and y, z ∈ R then x, z ∈ R.
Here are several more special properties of binary relations:

Re¬‚exivity: ∀x R(x, x)
Irre¬‚exivity: ∀x ¬R(x, x)
Symmetry: ∀x∀y(R(x, y) ’ R(y, x))
Asymmetry: ∀x∀y(R(x, y) ’ ¬R(y, x))
Antisymmetry: ∀x∀y[(R(x, y) § R(y, x)) ’ x = y]

Each of these conditions can be expressed as conditions on the extension of
the relation. The ¬rst, for example, says that for every x ∈ D, x, x ∈ R.

Chapter 15
Modeling relations in set theory / 423

To check whether you understand these properties, see if you agree with
the following claims: The larger than relation is irre¬‚exive and asymmetric.
The adjoins relation is irre¬‚exive but symmetric. The relation of being the
same shape as is re¬‚exive, symmetric, and transitive. The relation of ¤ on
natural numbers is re¬‚exive, antisymmetric, and transitive.
These properties of relations are intimately connected with the logic of
atomic sentences discussed in Chapter 2. For example, to say that the follow-
ing argument is valid is equivalent to saying that the predicate in question
(Larger, for example) has a transitive extension under all logically possible
circumstances. In that case the following inference scheme is valid: inference scheme

R(a, b)
R(b, c)
R(a, c)

Similarly, to say of some binary predicate R that

∀x R(x, x)

is logically true is to say that the extension of R is re¬‚exive in all logically
possible circumstances. Identity is an example of this.
In connection with the logic of atomic sentences, let™s look at two partic-
ularly important topics, inverse relations and equivalence relations, in a bit
more detail.

Inverse relations

In our discussion of the logic of atomic sentences in Section 2.2, we noted that
some of the logical relations between atomic sentences stem from the fact that
one relation is the “inverse” of another (page 52). Examples were right of and
left of, larger and smaller, and less than and greater than. We can now see
what being inverses of one another says about the extensions of such pairs of
Given any set-theoretic binary relation R on a set D, the inverse (some- inverse or converse
times called the converse) of that relation is the relation R’1 de¬ned by

R’1 = { x, y | y, x ∈ R}

Thus, for example, the extension of smaller in some domain is always the
inverse of the extension of larger. In an exercise, we ask you to prove some
simple properties of inverse relations, including one showing that if S is the
inverse of R, then R is the inverse of S.


. 76
( 107 .)