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

Watch
Scary
Badges: 13
Rep:
?
#1
Report Thread starter 3 years ago
#1
Given X a set, Take (\mathcal{P}(X),\subseteq) Where \mathcal{P}(X) is the power set of X, 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 \mathcal{P}(X) for a general set X. My attempt for the first part would be to test that X itself is reflexive, anti-symmetric and transitive, however i don't know if i'm to apply this to the set X or \mathcal{P}(X) 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 \subseteq is the partial order on the power set \mathcal{P}(X), but i'm not sure how i would generate the elements of X, would i say let A,B\in X then if A\subseteq B and B\subseteq A then surely A=B since A is contained in B another part that was confusing me is that if we have a subset of X is it a subset of itself i,e A\in \mathcal{P}(X) then does this imply that A \subseteq A.

Also determining the max and min of X or \mathcal{P}(X) seems to depend on if X 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 <L;\lor,\land> is called a lattice if L is a non-empty set, \lor and \land are binary operations on L and both \lor, \land 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
nomnomnoodles
Badges: 8
Rep:
?
#2
Report 3 years ago
#2
(Original post by Scary)
Given X a set, Take (\mathcal{P}(X),\subseteq) Where \mathcal{P}(X) is the power set of X, 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 \mathcal{P}(X) for a general set X. My attempt for the first part would be to test that X itself is reflexive, anti-symmetric and transitive, however i don't know if i'm to apply this to the set X or \mathcal{P}(X) 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 \subseteq is the partial order on the power set \mathcal{P}(X), but i'm not sure how i would generate the elements of X, would i say let A,B\in X then if A\subseteq B and B\subseteq A then surely A=B since A is contained in B another part that was confusing me is that if we have a subset of X is it a subset of itself i,e A\in \mathcal{P}(X) then does this imply that A \subseteq A.

Also determining the max and min of X or \mathcal{P}(X) seems to depend on if X 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 <L;\lor,\land> is called a lattice if L is a non-empty set, \lor and \land are binary operations on L and both \lor, \land 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
reply
nomnomnoodles
Badges: 8
Rep:
?
#3
Report 3 years ago
#3
(Original post by Scary)
Given X a set, Take (\mathcal{P}(X),\subseteq) Where \mathcal{P}(X) is the power set of X, 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 \mathcal{P}(X) for a general set X. My attempt for the first part would be to test that X itself is reflexive, anti-symmetric and transitive, however i don't know if i'm to apply this to the set X or \mathcal{P}(X) 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 \subseteq is the partial order on the power set \mathcal{P}(X), but i'm not sure how i would generate the elements of X, would i say let A,B\in X then if A\subseteq B and B\subseteq A then surely A=B since A is contained in B another part that was confusing me is that if we have a subset of X is it a subset of itself i,e A\in \mathcal{P}(X) then does this imply that A \subseteq A.

