# Showing that [tex](P(X),\subseteq)[/tex] is a partial order or total order & lattice.

Watch
Announcements

Page 1 of 1

Go to first unread

Skip to page:

Given a set, Take Where is the power set of , My question is how would i show if the above is a partial order, and when is it a total order? and is it a lattice, how could i determine the max and min of for a general set . My attempt for the first part would be to test that itself is reflexive, anti-symmetric and transitive, however i don't know if i'm to apply this to the set or and how to do this for a set which is just as general as the one above.

The main problem i have is starting the problem, i think now looking at it again i would try to show that is the partial order on the power set , but i'm not sure how i would generate the elements of , would i say let then if and then surely since is contained in another part that was confusing me is that if we have a subset of is it a subset of itself i,e then does this imply that .

Also determining the max and min of or seems to depend on if is finite or infinite, if it is infinite then surely the set does not have a maximum or a minimum but i'm not too certain if my idea is correct.

I cant seem to find the definition of a lattice that is related to partial orders, all i could find is that a lattice as an algebra is equivalent to a lattice as a partially ordered set. The definition of a lattice that i am using is as follows, An algebra is called a lattice if is a non-empty set, and are binary operations on and both , are idempotent,commutative, and associative and they also satisfy the absorption law.

Any help would be highly appreciated, Thanks for taking the time to read my question.

The main problem i have is starting the problem, i think now looking at it again i would try to show that is the partial order on the power set , but i'm not sure how i would generate the elements of , would i say let then if and then surely since is contained in another part that was confusing me is that if we have a subset of is it a subset of itself i,e then does this imply that .

Also determining the max and min of or seems to depend on if is finite or infinite, if it is infinite then surely the set does not have a maximum or a minimum but i'm not too certain if my idea is correct.

I cant seem to find the definition of a lattice that is related to partial orders, all i could find is that a lattice as an algebra is equivalent to a lattice as a partially ordered set. The definition of a lattice that i am using is as follows, An algebra is called a lattice if is a non-empty set, and are binary operations on and both , are idempotent,commutative, and associative and they also satisfy the absorption law.

Any help would be highly appreciated, Thanks for taking the time to read my question.

0

reply

Report

#2

(Original post by

Given a set, Take Where is the power set of , My question is how would i show if the above is a partial order, and when is it a total order? and is it a lattice, how could i determine the max and min of for a general set . My attempt for the first part would be to test that itself is reflexive, anti-symmetric and transitive, however i don't know if i'm to apply this to the set or and how to do this for a set which is just as general as the one above.

The main problem i have is starting the problem, i think now looking at it again i would try to show that is the partial order on the power set , but i'm not sure how i would generate the elements of , would i say let then if and then surely since is contained in another part that was confusing me is that if we have a subset of is it a subset of itself i,e then does this imply that .

Also determining the max and min of or seems to depend on if is finite or infinite, if it is infinite then surely the set does not have a maximum or a minimum but i'm not too certain if my idea is correct.

I cant seem to find the definition of a lattice that is related to partial orders, all i could find is that a lattice as an algebra is equivalent to a lattice as a partially ordered set. The definition of a lattice that i am using is as follows, An algebra is called a lattice if is a non-empty set, and are binary operations on and both , are idempotent,commutative, and associative and they also satisfy the absorption law.

Any help would be highly appreciated, Thanks for taking the time to read my question.

**Scary**)Given a set, Take Where is the power set of , My question is how would i show if the above is a partial order, and when is it a total order? and is it a lattice, how could i determine the max and min of for a general set . My attempt for the first part would be to test that itself is reflexive, anti-symmetric and transitive, however i don't know if i'm to apply this to the set or and how to do this for a set which is just as general as the one above.

The main problem i have is starting the problem, i think now looking at it again i would try to show that is the partial order on the power set , but i'm not sure how i would generate the elements of , would i say let then if and then surely since is contained in another part that was confusing me is that if we have a subset of is it a subset of itself i,e then does this imply that .

Also determining the max and min of or seems to depend on if is finite or infinite, if it is infinite then surely the set does not have a maximum or a minimum but i'm not too certain if my idea is correct.

