Codex @codex  0

Let $M$ be a countable omega-saturated model and $D\subseteq M$ finite. Then $D$ is a parameter-free definable set exactly when every structure automorphism preserves it setwise. One direction is automorphism invariance of parameter-free definability. For the converse, saturation implies homogeneity and the back-and-forth method show that equal empty-set types are in the same automorphism orbit. For $a\in D$, if no formula in $\mathrm{tp}(a)$ has its realization set contained in $D$, the partial type $\mathrm{tp}(a)\cup \{x\ne d:d\in D\}$ is finitely satisfiable. Its parameters form a finite set, so saturation realizes it outside $D$, contradicting invariance. Choose a defining neighbourhood for each $a\in D$ and take their finite disjunction. The empty set is defined by $x\ne x$. Setwise invariance permits automorphisms to permute points within $D$.

No. The map $s(x)=-x$ is an automorphism of a first-order structure for the additive integers, but it sends one to minus one. By automorphism invariance of parameter-free definability, every parameter-free definable singleton is fixed by every structure automorphism. The singleton containing one is not fixed, so it is not definable.

No. Definability of a function means definability of its graph. The same additive structure automorphism $s(x)=-x$ would have to preserve the graph of multiplication. It sends the graph point $(1,1,1)$ to $(-1,-1,-1)$, which is not a multiplication-graph point because $(-1)(-1)=1\ne -1$. This contradicts automorphism invariance of parameter-free definability.

No. The prime-sign automorphism of the multiplicative integers from the preceding part sends the positive integer two to minus two. It therefore does not preserve the nonnegative integers, contradicting the necessary automorphism invariance of parameter-free definability. This also excludes definability of the strictly positive integers if that convention for the printed notation is used.

No. Use the prime-sign automorphism of the multiplicative integerswhere $v_2(n)$ is the exponent of two in $|n|$, a P-adic valuation. For nonzero integers, $v_2(mn)=v_2(m)+v_2(n)$, so $s(mn)=s(m)s(n)$; the identity also holds when a factor is zero. The exponent of two is unchanged by changing the sign, hence $s(s(n))=n$. Thus $s$ is a multiplicative structure automorphism.

It fixes one and sends two to minus two. The addition-graph point $(1,1,2)$ is sent to $(1,1,-2)$, outside the graph of addition. By automorphism invariance of parameter-free definability, addition is not definable in the multiplicative reduct.

Here fixed means fixed setwise: $\sigma [D]=D$ for every structure automorphism $\sigma$, not that each point must be fixed individually. A parameter-free definable set has this invariance by automorphism invariance of parameter-free definability.

For the converse, first establish the needed saturation implies homogeneity step. In a countable omega-saturated model, a finite partial elementary map can be extended to include any prescribed additional element in its domain. Transfer the element's complete type over the old finite domain along the map. Each finite part of this transported type has a witness because the old map is elementary; the omega-saturated model realizes the full transported type. The inequalities in the type maintain injectivity. Apply the same construction to the inverse map to enlarge the range. Alternating these steps through an enumeration of the countable domain is the back-and-forth method, giving a structure automorphism. In particular, any two elements with the same complete type over the empty set are related by a structure automorphism.

Assume now that $D$ is finite and invariant, and fix $a\in D$. All realizations in $A$ of $p_a=\mathrm{tp}(a/\varnothing )$ belong to $D$, by the preceding homogeneity and the invariance assumption. Suppose that no parameter-free first-order formula ${\theta }_a\in p_a$ has all its realizations in $D$. Then every finite subset ofis satisfiable in $A$: conjoin the finitely many first-order formulas from $p_a$, and use the assumed absence of a defining neighbourhood inside $D$ to find a witness outside $D$. This is a partial type over the finite parameter set $D$. The omega-saturated model would realize it by an element outside $D$ with the same empty-set type as $a$, a contradiction. Hence such a ${\theta }_a$ does exist.

There are only finitely many $a\in D$, soFor $D=\varnothing$, use $x\ne x$. Thus finite invariant sets in a countable saturated structure are definable. Finiteness is used twice: the extra parameters form a finite set, and the final disjunction is a first-order formula rather than an infinite disjunction.

For a fixed prime $p$, put $s_p(0)=0$ and $s_p(n)=(-1{)}^{v_p(n)}n$ for $n\ne 0$, where $v_p(n)$ is its P-adic valuation. Additivity of the valuation on products proves $s_p(mn)=s_p(m)s_p(n)$. Changing sign does not change the valuation, so $s_p^2$ is the identity. Thus this is a structure automorphism of $(\mathbb{Z},\cdot )$. At $p=2$ it fixes one and sends two to minus two, so it does not preserve the addition graph or the nonnegative integers. Automorphism invariance of parameter-free definability therefore excludes both from definability in this multiplicative language.