0
$\begingroup$

let P(m,n) be "n is greater than or equal to m" where the domain is the set of nonnegative integers. What are the truth values of the following? Provide your argument

  • $∃n∀mP(m,n)$
  • $∀m∃nP(m,n)$

So I have been looking at this question for a while now, but I still don't understand how I'm supposed to do it. Any kind of assistance would be appreciated.

$\endgroup$
3
$\begingroup$

Let the domain be the set of all non-negative integers, $\mathbb N = \{0, 1, 2, \ldots\}$.

Let $P(m,n)$ denote "$n \geq m$".

  • $∃n\,∀m\,P(m,n):$ "There exists an $n \in \mathbb N$ such that for every $m \in n,\;n \geq m$." Is there any particular non-negative integer(s) $n$ that is/are greater than all other such integers? NO. There is no "greatest integer". Suppose such $n$ existed. But we still have that $p = n+1 \gt n$, etc.

  • $∀m\,∃n\,P(m,n)$ Now this statement expresses the following: "For every integer $m \in \mathbb N,\;$ there is some integer $n\in \mathbb N$ such that $n \geq m$. This is true. Whatever $m$ we choose, there exists an integer $n$ (for example, $n = m+1$) such that $n \geq m.$

Key note: It is crucial here to note how the order of the quantifiers significantly changes the meaning of the statement!

$\endgroup$
1
  • $\begingroup$ Needs another TU! +1 $\endgroup$ – Amzoti Oct 9 '13 at 0:31
1
$\begingroup$

Try writing it out in sentences. For the first we have there exists $n$ such that for all $m\in\mathbb N$, $n\geq m$. Is this true? What do you get when you write out the second?

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