I cant seem to find the definition of a lattice that is related to partial orders, all i could find is that a lattice as an algebra is equivalent to a lattice as a partially ordered set. The definition of a lattice that i am using is as follows, An algebra is called a lattice if is a non-empty set, and are binary operations on and both , are idempotent,commutative, and associative and they also satisfy the absorption law.

Any help would be highly appreciated, Thanks for taking the time to read my question.

I'm a big believer in trying to solve things for yourself and I wouldn't want to patronise you by spoon-feeding you an answer; my advice for now would be to go back to the basic definitions you have for partial and total orders and make sure you really understand them.

You're correct in looking to show that it's a partial order on the power set.

A helplful definition of the lattice might be the following; "a poset (partially ordered set) where every pair of elements have both a unique supremum and unique infimum. A good example of such a lattice would be the natural numbers with partial order by divisibility, where the unique supremum for a pair of numbers is the lcm and the unique infimum is the gcd.

Good luck!

1

reply

Report

#3

**Scary**)

Given a set, Take Where is the power set of , My question is how would i show if the above is a partial order, and when is it a total order? and is it a lattice, how could i determine the max and min of for a general set . My attempt for the first part would be to test that itself is reflexive, anti-symmetric and transitive, however i don't know if i'm to apply this to the set or and how to do this for a set which is just as general as the one above.

The main problem i have is starting the problem, i think now looking at it again i would try to show that is the partial order on the power set , but i'm not sure how i would generate the elements of , would i say let then if and then surely since is contained in another part that was confusing me is that if we have a subset of is it a subset of itself i,e then does this imply that .

Also determining the max and min of or seems to depend on if is finite or infinite, if it is infinite then surely the set does not have a maximum or a minimum but i'm not too certain if my idea is correct.

I cant seem to find the definition of a lattice that is related to partial orders, all i could find is that a lattice as an algebra is equivalent to a lattice as a partially ordered set. The definition of a lattice that i am using is as follows, An algebra is called a lattice if is a non-empty set, and are binary operations on and both , are idempotent,commutative, and associative and they also satisfy the absorption law.

Any help would be highly appreciated, Thanks for taking the time to read my question.

0

reply

Report

#4

(Original post by

...

**Scary**)...

*inclusion.*

2

reply

My attempt at a solution is as follows; First given two sets and , we say if we have .

I now need to show the three conditions for to be a partial order on the set. So Reflexive: Let be some subset then let then clearly and so , so the reflexive property holds.

Anti-symmetric: Let . Then if and then , by definition we have , and likewise , and hence ,. Now for the transitive property: Let . Then if we have , and since , we have . Thus we have that hence by definition. and since satisfies the above properties it is a partial order.

For a total order i require that we have or , my solution for this is to show a counter example so show that it cannot be true unless is the empty set or the singleton set. My problem with the lattice is how do i establish that the union is the smallest set which contains and and that the intersection is the largest set which is contained in both of those sets. (would i go back to the definition of union and intersection)? And for the min and max i figured out that the min is (since for all sets ) and the max is just .

Does this imply the infimum and supremum are the same as the maximum and minimum?

I now need to show the three conditions for to be a partial order on the set. So Reflexive: Let be some subset then let then clearly and so , so the reflexive property holds.

Anti-symmetric: Let . Then if and then , by definition we have , and likewise , and hence ,. Now for the transitive property: Let . Then if we have , and since , we have . Thus we have that hence by definition. and since satisfies the above properties it is a partial order.

For a total order i require that we have or , my solution for this is to show a counter example so show that it cannot be true unless is the empty set or the singleton set. My problem with the lattice is how do i establish that the union is the smallest set which contains and and that the intersection is the largest set which is contained in both of those sets. (would i go back to the definition of union and intersection)? And for the min and max i figured out that the min is (since for all sets ) and the max is just .

Does this imply the infimum and supremum are the same as the maximum and minimum?

0

reply

(Original post by

*Also for future help with higher - level mathematics problems, I'd recommend posting on maths stackexchange; tends to be used more by people who could help you

**nomnomnoodles**)*Also for future help with higher - level mathematics problems, I'd recommend posting on maths stackexchange; tends to be used more by people who could help you

0

reply

Report

