Originally Posted by

**kumpel** I need help in the following problem:

Let $\displaystyle \mathcal{L}=\mathcal{L}()$ be a (first order) language. Find $\displaystyle \mathcal{L}$-fomulae $\displaystyle \phi_{\leq n}, \phi_{= n}, \phi_{\geq n}$ that for any $\displaystyle \mathcal{L}$-structure $\displaystyle \mathcal{A}$ with support $\displaystyle A=|\mathcal{A}|$:

$\displaystyle \mathcal{A}\models \phi_{\leq n} \Leftrightarrow |A|\leq n$

$\displaystyle \mathcal{A}\models \phi_{= n} \Leftrightarrow |A|= n$

$\displaystyle \mathcal{A}\models \phi_{\geq n} \Leftrightarrow |A|\geq n$.

Some ideas: Because the signature is empty, there are no relations, no functions and no constants. The only possible formulae consist of terms like $\displaystyle x_i=x_j$ with variables and the logical signs (,),$\displaystyle \neg,\vee, \exists$ (others excluded by demand).

For $\displaystyle \phi_{= n}$ I guess something like:

$\displaystyle \exists x_i\left[\neg \left(\bigvee_{j=1}^{n}(x_i=x_j)\right)\vee\left(\ bigvee_{l=1}^{n-1}\bigvee_{m=l+1}^{n}(x_l=x_m) \right)\right]$

but this seems quite complex. Is there a shorter form? Or is it even correct? And the others?