Equivalence

At the heart of our approach to mathematics is the technique of calculation. When we calculate, we rearrange expressions to form new expressions in accordance with certain rules. These expressions may have many different values. One way we cope with this complexity is to identify values which have properties in common and collect them into groups. Such groups are called types. If a value v belongs to a type T, we say that v is of type T.

***

The first type we will explore is a very simple one – so simple it consists of only two values. The type is called boolean and its values are \top, pronounced “top” and \bot, pronounced “bottom”.

Now we can talk about the value of X = Y :

“The value of X = Y is of type boolean.”

or, equivalently,

“The value of X = Y is either \top or \bot.”

***

Equality between booleans is special, and so when we express equality between X and Y, where X and Y are boolean we write

X\equiv Y

pronounced “X equivales Y “.

What is so special about boolean equality – called equivalence – that we have special symbol for it? The answer gives us our first rule for calculating:

Associativity:
(X \equiv (Y \equiv Z)) \equiv ((X \equiv Y ) \equiv Z)

We give the rule a name to help us remember what it is. Here is how we would use the rule in calculations:

  X \equiv (Y \equiv Z)
\equiv\quad \{\textrm{associativity}\}
  (X \equiv Y ) \equiv Z

An important consequence of $\eqv$’s associativity is that when we have a series of expressions punctuated by $\eqv$ signs it does not matter where we put the brackets. Indeed, we need not write the brackets at all, as for instance in our next rule:\\

Symmetry: X\equiv Y\equiv Y\equiv X

We may parse this rule in several ways:

$ latex (X\equiv Y)\equiv (Y\equiv X)$

X\equiv (Y\equiv Y\equiv X)

(X\equiv Y\equiv Y)\equiv X

The last two expressions tell us that `equivaling’ Y\equiv Y with any boolean X is X. We say that Y\equiv Y is the identity of \equiv. Our next rule gives a name to the identity:

(2) X\equiv\top\equiv X

Up to this point we have simply postulated rules i.e. we have taken it as given that they hold. Our next rule, however, we will prove. How do we prove? When we postulate a rule we are saying that it is an expression which is equivalent to \top. So to show that an expression is a rule, we present a calculation showing that the said expression is also equivalent to \top.

Reflexivity: X\equiv X

Proof

X\equiv X

\equiv {{(2), parsed as X\equiv(\top\equiv X)

X\equiv\top\equiv X

\equiv {(2)}

\top

Such is the equivalence.

Challenge: Does anyone know how to get the latex \quad and \begin{tabular} commands to work in WordPress?

Advertisements

One Response to “Equivalence”

  1. Science After Sunclipse Says:

    Carnival of Mathematics

    Mark Chu-Carroll hosts the latest Carnival of Mathematics with a theme dear to my heart, the way cholesterol is: spam!
    Among the notable posts are My Tiny Kingdom’s report on helping with long-division homework. This reminds me: can any of the …

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: