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 .
No, it's not.
It seems that you start with ∀x P(x) and instantiate x with y. However, ∀x P(x) is not given: it is an assumption of an assumption and thus has to be proved. It is also not clear why you need to instantiate x since you can immediately derive ∃x Q(x) by MP and from there derive the conclusion.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.
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!
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...
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.
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 )
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:The converse of the intermediate value theorem is false: roughly speaking, if for all 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.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.
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.
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!