Direct proofs

  • #1
1,462
44

Homework Statement


What is the first step in proving a proposition of the form ##\forall x (P(x) \implies Q(x))##

Homework Equations




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?
 

Answers and Replies

  • #2
34,988
6,741

Homework Statement


What is the first step in proving a proposition of the form ##\forall x (P(x) \implies Q(x))##

Homework Equations




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))##.
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.
Mr Davis 97 said:
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?
 
  • #3
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,722

Homework Statement


What is the first step in proving a proposition of the form ##\forall x (P(x) \implies Q(x))##

Homework Equations




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?

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.
 

Related Threads on Direct proofs

  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
7
Views
7K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
7
Views
3K
Top