Counting Quantifiers: Exercise 2.20 Solutions

[Andrei1]

This is about exercise 2.20 from Hedman's course. Let me give my solutions to it.

...
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?

 

[Evgeny.Makarov]

(a) $\exists x\exists^{\geqslant 7}y(x\neq y)$
$\exists^{\geqslant 8}x(\varphi(x)\vee\neg\varphi(x))$

This is OK except that the answer does not say what $\varphi(x)$ is. Of course, $\varphi$ can be any formula. Another variant is from (d1): $\exists^{\geqslant 8}x(x=x)$. There is nothing wrong that there are several correct answers.

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

Correct.

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

This does not say what $\varphi(x,y)$ is. The simplest answer is the conjunction of two formulas: one according to the pattern in (a) and the other in (b), e.g., $(\exists^{\geqslant 45}x=x)\land\neg(\exists^{\geqslant 46}x=x)$.

(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)$

This is correct, but the formula can be shortened. First, $\bigwedge_i x_i=x_i$ is not necessary and $\bigwedge_{i\neq j} x_i\neq x_j$, which includes both $x_1\ne x_2$ and $x_2\ne x_1$, can be replaced with $\bigwedge_{i<j} x_i\neq x_j$.

(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)$.

Correct, but can be shorted as in (d1).