Recursive Definition of Is Equal To

Question

I'm working through some of the intro problems in Sudkamp's Languages and Machines (basically an intro book to finite automata, context free grammars, Turing machines, etc), and I'm struggling a bit with recursive definitions and the mathematical preliminaries. Can anyone explain how to get going with the following problem?

Give a recursive definition of the relation "is equal to" on N x N using the operator s.

N x N a relation of the Natural numbers, and the operator s refers to the "successor operator." I assume this has to do with the definition of addition. The sequence is 0, s(0), s(s(0)),... which equals 0, 1, 2, ...

I suspect that this can be solved with mathematical induction, but I'm not sure what the base case should even be.

Answer 1

Ref to :

• Thomas Sudkamp, Languages and machines : An Introduction to the Theory of Computer Science (2nd ed - 1997), Exercise 24, page 34.

We have to define a relation :

$Eq \subseteq \mathbb N \times \mathbb N$

defined thorugh the following equations :

$Eq(0,0)=$true

$Eq(0,s(n))=$false

$Eq(s(m),0)=$false

$Eq(s(m),s(n))=Eq(m,n)$.

---

Thus, "mimicking" the Example 1.5.2, page 23, we must have :

i) Basis : $[0,0] \in EQ$.

ii) Recursive step : if $[n,m] \in EQ$, then $[s(n),s(m)] \in EQ$.

iii) Closure : $[n,m] \in EQ$ only if it can be obtained from $[0,0]$ by a finite number of applications of the operations in the recursive step.