# Partially Ordered Set, example from Wiki.

• Jan 15th 2010, 11:30 PM
Mollier
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!
• Jan 16th 2010, 01:03 AM
HallsofIvy
Quote:

Originally Posted by Mollier
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.

Quote:

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?

Quote:

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.
• Jan 16th 2010, 02:30 AM
Mollier
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 :)
• Jan 16th 2010, 02:31 AM
Mollier
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 :)
• Jan 16th 2010, 04:29 AM
emakarov
Quote:

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.
• Jan 18th 2010, 03:56 AM
Mollier

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.
• Jan 18th 2010, 05:26 PM
Drexel28
Quote:

Originally Posted by Mollier

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.
• Jan 18th 2010, 07:58 PM
Mollier
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!