# Direct proofs

1. Nov 27, 2016

### Mr Davis 97

1. The problem statement, all variables and given/known data
What is the first step in proving a proposition of the form $\forall x (P(x) \implies Q(x))$

2. Relevant equations

3. The attempt at a solution
So this isn't exactly a homework question, but I am just trying to figure things out. So say that we have a conjecture of the form $\forall x (P(x) \implies Q(x))$. In my textbook, it says that to (formally) prove a proposition such as this, we first prove $P(c) \implies Q(c)$, where c is an arbitrary element of the domain of discourse, and then by the inference rule of universal generalization, conclude that $\forall x (P(x) \implies Q(x))$.

However, I confused as to how to get to the second step. First we begin with $\forall x (P(x) \implies Q(x))$. So to get to $P(c) \implies Q(c)$ don't we need to apply universal instantiation? And to apply universal instantiation, don't we first need to know that $\forall x (P(x) \implies Q(x))$ is true? Isn't that kind of circular?

2. Nov 28, 2016

### Staff: Mentor

I don't see that a second step is needed. Since c is chosen arbitrarily, and $P(c) \implies Q(c)$, you can conclude that $P(x) \implies Q(x)$ for any x in the domain you're considering.

3. Nov 29, 2016

### Ray Vickson

The statement $P(x) \implies Q(x)$ might be a theorem of some kind. Then establishing $P(c) \implies Q(c)$ amounts to giving a proof of the theorem. That may be easy, or it might be very difficult.