Results 1 to 9 of 9

Math Help - Partial Order

  1. #1
    Super Member
    Joined
    Apr 2009
    Posts
    677

    Partial Order

    I picked up this book to read Set Theory. "Intro to Modern Set Theory - J Roitman"

    It defines a partial order, \leq, on any set S as follows:
    For all x,y,z \in S

    Axiom 1: x \leq x
    Axiom 2: If x \leq y and y \leq x, then x=y
    Axiom 3: If x \leq y and y \leq z, then x \leq z

    Now I have a few questions:
    Q1. I'm not comfortable with the definition above. What is a 'partial order'? It has to some object which we should have defined earlier? (I mean, for e.g. a function from A to B is defines as a subset of the product set, AxB)

    So I tried to define it like that:
    Partial Order ' \leq' is a subset of SxS, such that:
    1. (x,x) in ' \leq'
    2. If (x,y) and (y,x) in ' \leq', then x=x
    3. If (x,y) and (y,z) in ' \leq', then (x,z) \in '\leq'

    Is the above good?

    Q2. I think there is another requirement
    If x and y are not equal, then exactly one of the (x,y) OR (y,x) should belong to \leq

    Where is this covered? Is it a theorem - if yes, can someone help me to prove it?

    Q3. The book I am referring isn't too convincing (for me). Is there a better text which anyone can recommend me?

    Thanks
    Last edited by aman_cc; December 2nd 2009 at 06:11 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by aman_cc View Post
    Q2. I think there is another requirement
    Exactly one of the (x,y) OR (y,x) should belong to \leq

    Where is this covered? Is it a theorem - if yes, can someone help me to prove it?
    I don't have time to answers the others now. But this one is not always true. Consider the partial ordering induced by set inclusion. Is it always true that A\subset B\text{ or }B\subset A? What you stated is called a total (or linear) ordering.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by Drexel28 View Post
    I don't have time to answers the others now. But this one is not always true. Consider the partial ordering induced by set inclusion. Is it always true that A\subset B\text{ or }B\subset A? What you stated is called a total (or linear) ordering.

    Oh !!! That means there is a very basic error in my understanding of the concept ! Thanks

    Please do look at other questions when you have time.

    Also let me know a good text to read this up. Thanks again !!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by aman_cc View Post
    I picked up this book to read Set Theory. "Intro to Modern Set Theory - J Roitman"

    It defines a partial order, \leq, on any set S as follows:
    For all x,y,z \in S

    Axiom 1: x \leq x
    Axiom 2: If x \leq y and y \leq x, then x=y
    Axiom 3: If x \leq y and y \leq z, then x \leq z

    Now I have a few questions:
    Q1. I'm not comfortable with the definition above. What is a 'partial order'? It has to some object which we should have defined earlier? (I mean, for e.g. a function from A to B is defines as a subset of the product set, AxB)

    So I tried to define it like that:
    Partial Order ' \leq' is a subset of SxS, such that:
    1. (x,x) in ' \leq'
    2. If (x,y) and (y,x) in ' \leq', then x=x
    3. If (x,y) and (y,z) in ' \leq', then (x,z) \in '\leq'

    Is the above good?


    Excellent. This is exactly what is meant by order: it is a relation and thus a subset of the corresponding cartesian product.


    Q2. I think there is another requirement
    If x and y are not equal, then exactly one of the (x,y) OR (y,x) should belong to \leq


    No, this is not required unless the partial order is complete.


    Where is this covered? Is it a theorem - if yes, can someone help me to prove it?

    Q3. The book I am referring isn't too convincing (for me). Is there a better text which anyone can recommend me?

    You may want to try the classic texts by Church, or Halmos, or Monk. You can also search in google "set theory": sometimes you can find surprisingly nice and well-written course notes from teacher.

    Tonio


    Thanks
    .
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by aman_cc View Post
    I picked up this book to read Set Theory. "Intro to Modern Set Theory - J Roitman"

    It defines a partial order, \leq, on any set S as follows:
    For all x,y,z \in S

    Axiom 1: x \leq x
    Axiom 2: If x \leq y and y \leq x, then x=y
    Axiom 3: If x \leq y and y \leq z, then x \leq z

    Now I have a few questions:
    Q1. I'm not comfortable with the definition above. What is a 'partial order'? It has to some object which we should have defined earlier? (I mean, for e.g. a function from A to B is defines as a subset of the product set, AxB)

    So I tried to define it like that:
    Partial Order ' \leq' is a subset of SxS, such that:
    1. (x,x) in ' \leq'
    2. If (x,y) and (y,x) in ' \leq', then x=x
    3. If (x,y) and (y,z) in ' \leq', then (x,z) \in '\leq'

    Is the above good?
    Yes. There are two ways of representing a relation on a set E. Originally we interpret the relation as a collection R\subset E\times E. With the property that (x,y)\in R\Leftrightarrow x\stackrel{R}{\sim}y. Since the two are logically equivalent listing the axioms in \stackrel{R}{\sim} form or as ordered pairs in R is the same thing.

    Q2. I think there is another requirement
    If x and y are not equal, then exactly one of the (x,y) OR (y,x) should belong to \leq

    Where is this covered? Is it a theorem - if yes, can someone help me to prove it?
    To expand upon what I said. Using our naieve concepts of set inclusion we know that

    1. A\subseteq A

    2. A\subseteq B\wedge B\subseteq A\implies A=B

    3. A\subset B\wedge B\subset C\implies A\subset C

    So we see that if we define a collection of sets carefully that set inclusion can certainly be a partial ordering on that collection. As I said though, this partial ordering is not linear. In other words it is not true that if two elements are in the collection that one is contained in the other or vice versa. A=\{1,2\},B=\{3,4\} is an example (given that A B was in the collection the ordering is defined upon)

    Q3. The book I am referring isn't too convincing (for me). Is there a better text which anyone can recommend me?

    Thanks
    I guarantee that Plato would have a much better suggestion than I, perhpaps PM him. But I personally liked Set Theory And Logic by Robert. R. Stoll. Actually, specifically what topic are you intending to study?

    Quote Originally Posted by aman_cc View Post
    Oh !!! That means there is a very basic error in my understanding of the concept ! Thanks

    Please do look at other questions when you have time.

    Also let me know a good text to read this up. Thanks again !!


    EDIT: Beat by Tonio!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by tonio View Post
    .

    Thanks very much, guys !

    So on my Q#2 - I guess now I understand why it is called 'partial'. Because it might not be defined for every x,y in S. So there might be some elements in S which you can't order. Correct?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by aman_cc View Post
    Thanks very much, guys !

    So on my Q#2 - I guess now I understand why it is called 'partial'. Because it might not be defined for every x,y in S. So there might be some elements in S which you can't order. Correct?
    Be careful with what you're saying here. In my example in my last post, depending on my collection I could certainly order \{1,2\}\subset \{1,2,3\}. The problems is that a partial ordering does not guarantee that given two members of a set that I can order them relative to one another.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,663
    Thanks
    1616
    Awards
    1
    Quote Originally Posted by aman_cc View Post
    Thanks very much, guys !
    So on my Q#2 - I guess now I understand why it is called 'partial'. Because it might not be defined for every x,y in S. So there might be some elements in S which you can't order. Correct?
    That is correct.
    I think that the best way to see a PO is to think about the power set of a set.
    The set of all subsets of a set is partially ordered by \subseteq.
    In particular, you can see the reason for 'partial'.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Nov 2009
    Posts
    10
    Quote Originally Posted by aman_cc View Post
    Q3. The book I am referring isn't too convincing (for me). Is there a better text which anyone can recommend me?
    I would have a look to "Introduction to set theory" by Hrbacek - Jech, for an introduction. Then "Set theory - The third millenium edition" by Jech.
    I really appreciated them. If you are then interested in more logic-related arguments and independence proofs, you can move on to "Set theory - An introduction to independence proofs" by Kunen.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Partial Order
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 28th 2011, 02:28 PM
  2. Partial Order
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 28th 2011, 12:02 PM
  3. Partial Order
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 24th 2009, 07:14 AM
  4. Partial Order
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 27th 2009, 04:08 AM
  5. lattice partial order
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 16th 2008, 10:37 AM

Search Tags


/mathhelpforum @mathhelpforum