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.

Assuming all the variables are naturals, why are those two equal? I don't get how $\implies$ is introduced in the latter equation: $(∀x)(x∈D \implies P(x))$

Thanks.

share|improve this question
    
In the latter equation, you're looking at all $x$, but all you want is that $P(x)$ occurs whenever $x\in D$. I think that's where $\implies$ comes in. –  Ian Coley Sep 17 '13 at 20:50

3 Answers 3

up vote 1 down vote accepted

As Peter Smith notes, most commonly

$$\forall x \in D.\ P(x) \quad \text{ is defined as }\quad\forall x.\ x \in D \implies P(x).$$

However, should this be unsatisfactory explanation for you, there is alternative argument below.


First \begin{align} \mathtt{true} \implies P(x) \quad \text{ is equivalent to } \quad P(x), \\ \mathtt{false} \implies P(x) \quad \text{ is equivalent to } \quad \mathtt{true}. \end{align} Hence,

\begin{align} \forall x \in D.\ P(x) &\quad\text{ is equivalent to }\quad \forall x \in D.\ x \in D \implies P(x), \\ \forall x \notin D.\ \mathtt{true} &\quad\text{ is equivalent to }\quad \forall x \notin D.\ x \in D \implies P(x). \end{align} Then, if we join them with $$P'(x) = \begin{cases}P(x) & \text{for }x \in D \\ \mathtt{true} & \text{for }x \notin D\end{cases}$$

we get

$$\forall x.\ P'(x) \quad\text{ is equivalent to }\quad \forall x.\ x \in D \implies P(x).$$

I hope this helps $\ddot\smile$

share|improve this answer
    
No, it doesn't help. The straightforward answer is that $(\forall x \in D)(P(x)$ is usually just defined as a slick abbreviation for $(\forall x)(x\in D \implies P(x))$. –  Peter Smith Sep 17 '13 at 22:35
    
@PeterSmith Usually it is defined this way, but it does not have to be, e.g. if the universe is not a set, perhaps there is some specific semantic to it. Of course, point taken, this is beyond the scope of this question. –  dtldarek Sep 17 '13 at 22:45

If you interpret both D and P as sets, both of them say precisely that D is a subset of P.

share|improve this answer

Because that's what the $\forall x\in D. P(x)$ notation is defined to mean.

share|improve this answer
1  
This is, of course, exactly right! –  Peter Smith Sep 17 '13 at 22:32

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.