2

I'm trying to work my way through Herbert Enderton's A Mathematical Introduction to Logic, and I'm currently stuck on the following exercise (3.2.3, to be precise):

Let $\mathfrak{A}$ be a model of $\text{Th }\mathfrak{N}_L$. For $a$ and $b$ in $\vert\mathfrak{A}\vert$ define the equivalence relation: \begin{align*}a\sim b\Longleftrightarrow\ &\mathbf{S}^\mathfrak{A}\text{ can be applied a finite number of times to one of}\\&a,b\text{ to reach the other.}\end{align*}Let $[a]$ be the equivalence class to which $a$ belongs. Order equivalence classes by $$[a]\prec[b]\text{ iff }a<^\mathfrak{A}b\text{ and }a\nsim b.$$Show that this is a well-defined ordering on the set of equivalence classes.

where $\mathfrak{N}_L=\left(\mathbb{N};0,S,<\right)$ and $S$ is the successor function.

I'm really not sure how to go about solving this problem, any help would be greatly appreciated. In particular, I'm not sure what the difference between an ordering and a well-defined ordering is. I do know, though, that for a relation to be an ordering, it needs to be transitive and satisfy trichotomy on the set.

Demosthene
  • 5,420

1 Answers1

3

Well-defined ordering is not a particular type of order; it means that the order so defined is well-defined, i.e. it does not depend on the single representative of the equivalence class.

In full :

having defined the equivalence classes by :

$[a] ≺ [b]$ iff $a <^A b$ and $a≁b$,

if we consider : $a_1 ∼ a$ and $b_1 ∼ b$, it still holds that :

$[a_1] ≺ [b_1]$.

For transitivity, we have to show that :

if $[a] ≺ [b]$ and $[b] ≺ [c]$, then $[a] ≺ [c]$.

The "obvious part" : if $a < b$ and $b < c$, then $a < c$, follows from Axiom (L5) [see page 194].

We have to prove also that : if $a ≁ b$ and $b ≁ c$, then $a ≁ c$.

Assume not, i.e. $a ∼ c$; this means that, for some $n$ : $c=S^na$ (because : $a < c$).

But this implies $c \in [a]$ and thus, by "well-definition" of the equivalence relation, that $[c]=[a]$.

So, by $[c]=[a]$ and $[a] ≺ [b]$ we have that : $[c] ≺ [b]$ and this implies $c < b$, contradicting the fact that $b < c$.

Mauro ALLEGRANZA
  • 94,169