Give two (or infinitely many) non-isomorphic models of the following ToL expression

Question

Give two (or infinitely many) non-isomorphic models of the following ToL (total order structure) expression (with predicate symbol $p(\cdot, \cdot)$)

$(\forall x)[¬p(x, x)] \ $ (irreflexivity)

$\, \land \, (\forall x)(\forall y)[p(x, y) \to \lnot p(y, x)] \ $ (strict anti-symmetry)

$\, \land \, (\forall x)(\forall y)(\forall z)[(p(x,y) \land p(y,z)) \to p(x,z)] \ $ (transitivity)

$\, \land \, (\forall x)(\exists y)p(x,y) \ $ (no-maximum)

Additional questions:

(1) What does it mean by "non-isomorphic models"?

(2) Why is the above a ToL?

Answer 1

One model should be obvious: just take as the domain the natural numbers, including $0$ and interpret $p(x,y)$ as $x <y$. It should be clear that the $<$ relation is irreflexive (no number is smaller than itself), asymmetric (if number $x$ is smaller than number $y$, then $y$ is not smaller than $x$), transitive (if $x$ smaller than $y$, and $y$ smaller $z$, then $x$ smaller $z$), and every number is smaller than some other number (i.e. There is always a greater number, i.e. There is no maximum number)

Now, I'll leave it up to you to find a second model, but it has to be non-isomorphic, which means that you can't do something like the natural numbers excluding $0$, while interpreting $p(x,y)$ still as $x<y$, because there is a mapping $f$ between the elements of these two domains such that objects $x$ and $y$ in the first domain stand in the relationship $p$ to each other if and only if $f(x)$ and $f(y)$ stand in that relationship, and that would mean that these two interpretations/models are isomorphic (basically, they have the same 'internal abstract structure'. Or: if you were to 'graph' the model by making the objects nodes and by drawing an arrow from $x$ to $y$ iff $p(x,y)$, and you would not label the nodes, then the graphs would look exactly the same).

Finally, a total order is a relation that is anti-symmetric and transitive (this makes it an order) and such that there is a relationship between any two elements (i.e. For any $x$ and $y$, you either have $p(x,y)$ or $p(y,x)$; this is what makes it total). Interestingly, the expressions given to you clearly make it an order, but do not necessitate totality ... so I am surprised they call it a total order.

Answer 2

Consider the two following models:

1. $(\mathbb{N},<_\mathbb{N})$, where $\mathbb{N}$ is the set of natural numbers and $<_\mathbb{N}$ is the usual strict order on $\mathbb{N}$;

2. $\big((\mathbb{N} \times \{0\}) \cup (\mathbb{N} \times \{1\}), <_{(\mathbb{N} \times \{0\}) \cup (\mathbb{N} \times \{1\})\!}\big)$, where $<_{(\mathbb{N} \times \{0\}) \cup (\mathbb{N} \times \{1\})\!}$ is defined by: $(m,a) <_{(\mathbb{N} \times \{0\}) \cup (\mathbb{N} \times \{1\})\!} (n,b)$ iff either $a < b$, or $a = b$ and $m <_\mathbb{N} n$. Intuitively, you should think of this structure as the axis of all natural numbers followed by another axis of all natural numbers. So, \begin{align} &(0,0) <_{(\mathbb{N} \times \{0\}) \cup (\mathbb{N} \times \{1\})\!} (1,0) <_{(\mathbb{N} \times \{0\}) \cup (\mathbb{N} \times \{1\})\!} (2,0) <_{(\mathbb{N} \times \{0\}) \cup (\mathbb{N} \times \{1\})\!} \ldots \\ <_{(\mathbb{N} \times \{0\}) \cup (\mathbb{N} \times \{1\})\!} &(0,1) <_{(\mathbb{N} \times \{0\}) \cup (\mathbb{N} \times \{1\})\!} (1,1) <_{(\mathbb{N} \times \{0\}) \cup (\mathbb{N} \times \{1\})\!} (2,1) <_{(\mathbb{N} \times \{0\}) \cup (\mathbb{N} \times \{1\})\!} \dots \end{align}

The two models are clearly total strict orders (in particular they are irreflexive, strictly antisymmetric and transitive) without maximums.

Moreover, the two models are not isomorphic, in the sense that there is a property fulfilled by the first model and not by the second one. Indeed, in the first model, for every element $n \in \mathbb{N}$ there is a finite number of smaller elements, i.e. all $m \in \mathbb{N}$ such that $m <_\mathbb{N} n$. On the contrary, in the second model, the element $(0,1) \in (\mathbb{N} \times \{0\}) \cup (\mathbb{N} \times \{1\})$ has an infinite number of smaller elements, all $(n,0) \in (\mathbb{N} \times \{0\}) \cup (\mathbb{N} \times \{1\})$, for any $n \in \mathbb{N}$.

This approach can be easily generalized, yielding infinitely many non-isomorphic total orders without maximums. Consider the family of models $\big((\mathbb{N} \times \{0\}) \cup \dots \cup (\mathbb{N} \times \{k\}), <_{(\mathbb{N} \times \{0\}) \cup \dots \cup (\mathbb{N} \times \{k\})\!}\big)_{k \in \mathbb{N}}$ where $<_{(\mathbb{N} \times \{0\}) \cup \dots \cup (\mathbb{N} \times \{k\})\!}$ is defined by: $(m,a)<_{(\mathbb{N} \times \{0\}) \cup \dots \cup (\mathbb{N} \times \{k\})\!} (n,b)$ iff either $a < b$, or $a = b$ and $m <_\mathbb{N} n$. Intuitively, you should think of the structure $\big((\mathbb{N} \times \{0\}) \cup \dots \cup (\mathbb{N} \times \{k\}), <_{(\mathbb{N} \times \{0\}) \cup \dots \cup (\mathbb{N} \times \{k\})\!}\big)$ as $k$ copies of the axis of all natural numbers, one copy after the other.