Results 1 to 8 of 8

Thread: 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.
    $\displaystyle 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: $\displaystyle aRa,\;for\;all\;a\in A$
    So, $\displaystyle (a,a)\in R$

    As I understand it, the ordered pair $\displaystyle (a,a)$ is in a partially ordered subset of $\displaystyle A$.
    Now, I guess I can "create" these ordered pairs by taking the Cartesian Product, $\displaystyle AxA$.
    This gives me among other things the diagonal terms $\displaystyle (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, $\displaystyle \{(1,2),(1,1),(2,2)\}$
    or, $\displaystyle \{(5,3),(5,5),(3,3)\} $

    There are then $\displaystyle n^2-n$ off-diagonal elements, so there are $\displaystyle 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, $\displaystyle 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
    19,769
    Thanks
    3027
    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.
    $\displaystyle 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: $\displaystyle aRa,\;for\;all\;a\in A$
    So, $\displaystyle (a,a)\in R$

    As I understand it, the ordered pair $\displaystyle (a,a)$ is in a partially ordered subset of $\displaystyle A$.
    No. All subsets of $\displaystyle 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, $\displaystyle AxA$.
    This gives me among other things the diagonal terms $\displaystyle (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, $\displaystyle \{(1,2),(1,1),(2,2)\}$
    or, $\displaystyle \{(5,3),(5,5),(3,3)\} $
    I really have no idea what you are doing. What is your objective?

    There are then $\displaystyle n^2-n$ off-diagonal elements, so there are $\displaystyle 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, $\displaystyle 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 $\displaystyle \leq$ is a reflexive relation on the set $\displaystyle A=\{1,2,3\}$, because $\displaystyle 1=1,2=2,3=3$?

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

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

    I've read somewhere that $\displaystyle aRa$ for all $\displaystyle a\in A$ can be seen as $\displaystyle (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 $\displaystyle \leq$ is a reflexive relation on the set $\displaystyle A=\{1,2,3\}$, because $\displaystyle 1=1,2=2,3=3$?

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

    You mentioned that divisibility is reflexive because $\displaystyle 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,577
    Thanks
    790
    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 $\displaystyle R$ on a set $\displaystyle A$ is a function of two arguments that returns true or false: for all $\displaystyle a_1\in A$, $\displaystyle a_2\in A$ we have $\displaystyle 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 $\displaystyle R(a_1,a_2)=\text{true}$ is conventionally written $\displaystyle a_1Ra_2$, e.g., $\displaystyle 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 $\displaystyle F$ with one condition: $\displaystyle \langle x,y_1\rangle\in F$ and $\displaystyle \langle x,y_2\rangle\in F$ imply $\displaystyle y_1=y_2$ for all $\displaystyle 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., $\displaystyle \langle\langle a_1,a_2\rangle,\text{true}rangle$. One prefers a simpler implementation, where one removes pairs where the last element is $\displaystyle \text{false}$ and keeps only the first element $\displaystyle \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 $\displaystyle a_1Ra_2$, where $\displaystyle R$ is an "abstract" relation, becomes $\displaystyle \langle a_1,a_2\rangle\in R$ where $\displaystyle 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 $\displaystyle \langle A, R\rangle$ where $\displaystyle A$ is a set and $\displaystyle R$ is a relation on $\displaystyle R$ satisfying some axioms. I.e., here $\displaystyle R$ can be viewed consisting of ordered pairs of elements of $\displaystyle A$. Of course, one becomes a little sloppy soon and, e.g., talks about a subset of a partial order $\displaystyle \langle A, R\rangle$ meaning a subset $\displaystyle A'$ of $\displaystyle A$ with the restriction of $\displaystyle R$ on $\displaystyle A'$. Literally, one can't take a subset of an ordered pair $\displaystyle \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
    22
    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 $\displaystyle n\mid n$. If $\displaystyle n\mid n'$ then $\displaystyle n'=nz$ for some $\displaystyle z\in\mathbb{Z}$ and similarly we have that $\displaystyle n=nz'$. So then we have that $\displaystyle z=\frac{1}{z'}$ but since $\displaystyle z\in\mathbb{Z}$ it follows that $\displaystyle z'=\pm 1$. But, since we are only dealing with natural numbers $\displaystyle z'=1\implies z=1\implies n=n'$ so it has anti-symmetry. If $\displaystyle n\mid m,m\mid \ell$ then $\displaystyle \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 $\displaystyle n|n'$ and $\displaystyle n'|n$ then $\displaystyle n=n'$.

    $\displaystyle n|n' \Rightarrow n=zn' $

    $\displaystyle n'|n \Rightarrow n'=zn $

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

    Since only natural numbers: $\displaystyle z=1 $

    Hence, $\displaystyle 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: Sep 5th 2011, 01:17 AM
  2. Question about partially ordered sets
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: Apr 6th 2011, 12:54 PM
  3. Partially ordered set with no maximal element
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Mar 9th 2010, 12:37 AM
  4. Replies: 7
    Last Post: Feb 25th 2010, 04:44 AM
  5. Partially ordered set.
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: Jan 10th 2010, 08:42 AM

Search Tags


/mathhelpforum @mathhelpforum