Logic – Translating Universal and Existential Quantifiers

article-writinglogiclogic-translationpredicate-logicquantifiers

Consider this proposition (which I know is false):

$$(\exists y{\in}\mathbb Z)\,(\forall x{\in}\mathbb Z)\,(y > x).$$

I am wondering whether the analogy of picking a variable value according to the order in which their quantifiers appear in the statement is correct: in the above, we pick an integer due to the existential quantifier then afterwards pick an integer according to the universal quantifier.

I am also wondering whether these informal translations (in which there are two distinct pickings, the first before the second) are accurate:

  • We can pick an integer which is greater than any integer we could pick.
  • We can pick an integer which is greater than every integer we could pick.

Is ‘every’ or ‘any’ better here for the universal quantifier?

Best Answer

$$(\exists y{\in}\mathbb Z)\,(\forall x{\in}\mathbb Z)\,(y > x)$$

Letting the discourse domain be implicit, your formula means $\Big(\exists y\;\big(\forall x \; y > x\big)\Big);$ here we pick a particular $y$ such that whichever $x$ we consider, $y>x.$

On the other hand, in the formula $\Big(\forall x \;\big(\exists y \; y > x\big)\Big),$ whichever $x$ we consider, the $y$ that we pick (notice that $y$ here generally depends on $x$) is such that $y>x.$

Observe that we are iteratively applying $(y>x),$ in a sense going back and forth between—rather than chronologically handling—the quantifiers.

  • We can pick an integer which is greater than any integer we could pick.
  • We can pick an integer which is greater than every integer we could pick.

A correction: “we can pick an integer that is greater than any/every integer we could pick”. Use ‘that’ for a restrictive clause, which adds specification or narrows in on a class of objects; use ‘which’ for a nonrestrictive clause, which adds supplementary, non-essential information. While many people disregard this distinction, it does help with precise communication, and is certainly relevant when translating formal logic to English.

Your suggestions are clear; however, a slight rephrasing (e.g., “some $y$ is greater than every $x$”) renders them ambiguous due to hanging quantifiers, so do look out for that.

Is ‘every’ or ‘any’ better here for the universal quantifier?

In this case, ‘every’ and ‘any’ interchangeably correspond to universal quantification. However, it's worth noting that sometimes, the word ‘any’ corresponds to ‘∃’ instead of ‘∀’! To wit:

  1. $\color\red{\textbf{If any}}$ intruder enters, the alarm will go off.

    $(\color\red{\boldsymbol{\exists}} x\, Ex)\color\red{\boldsymbol{\implies}} A$

  2. $\color\red{\textbf{If any}}$ command is understood by the dog, it is a genius.

    $(\color\red{\boldsymbol{\forall}} x\, Ux)\color\red{\boldsymbol{\implies }}G$

  3. She does $\color\red{\textbf{not}}$ have $\color\red{\textbf{any}}$ disease.

    She does not have some disease.

    $\color\red{\boldsymbol{\lnot \exists}} x\, Dx$

    $\forall x\, \lnot Dx$

    For every disease, she does not have it.

  4. She does not have every disease.

    $\lnot \forall x\, Dx$

    $\exists x\, \lnot Dx$

    For some disease, she does not have it.

The sentences within each group above are equivalent to one another. Although some of the black sentences sound stilted (after all, natural language is quite context-dependent), they are at least unambiguous; on the other hand, the trickier red sentences indicate that using the word ‘any’ judiciously can prevent ambiguity and mistranslation. In particular:

  • the meaning of ‘if any’ is sometimes ambiguous between ‘if some’ and ‘if every’, but frequently idiomatically means the former;
  • not any’ means ‘not some.