- #1

- 1,462

- 44

- I
- Thread starter Mr Davis 97
- Start date

- #1

- 1,462

- 44

- #2

fresh_42

Mentor

- 14,389

- 11,705

It says ##p \Longrightarrow q## is true, because ##p \Longrightarrow F \Longrightarrow q~,## and ##p = F## since you cannot get false out of true. However, it says nothing about ##q## itself.

- #3

- 1,462

- 44

What about if I try to prove the statement ##\forall n \in \mathbb{N} (P(n) \implies Q (n))##. I let ##n \in \mathbb{N}## and assume ##P(n)## is true, and find that ##P(n) \implies F##. What does this say about ##Q(n)## and the quantified statement as a whole?It says ##p \Longrightarrow q## is true, because ##p \Longrightarrow F \Longrightarrow q~,## and ##p = F## since you cannot get false out of true. However, it says nothing about ##q## itself.

- #4

fresh_42

Mentor

- 14,389

- 11,705

If you find ##P(n) \Longrightarrow F## then there is an ##n_0 \in \mathbb{N}## such ##P(n_0)=F##. If there wasn't any restrictions on ##n##, then ##P(n)=F## for all ##n##. The same as before: ##P(n_0) \Longrightarrow F \Longrightarrow Q(n_0)##, that is the implication is true, because ##P(n_0)## is false. You still don't know anything about ##Q(n)##, since you only deduced it from a false statement. But you can deduce any statement from a false one, true or not.What about if I try to prove the statement ##\forall n \in \mathbb{N} (P(n) \implies Q (n))##. I let ##n \in \mathbb{N}## and assume ##P(n)## is true, and find that ##P(n) \implies F##. What does this say about ##Q(n)## and the quantified statement as a whole?

- #5

- 1,462

- 44

One more question. With regard to quantifiers in general, is there any way to "distribute" the universal quantifier inside of the implication ##\forall n \in \mathbb{N} (P(n) \implies Q (n))##?If you find ##P(n) \Longrightarrow F## then there is an ##n_0 \in \mathbb{N}## such ##P(n_0)=F##. If there wasn't any restrictions on ##n##, then ##P(n)=F## for all ##n##. The same as before: ##P(n_0) \Longrightarrow F \Longrightarrow Q(n_0)##, that is the implication is true, because ##P(n_0)## is false. You still don't know anything about ##Q(n)##, since you only deduced it from a false statement. But you can deduce any statement from a false one, true or not.

- #6

fresh_42

Mentor

- 14,389

- 11,705

I'm not sure where you're heading at. The question is a bit as if you asked, whether there is a way to make the domain of a function part of the function. It is two different levels: ##P(n) \Longrightarrow Q(n)## is only a statement about a single number. You can only translate the all quantor to anOne more question. With regard to quantifiers in general, is there any way to "distribute" the universal quantifier inside of the implication ##\forall n \in \mathbb{N} (P(n) \implies Q (n))##?

- #7

Mark44

Mentor

- 34,687

- 6,394

Adding something that doesn't seem to have been mentioned.

An implication such as ##p \implies q## is false

- #8

Stephen Tashi

Science Advisor

- 7,583

- 1,472

Are you asking about the relation between ##\forall n \in \mathbb{N} (P(n) \implies Q(n))## and ##(\forall j \in \mathbb{N}\ P(j)) \implies ( \forall k \in \mathbb{N} \ Q(k) )## ?One more question. With regard to quantifiers in general, is there any way to "distribute" the universal quantifier inside of the implication ##\forall n \in \mathbb{N} (P(n) \implies Q (n))##?

- #9

- 1,462

- 44

I am mainly trying to understand quantifiers in more detail, without having to go study a whole book on logic (which I should do at some point).Are you asking about the relation between ##\forall n \in \mathbb{N} (P(n) \implies Q(n))## and ##(\forall j \in \mathbb{N}\ P(j)) \implies ( \forall k \in \mathbb{N} \ Q(k) )## ?

What is wrong with the following argument:

##\forall n (P(n) \implies Q(n)) \\ \forall n (\neg (P(n) \wedge \neg Q(n))) \\ \neg (\exists n (P(n) \wedge \neg Q(n))) \\ \neg (\exists n P(n) \wedge \exists n \neg Q(n)) \\ \neg (\exists n P(n) \wedge \neg \forall n Q(n)) \\ \exists n P(n) \implies \forall n Q(n)##

I feel like I'm doing something wrong because I don't see how the two statements are intuitively logically equivalent.

- #10

Stephen Tashi

Science Advisor

- 7,583

- 1,472

Those two statement are not equivalent.## \neg (\exists n (P(n) \wedge \neg Q(n))) \\ \neg (\exists n P(n) \wedge \exists n \neg Q(n)) ##

Few people who study mathematics also study quantifiers to the extent of being able to do complicated symbolic manipulations of quantified expressions. Instead they rely on a sophisticated version of "common sense" to think about quantified expressions. It's complicated to state the formal rules for manipulating symbolic expressions containing quantifiers. If you are trying to discover such rules for yourself, it will take a lot of work.I am mainly trying to understand quantifiers in more detail, without having to go study a whole book on logic (which I should do at some point).

I suggest that you use a variety of variables in order to make the "scope" of quantifiers clear. For example, instead of ## \neg (\exists n P(n) \wedge \exists n \neg Q(n)) ##, it is clearer to write

## \neg (\exists n P(n) \wedge \exists k \neg Q(k)) ##

or even

## \neg (\exists j P(j) \wedge \exists k \neg Q(k)) ##

If you use "##n##" every place a variable is required, you can confuse yourself into believing that one "##n##" has something to do with a different "##n##".

- #11

- 1

- 0

From the truth table for ##A\implies B##, if ##B## is false and ##A\implies B## is true, then the only possibility is that ##A## is false. Applying this fact to your problem, ##p## must be false and, therefore, ##p \implies q## must be true regardless of what ##q## may be (See (3) below).

Generally speaking, if you want to prove ##p\implies q## is true, you can do either of the following:

Generally speaking, if you want to prove ##p\implies q## is true, you can do either of the following:

- Assume ##p##, then prove ##q## (direct proof)
- Assume ##\neg q##, then prove ##\neg p## (proof by contrapositive)
- Prove ##\neg p##
- Prove ##q##

Last edited:

- Last Post

- Replies
- 6

- Views
- 17K

- Replies
- 12

- Views
- 5K

- Replies
- 2

- Views
- 6K

- Last Post

- Replies
- 3

- Views
- 780

- Last Post

- Replies
- 2

- Views
- 571

- Replies
- 3

- Views
- 12K

- Last Post

- Replies
- 4

- Views
- 2K

- Last Post

- Replies
- 5

- Views
- 7K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 4

- Views
- 5K