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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.