Give a sentence that's valid for a model whose universe has $n$ elements iff $n$ is even?

Question

More specifically, I am trying to answer one of my predicate calculus homework problems but I have been stuck for awhile.

The question is as follows:

Give a sentence A in the vocabulary $L = \{; R, =\}$, where $R$ is a binary predicate symbol, such that for all $n \in \mathbb{N}$, $n > > 0$, $A$ has a model whose universe has $n$ elements iff $n$ is even. (Hint: Think of $R$ as a pairing relation.)

One idea I came up with was to create a sentence to say that for every even number less than or equal to $n$ that there are two pairs of numbers that add to said even number. However, I run into two problems, the first being the addition function $+$ is not part of my vocabulary, and second the universe $M$ would need to consist of tuples of the form $(x, x'$) where $x$ and $x'$ are equal in value but are not equal in identity, if that makes any sense.

Any help would be greatly appreciated.

Answer 1

Take $A$ as the conjunction of the following sentences. $$ \forall x, \neg R(x,x) $$ $$ \forall x, \forall y, R(x,y) \leftrightarrow R(y,x) $$ $$ \forall x, \exists y, R(x,y) $$ $$ \forall x, \forall y, \forall z, \neg (y = z) \to (R(x,y) \to \neg R(x,z)) $$

Like the hint, we arrange that $R$ pairs elements of the set. The sentences mean 'an element is not paired with itself', 'if x is paired to y, then so is y to x', 'every element is paired to something', 'every element is paired to at most one element'. Alltogether, if $A$ holds in a model $M$, then there exists such a pairing on $M$, and $M$ has an even number of elements.

Answer 2

$$\forall x \exists y \forall z ((R(x,z) \land R(z,x) \land z \not = x) \leftrightarrow z = y)$$

This formula states that for every element in the domain, there is exactly one other element in the domain for which they stand in the relation $R$ to each other. So, if you list all elements, then every time you find an element in the domain that has not been listed yet, then for that element you must find a partner, and that partner cannot be one of the previously listed elements, or else you'd have an element with multiple partners. So, all the elements have to come in pairs of two.