# Need Help With a Derivation Involving Universal Quantifiers

• July 28th 2008, 01:41 PM
mirko
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 (Worried) 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
• July 28th 2008, 02:50 PM
Plato
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.
• July 29th 2008, 01:59 AM
mirko
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
• July 29th 2008, 03:37 AM
Moo
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 $\forall$ if there is an implication ("then")
- use $\exists$ if there is a condition, that is to say, for example, " $\exists$ x such that condition1 and condition2 and etc..."
• July 29th 2008, 04:30 AM
PiperAlpha167
Quote:

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 (Worried) 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.
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.
• July 29th 2008, 11:31 AM
mirko
Ah, now I understand it, thank you very much!

Quote:

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.

Quote:

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 (Nod)
• July 29th 2008, 11:28 PM
PiperAlpha167
Quote:

Originally Posted by mirko
... but I'm still stuck with (10). A little hint would be nice (Nod)

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.
• July 30th 2008, 08:20 AM
mirko
Got it! :) Thank you very much. Now onto the next problem. I'm sure I'll bother you guys again.

Mirko
• August 10th 2008, 07:48 AM
triclino
Quote:

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 (Worried) 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
f) Equivalence of quantifiers
g)Idempotent law
i) The conditional proof rule
• November 23rd 2011, 10:07 PM
logicguy
Re: Need Help With a Derivation Involving Universal Quantifiers
Quote:

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!
• November 24th 2011, 04:03 AM
emakarov
Re: Need Help With a Derivation Involving Universal Quantifiers
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 $x$ and $y$ in $\forall x y\,(Fxy\to\neg Fyx)$ with $x$.

I am not sure the derivation in post #9 is correct, though. First, existential elimination on $\exists x\,Fxx$ should be done first, and it is with that $x$ 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.