- Thread starter
- #1

...

Intuitively, $\exists^{\geqslant n}$ means "there exists at least $n$ such that".

...

(a) Using counting quantifiers, define a sentence $\varphi_7$ such that $M\models\varphi_7$ iff $|M|>7$.

(b) Using counting quantifiers, define a sentence $\varphi_{23}$ such that $M\models\varphi_{23}$ iff $|M|\leqslant 23$.

(c) Using counting quantifiers, define a sentence $\varphi_{45}$ such that $M\models\varphi_{45}$ iff $|M|=45$.

(d1) Define a first-order sentence $\varphi$ (not using counting quantifiers) that is equivalent to the sentence $\exists^{\geqslant n}x(x=x)$.

(e) Show that every formula using counting quantifiers is equivalent to a formula that does not use counting quantifiers. Conclude that first-order logic with counting quantifiers has the same expressive power as first-order logic.

**(a)**$\exists x\exists^{\geqslant 7}y(x\neq y)$

$\exists^{\geqslant 8}x(\varphi(x)\vee\neg\varphi(x))$

(b) $\neg\exists x\exists^{\geqslant 23}y(x\neq y)$

**(c)**$\exists^{\geqslant 45}x\neg\exists^{\geqslant 45}y\varphi(x,y)$

(d1) $\exists x_1\dots\exists x_n\left(\bigwedge_i x_i=x_i\wedge\bigwedge_{i\neq j} x_i\neq x_j\right)$

(e) $\exists x_1\dots\exists x_n\left(\bigwedge_i\varphi(x_i)\wedge\bigwedge_{i\neq j} x_i\neq x_j\right)$ is equivalent to $\exists^{\geqslant n}x\varphi(x)$.

I have some doubts regarding part (c) and also I do not like that in part (a) I found two solutions. What do you think?