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$."

  • 0
    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!2011-11-30

1 Answers 1

1

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.

  • 0
    Paul: use dollar symbols around latex commands. What is $X_a(x)$ in your comment? Did you mean $\chi_A(x)$? Then it is a number (a value of a function $\chi_A$ in point $x$), not a member of $A$. Read carefully my answers and comments.2011-11-30