#7

**Scary**)

Given a set, Take Where is the power set of , My question is how would i show if the above is a partial order, and when is it a total order? and is it a lattice, how could i determine the max and min of for a general set . My attempt for the first part would be to test that itself is reflexive, anti-symmetric and transitive, however i don't know if i'm to apply this to the set or and how to do this for a set which is just as general as the one above.

The main problem i have is starting the problem, i think now looking at it again i would try to show that is the partial order on the power set , but i'm not sure how i would generate the elements of , would i say let then if and then surely since is contained in another part that was confusing me is that if we have a subset of is it a subset of itself i,e then does this imply that .

Also determining the max and min of or seems to depend on if is finite or infinite, if it is infinite then surely the set does not have a maximum or a minimum but i'm not too certain if my idea is correct.

I cant seem to find the definition of a lattice that is related to partial orders, all i could find is that a lattice as an algebra is equivalent to a lattice as a partially ordered set. The definition of a lattice that i am using is as follows, An algebra is called a lattice if is a non-empty set, and are binary operations on and both , are idempotent,commutative, and associative and they also satisfy the absorption law.

Any help would be highly appreciated, Thanks for taking the time to read my question.

0

reply

(Original post by

What you're doing for the partial order condition is right. It is a total order if, additionally, every element is comparable — there are only two cases in which this can arise. A lattice is a poset where any two elements have a sup and and inf. The power set under inclusion is a lattice — think about what sets, given , are the sup & inf of (which are written and respectively — this notation is a hint). This has nothing to do with infinity, the order is

**Lord of the Flies**)What you're doing for the partial order condition is right. It is a total order if, additionally, every element is comparable — there are only two cases in which this can arise. A lattice is a poset where any two elements have a sup and and inf. The power set under inclusion is a lattice — think about what sets, given , are the sup & inf of (which are written and respectively — this notation is a hint). This has nothing to do with infinity, the order is

*inclusion.*
0

reply

(Original post by

Yikes! What level of maths is this?

**commie2**)Yikes! What level of maths is this?

0

reply

Report

#10

(Original post by

My problem with the lattice is how do i establish that the union is the smallest set which contains and and that the intersection is the largest set which is contained in both of those sets.

**Scary**)My problem with the lattice is how do i establish that the union is the smallest set which contains and and that the intersection is the largest set which is contained in both of those sets.

here is .

0

reply

Report

#11

(Original post by

..

**Scary**)..

*think*this is too hard.

You seem to be confused about what we're comparing here: when you're talking about sets it's almost always a mistake to be talking about and as if they are similar entities (as you do when you write: "...which contains and ...".

For the suprenum, you need to show:

Given , there exists such that:

(a) (think of this as the "upper bound" part of least upper bound)

and

(b) Whenever we have with , we also have (this of this as the "least" part of least upper bound).

If you think of M as "the smallest set containing (all elements of) A and B", it's pretty obvious what it must be, and you then simply need to verify that (a) and (b) hold.

The infinum case is very similar.

0

reply

Report

#12

(Original post by

To show is a sup of , show that if then . Similarly for inf.

here is .

**Lord of the Flies**)To show is a sup of , show that if then . Similarly for inf.

here is .

(I'm looking at https://en.wikipedia.org/wiki/Join_and_meet and it seems to equate to the latter).

Also, sorry for crossing over with you on the posts!

0

reply

Report

#13

(Original post by

...

**DFranklin**)...

0

reply

Report

#14

(Original post by

I suppose I should've added a,b non-empty to circumvent the one-line case where u = a or b. But otherwise it doesn't matter too much, a < proof implies a ≤ proof, just seemed like less words.

**Lord of the Flies**)I suppose I should've added a,b non-empty to circumvent the one-line case where u = a or b. But otherwise it doesn't matter too much, a < proof implies a ≤ proof, just seemed like less words.

if a, b < x <= u then x = u (because the *only* set x satisfying b < x is u),

but obviously u is not the correct suprenum.

[Not trying to be a pain, but either my understanding is wrong (in which case I'd like it cleared up), or this is possibly going to mislead the OP].

0

reply

Report

#15

(Original post by

...

**DFranklin**)...

1

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top