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

Scary

Badges: 13

Rep:

#1

Report Thread starter 3 years ago

#1

Given

a set, Take $(\mathcal{P}(X),\subseteq)$ Where $\mathcal{P}(X)$ 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 $\mathcal{P}(X)$ 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 $\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

, would i say let $A,B\in X$ then if $A\subseteq B$ and $B\subseteq A$ 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 $A\in \mathcal{P}(X)$ then does this imply that $A \subseteq A$ .

Also determining the max and min of

or $\mathcal{P}(X)$ 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 $<L;\lor,\land>$ is called a lattice if

is a non-empty set, $\lor$ and $\land$ are binary operations on

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

a set, Take $(\mathcal{P}(X),\subseteq)$ Where $\mathcal{P}(X)$ 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 $\mathcal{P}(X)$ 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 $\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

, would i say let $A,B\in X$ then if $A\subseteq B$ and $B\subseteq A$ 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 $A\in \mathcal{P}(X)$ then does this imply that $A \subseteq A$ .

Also determining the max and min of

or $\mathcal{P}(X)$ 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 $<L;\lor,\land>$ is called a lattice if

is a non-empty set, $\lor$ and $\land$ are binary operations on

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

a set, Take $(\mathcal{P}(X),\subseteq)$ Where $\mathcal{P}(X)$ 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 $\mathcal{P}(X)$ 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 $\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

, would i say let $A,B\in X$ then if $A\subseteq B$ and $B\subseteq A$ 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 $A\in \mathcal{P}(X)$ then does this imply that $A \subseteq A$ .

Also determining the max and min of

or $\mathcal{P}(X)$ 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 $<L;\lor,\land>$ is called a lattice if

is a non-empty set, $\lor$ and $\land$ are binary operations on

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

(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

and

, 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

, by definition we have $\forall x\in A$ , $x\in B$ and likewise $\forall x\in B$ , $x\in A$ and hence

, $\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

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 $\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

) and the max is just

.
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

a set, Take $(\mathcal{P}(X),\subseteq)$ Where $\mathcal{P}(X)$ 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 $\mathcal{P}(X)$ 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 $\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

, would i say let $A,B\in X$ then if $A\subseteq B$ and $B\subseteq A$ 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 $A\in \mathcal{P}(X)$ then does this imply that $A \subseteq A$ .

Also determining the max and min of

or $\mathcal{P}(X)$ 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 $<L;\lor,\land>$ is called a lattice if

is a non-empty set, $\lor$ and $\land$ are binary operations on

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

(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

and $\mathcal{P}(X)$ 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 $a,b\leqslant x\leqslant u$ then

. 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

and $\mathcal{P}(X)$ as if they are similar entities (as you do when you write: "...which contains

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

is a sup of

, show that if $a,b< x\leqslant u$ then

. 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

Quick Reply

Oops, nobody has posted
in the last few hours.

See more of what you like on
The Student Room

Today on TSR

Poll

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

Watched Threads

Oops, nobody has posted
in the last few hours.

See more of what you like on
The Student Room

TSR Support Team

Get Started

Using TSR

Info

TSR Group

Connect with TSR

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

Not what you're looking for? Try…

Quick Reply

Related discussions

Related articles

Oops, nobody has postedin the last few hours.

Oops, nobody is replying to posts.

See more of what you like onThe Student Room

Today on TSR

Poll

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

Watched Threads

Spotlight

Oops, nobody has postedin the last few hours.

Oops, nobody is replying to posts.

See more of what you like onThe Student Room

TSR Support Team

Get Started

Using TSR

Info

TSR Group

Connect with TSR

Oops, nobody has posted
in the last few hours.

See more of what you like on
The Student Room

Oops, nobody has posted
in the last few hours.

See more of what you like on
The Student Room