Page 1 of 3 123 LastLast
Results 1 to 15 of 45

Math Help - Logic

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    45

    Logic

    Hi. I have this problem to solve:


    (∀x(P(x,x)∧∀x∀y∀z[(P(x,y)∧P(y,z))→P(x,z)]∧∀x∀y[P(x,y)∨P(y,x)])→∃y∀xP(y,x).

    In natural language this means that if a relation P is reflexive and transitive and for two elements a,b we have P(a,b)∨P(b,a) then there is another element d in the universe that for every other element c of the universe we have P(d,c).

    Here is the first question:
    Give an interpretation that is no model of the above type. Seek an interpretation in an infinitive universe. The universe could be the natural numbers and the interpretation some known relation among the natural numbers.


    Some help ?? Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    To understand this formula better, we could consider an obvious example of a reflexive, transitive and total (x <= y \/ y <= x) relation: non-strict order on natural numbers. The formula says that there is the least element. Well, on natural numbers with regular <= there is indeed the least element. But what if we choose a set other than natural numbers? Or we could recall that natural numbers don't have the largest element, so what relation could we choose to interpret <=?

    Give an interpretation that is no model of the above type.
    Do you by chance study type theory?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    Quote Originally Posted by emakarov View Post
    To understand this formula better, we could consider an obvious example of a reflexive, transitive and total (x <= y \/ y <= x) relation: non-strict order on natural numbers. The formula says that there is the least element. Well, on natural numbers with regular <= there is indeed the least element. But what if we choose a set other than natural numbers? Or we could recall that natural numbers don't have the largest element, so what relation could we choose to interpret <=?

    Do you by chance study type theory?
    Yes but I want something that it's not a model of the type. And <= is a model correct ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    What I am saying is that by considering a different set with regular <= or by considering natural numbers with a different <= you'll get a non-model.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    Quote Originally Posted by emakarov View Post
    What I am saying is that by considering a different set with regular <= or by considering natural numbers with a different <= you'll get a non-model.

    Yes and thank you but I want the relation to be also reflexive and transitive. It must not satisfy just the third part : there is another element d in the universe that for every other element c of the universe we have P(d,c). Thats why I am so confused. And it must also be about natural numbers.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    Well, all the hint I can give is that there is a set of numbers with <= without the least element, and the set of natural numbers does not have the greatest element.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    Quote Originally Posted by emakarov View Post
    Well, all the hint I can give is that there is a set of numbers with <= without the least element, and the set of natural numbers does not have the greatest element.
    Do you mean to take >= on the natural numbers? Because if so I still dont get how it is not a model. I am confused. Because I understand that there would be no largest element but I have = (equality) also. So there could be the same element.
    Last edited by milagros; January 22nd 2010 at 06:56 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    I just dont get how to say it.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    Do you mean to take >= on the natural numbers? Because if so I still dont get how it is not a model. I am confused.
    Yes, I am thinking about \langle\mathbb{N},\ge\rangle, i.e., natural numbers with the \ge relation.
    Because I understand that there would be no largest element but I have = (equality) also. So there could be the same element.
    I don't understand your objection. Let's take 100. Is this the "least" element w.r.t. \ge, i.e., is it true that for every natural m, 100 \ge m? Can we say the same about other numbers?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    Quote Originally Posted by emakarov View Post
    Yes, I am thinking about \langle\mathbb{N},\ge\rangle, i.e., natural numbers with the \ge relation.
    I don't understand your objection. Let's take 100. Is this the "least" element w.r.t. \ge, i.e., is it true that for every natural m, 100 \ge m? Can we say the same about other numbers?
    I think I took it the wrong way. I thought that 100 of course its not the greatest but m could be 100 (m=100) so I satisfy the type. Thank you very much.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    I have also to prove with induction that this type applies to every definite universe. Any ideas there ?

    Thank you again.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    What is a "definite universe"? And what does "apply to a universe" mean? I am asking because these are not universally-accepted terms.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    For example in another set of natural numbers that has both the greatest and the least element. Not infinite universe. And I have to prove that this type is correct for all the non infinite universes. Hope I explained.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    For finite sets the formula can be proved by induction on the size of the set. A singleton has its minimum, and for the induction step, you remove one element x, find the minimum y of the rest of the elements, and then find the minimum of x and y. Note that the fact that any two elements are comparable is used to compare x and y.

    In general, if some fact is true for finite sets and false for infinite ones, very often it is proved by induction on the size of the set.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Junior Member
    Joined
    Oct 2009
    Posts
    45
    Quote Originally Posted by emakarov View Post
    For finite sets the formula can be proved by induction on the size of the set. A singleton has its minimum, and for the induction step, you remove one element x, find the minimum y of the rest of the elements, and then find the minimum of x and y. Note that the fact that any two elements are comparable is used to compare x and y.

    In general, if some fact is true for finite sets and false for infinite ones, very often it is proved by induction on the size of the set.

    Thankl you.
    Follow Math Help Forum on Facebook and Google+

Page 1 of 3 123 LastLast

Similar Math Help Forum Discussions

  1. Can someone check my logic (sentential logic)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 13th 2010, 03:30 AM
  2. logic
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: December 1st 2008, 08:49 AM
  3. logic
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: November 3rd 2008, 10:30 PM
  4. logic
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 2nd 2008, 11:53 PM
  5. Logic
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 12th 2007, 05:05 PM

Search Tags


/mathhelpforum @mathhelpforum