Equivalence Relation

Let A be a set, then a subset $\Re$ of $A \times A$ is called an equivalence relation on A if the following properties all hold

1.

     $(a,a) \in \Re \qquad a \in A$     -     reflexive law

2.

    if $(a,b) \in \Re$ then $(b,a) \in \Re$     -     symmetric law

3.

    if $(a,b) \in \Re$ and $(b,c) \in \Re$ then $(a,c) \in \Re$     -     transitive law

The reflexive property states that all objects are equivalent to themselves while the symmetric property states that if a is equivalent to b, then b is equivalent to a. The transitive property states that objects that are equivalent to the same object are equivalent to one another.

These conditions can also be written, using a different notation

1.

     $a \enskip \Re \enskip a \qquad \forall a \in A$

2.

     $a \enskip \Re \enskip b \quad \Rightarrow \quad b \enskip \Re \enskip a \qquad \forall a,b \in A$

3.

     $a \enskip \Re \enskip b$     and      $b \enskip \Re \enskip c \quad \Rightarrow \quad a \enskip \Re \enskip c \qquad \forall a,b,c \in A$

where the symbol $\forall$ denotes the universal quantifier `` for all ''.

As an example, consider a high-level block structured programming language like Pascal, and let D denote the set of all declared identifiers in a Pascal program, then ``is declared in the same block as'' constitutes an equivalence relation, while ``is declared in a block which encloses'' is not an equivalence relation since property (2) does not hold in the second example.

As a further example, consider aliased variables. If two or more variables denote the same memory address, the variables are called aliases of one another. The ANSI version of Fortran allows aliased variables to be introduced by means of the aptly named non-executable EQUIVALENCE statement which declares that two or more variables in a program refer to the same memory location. As an example, the statement

EQUIVALENCE (T1,T2), (INDEX, JCOUNT, LOOPVAR)

instructs the compiler that the variables T1 and T2 share one memory location and that INDEX, JCOUNT and LOOPVAR are to share another.

If $\cal{A}$ denotes the relation ``is an alias of'', then $\cal{A}$ constitutes an equivalence relation over the set of all program variables V. We can express the elements of the relation as

T1 $\cal{A}$ T2

INDEX $\cal{A}$ JCOUNT,      INDEX $\cal{A}$ LOOPVAR,      JCOUNT $\cal{A}$ LOOPVAR

We say that the set of all program variables V is partitioned by the equivalence relation $\cal{A}$. The set of all variables in V which are aliases of each other constitute what is called an equivalence class so that {T1, T2} and {INDEX, JCOUNT, LOOPVAR} constitute two separate equivalence classes. These ideas of partitioning and equivalence classes are formalised in the following definitions.