Skip to content

Comments on Quantifiers

  • Can you find formulas \(\varphi\) such that:

    1. If \(A\) is a model of \(\varphi\), then \(A\) has exactly one element.
    2. If \(A\) is a model of \(\varphi\), then \(A\) has at least two elements of the domain.
    3. If \(A\) is a model of \(\varphi\), then \(A\) has exactly two elements in the domain.
    4. For each \(n\in\mathbb{N}\), if \(A\) is a model of \(\varphi\), then \(A\) has exactly \(n\) elements in the domain.
    5. If \(A\) is a model of \(\varphi\), then the domain has infinitely many elements.

  • Consider the following three formulas:

    1. \(\forall x\forall y\forall z ((R(x,y)\wedge R(y,z)) \rightarrow R(x,z))\)
    2. \(\forall x\exists y R(x,y)\)
    3. \(\forall x \neg R(x,x)\)

    The conjunction of any two formulas can be satisfied in a model with finitely many elements in the domain. However, the conjunction of all three formulas can only be satisfied on a domain with infinitely many elements.

  • Let \(\mathsf{Q}\) be the theory consisting of the following formulas:

    (Q1) \(\quad\forall x(0\ne S(x))\)

    (Q2) \(\quad\forall x\forall y(S(x)=S(y)\rightarrow x=y)\)

    (Q3) \(\quad\forall x(x\ne 0\rightarrow \exists y(x= S(y)))\)

    (Q4) \(\quad\forall x (x \mathop{+} 0=x)\)

    (Q5) \(\quad\forall x \forall y(x\mathop{+} S(y)= S(x+y))\)

    (Q6) \(\quad\forall x (x\mathop{\times}0 = 0)\)

    (Q7) \(\quad\forall x \forall y(x\mathop{\times} S(y)=x \mathop{\times} y + x)\)

    We have the following:

    1. \(\mathsf{Q}\vdash \bar{2}\ne \bar{0}\)
    2. \(\mathsf{Q}\vdash \bar{0}\ne \bar{2}\)
    3. \(\mathsf{Q}\vdash \bar{0}\mathop{+} \bar{2} = \bar{2}\)
    4. \(\mathsf{Q}\vdash \bar{2}\mathop{+} \bar{0} = \bar{2}\)
    5. For all \(n\in\mathbb{N}\), \(\mathsf{Q}\vdash \bar{0} \mathop{+} \bar{n} = \bar{n}\)
    6. \(\mathsf{Q}\not\vdash \forall x(\bar{0} \mathop{+} x = x)\)

  • Suppose that \(T\) is a set of sentences such that for all \(n\in\mathbb{N}\), \(T\) has a model with \(n\) elements in the domain. Then \(T\) has a model with infinitely many elements in its domain.