Results 1 to 8 of 8

Math Help - Partially Ordered Set, example from Wiki.

  1. #1
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1

    Partially Ordered Set, example from Wiki.

    Hi,

    I was reading in the Naive Set Theory book by Halmos, and encountered partially ordered sets.
    It seems like a lot of people understand these things immediately. I am not one of those

    I did a bit of searching and read through the wiki on posets. Here's an example they give:

    Set of natural numbers equipped with the relation of divisibility.
    A=\{1,2,3,4,5,10,12,15,20,30,60\} is the set of all positive divisors of 60.

    Then this relation (divisibility) is reflexive, transitive and antisymmetric.

    (1)Reflexive: aRa,\;for\;all\;a\in A
    So, (a,a)\in R

    As I understand it, the ordered pair (a,a) is in a partially ordered subset of A.
    Now, I guess I can "create" these ordered pairs by taking the Cartesian Product, AxA.
    This gives me among other things the diagonal terms (1,1),(2,2),(3,3),\cdots,(60,60), all in all 11 diagonal terms.

    I can then go ahead and create a subset of A that is reflexive:
    perhaps, \{(1,2),(1,1),(2,2)\}
    or, \{(5,3),(5,5),(3,3)\}

    There are then n^2-n off-diagonal elements, so there are 2^{n^2-n} subsets of the off-diagonal pairs.
    I can combine any of these subsets with the diagonal to get a reflexive relation on A.
    All in all, 2^{n^2-n} reflexive relations..

    Is this a good way to think of the reflexive property, or am I way off?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,386
    Thanks
    1323
    Quote Originally Posted by Mollier View Post
    Hi,

    I was reading in the Naive Set Theory book by Halmos, and encountered partially ordered sets.
    It seems like a lot of people understand these things immediately. I am not one of those

    I did a bit of searching and read through the wiki on posets. Here's an example they give:

    Set of natural numbers equipped with the relation of divisibility.
    A=\{1,2,3,4,5,10,12,15,20,30,60\} is the set of all positive divisors of 60.

    Then this relation (divisibility) is reflexive, transitive and antisymmetric.

    (1)Reflexive: aRa,\;for\;all\;a\in A
    So, (a,a)\in R

    As I understand it, the ordered pair (a,a) is in a partially ordered subset of A.
    No. All subsets of A consist of members of a, not ordered pairs! Saying that divisibility is reflexive has nothing directly to do with ordered subsets of A anyway. Divisibility is reflexive because a= 1*a so a divides itself.

    Now, I guess I can "create" these ordered pairs by taking the Cartesian Product, AxA.
    This gives me among other things the diagonal terms (1,1),(2,2),(3,3),\cdots,(60,60), all in all 11 diagonal terms.

    I can then go ahead and create a subset of A that is reflexive:
    perhaps, \{(1,2),(1,1),(2,2)\}
    or, \{(5,3),(5,5),(3,3)\}
    I really have no idea what you are doing. What is your objective?

    There are then n^2-n off-diagonal elements, so there are 2^{n^2-n} subsets of the off-diagonal pairs.
    I can combine any of these subsets with the diagonal to get a reflexive relation on A.
    All in all, 2^{n^2-n} reflexive relations..

    Is this a good way to think of the reflexive property, or am I way off?

    Thanks!
    Yes, you certainly can but I don't know why you are doing it. Why do you want to know how many "reflexive relations" there are on a set? That doesn't appear to have anything to do with partial orders.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Hi,
    the reason I am writing all this rubbish is to try and understand what reflexive,transitive and antisymmetric really mean.
    In my last post, I just focused on reflexive, and of course go it all wrong.

    So, a reflexive relation is a relation on a set for which every element is related to itself.
    Can I say that \leq is a reflexive relation on the set A=\{1,2,3\}, because 1=1,2=2,3=3?

    < then is not a reflexive relation on set A=\{1,2,3\}..

    You mentioned that divisibility is reflexive because a=1*a, I think that makes sense.

    I've read somewhere that aRa for all a\in A can be seen as (a,a)\in R What is that all about?
    I actually read it here on the forums:
    http://www.mathhelpforum.com/math-he...ial-order.html

    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Hi,
    the reason I am writing all this rubbish is to try and understand what reflexive,transitive and antisymmetric really mean.
    In my last post, I just focused on reflexive, and of course go it all wrong.

    So, a reflexive relation is a relation on a set for which every element is related to itself.
    Can I say that \leq is a reflexive relation on the set A=\{1,2,3\}, because 1=1,2=2,3=3?

    < then is not a reflexive relation on set A=\{1,2,3\}..

    You mentioned that divisibility is reflexive because a=1*a, I think that makes sense.


    Thanks
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    the reason I am writing all this rubbish is to try and understand what reflexive,transitive and antisymmetric really mean.
    In my last post, I just focused on reflexive, and of course go it all wrong.
    One has to understand first what a relation is. A relation R on a set A is a function of two arguments that returns true or false: for all a_1\in A, a_2\in A we have R(a_1,a_2)\in\{\text{true},\text{false}\}. (And, of course, one first has to understand what a function of several arguments is.) The fact that R(a_1,a_2)=\text{true} is conventionally written a_1Ra_2, e.g., 1\le 3.

    Now, there are many ways to specify a function, or even to define what a function is. Some options are: it's a law that puts a single result into correspondence with each argument; it's an algorithm that computes the result from an argument; it's a set of pairs F with one condition: \langle x,y_1\rangle\in F and \langle x,y_2\rangle\in F imply y_1=y_2 for all x, y_1, y_2. It makes sense to specify the details only when one really needs them, e.g., in a proof. In set theory, the last option above is taken as a definition, though it is only one "implementation" of an abstract concept of a function.

    A relation viewed as a function of two arguments, would be considered a set of nested pairs, e.g., \langle\langle a_1,a_2\rangle,\text{true}rangle. One prefers a simpler implementation, where one removes pairs where the last element is \text{false} and keeps only the first element \langle a_1,a_2\rangle of other pairs. There is nothing special about this implementation, except that it is probably the simplest way to implement a relation. An important point is that it should be easily possible to convert one implementation into another.

    Therefore, the notation a_1Ra_2, where R is an "abstract" relation, becomes \langle a_1,a_2\rangle\in R where R is implemented as a set of pairs.

    Also, it is important to keep in mind the type of every object one deals with. For example, a set of numbers consists of numbers, which are themselves not sets. An partial order is a ordered pair \langle A, R\rangle where A is a set and R is a relation on R satisfying some axioms. I.e., here R can be viewed consisting of ordered pairs of elements of A. Of course, one becomes a little sloppy soon and, e.g., talks about a subset of a partial order \langle A, R\rangle meaning a subset A' of A with the restriction of R on A'. Literally, one can't take a subset of an ordered pair \langle A, R\rangle unless one considers a specific implementation of ordered pairs. Such implicit coercions are normal, but one has to be able to identify them when needed.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Emarkov: Thanks for the reply.

    Let me rephrase my question and not attempt any answer myself

    How can I tell that the set of natural numbers equipped with the relation of divisibility is a partially ordered set?

    Thanks.
    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 Mollier View Post
    Emarkov: Thanks for the reply.

    Let me rephrase my question and not attempt any answer myself

    How can I tell that the set of natural numbers equipped with the relation of divisibility is a partially ordered set?

    Thanks.
    Why not just verify the axioms?

    Clearly n\mid n. If n\mid n' then n'=nz for some z\in\mathbb{Z} and similarly we have that n=nz'. So then we have that z=\frac{1}{z'} but since z\in\mathbb{Z} it follows that z'=\pm 1. But, since we are only dealing with natural numbers z'=1\implies z=1\implies n=n' so it has anti-symmetry. If n\mid m,m\mid \ell then \ell=zm=zz'n\implies n\mid \ell so it has transitivity.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member Mollier's Avatar
    Joined
    Nov 2009
    From
    Norway
    Posts
    234
    Awards
    1
    Just rewriting a bit here:

    If n|n' and n'|n then n=n'.

    n|n' \Rightarrow n=zn'

    n'|n \Rightarrow n'=zn

     n'=z^2n' \Rightarrow z^2=1 \Rightarrow z= \pm 1

    Since only natural numbers:  z=1

    Hence, n=n'

    Thanks mate!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Q's on Partially Ordered Set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 5th 2011, 01:17 AM
  2. Question about partially ordered sets
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: April 6th 2011, 12:54 PM
  3. Partially ordered set with no maximal element
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 9th 2010, 12:37 AM
  4. Replies: 7
    Last Post: February 25th 2010, 04:44 AM
  5. Partially ordered set.
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: January 10th 2010, 08:42 AM

Search Tags


/mathhelpforum @mathhelpforum