Let $\mathcal{L}=\{\leq\}$ and $\mathcal{A}=\{\mathbb{N},\leq\}$, and $\mathcal{B}=\{K,\leq\}$ where $K=\{(a,b)\in\mathbb{N}^2:a\in\mathbb{N} \text{ and } b=1 \text{ or } b=2\}$ and pairs $(a,b)$ have the natural ordering on themselves but pairs $(a,2)$ are strictly greater then all pairs of the form $(a,1)$

Show that $\mathcal{A}\not\equiv\mathcal{B}$

So I believe what I want is a sentence which is true in one structure but not true in the other structure.

I can obviously identify some things that are properties of the naturals that won't be properties of the set $K$ like every natural has only finitely many elements less then or equal to it. But not ones that can be expressed in a single sentence.

  • 1
    $\begingroup$ In $\mathbb N$ we have only one number that has no predecessor while in $K$ we have two : $(0,1)$ and $(0,2)$. $\endgroup$ – Mauro ALLEGRANZA Oct 16 '19 at 15:08
  • 1
    $\begingroup$ Right, but without constant $1$, and the $+$ operation in $\mathcal{L}$ can this be expressed as a sentence? $\endgroup$ – AColoredReptile Oct 16 '19 at 15:09
  • $\begingroup$ What does it mean to be a predecessor? $x$ is a predecessor of $y$ if $x$ is the biggest thing less than $y$. Can you express this with only $<$? $\endgroup$ – HallaSurvivor Oct 16 '19 at 15:11
  • $\begingroup$ Ok $\neg\exists_z(x\leq z \wedge z\leq y)$ $\endgroup$ – AColoredReptile Oct 16 '19 at 15:17
  • $\begingroup$ @MauroALLEGRANZA That doesn't work either: your $z$ could be $m$ or any element less than $n$. You want $n\leq m \land n\neq m \land \forall z( (n\leq z \land z\leq m)\rightarrow (z = n\lor z = m))$ $\endgroup$ – Alex Kruckman Oct 16 '19 at 17:05

Exactly one element of $\mathcal{A}$ has no predecessors, while two distinct elements of $\mathcal{B}$ have no predecessors. See if you can write $\text{isPred}(x,y)$ and use this to distinguish the structures.

I hope this helps ^_^

| cite | improve this answer | |
  • 1
    $\begingroup$ Thanks I have a good idea of what to do now. $\endgroup$ – AColoredReptile Oct 16 '19 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.