ńņš. 77 |

424 / First-order Set Theory

Equivalence relations and equivalence classes

Many relations have the properties of reļ¬‚exivity, symmetry, and transitivity.

We have seen one example: being the same shape as. Such relations are called

equivalence relations, since they each express some kind of equivalence among

equivalence relations

objects. Some other equivalence relations expressible in the blocks language

include being the same size as, being in the same row as, and being in the same

column as. Other equivalence relations include has the same birthday as, has

the same parents as, and wears the same size shoes as. The identity relation

is also an equivalence relation, even though it never classiļ¬es distinct objects

as equivalent, the way others do.

As these examples illustrate, equivalence relations group together objects

that are the same in some dimension or other. This fact makes it natural to

talk about the collections of objects that are the same as one another along the

given dimension. For example, if we are talking about the same size relation,

say among shirts in a store, we can talk about all the shirts of a particular size,

say small, medium, and large, and even group them onto three appropriate

racks.

We can model this grouping process very nicely in set theory with an im-

portant construction known as equivalence classes. This construction is widely

used in mathematics and will be needed in our proof of the Completeness The-

orem for the formal proof system F .

Given any equivalence relation R on a set D, we can group together the

objects that are deemed equivalent by means of R. Speciļ¬cally, for each x ā D,

let [x]R be the set

{y ā D | x, y ā R}

In words, [x]R is the set of things equivalent to x with respect to the relation

R. It is called the equivalence class of x. (If x is a small shirt, then think

equivalence classes

of [x]SameSize as the storeā™s small rack.) The fact that this grouping opera-

tion behaves the way we would hope and expect is captured by the following

proposition. (We typically omit writing the subscript R from [x]R when it is

clear from context, as in the following proposition.)

Proposition 9. Let R be an equivalence relation on a set D.

1. For each x, x ā [x].

2. For all x, y, [x] = [y] if and only if x, y ā R.

3. For all x, y, [x] = [y] if and only if [x] ā© [y] = ā….

Proof: (1) follows from the fact that R is reļ¬‚exive on D. (2) is more

substantive. Suppose that [x] = [y]. By (1), y ā [y], so y ā [x]. But

Chapter 15

Modeling relations in set theory / 425

then by the deļ¬nition of [x], x, y ā R. For the converse, suppose

that x, y ā R. We need to show that [x] = [y]. To do this, it suļ¬ces

to prove that [x] ā [y] and [y] ā [x]. We prove the ļ¬rst, the second

being entirely similar. Let z ā [x]. We need to show that z ā [y]. Since

z ā [x], x, z ā R. From the fact that x, y ā R, using symmetry,

we obtain y, x ā R. By transitivity, from y, x ā R and x, z ā R

we obtain y, z ā R. But then z ā [y], as desired. The proof of (3)

is similar and is left as an exercise.

Exercises

15.29 Open the Fitch ļ¬le Exercise 15.29. This ļ¬le contains as goals the sentences expressing that the

Ć‚ same shape relation is reļ¬‚exive, symmetric, and transitive (and hence an equivalence relation).

You can check that each of these sentences can be proven outright with a single application

of Ana Con. However, in this exercise we ask you to prove this applying Ana Con only to

atomic sentences. Thus, the exercise is to show how these sentences follow from the meaning

of the basic predicate, using just the quantiļ¬er rules and propositional logic.

For the next six exercises, we deļ¬ne relations R and S so that R(a, b) holds if either a or b is a

tetrahedron, and a is in the same row as b, whereas S(a, b) holds if both a and b are tetrahedra, and in

the same row. The exercises ask you to decide whether R or S has various of the properties we have been

studying. If it does, open the appropriate Fitch exercise ļ¬le and submit a proof. If it does not, submit

a world that provides a counterexample. Thus, for example, when we ask whether R is reļ¬‚exive, you

should create a world in which there is an object that does not bear R to itself, since R is not in fact

reļ¬‚exive. In cases where you give a proof, you may use Ana Con applied to literals.

