order property vs. antisymmetric property

Question

The definition of order property is well known:for a first-order theory $T$ the order property means that for some first-order formula $\phi(\bar{x},\bar{y})$ linearly orders in $M$ some infinite $\mathbf{I}\subseteq {}^{lg(\bar{x})}M$. Now I have come with another concept: what if $\phi(\bar{x},\bar{y})$ is asymmetric on some infinite $A\subseteq M, M$ a model of $T$? Is this stronger or weaker property than OP ? A brief justification is required.

EDIT for the comment below that this definition is not standard I'm including a snippet from Shelah's book Classification theory.

EDIT

Answer 1

Let me recall the definitions. Fix a complete theory $T$.

• A partitioned formula is a formula $\varphi(\overline{x},\overline{y})$, where the free variables in $\varphi$ are partitioned into the tuples $\overline{x}$ and $\overline{y}$.
• A partitioned formula has the order property if (in some model $M$ of $T$) there are tuples $(\overline{a}_i)_{i\in \omega}\in M^{\overline{x}}$ and $(\overline{b}_i)_{i\in \omega}\in M^{\overline{y}}$ such that $M\models \varphi(\overline{a}_i,\overline{b}_j)$ if and only if $i<j$. [Note that I write $M^{\overline{x}}$ for the set of tuples from $M$ that can be substituted for the variables $\overline{x}$, and similarly for $\overline{y}$.]
• A formula $\varphi(x_1,\dots,x_n)$ has Property E if (in some model $M$ of $T$) there is an infinite set $A$ such that for every $n$-tuple of distinct elements $a_1,\dots,a_n$ from $A$, we there are permutations $\sigma,\sigma'\in S_n$ such that $M\models \varphi(a_{\sigma(1)},\dots,a_{\sigma(n)})$ and $M\models \lnot \varphi(a_{\sigma'(1)},\dots,a_{\sigma'(n)})$. [Note that I have never heard this called "Property E" except in the quote from Shelah in your question. In his original paper, Ehrenfeucht talks about "definable relations which are antisymmetric and connected in $A$".]

Note that the order property is about partitioned formulas, while Property E is about ordinary (unpartitioned) formulas, so at the level of formulas, it doesn't really make sense to ask which is stronger. What is true (and I suppose this is what Shelah means when he writes that Property E is stronger) is that if $\varphi(x_1,\dots,x_n)$ has Property E, then there is a partition of the variables $x_1,\dots,x_n$ into $\overline{x}$ and $\overline{y}$ such that $\varphi(\overline{x},\overline{y})$ has the order property.

Sketch of proof: Suppose $\varphi$ has Property E, witnessed by an infinite set $A$. Enumerate $A$ as a sequence $I = (a_i)_{i\in \omega}$. Using Ramsey's Theorem and compactness, find an indiscernible sequence $I' = (a_q')_{q\in \mathbb{Q}}$ realizing the EM-type of $I$ in an elementary extension $M\preceq M'$. Then $I'$ is an indiscernible sequence that is not an indiscernible set, and in particular there are fixed permutations $\sigma$ and $\sigma'$ such that for every increasing sequence $q_1<\dots<q_n$, we have $M'\models \varphi(a_{q_{\sigma(1)}},\dots,a_{q_{\sigma(n)}})$ and $M'\models \lnot \varphi(a_{q_{\sigma'(1)}},\dots,a_{q_{\sigma'(n)}})$. Now you can follow the usual proof that in stable theories, every indiscernible sequence is an indiscernible set, and observe that from this failure of $I'$ to be an indiscernible set, the proof gives an instance of the order property witnessed by a partitioned version of $\varphi$.

On the other hand, if you take a formula with the order property, its "unpartitioned" form does not necessarily have Property E. For example, consider the structure in the language $\{R\}$, where $R$ is a binary relation, with domain $\{a_i\mid i\in \omega\}\cup \{b_i\mid i\in \omega\}$, such that $a_iRb_j$ if and only if $i<j$. Then $xRy$ has the order property, but $x_1Rx_2$ does not have Property E.

As a final comment, I want to observe that at the level of theories, if $T$ has a formula with the order property (i.e. $T$ is unstable), then $T$ has a formula with Property E, as long as we're willing to allow the formula witnessing Property E to have $n$ tuples of variables instead of $n$ single variables, and to allow the set $A$ to be a set of tuples instead of a set of singletons.

Indeed, if $\varphi(\overline{x},\overline{y})$ has the order property, then letting $A = \{(\overline{a}_i,\overline{b}_i)\mid i\in \omega\}$, the formula $\theta(\overline{x}_1,\overline{y}_1,\overline{x}_2,\overline{y}_2)$ defined by $\varphi(\overline{x}_1,\overline{y}_2)$ is connected and antisymmetric in the set $A$. If we take $i<j$, then $M\models \theta(\overline{a}_i,\overline{b}_i,\overline{a}_j,\overline{b}_j)$, while $M\models \lnot\theta(\overline{a}_j,\overline{b}_j,\overline{a}_i,\overline{b}_i)$. Here the two permutations in $S_2$ witnessing Property E are the identity and the transposition swapping $(\overline{a}_i,\overline{b}_i)$ with $(\overline{a}_j,\overline{b}_j)$.

So the properties are closely related! Summary:

• If a formula has Property E, some partitioned version has the order property.
• Therefore, if a theory has a formula with Property E, it is unstable.
• If a partitioned formula has the order property, it is not always the case that it has Property E after forgetting the partition.
• If a theory is unstable, then it may not have a formula with Property E as defined by Ehrenfeucht, but it does have a formula with a natural generalization of Property E, where we consider tuples, not just singletons.