2
$\begingroup$

Okay, so I'm stuck on a question and I'm not sure how to solve it, so here it is: In the following questions, $B_n = \mathcal{P}(\{1, ... , n\})$ is ordered by containment, the set $\{0,1\}$ is ordered by the relation $0 \leq 1$, and $\{0,1\}^n$ is ordered using the product order.

a) Draw Hasse diagram of $\{0,1\}^3$

b) Give an order isomorphism from $B_3$ to $\{0,1\}^3$

c) Prove that $B_n$ is isomorphic to its dual. Your proof must include a clear explicit definition of the order isomorphism you use to prove this.

d) Prove that $\{0,1\}^n$ is isomorphic to $B_n$. Your proof must include a clear and explicit definition of the order isomorphism you use to prove this.

Okay so I got a) and b), I started on c) but what's throwing me off is that $B_n$ is infinite (meaning I have to show that its isomorphic to its dual for all sets (or elements?) of numbers.

I started c) by "Let $R$ be an order relation on $S$. The dual order is $R^{-1}$. In other words if $a R b$ then $b R a$."

$\endgroup$
3
  • $\begingroup$ I've added LaTeX formatting to your question, and also tried to give a more descriptive title; if you think of a better one, or any other edits, please feel free to make them. $\endgroup$
    – Zev Chonoles
    Nov 30, 2011 at 3:03
  • 1
    $\begingroup$ Also, I would like to express my appreciation for explaining what is confusing you; all too often, users post questions without even demonstrating they have thought about it. People are, of course, much more willing to help those who have put effort into it themselves, so I'm sure you'll get some good answers soon. $\endgroup$
    – Zev Chonoles
    Nov 30, 2011 at 3:04
  • $\begingroup$ Thanks soo much, I'm new to this, also the last bit there is R^(-1) sorry, you put R - 1. thanks so much again! $\endgroup$
    – Paul
    Nov 30, 2011 at 3:33

1 Answer 1

Reset to default
1
$\begingroup$

In c) and d) you don't work with infinite sets $B_n$. These sets are finite, for each $B_n$ has exactly $n$ elements and $n$ is a natural number, hence finite! But you're right you have an infinite family of sets: $B_1,B_2,B_3,\ldots$. These facts c) and d) are stated in a general way, that is they mean that whatever value of $n$ you take, the isomorphisms will hold for this certain $n$. To prove these facts you abstractly fix one conrete value of $n$ and provide a proof for this $n$.

Below you have some loose hints how proofs can be done.

To prove c) consider the function $f:(B_n,\subseteq)\to(B_n,\subseteq^{-1})$ given by the formula $f(A)=\{1,\ldots,n\}\setminus A$ (ie. take simply the complement of $A$). This function preserves the order because for any abstract sets $X,Y\subseteq Z$ we have: $X\subseteq Y \Leftrightarrow Z\setminus Y\subseteq Z\setminus X$. Bijectivity of $f$ is trivial.

Proving d) is also very easy. Consider the function $g:B_n\to\{0,1\}^n$ defined as follows: $g(A)=(\chi_A(1),\chi_A(2),\ldots,\chi_A(n))$, where $\chi_A$ is the characteristic function of $A$ ie. $\chi_A(x)=0$ if $x\not\in A$ and $\chi_A(x)=1$ if $x\in A$. I leave you to show that $A\subseteq B$ implies $g(A)\le g(B)$ in the product order sense as well as that $g$ is a bijection.

If you have any questions, feel free to ask.

$\endgroup$
8
  • $\begingroup$ wait so then for d) do I have to show that x is also an element of B? $\endgroup$
    – Paul
    Nov 30, 2011 at 4:00
  • $\begingroup$ okay so x is elements of both A and B since its a bijection, but I have to show that its a bijection right? $\endgroup$
    – Paul
    Nov 30, 2011 at 4:16
  • $\begingroup$ okay since I have to show that its isomorphic, I have to show that both sets have the same number of elements and they each correspond to each other. That part is clear, but like in c) do I have to show that g(A)\A and g(B)\B? $\endgroup$
    – Paul
    Nov 30, 2011 at 4:22
  • $\begingroup$ Paul: I have a hard time to understand you comments. Let's talk about d). You have to show that two orders are iso. The first order consists of subsets of $\{1,\ldots,n\}$, the second one -- of $n$-tuples $(a_1,\ldots,a_n)$, where $a_i\in\{0,1\}$. So you have to translate somehow subsets of $\{1,\ldots,n\}$ to these $n$-tuples. This is done by function $g$ which looks at subsets (by looking at its elements) and assigns to these subsets $n$-tuples. It has to be an order isomorphism, so if $A\subseteq B$ (ordering in $B_n$), then $g(A)\le g(B)$ (ordering in $\{0,1\}^n$). So to check this... $\endgroup$
    – Damian Sobota
    Nov 30, 2011 at 14:06
  • $\begingroup$ ... you take two elements $A,B$ of $B_n$, which are subsets of $\{1,\ldots,n\}$, assume that $A\subseteq B$ (ordering in $B_n$) and have to show that $g(A)\le g(B)$ in the sense of the product order on $\{1,\ldots,n\}$. And if $g$ is to be an isomorphism, then it must be a bijection. So you have to show that $g$ is injective (there is no element in $\{0,1\}^n$ corresponding via $g$ to two different elements of $B_n$) and surjective (to each element of $\{0,1\}^n$ there is an element of $B_n$ corresponding to it via $g$). $\endgroup$
    – Damian Sobota
    Nov 30, 2011 at 14:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .