4

In Immerman's book "Descriptive complexity" he says that

$A \cong B$ implies $A = B$ when $A$ and $B$ are totally ordered structures.

See: (Descriptive Complexity, Neil immerman)

Definition $\bf 1.21\quad$ (Isomorphism of Unordered Structures) Let $\cal A$ and $\cal B$ be structures of vocabulary $\tau=\langle R_1^{a_1},...,R_r^{a_r},c_1,...,c_2\rangle$. We say that $\cal A$ is isomorphic to $\cal B$, written, ${\cal A}\cong{\cal B}$, iff there is a map $f:|{\cal A}|\to|{\cal B}|$ with the following properties:

  1. $f$ is $1:1$ and onto.
  2. For every input relation symbol $R_i$ and for every $a_i$-tuple of elements of $\cal|A|$, $e_1,...,e_{a_i}$, $$\langle e_1,...,e_{a_i}\rangle\in R_i^{\cal A}\qquad\Leftrightarrow\qquad\langle f(e_1),...,f(e_{a_i})\rangle\in R_i^{\cal B}$$
  3. For every input constant symbol $c_i$, $f(c_i^{\cal A})=c_i^{\cal B}$.

The map $f$ is called an isomorphism. $$\tag*{$\square$}$$ $\quad$ As an example, see graphs $G$ and $H$ in Figure 1.1 which are isomorphic using the map that adds one mod five to the numbers of the vertices of $G$.
$\quad$ Note that we have defined isomorphism so that they need only preserve the input symbols, not the ordering and other numeric relations. If we included the oredring relation then we would have $\cal A\cong B$ iff $\cal A=B$. To be completely precise, we should call the mapping $f$ defined above an "isomorphism of unordered structures" and say that $\cal A$ and $\cal B$ are "isomorphic as unordered structures". (Note also that, since "unordered string" does not make sense, neither does the concept of isomorphism for strings. By a strict interpretation of Definition 1.21, two strings would be isomorphic as unordered structures iff they had the same number of each symbol.)
$\quad$ The following proposition is basic.

He defines the input relations as the relations that are not ordering, plus, times.

However, if we define the structures $(\{0,1\},\leq)$ and $(\{1,2\},\leq)$ are clearly isomorphic as ordered structures ($\leq$ is the usual ordering on the natural numbers). They are not equal, however. So what does he mean exactly?

user153330
  • 1,726
user265233
  • 41
  • I am not sure this 'ordering' here means partially ordering or something like that. Doesn't it say anything about it in the context? – Berci Aug 28 '15 at 23:59
  • It should be a total order. – user265233 Aug 29 '15 at 00:00
  • 3
    In the context of descriptive complexity, "ordered structure" usually means a finite structure whose underlying set (also called its universe or its domain) is of the form ${1,2,\dots,n}$ for some natural number $n$ and whose basic relations include the standard linear ordering relation of natural numbers (restricted to ${1,2,\dots,n}$). With this understanding, Immerman's assertion is correct. (With the usual, model-theoretic notion of "ordered structure", Immerman's statement would not be correct, because of counterexamples like yours.) – Andreas Blass Aug 29 '15 at 00:15
  • @AndreasBlass: this is an answer. – Berci Aug 29 '15 at 01:08

1 Answers1

3

At Barci's suggestion and in order not to unnecessarily leave this question unanswered, I'm repeating my comment as an answer. In the context of descriptive complexity, "ordered structure" usually means a finite structure whose underlying set (also called its universe or its domain) is of the form $\{1,2,\dots,n\}$ for some natural number $n$, and whose basic relations include the standard ordering of the natural numbers (restricted to $\{1,2,\dots,n\}$). With this understanding, Immerman's assertion is correct. (With the usual, model-theoretic notion of "ordered structure, Immerman's statement would not be correct, because of counterexamples like yours.)

Addendum: Some authors prefer to use $\{0,1,\dots,n-1\}$ instead of $\{1,2,\dots,n\}$. Either way, one of the two structures in your counterexample would not count as an ordered structure, but different authors might disagree as to which one it is.

Andreas Blass
  • 71,833