Undergrad Proving p -> q: What Does a False Derivation Mean?

[Mr Davis 97]

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$?

 

[fresh_42]

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.

 

[Mr Davis 97]

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?

 

[fresh_42]

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.

 

[Mr Davis 97]

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))$?

 

[fresh_42]

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)\,\}$.

 

[Mark44]

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.

 

[Stephen Tashi]

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) )$ ?

 

[Mr Davis 97]

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.

 

[Stephen Tashi]

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

 

[Dan Christensen]

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