A first-order structure $M$ is *Leibnizian*, if any two distinct
elements $a,b\in M$ satisfy different $1$-types; that is, if there
is some formula $\varphi$ such that $M\models\varphi(a)$ and
$M\models\neg\varphi(b)$. Thus, a Leibnizian model is one in which
you can distinguish any two elements by properties expressible in
the language, or to put it differently, a Leibnizian model is one
in which *indiscernibles are identical*.


In contrast, a structure $M$ is *pointwise definable*, if every
individual element $a\in M$ is definable in $M$, so that there is
some formula $\varphi(x)$ which is satisfied in $M$ only at $x=a$.


Every pointwise definable model is Leibnizian, of course, since
elements can be distinguished by their defining characteristics.
But in general, the concepts are distinct:


* **A Leibnizian model with non-definable elements** (infinite language).
In the language with infinitely many constant symbols
$c\_0,c\_1,\ldots$, consider a model $M$ interpreting them all
differently and having exactly one additional point, which is not
the interpretation of any constant. This model is Leibnizian,
since for any two points, one of them is one of the constants and
hence definable. But the single extra point is not definable in
$M$, because any formula $\varphi$ uses only finitely many of the
constant symbols, and hence cannot define that point, because in
the reduct of the model to the language of $\varphi$, there are
automorphisms that permute all the other points not named by a
constant in $\varphi$. Note that most of the elements of this
model are definable. (Alternatively, one could take an elementary
extension of the model and note that all the unnamed points will
be automorphic.)
* **A Leibnizian model with no definable elements** (infinite language). Consider the
model $\langle
2^\omega,U\_s\rangle\_{s\in 2^{<\omega}}$, where the domain is
Cantor space $2^\omega$, the set of all infinite binary sequences, and the
predicate $U\_s(z)$ holds exactly when $z$ begins with the finite
string $s$. So this is Cantor space with predicates for the basic
open sets. The model is Leibnizian, since any two distinct $y,z$
in Cantor space must disagree on some $U\_s$. But the model has no
definable elements at all, because any formula $\varphi(x)$ uses
only finitely many predicates $U\_s$, and the reduction of the
model to that language has numerous automorphisms with no fixed
points: one can flip bits on any coordinate beyond the length of
any $s$ that appears in $\varphi$.
* **A Leibnizian model with non-definable elements** (finite
language). Consider the language with just one unary function
symbol $S$, and form the *CandyLand* model (named by Arden Koehler), which has 
one lollipop of every finite size, plus one infinite lollipop stick. More precisely, the model has 
infinitely
many base point elements $x\_1,x\_2,x\_3,\ldots$ plus one more
$x\_\infty$, such that none of them is in the range of $S$, and
furthermore, the function $S$ applied to base point $x\_n$ iterates
for exactly $n$ steps before finding a fixed point, and where
$S^k(x\_\infty)$ never repeats. $$x\_1\neq
S(x\_1)=S^2(x\_1),\qquad x\_n\neq S^k(x\_n)\neq
S^n(x\_n)=S^{n+1}(x\_n)\quad(k<n)$$ So $x\_n$ is the base of a size $n$ lollipop. Note that every element
on a finite lollipop is definable by the number of times that $S$
may be applied in reverse and the number of forward iterates
necessary to reach the fixed point. So those points can be
distinguished from any other in the model; and any two distinct
points on the infinite lollipop can be distinguished by their
height, the number of times $S$ can be reversed from them. So the
model is Leibnizian. But meanwhile, none of the elements on the
infinite lollipop is definable. To see this, use a
compactness/upward Löwenheim-Skolem argument to find an
elementary extension of $M$ that has at least one additional
infinite lollipop with a base point, and then note that the two
infinite lollipops are automorphic, and so contain no definable
elements. (Alternatively, one can show that the structure admits
elimination of quantifiers down to the language of $S$ together
with the predicates $H\_n(x)$ that assert that $x$ has height $n$,
meaning that $S$ can be inverted exactly $n$ times but not more
from $x$, but no quantifier-free assertion in this language can
define the base point of the infinite lollipop.)


My question is whether we can have it all:


**Question.** Is there a first-order structure $M$ in a finite
language, such that $M$ is Leibnizian, but has no definable
elements?


Having an elementary example would help to clarify a
certain issue on which Arden Koehler, a graduate student in my seminar this semester, is
writing.



Is there a Leibnizian model with no definable elements, in a finite language?
$\newcommand\Z{\mathbb{Z}}\newcommand\P{\mathbb{P}}$Here is a simple account of a large class of examples.


**Theorem.** With probability one, the structure
$\langle\Z,<,A\rangle$ is Leibnizian and has no definable
elements, where $<$ is the usual order on the integers and
$A\subset\Z$ is a unary predicate chosen randomly with respect to
the coin-flipping probability measure.


**Proof.** Almost surely, a random predicate $A\subset\Z$ is not
periodic (since it gets infinitely many independent chances to
violate the pattern of any given period), and for a non-periodic
$A$, the structure $\langle\Z,<,A\rangle$ is Leibnizian, because
with any $n\in\Z$ as a parameter, we may define all the other
$m\in\Z$ as a certain number of steps above or below $n$, and so
since by non-periodicity the pattern of $A$ above and below $n$
will be different than the corresponding pattern of $A$ above and
below $m$, and this will be an expressible property distinguishing
$n$ and $m$. So with probability one, the structure $\Z\_A$ is
Leibnizian.


Similarly, almost surely $\langle\Z,<,A\rangle$ has
no definable elements. The basic idea (noted by Emil in the comments) is that if
$\varphi$ defines $n$ with positive probability $\epsilon>0$, then
since the measure is translation invariant, it follows that
$\varphi$ defines any given $m$ with the same probability
$\epsilon$. By considering more than $1/\epsilon$ many points, we
would have a positive probability that two different points are
both defined by the same formula, which is a contradiction.


(Note that for any formula $\varphi$ in the language and any
integers $\vec n$, the set of predicates $A\subset\Z$ for which
$\langle\Z,<,A\rangle\models\varphi(\vec n)$ is indeed a
measurable set in the probability space, since this is true in the
case of an atomic formulas, and the quantifiers of $\varphi$
amount to countable unions and intersections. Thus, the question
of whether a given formula $\varphi$ defines $n$ does have some
probability.) **QED**


My earlier post showed that if $A\subset\Z$ is arithmetically generic,
then $\langle\Z,<,A\rangle$ is Leibnizian and has no definable
elements. The reason was that (i) it is Leibnizian, because $A$ is
not periodic; and (ii) if $\varphi$ defined $n$, then some finite
condition $A\cap[-m,m]$ would force this situation; but since that
finite pattern would also arise elsewhere in $A$, we would have a
translation $\pi(A)$ also extending that condition, and so we
would have $\varphi$ defining $\pi^{-1}(n)$ as well, a
contradiction.


MathOverflow collaboration is great,
because the original randomness idea appeared in James's answer,
which I then verified with the forcing argument, and then Emil saw
how to do it easily with an elementary probability argument. And Christian is proposing another argument with this structure that may simplify things further.


