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

Exercises

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

extension

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

predicates.

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.