Results 1 to 11 of 11

Math Help - Need Help With a Derivation Involving Universal Quantifiers

  1. #1
    Newbie
    Joined
    Jul 2008
    Posts
    7

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2008
    Posts
    7
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    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..."
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2006
    Posts
    71
    Quote Originally Posted by mirko View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jul 2008
    Posts
    7
    Ah, now I understand it, thank you very much!

    Quote Originally Posted by PiperAlpha167 View Post
    (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 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2006
    Posts
    71
    Quote Originally Posted by mirko View Post
    ... 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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jul 2008
    Posts
    7
    Got it! Thank you very much. Now onto the next problem. I'm sure I'll bother you guys again.

    Mirko
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Aug 2008
    Posts
    42
    Quote Originally Posted by mirko View Post
    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
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Nov 2011
    Posts
    1

    Re: Need Help With a Derivation Involving Universal Quantifiers

    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!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Let A, B, and C be subsets of some Universal set U...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 9th 2011, 12:59 AM
  2. Derivation and Jordan derivation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 8th 2011, 09:22 PM
  3. Replies: 0
    Last Post: May 8th 2011, 01:54 PM
  4. Replies: 1
    Last Post: August 26th 2009, 08:04 AM
  5. Proof involving different quantifiers?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 1st 2009, 12:28 PM

Search Tags


/mathhelpforum @mathhelpforum