MHB Counting Quantifiers: Exercise 2.20 Solutions

  • Thread starter Thread starter Andrei1
  • Start date Start date
  • Tags Tags
    Counting
AI Thread Summary
The discussion focuses on solutions to exercise 2.20 from Hedman's course regarding counting quantifiers in first-order logic. Participants propose various definitions for sentences that express conditions on the size of a model, such as having more than 7 elements or exactly 45 elements. There is a consensus that multiple correct answers exist for these definitions, though some participants express concerns about the clarity of certain variables used in the solutions. Additionally, it is noted that every formula with counting quantifiers can be expressed without them, confirming the expressive equivalence of both forms of first-order logic. The conversation highlights the flexibility and nuances in formulating logical expressions.
Andrei1
Messages
36
Reaction score
0
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?
 
Physics news on Phys.org
Andrei said:
(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.

Andrei said:
(b) $\neg\exists x\exists^{\geqslant 23}y(x\neq y)$
Correct.

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

Andrei said:
(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$.

Andrei said:
(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).
 

Similar threads

Back
Top