Next: Real and Complex Numbers Up: Sentences and Formulas Previous: Truth functions

# Equality

There are two somewhat divergent views as to the role of the equality symbol in logic. Some people say that the symbol ``='' plays a special role and must be treated as a logical symbol just like , or . According to this view, the symbol = can only be interpreted by the relation by which an element is related to itself and nothing else. The other point of view is that the equality relation can be axiomatized so that any relation satisfying the axioms is a legitimate candidate for the meaning of =. This has a potential affect on our logical system since on the face of it there might be a possibility that a set of sentences can be made true with some abstract equality relation but not with an interpretation which correctly interprets ``=''.

To illustrate the difference between these viewpoints, consider the integers mod n. In this structure, we often work with equality defined not as actual equality, but rather as the equivalence relation, ``(x-y) is a multiple of n''. In other words, we put n equal to 5 and say something like, ``Take for equal any two numbers with the same remainder when divided by 5.'' This point of view is the only one that makes sense when we say for instance that 25 is a simultaneous solution to the two congruences and . On the other hand, taking mod 5 as an example, we could just say that the universe we are considering has just five points, with all the arithmetic operations defined mod 5.

Let us begin by stating the abstract axioms for the equality relation.

Note that in this definition items (4) and (5) are really more than one axiom since there is a different axiom for each function symbol and for each relation symbol. In Example 2 we included the equality axioms as part of the axioms for group theory and frequently in algebra equality is interpreted just by some relation satisfying these axioms. So for instance in Example 3, the symbol = was interpreted by a relation other than actual equality.

In order to reconcile these two views about equality, we must make a brief excursion into the mathematical theory of equivalence relations.

Given an equivalence relation on a universe U, we can form equivalence classes. The   equivalence class of an element x is . The equivalence class of x is often denoted with the notation, [x]. The basic facts about equivalence classes are

If , then [x] = [y].
If , then
If , then [x] = [y]

Thus, the operation of taking equivalence classes converts into actual equality.

Let us illustrate with mod 5 arithmetic. Start with the universe of integers, and define iff x-y is divisible by 5. The five equivalence classes of this relation are the five sets,

Each equivalence class is the class of any one of its members. i.e. [-10] = [-5] = [0] = [5] = [10] and the class of each of these numbers is just the first of the sets we have listed.

In order to do modular arithmetic, we must do more than just define these classes, we must be able to add and multiply them. The definition of addition goes like this: To add classes, pick one element out of each, add those elements and take class of the sum. So for instance, [3] + [2] = [0]. What is needed is some assurance that our value for the sum of two classes does not depend on which elements we choose from each class. We need to know

Taking into account the fact that means the same thing as , this means that must satisfy the axiom,

Similarly, in order to define multiplication on equivalence classes, we need the axiom,

Since these two axioms are easily proven, all is well and arithmetic is well defined on mod 5 classes. These two axioms are both instances of our equality axiom 4.

Any attempt to similarly define < for equivalence classes of the mod 5 relation is doomed to failure. This is because modular equivalence does not satisfy our axiom equality axiom 5. That is to say

is plainly false.

Summarizing, if we delete the symbol < from the language of arithmetic, and interpret = with mod 5 equivalence, all of our equality laws are true and thus we can convert to actual equality by taking our universe not to be the set of integers, but rather five point universe whose ``points'' are the five equivalence classes.

This process of using equivalence classes can be used in general. Starting with an interpretation making the equality axioms true, we can always pass to equivalence classes to obtain a new interpretation in which the symbol = is interpreted by actual equality. The process is straight forward: Form a new universe whose points are equivalence classes of the old universe. Using the notation [x] to stand for the set of all those y ``equal'' to x, define new functions by f([x]) = [f(x)]. Define the truth value of r[x] to be the same as the truth value of r(x). The equality axioms guarantee that these definitions are well defined. This creates a new interpretation each of whose ``points'' is a subset of the previous interpretation. In this new interpretation, a point is equal only to itself and nothing else.

This process is done in many areas of mathematics. One common example is the definition of the     rational numbers. There we define the universe to be the set of all pairs of integers, with 0 < y. For equality use the equivalence relation,

The arithmetical operations and the < relation are then defined as:

If a > 0, then
If a < 0, then
If a = 0, then
iff

The pair is the interpretation of the symbol 0 and is the interpretation of the symbol 1. These definitions satisfy all the equality axioms.

Because abstract equality can always be converted to actual equality by taking equivalence classes, we can make a simplification in our logical theory. We need not make any special conventions about equality, it is just a relation symbol like any other. However, by including the equality axioms in an axiom set, we can always assume that its models always interpret = with actual equality.

Next: Real and Complex Numbers Up: Sentences and Formulas Previous: Truth functions

Richard Mansfield
Wed Oct 21 14:09:45 EDT 1998