15.30 Is R reļ¬‚exive? 15.31 Is R symmetric? 15.32 Is R transitive?

Ć‚ Ć‚ Ć‚

15.33 Is S reļ¬‚exive? 15.34 Is S symmetric? 15.35 Is S transitive?

Ć‚ Ć‚ Ć‚

15.36 Fill in the following table, putting yes or no to indicate whether the relation expressed by the

predicate at the top of the column has the property indicated at the left.

Smaller SameCol Adjoins LeftOf

Transitive

Reļ¬‚exive

Irreļ¬‚exive

Symmetric

Asymmetric

Antisymmetric

Section 15.5

426 / First-order Set Theory

15.37 Use Tarskiā™s World to open the ļ¬le Vennā™s World. Write out the extension of the same column

relation in this world. (It contains eight ordered pairs.) Then write out the extension of the

between relation in this world. (This will be a set of ordered triples.) Finally, what is the

extension of the adjoins relation in this world? Turn in your answers.

15.38 Describe a valid inference scheme (similar to the one displayed on page 423) that goes with

each of the following properties of binary relations: symmetry, antisymmetry, asymmetry, and

irreļ¬‚exivity.

15.39 What are the inverses of the following binary relations: older than, as tall as, sibling of, father

of, and ancestor of ?

15.40 Give informal proofs of the following simple facts about inverse relations.

1. R is symmetric iļ¬ R = Rā’1 .

2. For any relation R, (Rā’1)ā’1 = R.

15.41 Use Tarskiā™s World to open the ļ¬le Vennā™s World. Write out equivalence classes that go with

each of the following equivalence relations: same shape, same size, same row, and identity.

You can write the equivalence classes using list notation. For example, one of the same shape

equivalence classes is {a, e}.

15.42 Given an equivalence relation R on a set D, we deļ¬ned, for any x ā D:

[x]R = {y ā D | x, y ā R}

Explain how Proposition 1 can be used to show that the set displayed on the right side of this

equation exists.

15.43 (Partitions and equivalence relations) Let D be some set and let P be some set of non-empty

subsets of D with the property that every element of D is in exactly one member of P. Such a

set is said to be a partition of D. Deļ¬ne a relation E on D by: a, b ā E iļ¬ there is an X ā P

such that a ā X and b ā X. Show that E is an equivalence relation and that P is the set of its

equivalence classes.

15.44 If a and b are subsets of D, then the Cartesian product (deļ¬ned in Exercise 15.27) a Ć— b is a

binary relation on D. Which of the properties of relations discussed in this section does this

relation have? (As an example, you will discover that a Ć— b is irreļ¬‚exive if and only if a ā© b = ā….)

Your answer should show that in the case where a = b = D, a Ć— b is an equivalence relation.

How many equivalence classes does it have?

15.45 Prove part (3) of Proposition 9.

Chapter 15

Functions / 427

Section 15.6

Functions

The notion of a function is one of the most important in mathematics. We

have already discussed functions to some extent in Section 1.5.

Intuitively, a function is simply a way of doing things to things or assign-

ing things to things: assigning license numbers to cars, assigning grades to

students, assigning a temperature to a pair consisting of a place and a time,

and so forth. Weā™ve already talked about the father function, which assigns

to each person that personā™s father, and the addition function, which assigns

to every pair of numbers another number, their sum.

Like relations, functions are modeled in set theory using sets of ordered functions as special

kind of relation

pairs. This is possible because we can think of any function as a special type

of binary relation: the relation that holds between the input of the function

and its output. Thus, a relation R on a set D is said to be a function if it

satisļ¬es the following condition:

āxāā¤1 y R(x, y)

Functional:

In other words, a relation is a function if for any āinputā there is at most one

āoutput.ā If the function also has the following property, then it is called a

total function on D: total functions

Totality: āxāy R(x, y)

Total functions give āanswersā for every object in the domain. If a function

is not total on D, it is called a partial function on D.3 partial functions

Whether or not a function is total or partial depends very much on just

