# Definable sets in infinite structures

Working in first order logic, let $\mathcal{M} = (M,I)$ be an $\mathcal{L}_A$-structure, where $A$ consists only of the unary function symbol $F_1$ (here, $M$ is the universe and $I: \{x_i\} \rightarrow M$ the interpretation of variables in $M$). I was asked to come up with

1. an example of an infinite $\mathcal{M}$ in which every singleton $\{m\}$ in $M$ is definable, and
2. an example of an infinite $\mathcal{M}$ in which no nonempty finite subset of $M$ is definable.

I was hoping to clear up some of my confusion related to the meaning of "$A$ consists only of $F_1$" which seems to be holding me up:

If I take this to mean that $A$ also includes the symbol $\hat{=}$, then can I not take care of (1) right off the bat and make $\{m\}$ trivially definable from parameters in the set $\{m\}$ using $\varphi(x_1, x_2) := (x_1 \hat{=} x_2)$? Then only those $\mathcal{M}$-assignments $\nu$ with $\nu(x_2) = m = \nu(x_1)$ witness membership in $\{m\}$. And I don't see how any automorphism of $\mathcal{M}$ can expand the set definable via $\varphi[m,m]$ beyond $\{m\}$, since $m$, itself a parameter here, must be a fixed point of any such automorphism.

But then under this reading, how do I block against definability of singletons in the second case whatever the $\mathcal{M}$? The $\varphi(x_1, x_2)$ above seems to work whatever the $\mathcal{M}$ unless I am grossly misunderstanding the satisfaction notion for formulas of the form $(a \hat{=} b)$.

[And even so, I don't see how I could read "$A$ consists only of $F_1$" to mean that $A$ excludes the symbol "$\hat{=}$". If I excluded $\hat{=}$ from $A$, how would anything be definable? I wouldn't even have $\mathcal{L}_A$-formulas to define things with, since giving up $\hat{=}$ and predicate symbols I would not even be able to form the atomic formulas, right?]

• Perhaps by definable they mean definable over $\varnothing$, i.e. without parameters? That way 1. is not so trivial and 2. is possible. Commented Oct 21, 2017 at 21:31
• @Adayah Ah, that might be so. Does anything jump out as incorrect to you in my question? In particular, am I right in thinking that the $\varphi$ above would cause a problem for 2 if "definable" here means definable from parameters in a nonempty subset of $M$? Commented Oct 21, 2017 at 21:35
• Regardless of whether we allow parameters, we don't mean "definable in a nonempty subset" when we say "definable," so that is wrong. Commented Oct 22, 2017 at 1:13
• @NoahSchweber Sure, thank you. I meant my follow-up question to Adayah's comment as more of a hypothetical to check that the formula saying "I am $m$" would indeed be problematic for 2 if I were to misread "definable" (as I did as you both have pointed out) as definable $\textit{from}$ parameters in a nonempty subset of the universe. Commented Oct 22, 2017 at 1:35
• I'm just not sure where the "in a nonempty subset of the universe" came from in the first place - it's not part of the question explicitly, and it's not part of the definition of definability (from parameters or not). Commented Oct 22, 2017 at 1:37

If you consider "definable without parameters" then you can consider: - $$(\mathbb N,<)$$ in which every singleton is definable, - $$(\mathbb Z,<)$$ in which no non-empty finite set is definable.