2
$\begingroup$

I remember a high school book I read a long time ago explains that every statement in the form of $\forall x\in D,P(x)$ can be turned into an implication.

For example, isn't

"For every real number $x$, $x^2$ is non-negative."

equivalent to

"If $x$ is a real number, then $x^2$ is non-negative."?

However, I came across a wikipedia article about universal quantifier that says something about bounded quantifier, which I haven't heard before. Then I thought, and confirmed, that bounded quantifier can actually be written as unbounded quantifier, and that the statement I read in the book I said above is actually a bounded version.

For example, $\forall x\in D,P(x)$ becomes $\forall x,[x\in D \implies P(x)]$ My question is: was what I read in the book correct? That every bounded universal statement can be converted into an implication? Another one is: Can or can't every (unbounded) universal statement become implication?

I ask this because I am confused. I thought every universal statement can become an implication, the wikipedia article and the fact that I cannot find (google) any other article about my thought make me want to post this question. Besides, don't we use arguably the same starting premise when we want to prove a universal statement and an implication? Both use "Let x be ..." or "Assume that ..." or "Take arbitrary x ..." (the latter especially is used most often when facing a universal statement) as starting premise, don't they?

Thanks for the answer. ^^

ADDITION: Why can't $\forall x\in D,P(x)$ just become $x\in D \implies P(x)$ instead of $\forall x,[x\in D \implies P(x)]$?

$\endgroup$
9
  • $\begingroup$ See Restricted quantifier as well as restricted or relativized quantification. $\endgroup$ Jun 6 '18 at 13:24
  • $\begingroup$ Thanks. Then, in my example, the statement "If $x$ is a real number, then $x^2$ is non-negative." is just a predicate whose truth depends on $x$. Am I reading that correctly? $\endgroup$
    – bms
    Jun 6 '18 at 13:32
  • $\begingroup$ Correct; but often the assertion "If $x$ is a real number, then $x^2$ is non-negative" is read as implicitly universally quantified. $\endgroup$ Jun 6 '18 at 13:36
  • $\begingroup$ I see. However, does this mean we cannot simply write $\forall x,P(x)$ without knowing what or where $x$ comes from? And this means that $\forall x,P(x)$ actually means $\forall x \in X,P(x)$ for some set $X$, right? $\endgroup$
    – bms
    Jun 6 '18 at 13:50
  • $\begingroup$ Not clear ... the formula $\forall x P(x)$ is obviously formally correct. But it is ... a formula. How we interpret the predicate symol $P$ ? If we interpret it as "$x \text { is Even}$" in the domain or universe of natural numbers, the resulting statement will be FALSE. If instead we interpret it as "$x \text { is Mortal}$" in the domain or universe of human beings, the resulting statement will be TRUE. $\endgroup$ Jun 6 '18 at 13:54
5
$\begingroup$

$\forall x \in D \colon P(x)$ is simply an abbreviation for the formula $\forall x ( x \in D \implies P(x))$ -- there really isn't more to it. You will find this convention in any decent textbook that covers the basics of first order logic.

And you can't replace it by $x \in D \implies P(x)$ for the simple reason that the latter is not a sentence -- it has unbounded free variables (namely $x$). Hence it's not equivalent to the sentence $\forall x \in D \colon P(x)$.

$\endgroup$
8
  • $\begingroup$ I see. So are you saying that every implication has to be properly quantified, or just in this case? Because I thought that the statement "If $x \in \mathbb{R}$, then $x^2$ is non-negative" is valid every day. Do you mean that it is not valid until I add "For every $x$" in the beginning?" $\endgroup$
    – bms
    Jun 6 '18 at 13:16
  • $\begingroup$ @bms Valid and true are different concepts: $\forall x \in \mathbb R \colon x^2 \ge 0$ is a true sentence. $x \in \mathbb R \implies x^2 \ge 0$ is not a sentence at all but it is a vaid formulae -- it's true for every assignment of $x$. $\endgroup$ Jun 6 '18 at 13:21
  • $\begingroup$ Hmm.. I have more questions actually. However, if it feels like I need to go through some definitions, could you suggest me one or two college level (ungrad or grad) logic textbooks that elementary cover this topic? $\endgroup$
    – bms
    Jun 6 '18 at 13:25
  • 1
    $\begingroup$ @bms That's right. However most mathematicians won't be that pedantic and often implicitly assume universal quantifiers ranging over every free variable. You will find this implicit assumption spelled out at least in some textbooks by logicians -- they will talk about the 'universal closure' of these formulae. $\endgroup$ Jun 6 '18 at 13:44
  • 1
    $\begingroup$ While your answer is certainly correct for typical textbooks on first-order logic, it's not in general true that the bounded quantifier is just a shorthand. If the underlying foundational system is some type theory, then unbounded quantifiers may not even be meaningful. Furthermore, in type theories that have a universal type but are based on a variant of 3-valued logic, bounded quantification can be weaker than the quantified implication. Philosophically speaking, we think in terms of bounded quantifiers. Even the symmetry in "¬∀x∈S ( P(x) ) ≡ ∃x∈S ( ¬P(x) )" is broken by the 'shorthand'. =) $\endgroup$
    – user21820
    Jun 16 '18 at 8:34

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.