Thread: Need Help With a Derivation Involving Universal Quantifiers

Hi!

I'm trying to teach myself logic, using Suppes' Introduction to Logic, which seems to be a great book, but it unfortunately comes without any solutions to the exercises Well, and now I'm stuck with the following exercise:

"If one man is the father of a second, then the second is not father of the first. Therefore, no man is his own father." (or read it on google; I was able to solve most of them, except 3,4,9, and 10).

How do you solve that? Any help is greatly appreciated!

Mirko

This is not a solution, but rather a comment.
I think that there are much better book that Suppes’ to use to teach oneself logic. I cannot locate my copy, so I cannot lookup that problem.
You might look into basic texts by I. Copi or M. Resnik.
Also some of the modern discrete mathematic do a wonderful job with basic logic and set theory.

Oh, you don't need to look for your copy, the book is available from google.

Ok, I'll see if I can get a book from Copi or Resnik, but in the meantime, I'd like to continue with Suppes, so if anybody has an idea (also for the exercises 4, 9, and 10 in the above-mentioned link)?

Thanks again!

Mirko

I don't understand what you're asked to "solve" ?

If you have to write a formula using quantifiers, there's something that may be useful :
- use if there is an implication ("then")
- use if there is a condition, that is to say, for example, " x such that condition1 and condition2 and etc..."

Originally Posted by mirko

Hi!

I'm trying to teach myself logic, using Suppes' Introduction to Logic, which seems to be a great book, but it unfortunately comes without any solutions to the exercises Well, and now I'm stuck with the following exercise:

"If one man is the father of a second, then the second is not father of the first. Therefore, no man is his own father." (or read it on google; I was able to solve most of them, except 3,4,9, and 10).

How do you solve that? Any help is greatly appreciated!

Mirko

The argument looks something like this:

(x)(y)[Fxy -> ~Fyx] |= ~(Ex)[Fxx]

Basically, it claims that the single premiss entails the conclusion.

Loose derivation:

Assume (Ex)[Fxx] (the negation of the conclusion)
Strip (Ex) and introduce temporary constant say, a. Why?
Now we have Faa.
Successively strip (x) then (y) in premiss.
We're free to use a in both cases. Why?
Thus we now have:
Faa -> ~Faa.
Apply detachment to Faa and Faa -> ~Faa to get ~Faa.
Now we're in business because:
Faa and ~Faa (clearly a contradiction).
By deduction theorem we now have:
(Ex)[Fxx] -> (Faa and ~Faa).
By the "Law" of Absurdity we can conclude:
~(Ex)[Fxx] which is what we've been trying to reach from our lone premiss.

Note: the last couple of steps are usually rolled into a derived rule of inference called reductio ad absurdum (or RAA).

Final:
Suppes knows his stuff. I wouldn't pass up any opportunity to read what he has to say. Of course, my opinion.

Ah, now I understand it, thank you very much!

Originally Posted by PiperAlpha167

(x)(y)[Fxy -> ~Fyx] |= ~(Ex)[Fxx]

Yes, that's what I had too, but I hadn't thought of using an indirect proof.

Originally Posted by PiperAlpha167

Successively strip (x) then (y) in premiss.
We're free to use a in both cases. Why?

I didn't know that was allowed, but now that I think of it, it all makes sense. With that knowledge, solving (4) and (9) was easy, but I'm still stuck with (10). A little hint would be nice

Originally Posted by mirko

... but I'm still stuck with (10). A little hint would be nice

OK, here's a reasonable start:

Basically (10) says that any irreflexive, transitive relation is necessarily asymmetric.
It's a standard theorem. The typical proof is a proof by contradiction.
Assume the relation is not asymmetric, and then see what the premisses have to say about such an assumption.

Got it! Thank you very much. Now onto the next problem. I'm sure I'll bother you guys again.

Mirko

Originally Posted by mirko

Hi!

I'm trying to teach myself logic, using Suppes' Introduction to Logic, which seems to be a great book, but it unfortunately comes without any solutions to the exercises Well, and now I'm stuck with the following exercise:

"If one man is the father of a second, then the second is not father of the first. Therefore, no man is his own father." (or read it on google; I was able to solve most of them, except 3,4,9, and 10).

How do you solve that? Any help is greatly appreciated!

Mirko

Using the formula of PiperAlpha 167 ,here is a more detailed proof:
But before the proof let us denote the meaning of couple of symbols,so
Let (x) mean .................................................. .........for all x
Let Ex mean.............................................. ......there exists an x
Let ~ mean not
And.
1) (x)(y)[Fxy -> ~Fyx].........assumpsion
2) (y)[Fxy -> ~Fyx]........from 1 and using Univ.Elimination,where we put x=x We could put x=a
3) [Fxx -> ~Fxx]........from 2 and using Univ.Elimin.,where we put y=x
4) (Ex)[Fxx]...............assumption to start a contradiction
5) Fxx......................from 4 and using Existential Elimination
6) ~Fxx .....................from 3 and 5 and using M.Ponens
7) (x)[~Fxx]..................from 6 and using Univ.Introduction
8) ~Ex[Fxx].....................from 7 and equivalence of quantifiers
9) Ex[Fxx] & ~Ex[Fxx]...........from 4 and 8 and using addition introduction
10) ~Ex[Fxx].................from 4 to 9 and using contradiction
Now from step 4 we can do a different proof,so
4) (Ex)[Fxx]....................hypothesis
5) Fxx......................from 4 and using Existential Elimination
6) ~Fxx .....................from 3 and 5 and using M.Ponens
7) (x)[~Fxx]..................from 6 and using Univ.Introduction
8) ~Ex[Fxx].....................from 7 and equivalence of quantifiers
9) (Ex)[Fxx]---->~Ex[Fxx].....from 4 to 8 and using the rule of conditional proof
10) ~(Ex)[Fxx]v ~(Ex)[Fxx].....from 9 and using material implication
11) ~(Ex)[Fxx]...................from 10 and using idempotent law
The laws of logic used are:
a) Universal Elimination
b) Universal Introduction
c) Existential Elimination
d) M.Ponens
e) Addition Introduction
f) Equivalence of quantifiers
g)Idempotent law
h)The rule of contradiction
i) The conditional proof rule

1) (x)(y)[Fxy -> ~Fyx].........assumpsion
2) (y)[Fxy -> ~Fyx]........from 1 and using Univ.Elimination,where we put x=x We could put x=a
3) [Fxx -> ~Fxx]........from 2 and using Univ.Elimin.,where we put y=x

This is a really old thread, but I was stuck on this problem as well. I don't understand how we can use Universal Specification (or Univeral Elimination) on the variables x and y, and have them both be x? Shouldn't they be different variables? When Univ. specification is used, when should the variables be the same, and when should they be different?

If someone could clarify this, that would be most appreciated!

Universal elimination can instantiate a variable with any term whatsoever (as long as the term's free variables do not become bound after the substitution). Nothing prevents instantiating both and in with .

I am not sure the derivation in post #9 is correct, though. First, existential elimination on should be done first, and it is with that that the universal variables should be instantiated. Second, step 7 uses universal introduction on the variable that is still free in the open assumption in step 5.