How to pull zero and negative integers out of a hat. Pt 2

[Robert J. Kolker]

In this lesson we branch off from the main theme briefly to deal with equivalence relations and particularly equivalence relations that preserve algebraic relations. In part 3 we shall apply the material here present to finally get negative integers and zero.

Let S be a non-empty set and let ~ be a binary relation on S.

Definition 1:

We say that ~ is an equivalence relation if and only if

a. For all s in S s ~ s (Reflexivity)

b. For all s, t in S s ~ t implies t ~ s (Symmetry)

c. For all s, t, u in S s ~ t and t ~ u imply s ~ u (Transitivity)

Define a subset of S, E\sub s for element s in S to be

{t in S | t ~ s}. This is read: "the set of t in S such that t ~ s"

Let r,s in S.

Lemma 1

If r ~ s The E\sub r = E\sub s

Lemma 2

If not r ~ s then E\sub r .intersect. E\sub s = empty set. Puting it another way E\sub r and E\sub s are disjoint (have no elements in common)

(NB: set 1 .intersect. set 2 is the set of all elements common to both set 1 and set 2).

Proof of Lemma 1. Suppose t in E\sub r. Then by definition t ~ r. r ~ s by hypothesis, therefore t ~ s by transitivity, hence t in E\sub s. By the same reasoning t in E\sub s implies t in E\sub r so E\sub s = E\sub r.

Proof of Lemma 2. not r ~ s by hypothesis. If E\sub r and

E\sub s have an element t in common then r ~ t and t ~ s (by symmetry) so r ~ s by transitivity. But this contradicts the hypothesis that not r ~ s (hence not s ~ r by symmetry).

Conclusion. The equivalence relation ~ decomposes the set S into a collection of pairwise disjoint subsets.

S = E1 U E2 U .... where U is the union operator on sets.

A U B = {z | z in A or z in B}. or is the inclusive or.

The converse is also true. Every decomposition of S into disjoint non-empty subsets produces an equivalence relation. Given the decomposition S = E1 U E2 U.... Define s ~* t if and only if for some n, both s and t are in En. I leave it as an exercise to show ~* is an equivalence relation by definition 1.

Next we deal with binary operations. A binary operation (such as + or x) is an operation the combines two elements to produce a third (not necessarily distinct from the prior two). Let us denote a generic binary operator on the non empty set S by o (lower case "oh"). So for s, t in S

s o t is an element of S. Now we put together equivalence relations and binary operators. We say the equivalence relation ~ on S preserves the binary operator o if and only if

s ~ s' and t ~ t' imply s o t ~ s' o t'

We can now extend the binary operator to the decomposition of S produced by the equivalence relation ~ if ~ preserve o

We extend o to apply to the set of subsets of S produced by ~ as follows:

Let E(s) = E\sub s and E(t) = E\sub t for s, t in S. Then we define E(s) o E(t) = E(s o t). In effect we have lifted o from being a binary operator on elements of S to an operator on a collection of subsets of S, namely, the equivalences classes of ~.

This a procedure that is used throughout modern mathematics where we take an operation defined on one domain and extend it (by analogy, as it were) to an operation on a more general domain. That is how we are going to extend the arithmetic binary operations + and x on the natural integers to a larger class of objects which includes the natural integers as a proper subset.

So stand by for Part 3, where we combine the lessons of Part 2 with the constructions of Part 1.

.....

Bob Kolker