# Showing that $$(P(X),\subseteq)$$ is a partial order or total order & lattice.

Watch
Announcements
#1
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
3 years ago
#2
(Original post by 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.
Hi! Just for context I'm currently doing my masters in pure mathematics, specialising in group theory.
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
3 years ago
#3
(Original post by 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.
*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
3 years ago
#4
(Original post by Scary)
...
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.
2
#5
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?
0
#6
(Original post by 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
Thank you i will be sure to have a look
0
3 years ago
#7
(Original post by 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.
Yikes! What level of maths is this?
0
#8
(Original post by 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.
Hi thank you for your response, For a total order, is it only when the set itself is the empty set or a singleton
0
#9
(Original post by commie2)
Yikes! What level of maths is this?
0
3 years ago
#10
(Original post by 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.
To show is a sup of , show that if then . Similarly for inf.

here is .
0
3 years ago
#11
(Original post by Scary)
..
I'm basically looking these terms up on Wikipedia because I've never done lattices, but I don't 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
3 years ago
#12
(Original post by Lord of the Flies)
To show is a sup of , show that if then . Similarly for inf.

here is .
Is it "" or ""?

(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
3 years ago
#13
(Original post by DFranklin)
...
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.
0
3 years ago
#14
(Original post by 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.
I think this is kind of what you're saying by "circumventing the case where u = a or b", but if we take X = {1,2,3}, a = {1}, b = {1,2} and (erroneously) that u = {1,2,3}, then it's true that:

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
3 years ago
#15
(Original post by DFranklin)
...
My apologies you are quite right! Thanks for the catch, will correct now
1
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### Poll

Join the discussion

#### Do you have the space and resources you need to succeed in home learning?

Yes I have everything I need (156)
60.7%
I don't have everything I need (101)
39.3%