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.

I need to prove the statement $\forall x (A(x) \to B(x)) \to (\forall xA(x) \to \forall xB(x))$ is logically valid. Here's what I'm thinking.

Assume that the statement is not logically valid. This means that the left hand side of the main implication must be true for some values while the right hand side is false for some values. Specifically $$(A(c) \to B(c)) \to (A(d) \to B(e))$$. This is where I'm stuck. If I could have instantiated all the quantifiers to c, then the right hand side of the implication would tell me A(c) would be true and B(c) would be false in order to have that whole statement be false (these correspond to A(d) and B(e)). Thus, the left hand side would also be false, which contradicts the assumption that it is true.

So am I allowed to instantiate everything to c? I don't think so, that wouldn't be general at all. So am I on the right track or completely off?

I've also tried converting to conjunctive form but that didn't go anywhere.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

Assume the statement is false. Then the hypothesis ($\forall{x}.A(x)\rightarrow B(x))$ is true and the conclusion ($\forall{x}.A(x)\rightarrow \forall{x}.B(x))$ is false. Since the conclusion is false, its hypothesis ($\forall{x}.A(x)$) is true and its conclusion ($\forall{x}.B(x)$) is false. So there exists $c$ such that $\neg B(c)$. Specializing the other two universal quantifiers, we have $A(c)\rightarrow B(c)$ and $A(c)$, from which we deduce $B(c)$, bringing us to the desired contradiction.

share|improve this answer
    
You should preface everything by saying that if the statement is not logically valid, there is a model $\mathcal A$ in which the statement is falsified. In this case $c$ is an element of $\mathcal A$. –  David Harris Jan 24 '12 at 20:56
add comment

Attempting a proof by contradiction appears just to introduce confusion here. Better to argue directly, which happens to be easy:

Recall that $P\to(Q\to R)$ is logically equivalent to $(P\land Q)\to R$ as a matter of propositional calculus. Thus what you need to show is that if all $A$ are $B$ and everything is $A$, then everything is $B$ -- which ought to be obvious. If you take some arbitrary $x$, you know that $A(x)$ because of the second premise. The first premise then tells you $B(x)$, which is what you want to show.

share|improve this answer
add comment

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.