3
$\begingroup$

Before anyone marks this as duplicate, I note that a similar question has been brought up before, but I would like to point out that I am covering new ground here.

Part I

Consider the statement: "There is no largest natural number.".

In formal logic, I can think of two ways to represent this.

  1. $(\forall x \in \mathbb{N})(\exists y \in \mathbb{N})[y>x]$

  2. $(\neg \exists x \in \mathbb{N})(\forall y \in \mathbb{N})[y\leq x]$

Some people felt that the second representation is a better fit for the statement than the first. May I ask, those who are of this view, why? Perhaps, in formal logic writing, is there an unspoken rule for what kind of quantifiers should come before others? For example, should $\forall$ come before $\exists$, or otherwise? Does either make the logic "flow" better?

Part II

Consider the statement: "There is a largest natural number.".

  1. $(\exists x \in \mathbb{N})(\forall y \in \mathbb{N})[y\leq x]$

  2. $(\exists x \in \mathbb{N})(\forall y \in \mathbb{N})[y\leq x]$

Now this is where things start to get really mind-boggling for me. It is trivial to note that the statement in Part II is the negation of the statement in Part I. This would mean that we need only negate 1. and 2. to get 3. and 4. respectively, where 3. and 4. should accurately represent the statement in Part II.

I may have negated 1. and 2. incorrectly, but assuming I did not, negating 1. and 2. actually results in the same statement. Then, since they both negate to give the exact same statement (phrasing), why should either one fit better for the sentence in Part I? Or rather, how is it possible that two sentences, with different phrasings, although same meaning, when negated, can give the same exact sentence? Should they not give two negations with different phrasings but the same meaning as well?

Conclusion

I would like to state that I am new to this area of Mathematics and this topic really intrigues me, so I am trying to find out a little more from all of you bright minds on stackexchange!

I would also like to take this opportunity to seek out any other ways to represent the above statement and its negation, other than those I have mentioned, if any!

$\endgroup$
6
  • $\begingroup$ 3 and 4 look the same... $\endgroup$ – Mauro ALLEGRANZA Feb 4 '20 at 19:35
  • $\begingroup$ That is precisely my point. If you would read the paragraph with the words in bold italics :) $\endgroup$ – Ethan Mark Feb 4 '20 at 19:36
  • $\begingroup$ 1 and 2 are equivalent; the negation of 1 is 5) $\lnot \forall x \ldots$. Applying the same transformations used for 1 and 2, you prove that 5) and 4) are the same. $\endgroup$ – Mauro ALLEGRANZA Feb 4 '20 at 19:38
  • $\begingroup$ A "literal" translation of "There is no..." will be $\lnot \exists x \ldots$. But also in natural language we can agree that to assert that there is no largest number is the same as asserting that for every number there is a larger one. $\endgroup$ – Mauro ALLEGRANZA Feb 4 '20 at 19:40
  • $\begingroup$ Sorry, which statement is 5)? And also, I understand that 1 and 2 are logically equivalent. But in terms of phrasing, they are different and some people have said that 2. is a better representation of the statement than 1.. Part of my question is asking why should that be the case (as in, I would like to hear their views, if possible), knowing very well that both 1. and 2. are logically equivalent, as you have rightly pointed out. $\endgroup$ – Ethan Mark Feb 4 '20 at 19:42
1
$\begingroup$

1 and 2 are not logically equivalent, since purely logically we are dealing with two different predicate symbols $>$ and $\leq$, and hence the negation of $y>x$ is not the same as $y \leq x$.

As such, the logical negation of $2$ is indeed $4$, but $3$ is not the logical negation of $1$. Instead, that would be:

$(\exists x \in \mathbb{N})(\forall y \in \mathbb{N})[\neg y>x]$

But, within the context of arithmetic (or, if you want, once we provide the standard axioms for $\leq$ and $>$), the statements do end up saying the same thing, and so we can say they are arithmetically equivalent, and so from that point of view, both are perfectly acceptable ways to symbolize the statement.

Still, should one be preferred over the other? Does one translate the statement more 'directly'? Here, I can see that someone might argue that 'There is no ...' translates as 'there is not a ..', and thus as $\neg \exists x...$, so I could see that fom that perspective someone might prefer $2$ over $1$

I have never seen anyone arguing that a certain order of quantifiers is to be preferred over the other though, so I don't think that is the reason why some people prefer $2$ over $1$

$\endgroup$
2
  • $\begingroup$ I think you have the closest to what I am looking for :) perhaps it is how 1. and 2. are translated into English that concerns some! I also never would have thought to negate 1. in that way, so thank you for that as well! $\endgroup$ – Ethan Mark Feb 5 '20 at 0:12
  • $\begingroup$ @EthanMark. Glad I could help! :) $\endgroup$ – Bram28 Feb 5 '20 at 0:46
1
$\begingroup$

First, your expression of (2) is just a bit odd. The more usual form would be: $$\neg(\exists x\in\mathbb{N})(\forall y\in\mathbb{N})[y\leq x]$$(1) arises from (2) by pushing the negation through the quantifications according to the usual rules (plus a special property of $>$). If you want the parallel negated statements, then, you should first put a $\neg$ in front of (1), and then push it through. So we get:

  1. $\neg (\forall x\in\mathbb{N})(\exists y\in\mathbb{N})[y> x]$
  2. $(\exists x\in\mathbb{N})(\forall y\in\mathbb{N})[y\leq x]$

These are equivalent, but look different, just like your (1) and (2).

$\endgroup$
3
  • $\begingroup$ Just to be clear, are you saying that $(\neg \exists x \in \mathbb {N})(\forall y \in \mathbb {N})[y \leq x]$ is equivalent to $\neg (\exists x \in \mathbb {N})(\forall y \in \mathbb {N})[y \leq x]$? $\endgroup$ – Ethan Mark Feb 5 '20 at 0:15
  • 1
    $\begingroup$ Yes. Quite generally, $(\neg\exists x)\phi(x)$ is equivalent to $\neg(\exists x\phi(x))$ for any formula $\phi(x)$. They both say that there are no elements satisfying $\phi(x)$. $\endgroup$ – Michael Weiss Feb 5 '20 at 13:50
  • $\begingroup$ Ah. I thought that $\neg$ outside of the brackets would imply that the negation has to be “expanded” into both brackets! $\endgroup$ – Ethan Mark Feb 5 '20 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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