Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
I prefer this option: "The set of perfect numbers has a maximum". The answer given to you can be improved by removing either 'other' or 'or equal to'. –  Git Gud Aug 19 at 23:11
    
Actually, if you ask your average number theorist how they would state this (for perfect numbers, at least) they would say "there are finitely many perfect numbers" although this folds in some extra knowledge about upper-bounded subsets of the natural numbers being finite. –  Mario Carneiro Aug 20 at 5:32

3 Answers 3

up vote 5 down vote accepted

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$.

share|improve this answer
    
Thanks, I can see how my translation is ambiguous now. Regarding, the idiomatic answer given in my question does the word "other perfect numbers" in the answer fit well because for all will include all the numbers including x. ? –  Sibi Aug 19 at 23:39
1  
That is a peculiarity in the sample answer that I don't like. "Other" seems to imply that the statement only applies if $y\neq x$ but as you point out, that is not part of the FOL statement. If you go this way you want to claim that it is implicit that $x\leq x$, and of course this is true if you interpret $\leq$ as the less-than-or-equal relation. However if you had a different interpretation, it could be false. This is why I prefer something like "There is a largest perfect number." –  James Aug 19 at 23:55
    
Thanks, another naive question: Does the order matter if the quantifiers are the same: ∀x∀y ? –  Sibi Aug 20 at 0:20
1  
@Sibi No, order does not matter in that case. We have $\forall x\forall y\iff \forall y\forall x$, $\exists x\exists y\iff \exists y\exists x$, and $\exists x\forall y\implies \forall y\exists x$, but the last is not bidirectional in general. This is part of the reason why adjacent quantifiers of the same type are often grouped together, as $\forall x,y$ or if it is a restricted quantifier, $\forall x,y\in X$ as an abbreviation to $\forall x(x\in X\to\forall y(y\in X\to\dots))$. –  Mario Carneiro Aug 20 at 2:41
    
@MarioCarneiro Thanks, that made it very clear. –  Sibi Aug 20 at 10:16

$\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.

share|improve this answer
1  
The main problem with this kind of direct translation into English is that English quickly runs out of antecedents to distinguish $x,y$ from each other in the last part. Here you used "they" and "it"; I don't know what you would do for three quantifiers. –  Mario Carneiro Aug 20 at 2:48
1  
@MarioCarneiro I'd just start naming things. "There exists a number, call it X, such that X is a perfect number and for any number, call it Y, then if Y is a perfect number it follows that Y is at most X." –  Graham Kemp Aug 20 at 4:55
    
@GrahamKemp I think his point is that you should always be naming things, rather than waiting for confusion to set in. –  ssdecontrol Aug 20 at 6:52

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.