what the domain D of discourse is. If D is the set of all people living or dead,

then intuitively the father of function is total, though admittedly things get a

bit hazy at the dawn of humankind. But if D is the set of living people, then

this function is deļ¬nitely partial. It only assigns a value to a person whose

father is still living.

There are some standard notational conventions used with functions. First,

it is standard to use letters like f, g, h and so forth to range over functions.

Second, it is common practice to write f (x) = y rather than x, y ā f when f (x)

f is a function.

The domain of a function f is the set domain of function

{x | āy(f (x) = y)}

3 Actually, usage varies. Some authors use āpartial functionā to include total functions,

that is, to be synonymous with function.

Section 15.6

428 / First-order Set Theory

while its range is

{y | āx(f (x) = y)}

It is common to say that a function f is deļ¬ned on x if x is in the domain of

f. Thus the father of function is deļ¬ned on the individual Max, but not on

deļ¬ned vs. undeļ¬ned

the number 5. In the latter case, we say the function is undeļ¬ned. The domain

of f will be the entire domain D of discourse if the function f is total, but

will be a subset of D if f is partial.

Notice that the identity relation on D, { x, x | x ā D}, is a total function

on D: it assigns each object to itself. When we think of this relation as a

function we usually write it as id. Thus, id(x) = x for all x ā D.

Later in the book we will be using functions to model rows of truth tables,

naming functions for individual constants, and most importantly in deļ¬ning

the notion of a ļ¬rst-order structure, the notion needed to make the concept

of ļ¬rst-order consequence mathematically rigorous.

Exercises

15.46 Use Tarskiā™s World to open the ļ¬le Vennā™s World. List the ordered pairs in the frontmost (fm)

function described in Section 1.5 (page 33). Is the function total or partial? What is its range?

15.47 Which of the following sets represent functions on the set D = {1, 2, 3, 4}? For those which are

functions, pick out their domain and range.

1. { 1, 3 , 2, 4 , 3, 3 }

2. { 1, 2 , 2, 3 , 3, 4 , 4, 1 }

3. { 1, 2 , 1, 3 , 3, 4 , 4, 1 }

4. { 1, 1 , 2, 2 , 3, 3 , 4, 4 }

5. ā…

15.48 What is the domain and range of the square root function on the set N = {0, 1, 2, . . .} of all

natural numbers?

15.49 Open the Fitch ļ¬le Exercise 15.49. The premise here deļ¬nes R to be the frontmost relation.

Ć‚ The goal of the exercise is to prove that this relation is functional. You may use Taut Con as

well as Ana Con applied to literals.

A function f is said to be injective or one-to-one if it always assigns diļ¬erent values to diļ¬erent objects

in its domain. In symbols, if f(x) = f (y) then x = y for all x, y in the domain of f .

15.50 Which of the following functions are one-to-one: father of, student id number of, frontmost, and

ļ¬ngerprint of ? (You may need to decide just what the domain of the function should be before

deciding whether the function is injective. For frontmost, take the domain to be Vennā™s World.)

Chapter 15

The powerset of a set / 429

15.51 Let f (x) = 2x for any natural number x. What is the domain of this function? What is its

range? Is the function one-to-one?

15.52 Let f (x) = x2 for any natural number x. What is the domain of this function? What is its

range? Is the function one-to-one? How does your answer change if we take the domain to

consist of all the integers, both positive and negative?

15.53 Let E be an equivalence relation on a set D. Consider the relation R that holds between any

x in D and its equivalence class [x]E . Is this a function? If so, what is its domain? What is its

range? Under what conditions is it an one-to-one function?

Section 15.7

The powerset of a set

Once we get used to the idea that sets can be members of other sets, it is

natural to form the set of all subsets of any given set b. The following theorem,

which is easy to prove, shows that there is one and only one such set. This

set is called the powerset of b and denoted ā„˜b or ā„˜(b). powersets (ā„˜)

Proposition 10. (Powersets) For any set b there is a unique set whose mem-

ńņš. 77 |