Results 1 to 11 of 11

Math Help - Help with questionable FOL translation and a proof based on the same principle

  1. #1
    Newbie
    Joined
    Mar 2011
    Posts
    12

    Help with questionable FOL translation and a proof based on the same principle

    I'm using Fitch-style proofs where ~ denotes negation sign and x shows subproof, xx subproof within subproof et.c. (Sorry about this getting a bit messy, but in lack of better ideas this is how I try to write proofs here).



    Exercise:

    Translate the following into First Order Language by using predicates Number, Larger, Odd, Prime and the constant symbol 2:

    "There is a number which is larger than every other number"

    Solution:
    " \exists x (Number(x) \wedge \forall y (Number(y) \to Larger(x,y)))

    where Larger(x,y) means x is larger than y."

    Is this really correct? I would like to add " \wedge ~(x=y)" in front of the conditional. Does the above given answer not imply that x is larger than every other number AND also that it is larger than itself (or at least that some number is larger than itself)?
    If it is true for all objects y, then it should also be true when y refers to the same object as x.

    To me this principle seems obvious. Applicated:

    Another exercise/solution from the same source states that one cannot prove ~ \exists x \forall y R(y,x) from a set of premises, including ~ \exists x R(x,x). I believe the conclusion is provable using only this premise;


    1. ~ \exists x R(x,x)
    2. x \exists x \forall y R(y,x) assumption towards contradiction
    3. xx [a] \forall y R(y,a)assumption towards \exists elimination
    4. xx R(a,a) \forall elimination 3
    5. xx \exists x R(x,x) \exists introduction 4
    6. x \exists x R(x,x)                                  \exists elimination 2, 3-5
    7. xContradiction Contradiction intro 1,6
    8. ~ \exists x \forall y R(y,x) ~ intro 2-7

    Help is much appreciated, I feel quite puzzled about this since the given solutions to the exercises contradict my reasoning and the proof...
    Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by HeadmasterEel View Post
    " \exists x (Number(x) \wedge \forall y (Number(y) \to Larger(x,y)))

    where Larger(x,y) means x is larger than y."

    Is this really correct?
    No.

    Quote Originally Posted by HeadmasterEel View Post
    I would like to add " \wedge ~(x=y)" in front of the conditional. Does the above given answer not imply that x is larger than every other number AND also that it is larger than itself (or at least that some number is larger than itself)?
    Right, you need the conjunct that ~x=y, otherwise, you have an x such that x is larger than itself, which is NOT entailed by the mere fact that there is an x that is larger than every OTHER y.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by HeadmasterEel View Post
    Another exercise/solution from the same source states that one cannot prove ~ \exists x \forall y R(y,x) from a set of premises, including ~ \exists x R(x,x). I believe the conclusion is provable using only this premise
    Maybe there is a misunderstanding about how the exercise is stated, because you are correct that ~ExRxx does imply ~ExAyRyx.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Mar 2011
    Posts
    12
    Thanks very much for your replies MoeBlee! It is appreciated=)

    very unsure since these solutions are taken from an old exam why one would expect them to be correct. And usually the exams are correct even though one may have trouble seeing it at first so I will stay humble ...

    The exact formulation of the "advanced" exercise is to either give a counter example or a proof of the following:

    Premises:
    1. \forall x \forall y \forall z ((R(x,y) \wedge R(y,z)) \to R(x,z) )
    2. \forall x \forall y (R(x,y) \to \exists z (R(x,z) \wedge R(z,y)))
    3.~ \exists  x R(x,x)

    Conclusion:
    ~ \exists x \forall y R(y,x)

    In the first post in this thread I think I proved this conclusion from only premise 3, then it must also follow when including more premises...

    But the solution given to this exercise presents a counter example as follows:

    "Let M be a model. The universe of this model is [0,1] = {a \in REAL : 0 \leqslant a \leqslant 1} where REAL is the set of real numbers. The interpretation R = {(a,b): a,b \in REAL and a<b } , that is R(a,b) \Leftrightarrow a<b. Then the premises are true but the conclusion is false since 1 is the largest element in the model M."

    My point is that, sure 1 is the largest element and it is larger than all the other elements. But 1 is not larger than itself. No element is larger than itself.
    Hence, also in this model it is true that ~ \exists x \forall y R(y,x), that is: it is not true that there is an objct which is larger than every object.

    This is very similar to the translation problem in that it does not seem to take into account that x and y can refer to the very same object (which I believe they can? that seems o be the key question here).

    Further input is most welcome=)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by HeadmasterEel View Post
    give a counter example or a proof
    Okay "OR a proof." Yes, and we don't even need the first two premises, indeed, as you observed ~ExRxx proves ~ExAyRyx.

    Quote Originally Posted by HeadmasterEel View Post
    I proved this conclusion from only premise 3, then it must also follow when including more premises
    Yep, and that observation even has a name; it's called the 'monotonic property' of our logic. That is, if a set of formulas G proves a formula P then, if G is a subset of H, then H also proves P.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by HeadmasterEel View Post
    in this model it is true that ~ \exists x \forall y R(y,x), that is: it is not true that there is an objct which is larger than every object.
    Unless I'm overlooking something, you're right. Where did you get these exam "answers"? Given your description of them, unless I'm spacing out right now, they're wrong.

    Quote Originally Posted by HeadmasterEel View Post
    x and y can refer to the very same object (which I believe they can?
    Yep, it very well could be that x=y.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165
    Quote Originally Posted by HeadmasterEel View Post
    "There is a number which is larger than every other number"
    I agree, I think you were right to catch that requirement. I believe its prenex normal form would be something like:

    \exists x\forall y((Number(x)\wedge Number(y)\wedge x\neq y)\Rightarrow Larger(x, y)

    Using set notation and bounded quantifiers we might shorten it:

    \exists (x\in N)\forall (y\in N)(x\neq y \Rightarrow x > y)

    As for the proof, I think the statement (when interpreted) makes more sense if you process the negation through (and do quantifier transformations). If we think of R as "less than," for instance, then the first sentence says for each x there is a y that is not less than it (i.e., for each x we can find a larger y). The other says every x is not larger than itself. I think there is something up with that proof, though. I'll think about it later.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Mar 2011
    Posts
    12
    Quote Originally Posted by bryangoodrich View Post
    I

    As for the proof, I think the statement (when interpreted) makes more sense if you process the negation through (and do quantifier transformations). If we think of R as "less than," for instance, then the first sentence says for each x there is a y that is not less than it (i.e., for each x we can find a larger y). The other says every x is not larger than itself. I think there is something up with that proof, though. I'll think about it later.

    I'm sorry but my english is not perfect and I feel a bit unsure what you mean here...

    But as I try to interpret what you mean;

    ~ \exists x \forall y R(y,x) corresponds to \forall x \exists y ~ R(x,y)

    and ~ \exists x R(x,x) corresponds to \forall x ~ R(x,x) ;

    still I think the first is readily proven from the second, both formally:
    \forall x ~ R(x,x)
    ~ R(a,a)
    \exists y ~ R (a,y)
    \forall x \exists y ~ R (X,y)

    with proper rules, and informally by reasoning:

    "
    the first sentence says for each x there is a y that is not less than it (i.e., for each x we can find a larger y)
    ."
    here I would like to SAY "for each x we can find a large OR EQUALLY LARGE y", since I think "Not less than" means "equally large or larger".

    All objects are not less than itself, hence it is true that we can find an object which is not larger than x for all x, namely x itself is not larger than x.

    Maybe this was just what you tried to say?=) Or maybe I made some mistakes in the reasoning.. as usual, input always welcome and appreciated=)
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Mar 2011
    Posts
    12
    Quote Originally Posted by MoeBlee View Post
    Unless I'm overlooking something, you're right. Where did you get these exam "answers"? Given your description of them, unless I'm spacing out right now, they're wrong.

    Yep, it very well could be that x=y.

    Well, these solutions are "suggested solutions" from the course homepage and usually those are quite correct even when it is first hard to see. That is why I wanted assurances here before I jump to conclusions about the suggested solutions...
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by HeadmasterEel View Post
    maybe I made some mistakes in the reasoning
    I didn't doublecheck the details of the annotation of your proof in your first post, but your reasoning itself is all correct.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by HeadmasterEel View Post
    these solutions are "suggested solutions" from the course homepage
    What's the URL of that homepage? I'd like to see it myself to verify that it is incorrect.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pretty questionable one.
    Posted in the Statistics Forum
    Replies: 3
    Last Post: December 5th 2010, 05:42 AM
  2. questionable questions
    Posted in the Algebra Forum
    Replies: 9
    Last Post: February 5th 2010, 08:35 AM
  3. Proof utilizing archemedian principle
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 1st 2010, 05:52 PM
  4. Principle of Induction Proof
    Posted in the Algebra Forum
    Replies: 9
    Last Post: October 14th 2008, 10:57 AM
  5. Complexity based proof of infinitude of Primes
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: February 10th 2007, 01:29 PM

Search Tags


/mathhelpforum @mathhelpforum