5
$\begingroup$

Consider the following two definitions of the natural numbers:

  • The natural numbers are the algebraic structure $\mathbb{N}_1$ generated by one constant, $0$ and one unary function, $S$ (and no relations).
  • The natural numbers are the monoid $(\mathbb{N}_2, 0, +)$ with presentation $\langle 1 \mid \rangle$.

These two definitions are equivalent, in the sense that there exists a certain "nice" bijection between the structures they define: namely, the unique function $f : \mathbb{N}_1 \to \mathbb{N}_2$ with $f(0) = 0$ and $f(S(x)) = f(x) + 1$, which is a bijection.

How could we prove that the bijection $f$ satisfying those two equations really does exist? One option, of course, is to take your favorite set theory, define all of these objects formally, and use first-order logic to construct a proof.

However, it's also possible to show that this bijection exists without using set theory or logic at all. The method is essentially the same as using Tietze transformations to define an isomorphism between the groups generated by two group presentations.

Groups and Tietze transformations

Consider the following two group presentations (which I'm writing using deliberately bulky notation). First:

  1. $a$
  2. $b$
  3. $ab$ = $ba$
  4. $a^3 = b^2$

And second:

  1. $c$

Both of these presentations present the infinite cyclic group. If we want to construct an isomorphism, then using set theory and first-order logic would be overkill. Instead, we can simply use Tietze transformations, as shown:

  • Add a generator $c$ with definition $c = b a^{-1}$ (5 and 6 below).
  • Add a relation $c^3 = b$ (7 below). Proof: $c^3 = (b a^{-1})^3 = b^3 a^{-3} = b^3 b^{-2} = b$.
  • Add a relation $c^2 = a$ (8 below). Proof: $c^2 = (b a^{-1})^2 = b^2 a^{-2} = a^3 a^{-2} = a$.
  • Remove the relation $c = b a^{-1}$ (6 below). Proof: $c = c^3 c^{-2} = b a^{-1}$.
  • Remove the relation $ab = ba$ (3 below). Proof: $ab = c^2 c^3 = c^3 c^2 = ba$.
  • Remove the relation $a^3 = b^2$ (4 below). Proof: $a^3 = (c^2)^3 = (c^3)^2 = b^2$.
  • Remove the generator $a$ with definition $a = c^2$ (1 and 8 below).
  • Remove the generator $b$ with definition $b = c^3$ (2 and 7 below).
  1. $a$
  2. $b$
  3. $ab = ba$
  4. $a^3 = b^2$
  5. $c$
  6. $c = b a^{-1}$
  7. $c^3 = b$
  8. $c^2 = a$

After all of these transformations have been completed, the only item remaining is item 5, which is the generator $c$.

So, using the Tietze transformations, we have constructed an isomorphism $f$ from the first group to the second group, with $f(a) = c^2$ and $f(b) = c^3$.

Generalizing

Define a generic presentation as an algebraic theory. We refer to the free algebra of the theory as "the algebra generated by the presentation."

The first definition of the natural numbers above ($\mathbb{N}_1$) is formalized as this generic presentation:

  1. $0$ (a generator which is a nullary operation)
  2. $S(-)$ (a generator which is a unary operation)

And the second definition of the natural numbers ($\mathbb{N}_2$) is formalized like so:

  1. $0$
  2. $P(-,-)$
  3. $P(0,x) = x$
  4. $P(x,0) = x$
  5. $P(x,P(y,z)) = P(P(x,y),z)$
  6. $1$

As mentioned at the beginning of this question, there is a bijection $f : \mathbb{N}_1 \to \mathbb{N}_2$ with $f(0) = 0$ and $f(S(x)) = P(f(x), 1)$. How can we construct this bijection?

Much as we did with the infinite cyclic group above, we can construct this bijection using a sequence of transformations which are similar to the Tietze transformations.

However, the Tietze transformations themselves are not quite sufficient for this purpose. In addition to the four Tietze transformations, we need to add two additional "Tietze-like transformations" to our toolbox. Specifically, in addition to adding (or removing) a constant along with a single equation defining it, I think we need to be able to add (or remove) a function symbol along with a set of equations defining it. (I think we can require the set of equations to be a primitive recursive function definition; I haven't worked out the details.)

Furthermore, two of the Tietze transformations need to be altered to make them more powerful. Specifically, the Tietze transformations allow us to add or remove a relation if we can prove that relation from the other relations using a simple proof by substitution. We need to alter these so that we are also permitted to use inductive proofs of equality. (Again, I haven't worked out the details.)

The resulting "toolset" consists of six Tietze-like transformations: adding or removing a (constant) generator; adding or removing a function; and adding or removing a relation (potentially using an inductive proof). These six transformations are sufficient to construct the desired bijection between $\mathbb{N}_1$ and $\mathbb{N}_2$.

Below is the construction. Once again, it consists of a sequence of Tietze-like transformations, starting with the first presentation and ending with the second one.

  • Add a generator $1$ with definition $1 = S(0)$ (3 and 4 below).
  • Add a generator $P(-,-)$ with definition $P(x,S(y)) = S(P(x,y))$ and $P(x,0) = x$ (5, 6, and 7 below).
  • Add a relation $P(x,1) = S(x)$ (8 below). Proof: $P(x,1) = P(x,S(0)) = S(P(x,0)) = S(x)$.
  • Add a relation $P(0,x) = x$ (9 below). The proof is by induction. The $0$ case: $P(0,0) = 0$. The $S$ case: $P(0,S(x)) = S(P(0,x)) = S(x)$.
  • Add a relation $P(x,P(y,z)) = P(P(x,y),z)$ (10 below). The proof is by induction. The $0$ case: $P(x,P(y,0)) = P(x,y) = P(P(x,y),0)$. The $S$ case: $P(x,P(y,S(z))) = P(P(x,y),S(z))$ (details omitted).
  • Remove the relation $1 = S(0)$ (4 below). Proof: $1 = P(0,1) = S(0)$.
  • Remove the relation $P(x,S(y)) = S(P(x,y))$ (6 below). Proof: $P(x,S(y)) = P(x,P(y,1)) = P(P(x,y),1) = S(P(x,y))$.
  • Remove the generator $S(-)$ with definition $S(x) = P(x,1)$ (2 and 8 below).
  1. $0$
  2. $S(-)$
  3. $1$
  4. $1 = S(0)$
  5. $P(-,-)$
  6. $P(x,S(y)) = S(P(x,y))$
  7. $P(x,0) = x$
  8. $P(x,1) = S(x)$
  9. $P(0,x) = x$
  10. $P(x,P(y,z)) = P(P(x,y),z)$

When we work through the above list of transformations, we start with items 1 and 2, and we add items 3 through 10, and then we remove items 2, 4, 6 and 8, leaving items 1, 3, 5, 7, 9, and 10. This list of items is identical to the second presentation above, so we have successfully constructed the bijection.

Summary and question

There are 6 "Tietze-like transformations" that we've used to construct the desired bijection between the two definitions of the natural numbers above:

  1. Adding a relation which can be proved from the other relations.
  2. Removing a relation which can be proved from the other relations.
  3. Adding a (nullary) generator along with a relation defining it.
  4. Removing a (nullary) generator along with a relation defining it.
  5. Adding a generator with any arity along with a set of equations constituting a primitive recursive definition of that generator.
  6. Removing a generator with any arity along with a set of equations constituting a primitive recursive definition of that generator.

Transformations 1 through 4 are the Tietze transformations; 5 and 6 are new. (Of course, 3 and 4 are special cases of 5 and 6.)

I'm sure that I'm not the first person to come up with this idea. Have these "Tietze-like transformations" been studied before?

$\endgroup$
7
  • $\begingroup$ I apologize for the great length of this question, and I would greatly appreciate any suggestions for how to trim it down or to make it easier to understand. $\endgroup$ Commented Aug 22, 2020 at 3:08
  • $\begingroup$ You're defining "the" natural numbers as a structure that is unique up to unique isomorphism, but not unique. $\endgroup$
    – YCor
    Commented Aug 22, 2020 at 10:57
  • $\begingroup$ What does 'equivalent' mean? $\endgroup$ Commented Aug 25, 2020 at 18:22
  • $\begingroup$ @KeithKearnes Suppose we have two algebraic structures $A$ and $B$. (By "algebraic structure" I mean an individual algebra, not a variety of algebras or an algebraic theory.) Then I call $A$ and $B$ equivalent if there is some "reasonably chosen" algebraic structure $C$ such that $A$ is simply $C$ with some of the operations removed, and $B$ is also simply $C$ with some of the operations removed. In the natural numbers example here, $A = (\mathbb{N}, 0, S)$, $B = (\mathbb{N}, 0, 1, P)$, and $C = (\mathbb{N}, 0, 1, P, S)$ (where $P$ is the addition operation and $S$ is the successor operation). $\endgroup$ Commented Aug 25, 2020 at 19:01
  • $\begingroup$ What does 'reasonably chosen' mean? $\endgroup$ Commented Aug 25, 2020 at 20:10

1 Answer 1

3
$\begingroup$

Tietze transformations for arbitrary algebraic theories (with respect to their presentations) have been considered in Malbos–Mimram's Homological Computations for Term Rewriting Systems, in the context of rewriting systems (that is, equations are considered directed). They consider (Definition 7) two operations (and their converses):

  • Adding a superfluous operation. Add a new operation $f : n$ and a rewrite $R : t \Rightarrow f(x_1, \ldots, x_n)$ for some term $x_1, \ldots, x_n \vdash t$.
  • Adding a derivable relation. For terms $u, v$ that are interderivable (via rewriting), add a new relation $R : u \Rightarrow v$.

They state (Proposition 8) that two algebraic theories $P$ and $Q$ are isomorphic (and hence have the same models) iff they are Tietze equivalent in that $Q$ may be derived from $P$ through a series of Tietze transformations. (Though they do not give a proof in the paper.)

Their second Tietze operation (and its converse) correspond to your operations 1 and 2. However, their first operation (and its converse) are simpler than your operations 3 through to 6.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .