Is this a proper use of universal instantiation? If not, how could this proof be corrected?

Suppose:

Prove:

Proof:

is arbitray, so

, so choose a such that

By universal instantiation let .

Therefore .

Printable View

- May 18th 2011, 09:53 PMOntologProper use of Universal Instantiation
Is this a proper use of universal instantiation? If not, how could this proof be corrected?

Suppose:

Prove:

Proof:

is arbitray, so

, so choose a such that

By universal instantiation let .

Therefore .

- May 19th 2011, 03:33 AMemakarov
No, it's not.

Quote:

is arbitray, so

If, on the other hand, you*assume*P(y), then you can conclude ∀x P(x) because the assumption contains y free. Also, it is not clear where you close the assumption P(y).

To say something more precise, you have to say what formalism you are using, even informally (e.g., natural deduction or sequent calculus).

This conclusion can't be proved without the law of excluded middle. Suppose that ∀x P(x) is true. Then ∃x Q(x) from the assumption, and so ∃x (P(x) -> Q(x)). If ∀x P(x) is false, then there exists an x0 such that P(x0) is false. Therefore, P(x0) -> Q(x0) is true. - May 19th 2011, 12:45 PMOntolog
I can see this, yes I should have added another assumption that .

Yes, I can see that by assuming I wouldn't need to instantiate x to derive . However, wouldn't I need to instantiate x to show that , since in this expression we are saying that the x for which P(x) is the same as the x for which Q(x).

This is something I have been unclear on. I am studying from a book "How To Prove It" (Vellemen 2006) and I am (attempting to) use the formalism presented there. I believe it is "first-order logic."

I don't follow this argument for the same reason I mentioned earlier. To show that is true, don't we need to demonstrate that the x for which P(x) is the same as the x for which Q(x)?

Again I can't follow. Where is it shown that ?

Therefore, by modus tollens:

But the converse is not necessarily true:

I realize that there must be something blindingly obvious that I'm missing here so please bear with me! - May 19th 2011, 02:05 PMPlato
- May 19th 2011, 02:38 PMOntolog
OK, some context for how this problem came up. In the book there is a straightforward exercise:

Prove that if is true, then is true.

Then there is a note that "The other direction of the equivalence is quite a bit harder to prove. See exercise 29 of Section 3.5", where we find the problem:

Prove that if then .

And just as I look up the original problem text I find that the author gives a hint: "Remember that is equivalent to ." Which is something I'll have to think about... (Wondering) - May 19th 2011, 02:43 PMMoeBlee
The hint suggests considering the case ~AxPx and the case ExQx. Show that in either case we have Ex(Px -> Qx).

- May 19th 2011, 02:55 PMemakarov
Recall that an implication is true iff the conclusion is true (regardless of the premise) or the premise is false (regardless of the conclusion).

Suppose ∀x P(x) is true, which also means that ∃x Q(x) is true. Fix x0 that makes Q true. Then P(x0) -> Q(x0) is true regardless of whether P(x0) is true or not. Similarly, if ∀x P(x) is false, suppose P(x0) is false. Then P(x0) -> Q(x0) is true regardless of whether Q(x0) is true. - May 19th 2011, 04:20 PMOntolog
I understand now. I suppose there are some alternative systems of logic that treat implications differently? Because intuitively, an implication is defined by a premise and a consequence which follows from that premise. In fact, I wonder how many typical proofs in mathematics make use of the fact that if Q(x) then for any P and x. In other words, is this merely an idiosyncrasy of first-order logic or does it have any practical implications? (No pun intended :p)

- May 19th 2011, 04:40 PMPlato
- May 19th 2011, 05:04 PMemakarov
Yes, without the rule that true conclusion makes the whole implication true we would not be able to say general facts whose converse is false, both in mathematics and in real life. An example from Wikipedia:

Quote:

Being at least 30 years old is necessary of serving in the U.S... That is, if you are a senator, it follows that you are at least 30 years old.

*a*,*b*and every*u*between f(a) and f(b) there exists a*c*such that f(c) = u, it does not follow that f is continuous.

Still another example: If f : A -> B and g : B -> C are injections, then so is the composition g o f, but not conversely (if g o f is injective, then so is f, but not necessarily g).

Other concepts of implications have been considered in philosophy and logic. See this Wikipedia section, for example. You can probably find a lot of information in the Stanford Encyclopedia of Philosophy. - May 19th 2011, 05:24 PMOntolog
- May 19th 2011, 05:27 PMOntolog
Fascinating :) Thanks for the link to that Wikipedia section, it basically laid out precisely the concerns I had with logical implication. I think my problem is that I get too philosophical when I should be more "hyper-literal" when dealing with mathematics. I'm slowly starting to get it. Thanks for all your help so far!