Describe finite structure up to isomorphism as model of two sentences.

I'm trying to solve the following exercise:

Let $$A$$ be a finite structure.

Find $$σ_1\in$$ Th$$(A)$$ such that any model of $$σ_1$$ has universe of the same cardinality as $$A$$.

Now assume $$L$$ (the language we're using) has finitely many symbols. Find a single existential sentence $$σ_2$$ (where an existential sentence is one of the form $$\exists x_1 ... \exists x_n\varphi$$ where $$\varphi$$ is quantifier free) such that any model of $$\lbrace σ_1, σ_2\rbrace$$ is isomorphic to $$A$$.

The first part seems simple - if we assume $$|A|=n$$, then we can just take a formula

$$σ_1 = \exists x_1 ... \exists x_n(x_1\neq x_2 \wedge x_1\neq x_3 \wedge ... \wedge x_{n-1}\neq x_n \wedge \forall y (y=x_1 \lor y=x_2 \lor ... \lor y=x_n ))$$

saying that there are at least $$n$$ elements and at most $$n$$ elements.

I have no idea what form $$σ_2$$ would take - I tried thinking about a simple case where $$|A|=1$$ and the language contains only a unary relation symbol $$R$$, but even then I don't know what you could do. Clearly in this case either $$R^A = \emptyset$$ or $$R^A =A$$, but then without knowing what interpretation $$A$$ gives to $$R$$ I don't see how you'd settle on the sentence. In this case it'd be easy enough to distinguish cases and just say e.g. that if $$R^A =A$$ then let $$σ_2 = \exists x Rx$$ but I struggle to see how you'd generalise to any arbitrary finite language and size of $$A$$.

I have no idea where to begin, so any help you could offer would be really appreciated.

Well let's start by observing that the idea (where our language consists of a single unary relation symbol $$R$$)

if $$R^A=A$$ then let $$\sigma_2=\exists xRx$$.

does not work if there is more than one element in $$A$$: all this $$\sigma_2$$ says is that $$R^A$$ has at least one element. Already there are two (up to isomorphism) structures with two elements which satisfy $$\sigma_2$$ but are not isomorphic (one in which $$R$$ holds once, and one in which $$R$$ holds twice).

"$$\forall xRx$$" would do the job but of course we don't want that. So how can we do things with just existential quantifiers?

Well, let's think about a structure with two elements $$u,v$$ where $$R$$ holds of $$u$$ but not $$v$$. We can describe this as follows:

• There are two elements.

• There is one element where $$R$$ holds.

• There is one element where $$R$$ fails.

The first point is taken care of by $$\sigma_1$$. The second and third can be written together as $$(\exists xRx)\wedge (\exists x\neg Rx),$$ which in turn can be put in the form desired as

$$\exists x,y(Rx\wedge \neg Ry)$$.

This last form suggests what we should be doing in general: to describe an $$n$$-element structure, we first fix some enumeration $$a_1,...,a_n$$ of its elements and then

consider a sentence of the form $$\exists x_1,...,x_n([\mathsf{stuff}])$$ where "$$\mathsf{stuff}$$" describes how the $$a_i$$s interact - with $$x_i$$ interpreted as $$a_i$$.

This does not work, however: consider, in the language with a single unary relation $$R$$, a structure with three elements where $$R$$ holds on exactly one element versus a structure with three elements where $$R$$ holds on exactly two elements. If we look at the corresponding sentences of the type above, we get equivalent sentences (which we definitely don't want) since

nothing is keeping the variables distinct.

We can fix this by

folding appropriate distinctness clauses into the idea above, so that e.g. in the $$R$$-structure with two elements where $$R$$ holds once we'd get $$\exists x,y(x\not=y\wedge Rx\wedge\neg Ry).$$

At this point there are a couple questions to ask yourself:

• Where did we use the assumption of a finite language?

• Why do we need $$\sigma_1$$ as well as this $$\sigma_2$$?

• This was super helpful, and I see what I was missing. Thank you! – oxfri Oct 29 '20 at 0:13