Proving that p -> q

  • #1
1,462
44
This might be a silly question. Suppose that I am trying to prove that ##p \implies q##. And suppose that after assuming ##p## to be true, I derive a statement that is always false, i.e. I find that ##p \implies F##. What does this say about ##p##? What does this say about the original conditional ##p \implies q##?
 

Answers and Replies

  • #2
14,389
11,705
This might be a silly question. Suppose that I am trying to prove that ##p \implies q##. And suppose that after assuming ##p## to be true, I derive a statement that is always false, i.e. I find that ##p \implies F##. What does this say about ##p##? What does this say about the original conditional ##p \implies q##?
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
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.
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?
 
  • #4
14,389
11,705
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?
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.
 
  • Like
Likes Mr Davis 97
  • #5
1,462
44
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.
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))##?
 
  • #6
14,389
11,705
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))##?
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 an any, i.e. make no restrictions on ##n##. Another way is the set theoretic notation ##\{\,n\, : \,P(n)\,\}\subseteq \{\,n\, : \,Q(n)\,\}##.
 
  • #7
34,687
6,394
This might be a silly question. Suppose that I am trying to prove that ##p \implies q##. And suppose that after assuming ##p## to be true, I derive a statement that is always false, i.e. I find that ##p \implies F##. What does this say about ##p##? What does this say about the original conditional ##p \implies q##?
Adding something that doesn't seem to have been mentioned.
An implication such as ##p \implies q## is false only when p is true and q is false. For all other combinations of the truth values of p and q, the implication is true. In other words, if both p and q are true, the implication is true, and if p is false, the implication is also true, regardless of the truth value of q.
 
  • #8
Stephen Tashi
Science Advisor
7,583
1,472
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))##?
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) )## ?
 
  • #9
1,462
44
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) )## ?
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).

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
## \neg (\exists n (P(n) \wedge \neg Q(n))) \\ \neg (\exists n P(n) \wedge \exists n \neg Q(n)) ##
Those two statement are not equivalent.

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).
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 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##".
 
  • Like
Likes Mr Davis 97 and fresh_42
  • #11
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:
  1. Assume ##p##, then prove ##q## (direct proof)
  2. Assume ##\neg q##, then prove ##\neg p## (proof by contrapositive)
  3. Prove ##\neg p##
  4. Prove ##q##
To prove ##p\implies q## is false, prove ##p## and ##\neg q##.
 
Last edited:

Related Threads on Proving that p -> q

  • 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
Top