# 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.
$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!
• 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.
$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.

Quote:

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?

Quote:

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