Is there a set A where (\mathcal{P}(A), \subseteq) is totally ordered?

[Jacobpm64]

Are there any sets A for which [tex](\mathcal{P}(A), \subseteq)[/tex] is totally ordered? Prove your answer.

To be courteous, I will include the definitions for partial ordering and total ordering.

A relation is a partial order if the relation is reflexive, antisymmetric, and transitive. (in this case, the notation [tex](\mathcal{P}(A), \subseteq)[/tex] just denotes that [tex] \mathcal{P}(A) [/tex] under the relation [tex] \subseteq[/tex] is a partially ordered set.

A partially ordered set A with partial order [tex] \leq [/tex] is said to be totally ordered if given any two elements a and b in A, either [tex] a \leq b [/tex] or [tex] b \leq a [/tex].

So, to attempt this problem. I tried making up examples first. The only set A that I could come up with for which [tex](\mathcal{P}(A),\subseteq)[/tex] is totally ordered is a set with one element. Just to see this, let A = {1}. In this case, [tex] \mathcal{P}(A) = [/tex]{[tex]\emptyset[/tex] , {1}}. So, if I pick any two elements, a and b. [tex] a \leq b [/tex] or [tex] b \leq a [/tex]. For example, if I'd pick [tex] \emptyset [/tex] and {1}. Then, [tex] \emptyset \subseteq [/tex]{1}. So I think it works. I don't know if there are any other sets, A, where this works or if I'm even thinking about this correctly. (once I figure out all the sets, I'll attempt to put a proof up). Thanks in advance.

 

[morphism]

What you did is completely valid. P({1}) is totally ordered under inclusion, and this is enough to answer the problem.

If you want all such sets, then this isn't hard either. P(empty set) is also (trivially) totally ordered under inclusion. On the other hand if A contains at least two elements, say x and y, then {x} and {y} cannot be compared by inclusion, so P(A) isn't totally ordered.

 

[Jacobpm64]

so, in order to prove that it works for the empty set and a set with only one element, I need to provide a proof with two cases, correct?

Let me try to type that one up. Give me a bit, I'll post it here.

 

[Jacobpm64]

Claim: If A = [tex] \emptyset [/tex] or A has only one element, then[tex](\mathcal{P}(A),\subseteq)[/tex] is totally ordered.

Proof: Let A be a set. Assume A = [tex] \emptyset [/tex] or A has only one element.
Case 1: Suppose A = [tex] \emptyset [/tex]. Thus, [tex] \mathcal{P}(A) = [/tex]{ [tex] \emptyset [/tex] }. Let a = [tex] \emptyset [/tex] and b = [tex] \emptyset [/tex]. Therefore, [tex] a \geq b [/tex]. Hence, if A = [tex] \emptyset [/tex], then [tex](\mathcal{P}(A),\subseteq)[/tex] is totally ordered.
Case 2: Suppose A has only one element. Let x be an arbitrary element in A. Therefore, A = {x}. Thus, [tex] \mathcal{P}(A) [/tex] = { [tex] \emptyset [/tex], {x}}.

I'm stuck now.. Do I have to break it into a lot of cases, where empty set and empty set are chosen, empty set and x are chosen, or x and x are chosen?

 

[morphism]

Since the empty set is in {x}, you're done. You don't really have to break it into any cases. I think it's obvious.

Actually, ALL you need to do to solve your question is say: "Yes. P({empty}) has only one element and so must be totally ordered."

 

[Jacobpm64]

All right, thanks a lot.