Finding sentences for models

Question

This is coming from a past paper (Ref: Oxford 2005, Paper B1 Foundations)

Suppose we have $\mathcal{L}$ a first-order language with equality, with connectives $\neg, \rightarrow$, quantifier $\forall$ and whose only nonlogical symbol is $R$ some binary-relation symbol.

Question: I want to find sets of sentences whose models are precisely:

1. partially ordered sets
2. sets of size $n$ for some fixed non-zero natural number $n$

I really have no idea how to approach this type of question where you are asked to give sentences whose models are some specific collection. I have seen very few examples of this king of question.

My thoughts are as follows:

For (1), we want something like:

• ($A_1$) $\forall x (xRx)$
• ($A_2$) $\forall x \forall y ((xRy \land yRx)\rightarrow x=y)$
• ($A_3$) $\forall x \forall y \forall z ((xRy \land yRz) \rightarrow xRz)$

Then the sentence we want is $A=A_1 \land A_2 \land A_3$

All I'm going off here is that this resembles to way one defines a partial ordering on an arbitrary set.

For (2), I don't really have any idea.

If someone could verify my thoughts on (1) and assist with (2) it would be very appreciated.

Answer 1

HINT: Recall that $\exists x\varphi$ is equivalent to $\lnot\forall x\lnot\varphi$. Use this to write a sentence whose content "There exists $x_1,\ldots,x_n$ which are different from one another, and for any $x$, $x$ is equal to $x_1$ or $x_2$ or ... $x_n$."

Note by the way, that $\land$ and $\lor$ are not in your language either, but can be written as shorthands for a combination of $\lnot$ and $\rightarrow$. Other than this point, the first part is correct. These are the axioms asserting that $R$ is a partially ordered set.