16
$\begingroup$

Other students in office hour said this is the correct form $(\forall x)(\exists y)(y>x)$ { for all x natural number, there exists y such that y is greater than x }

But "there does not exist a largest natural number " $\neg(\exists x)(x\text{ largest natural number})$

Am I even close ?

$\endgroup$
  • 2
    $\begingroup$ You have said "it is not true that for all $x$ there exists $y$ such that $y>x$". Think about whether that is an appropriate translation. $\endgroup$ – Ian Apr 19 '17 at 0:17
  • 2
    $\begingroup$ $\forall x \exists y (y > x)$ for $\forall x \exists y (y > x)$. Formatting tips here. $\endgroup$ – Em. Apr 19 '17 at 3:30
  • 1
    $\begingroup$ This was edited to say something completely different from what it originally said. Don't do that, because it makes the answers based on the original question seem nonsensical. $\endgroup$ – Jim Balter Apr 20 '17 at 6:31
43
$\begingroup$

The formula $\forall x \exists y (y > x)$ reads "for any $x$ there is a $y$ which is larger than $x$" which says that any $x$ is not largest and therefore no $x$ is largest. You can also use the formula $\forall \equiv \neg\exists\neg$ to get

$$ \begin{align*} \forall x \exists y (y > x) &\equiv \neg\exists x \neg \exists y (y > x) \\ &\equiv \neg \exists x \forall y \neg(y > x) \\ &\equiv \neg \exists x \forall y (y \le x) \end{align*} $$

which says that "there is no $x$ such that every $y$ is less than or equal to $x$". This better fits with the "there does not exist a largest natural number" phrasing.

$\endgroup$
5
$\begingroup$

The statement as you have written it is false. If you read it out loud, $x$ has to be chosen before $y$ and for all $x$ you can find a greater $y$. You want to say that if you choose $y$. You want to choose $y$ first, then say that it is not greater than all $x$.

$\endgroup$
  • $\begingroup$ so, (Ay)(Ex)(y>x)??? $\endgroup$ – Quency Caroline Apr 19 '17 at 0:26
  • $\begingroup$ No, given $y$ there has to be a larger $x$, so it should be $x \gt y$ $\endgroup$ – Ross Millikan Apr 19 '17 at 1:07
  • $\begingroup$ @QuencyCaroline That statement says every natural number has one smaler than it, which is not true. $\endgroup$ – immibis Apr 19 '17 at 1:37
  • $\begingroup$ $(\forall x)(\exists y)(y>x)$ is false? Assuming the universe of discourse is the natural numbers, can you give a counterexample? $\endgroup$ – jwodder Apr 19 '17 at 17:59
  • $\begingroup$ @jwodder: when the answer was written there was a not sign before the sentence. As you have written it and the question now has it, it is true. $\endgroup$ – Ross Millikan Apr 19 '17 at 18:41
5
$\begingroup$

Yes, you are close.

So far, you have:

$\neg \exists x \,\,(x\text{ largest natural number})$

Since you're looking for the "symbolic form", your next step is to convert "largest natural number" to symbols.

  • Note that "largest natural number" is the same thing as "number that is greater than all other natural numbers";

  • To make things easier, note that the above is the same thing as "number that is greater than or equal to all natural numbers" (therefore, including itself without a problem!);

  • Further rephrase it as "number such that all numbers are less than or equal to it", so we have:

$x$ is a number such that all numbers are less than or equal to $x$

  • Observe that this last sentence can be easily translated to symbols as

$$\forall n \,\,\, n \le x$$

Now, just plug that into your original sentence, obtaining:

$\neg \exists x \,\,(\forall n \,\,\, n \le x)$


Note 1: This is not the only correct way to do this. It is possible to express the same fact differently.

Note 2: in the context of this question, it is clear that we are talking about natural numbers. But generally, it would be better to specify this, by writing:

$\neg \exists x \in \mathbb{N} \,\,(\forall n \in \mathbb{N} \,\,\, n \le x)$


