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.
$\begingroup$ $\endgroup$
2 
- $\begingroup$ This is an interesting question! Can you describe how it came up? $\endgroup$TomKern– TomKern2022-07-13 04:26:46 +00:00Commented 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– user1079522022-07-13 14:54:21 +00:00Commented Jul 13, 2022 at 14:54
Add a comment |
3 Answers
$\begingroup$ $\endgroup$
3 $\omega+\zeta$ satisfies all the first-order sentences satisfied by $\omega$, but $\zeta$ does not satisfy "there is a smallest element".
- $\begingroup$ And $\zeta$ here is? $\endgroup$2022-07-13 04:32:59 +00:00Commented Jul 13, 2022 at 4:32
- 1$\begingroup$ The order type of the integers $\endgroup$TomKern– TomKern2022-07-13 04:35:37 +00:00Commented Jul 13, 2022 at 4:35
- $\begingroup$ What is the proof that it satisfies the first-order sentences satisfied by $\omega$? $\endgroup$user107952– user1079522022-07-13 14:51:36 +00:00Commented Jul 13, 2022 at 14:51
$\begingroup$ $\endgroup$
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.
$\begingroup$ $\endgroup$
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.
