ARS: Invariants (2018)

(finished, but not polished)

Aims

To answer the following questions:

• What is meant by a "nice description" of equivalence classes in the exercises?
• What is an invariant?
• How to build more complicated invariants from simpler ones in a compositional way?
• How to describe equivalence relations and partitions by invariants?
• How to prove that something is impossible?

Examples of Invariants

Let us take the example from the first exercise.

​​​​    ab -> ba
​​​​    ba -> ab
​​​​    aa ->
​​​​    b ->

What, intuitively, are some invariants? Which properties do not change when we apply the rules?

Here is a list we came up with in class, can you find more?

If we only have

​​​​    ab -> ba
​​​​    ba -> ab

invariants are

​​​​    length
​​​​    number of a's
​​​​    number of b's
​​​​    number of a's + number of b's
​​​​    number of a's = number of b's
​​​​    number of a's + number of b's = length
​​​​    ...

We can split this list into two different groups. In the first group,

$P$ is a function to the integers

​​​​    length
​​​​    number of a's
​​​​    number of b's
​​​​    number of a's + number of b's
​​​​    ...

in the second group

$P$ is a function to the booleans (truth values)

​​​​    number of a's = number of b's
​​​​    number of a's + number of b's = length

Notice that one can build larger invariants from smaller ones as we have done in

​​​​    number of a's + number of b's
​​​​    number of a's + number of b's = length

Definition of Invariant

Definition: A function

$P:A\to B$ is an invariant for an ARS

$(A,\to )$ if

$$a\to b⟹P(a)=P(b)$$ for all

$a,b\in A$.

Remark: We call

$P$ a property of

$(A,\to )$ if

$P$ is a function from

$A$ to the Booleans.

The Partition Induced by an Invariant

We have seen that every function

$f:X\to Y$ induces a partition on

$X$. So does an invariant.

Being an invariant of

$(A,\to )$ means that the partition induced by

$P$ on

$A$ is an 'abstraction' of the partition induced by

$\to$. Or, in other words, that the partition induced by

$\to$ 'refines' the partition induced by

$P$.

Proving the Impossible

How do you prove that there is no path in an ARS that leads from

$a$ to

$b$?

How do you prove a statement of the form "not

$a\stackrel{\ast }{⟶}b$" or "not

$a\stackrel{\ast }{⟷}b$"?

How do you prove that

$a$ and

$b$ are in different equivalence classes?

Such reasoning typically cannot be done by applying a mechanical method (or algorithm) to the available data. Some insight is often needed.

But there is a method that helps.

The method says that the required insight can be formulated as an invariant property

$P$ on the

$A$ such that

$$P(a)=trueP(b)=false$$

Exercise: Show that if

$P$ is an invariant property of the ARS

$(A,\to )$ and

$P(a)=true$ and

$P(b)=false$ then

• not
  $a\stackrel{\ast }{⟶}b$
• not
  $a\stackrel{\ast }{⟷}b$
• $a$ and
  $b$ are in different equivalence classes

Building Complete Invariants

We have seen that one can combine invariants.

Here we show how to build from invariant properties a complete set of invariants, or also, one complete invariant.

Example: Let

$(A,\to )$ be the ARS generated by the schemas of rules

​​​​    ab -> ba
​​​​    ba -> ab
​​​​    aa ->
​​​​    bb ->

There are two invariant properties that come to mind immediately:

• $P_a(w)$ if the number of a in
  $w$ is even
• $P_b(w)$ if the number of b in
  $w$ is even

These two invariants are complete in the sense that they disinguish all words that are not equivalent. In other words, if two words agree on

$P_a$ and

$P_b$, then they must be equivalent. This can be stated more formally as follows.

• If
  $P_a(w)=P_a(v)$ and
  $P_b(w)=P_b(v)$, then
  $w\stackrel{\ast }{\leftrightarrow }v$.

The converse also holds by virtue of the the properties being invariant.

Exercise: Show that the invariants being complete implies that

$(A,\to )$ has at most 4 equivalence classes. What property of the invariants guarantees that in this example there are exactly 4 equivalence classes?

We can also combine the two invariants into one invariant

$$P:A\to \mathbb{B}\times \mathbb{B}$$

where

$\mathbb{B}$ stands for the set

$\{true,false\}$ of Booleans by defining

$$P(w)=(P_a(w),P_b(w)).$$

Exercise: Show that

$P$ is complete for

$(A,\to )$ in the sense that

$w\stackrel{\ast }{\leftrightarrow }v$ if and only if

$P(w)=P(v)$.

A Final Challenge

This is a well-known puzzle, don't look up the answer on the internet.

Take a chess board and tiles (or dominoes) that cover exactly two squares of the board.

• Is it possible to cover the board with the dominoes? If I explained the situation properly the answer should be an obvious yes. ^[1]
• Now replace the chess board by a board that has 9 rows and columns. What is the answer now? What is the invariant you use to prove your answer? (Hint: First simplify the question and look at a 3x3 board.)
• Now go back to the 8x8 chess board but remove two diagonally opposite squares. Can you cover it with dominoes now?

This puzzle indicates that invariants have a much wider range of applications than our ARS examples. ^[2] Invariants are one of the most powerful problem solving techniques.

Remark on Problem Solving: Notice how we thought about the chess board puzzle by making it more general. Instead of just looking at one board shape and asking whether it can be tiled, we used at a range of different board shapes. Generalising a problem in such a way is an important problem solving technique.

Summary

From a mathematical point of view, an invariant on

$A$ is just a function

$f:A\to B$.

As any function,

$f$ induces a partition on

$A$ given by the equivalence relation

$a_1\equiv a_2\iff f(a_1)=f(a_2)$.

We sometimes say that

$f$ classifies the elements of

$a$ up to the equivalence relation.

In our examples the equivalence relation is the equivalence closure

$\stackrel{\ast }{⟷}$ of the relation

$\to$ of an ARS

$(A,\to )$.

And the function

$f:A\to B$ is called an invariant if

$a\to b\Rightarrow f(a)=f(b)$, or, equivalently, if

$a\stackrel{\ast }{⟷}b\Rightarrow f(a)=f(b)$.

---

1. By "covering the board" or "tiling the board" I mean that every square of the board is under exactly one dominoe (tile) and that every dominoe (tile) is over exactly two squares. ↩︎

2. In fact, one can formulate the chess puzzle as an ARS where an element of the ARS is a configuration of dominoes on the board and the relation

   $\to$ is the relation given by adding one dominoe to a given configuration. ↩︎