1
$\begingroup$

The class $W$ of well-ordered sets is not first-order axiomatizable. However, it does have an associated first-order theory $Th(W)$. I define a pseudo-well-ordered set to be an ordered set $(S;\leq)$ that satisfies $Th(W)$. My question is, is the class of pseudo-well-ordered set closed under taking substructures? If so, I want a proof. If not, I would like an explicit pseudo-well-ordered set $(S;\leq)$ and a suborder $(T;\leq)$ of $(S;\leq)$ such that $(T;\leq)$ is not pseudo-well-ordered.

$\endgroup$
2
  • $\begingroup$ This is an interesting question! Can you describe how it came up? $\endgroup$
    – TomKern
    Jul 13, 2022 at 4:26
  • $\begingroup$ @TomKern I don't really know, but it just popped into my brain yesterday night. That is all there is to it. $\endgroup$
    – user107952
    Jul 13, 2022 at 14:54

3 Answers 3

5
$\begingroup$

$\omega+\zeta$ satisfies all the first-order sentences satisfied by $\omega$, but $\zeta$ does not satisfy "there is a smallest element".

$\endgroup$
3
  • $\begingroup$ And $\zeta$ here is? $\endgroup$
    – Asaf Karagila
    Jul 13, 2022 at 4:32
  • $\begingroup$ The order type of the integers $\endgroup$
    – TomKern
    Jul 13, 2022 at 4:35
  • $\begingroup$ What is the proof that it satisfies the first-order sentences satisfied by $\omega$? $\endgroup$
    – user107952
    Jul 13, 2022 at 14:51
4
$\begingroup$

Your question has a strong negative answer. Let $S$ be any linear order which is not a well-order (for example, any pseudo-well-order which is not a well-order). Then $S$ has an infinite descending chain $s_0>s_1>s_2>\dots$. Let $T=\{s_i\mid i\in \omega\}$. Then $T$ is a sub-order with no minimal element, so $T$ is not a pseudo-well-order.

So we've shown: every sub-order of $S$ is a pseudo-well-order if and only if $S$ is actually a well-order.

However, there is a positive answer to a related question. A definable sub-order of $S$ is one of the form $\varphi(S)=\{s\in S\mid S\models \varphi(s)\}$ for some formula $\varphi(x)$ with one free variable. Let $S$ be a pseudo-well-order. Then every definable sub-order of $S$ is a pseudo-well-order.

The proof is not hard. Fix a pseudo-well-order $S$ and a formula $\varphi(x)$ with one free variable. Let $\psi\in \mathrm{Th}(W)$. Write $\psi^\varphi$ for the relativization of $\psi$ to $\varphi(x)$. So for any linear order $L$, $L\models \psi^\varphi$ if and only if $\varphi(L)\models \psi$. Now for any well-order $L$, the suborder $\varphi(L)$ is also a well-order, so $\varphi(L)\models \psi$. Thus $L\models \psi^\varphi$, so $\psi^\varphi\in \mathrm{Th}(W)$. Since $S$ is a pseudo-well-order, $S\models \psi^\varphi$, so $\varphi(S)\models \psi$. We've shown that $\varphi(S)\models \mathrm{Th}(W)$, so this definable sub-order is a pseudo-well-order.

$\endgroup$
2
$\begingroup$

Take any countable non-standard model of $\sf PA$ which is elementarily equivalent to the standard one, it is known that the order type of such model has the form $\Bbb{N+Q\times Z}$, therefore it contains a suborder isomorphic to $\Bbb Q$, which is clearly not satisfying the theory of pseudo-well-orders.

$\endgroup$

You must log in to answer this question.

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