Idiomatic mathematical english statement for ∃x[P(x) ∧ ∀y(P(y) → y ≤ x)]

Question

I have been working on problems from Velleman's How to Prove book and hit upon the following problem:

Translate the following statements into idiomatic mathematical English:

∃x[P(x) ∧ ∀y(P(y) → y ≤ x)], where P(x) means “x is a perfect number.”

I worked out the problem in the following steps:

* ∃x[P(x) ∧ ∀y(P(y) → y ≤ x)]
* ∃x(P(x) ∧ ∀y(If y is a perfect number then y is less than or equal
  to x.))
* ∃x(P(x) ∧ Every perfect number is less than or equal to x.)
* Every perfect number is less than or equal to some perfect number.

But the idiomatic answer seems to be:

There exists a perfect number such that all the other perfect numbers are either less or equal to it.

I would like to know if there is any problem with my solution ? Also, I would like to know if there are some general guidelines while forming the idiomatic mathematics statement (or any statement) from logical connectives.

Answer 1

The problem with your translation is that there is ambiguity about the scope of the quantifiers you use. In particular the sentence expresses the claim that "There is a perfect number, so that every perfect number is less than or equal to the first." Or as Git Gud says, there is a maximum perfect number.

Unfortunately, what you have written is, most naturally, read as expressing that the claim that "For every perfect number, there is a perfect number greater than or equal to it." These two are not logically equivalent. For instance, we can prove your translation by noting that every perfect number is less than or equal to itself, however this does not suffice to prove that there is an upper-bound on all the perfect numbers considered at once. For a similar example, where it is easier to see the fallacy, instead interpret $P$ as "$n$ is a prime number." Then certainly for every prime $n$ there is a prime $m$ (take $m=n$) so that $n\leq m$. However it is not the case that there is a prime $n$ so that every prime is less than or equal to $n$, as there are infinitely many primes.

Formally speaking you have confused a claim of the form $\exists \forall$ with $\forall \exists$.

Answer 2

You messed up the order of the quantifiers. What you wrote translates back to be: $$ \forall y ~ [P(y) \to \exists x ~ (P(x) \land y \leq x)] $$ In your version, this perfect number $x$ might depend on the perfect number $y$ that is chosen. In the original version however, the perfect number $x$ must be chosen first (independently of $y$).

---

To illustrate why order matters, consider the following two statements (where we assume that our universe is the set of all integers): $$ \exists a ~ \forall b ~ [ a > b] \qquad\text{and}\qquad \forall b ~ \exists a ~ [ a > b] $$ The first statement is false, since there isn't some magical integer $a$ that is bigger than any integer $b$ that we pick (for example, it fails if $b = a + 7$). The second statement is true, since given any integer $b$, I can find an integer $a$ (for example, take $a = b + 5$) that is bigger than $b$.

Answer 3

$\exists x [P(x) \wedge \forall y [P(y) \to y\leq x]$

This is read from left to right as: "There exists a number such that it is perfect and for all numbers that if they are perfect it follows that they are less than or equal to it."

In more natural language, this can be stated as: "There exists a perfect number that will be greater than or equal to every perfect number," or possibly "There is a perfect number that no other perfect number is greater than."

Or to paraphrase: "There exists a largest perfect number."

---

Always read propositional logic from left to right. The order of the qualifiers affects the meaning of the statement.