Also determining the max and min of X or \mathcal{P}(X) seems to depend on if X 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 <L;\lor,\land> is called a lattice if L is a non-empty set, \lor and \land are binary operations on L and both \lor, \land 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
reply
Lord of the Flies
Badges: 18
Rep:
?
#4
Report 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 a,b\subseteq X, are the sup & inf of a,b (which are written a \lor b and a\land b respectively — this notation is a hint). This has nothing to do with infinity, the order is inclusion.
2
reply
Scary
Badges: 13
Rep:
?
#5
Report Thread starter 3 years ago
#5
My attempt at a solution is as follows; First given two sets A and B, we say A\subseteq B if \forall x \in A we have x\in B.
I now need to show the three conditions for \subseteq to be a partial order on the set. So Reflexive: Let A\subseteq X be some subset then let x\in A then clearly x\in A and so A\subseteq A, so the reflexive property holds.
Anti-symmetric: Let A,B\subseteq X. Then if A\subseteq B and B\subseteq A then A=B, by definition we have \forall x\in A, x\in B and likewise \forall x\in B, x\in A and hence A=B,\forall x \in A,B. Now for the transitive property: Let A,B,C\subseteq X. Then if A\subseteq B we have \forall x \in A ,x\in B and since B\subseteq C, \forall x \in B we have x\in C. Thus \forall x \in A we have that x\in C hence A\subseteq C by definition. and since \subseteq satisfies the above properties it is a partial order.
For a total order i require that \forall A,B\in \mathcal{P}(X) we have A\subseteq B or B\subseteq A, my solution for this is to show a counter example so show that it cannot be true unless X 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 X and \mathcal{P}(X) 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 \emptyset(since \emptyset \in A for all sets A) and the max is just X.
Does this imply the infimum and supremum are the same as the maximum and minimum?
0
reply
Scary
Badges: 13
Rep:
?
#6
Report Thread starter 3 years ago
#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
reply
commie2
Badges: 2
Rep:
?
#7
Report 3 years ago
#7
(Original post by Scary)
Given X a set, Take (\mathcal{P}(X),\subseteq) Where \mathcal{P}(X) is the power set of X, 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 \mathcal{P}(X) for a general set X. My attempt for the first part would be to test that X itself is reflexive, anti-symmetric and transitive, however i don't know if i'm to apply this to the set X or \mathcal{P}(X) 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 \subseteq is the partial order on the power set \mathcal{P}(X), but i'm not sure how i would generate the elements of X, would i say let A,B\in X then if A\subseteq B and B\subseteq A then surely A=B since A is contained in B another part that was confusing me is that if we have a subset of X is it a subset of itself i,e A\in \mathcal{P}(X) then does this imply that A \subseteq A.

Also determining the max and min of X or \mathcal{P}(X) seems to depend on if X 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 <L;\lor,\land> is called a lattice if L is a non-empty set, \lor and \land are binary operations on L and both \lor, \land 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
reply
Scary
Badges: 13
Rep:
?
#8
Report Thread starter 3 years ago
#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 a,b\subseteq X, are the sup & inf of a,b (which are written a \lor b and a\land b 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
reply
Scary
Badges: 13
Rep:
?
#9
Report Thread starter 3 years ago
#9
(Original post by commie2)
Yikes! What level of maths is this?
advanced undergraduate to post graduate.
0
reply
Lord of the Flies
Badges: 18
Rep:
?
#10
Report 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 X and \mathcal{P}(X) and that the intersection is the largest set which is contained in both of those sets.
To show u is a sup of a,b, show that if a,b\leqslant x\leqslant u then x= u. Similarly for inf.

( here \leqslant is \subseteq).
0
reply
DFranklin
Badges: 18
Rep:
?
#11
Report 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 X and \mathcal{P}(X) as if they are similar entities (as you do when you write: "...which contains X and \mathcal{P}(X)...".

For the suprenum, you need to show:

Given A, B \in  \mathcal{P}(X), there exists M \in \mathcal{P}(X) such that:

(a) A \subseteq M, B \subseteq M (think of this as the "upper bound" part of least upper bound)

and

(b) Whenever we have N \in \mathcal{P}(X) with A \subseteq N, B \subseteq N, we also have M \subseteq N (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
DFranklin
Badges: 18
Rep:
?
#12
Report 3 years ago
#12
(Original post by Lord of the Flies)
To show u is a sup of a,b, show that if a,b< x\leqslant u then x= u. Similarly for inf.

( here < is \subset).
Is it "a,b<x \leqslant u" or "a,b \leqslant x \leqslant u"?

(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
Lord of the Flies
Badges: 18
Rep:
?
#13
Report 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
reply
DFranklin
Badges: 18
Rep:
?
#14
Report 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
reply
Lord of the Flies
Badges: 18
Rep:
?
#15
Report 3 years ago
#15
(Original post by DFranklin)
...
My apologies you are quite right! Thanks for the catch, will correct now
1
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

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%

Watched Threads

View All