Bonus: The students you mentioned are correct too. They chose to rephrase the sentence in a different sentence (but still equivalent). Instead of saying "there is no largest natural number", they are saying "all natural numbers have the property of being smaller than some number", which is the same thing, in the end.

$\endgroup$
1
$\begingroup$

It depends on whether with largest natural number you mean a greatest or a maximal element, though the difference would be important only for a non-total order.

If $(X,<)$ is a partially ordered set, we say that $a\in X$ is

  • a greatest element if $\forall x\in X\colon (x< a\lor x=a)$
  • a maximal element if $\forall x\in X\neg(a<x)$

(In a totally ordered set, exactly one of $x<a$, $x=a$, $x>a$ must be true, hence therre the notions of greatest and maximal element coincide).

Hence "There is no $a$ such that $a$ is a greatest/maximal element" translates "literally" to either $$ \neg\exists a\in \Bbb N\colon \forall x\in\Bbb N\colon (x<a\lor x=a)$$ or $$ \neg\exists a\in \Bbb N\colon \forall x\in\Bbb N\colon \neg(a<x)$$

If you make use of "$\neg\exists=\forall\neg$" and "$\neg\forall=\exists\neg$", you might equivalently write $$ \forall a\in \Bbb N\colon \exists x\in\Bbb N\colon (x\not <a\land x\ne a)$$ and $$ \forall a\in \Bbb N\colon \exists x\in\Bbb N\colon (a<x),$$ respectively.

$\endgroup$
1
$\begingroup$

In English: "there is no natural n, for which all natural k would be smaller than n".

$\lnot \exists n \forall k (k, n) \in \mathbb{N}^2 \land k < n$

$\endgroup$
1
$\begingroup$

I was going to write this in a comment, but I think it's better if I gave an answer.

I'm going to begin by pointing out things about the two statements in the question.

The first statement does have the intended meaning. I think it can still be made more precise.

The second statement is circular, or ambiguous at best. There is no way of saying what the largest natural number is until it has been decided definitely whether it exists or not.

Finally, although the domain has been described in the worded statement, for the logical statement to make sense, it must include the correct domain.

Since T. Gunn's answer very nicely covers the question, I will instead give an example of a correct statement which is useful in the study of modern algebra, how number (and other) sets are constructed, the relations between them, and the rigorous framework used to describe these ideas:

$$\forall n \in \mathbb N,n + 1 > n \land n + 1 \in \mathbb N$$

Though, to be precise this is a logically equivalent statement, not an identical one. And I have assumed, the addition operator and ordering relation ">" have already been defined.

This statement makes the intended meaning, and its demonstration, more explicit. It describes a function which guarantees the required property will be satisfied.

$\endgroup$
  • $\begingroup$ If the addition operator has already been defined (as a function $\mathbb N\times\mathbb N\to\mathbb N$), then the proposition $n+1\in\mathbb N$ is redundant. $\endgroup$ – Rahul Apr 19 '17 at 22:27
  • $\begingroup$ @Rahul Fair point. I just thought writing it out would make the underlying framework more apparent. $\endgroup$ – ThisIsNotAnId Apr 19 '17 at 23:28
-1
$\begingroup$

Since you are interested in formalisms, I would suggest to rephrase the statement to be more formal. In Mathematical logic, one usually uses quantors (similarly, the negation operator) and parentheses in the following way: $$ \forall x (\; \text{logical statement} \;) $$ So, nesting this, your statement becomes $$ \forall x \in \mathbb{N}\left(\,\exists y \in \mathbb{N}\left(\,y>x\right) \right) $$ and the other statement, the one you were asking for, becomes $$ \neg (\,\exists M \in \mathbb{N} \,(\,\forall l \in \mathbb{N} \,(\,M \geq l)) $$ where I replaced your variable-symbol $x$ by $M$ and used $l$ as the variable-symbol for your natural number.

$\endgroup$

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.