# Math Help - Partial Order

1. ## 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

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

3. Originally Posted by Drexel28
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 !!

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

5. Originally Posted by aman_cc
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?

Originally Posted by aman_cc
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!

6. Originally Posted by tonio
.

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?

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

8. Originally Posted by aman_cc
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'.

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