Welcome to our community

Be a part of something great, join today!

counting quantifier

Andrei

Member
Jan 18, 2013
36
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

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
(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).