<<

. 77
( 107 .)



>>

Section 15.5
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
( 107 .)



>>