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
    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.2011-11-30
  • 1
    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.2011-11-30
  • 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
    wait so then for d) do I have to show that x is also an element of B?2011-11-30
  • 0
    okay so x is elements of both A and B since its a bijection, but I have to show that its a bijection right?2011-11-30
  • 0
    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?2011-11-30
  • 0
    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...2011-11-30
  • 0
    ... 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$).2011-11-30
  • 0
    Okay, so I'm thinking, "X_a(x) is an element of A iff x = 1 and X_a (x) is not an element of A iff x = 0." , "X_b(x) is an element of B iff x greater or equal to 1 and X_b(x) is not an element of B iff x = 0" So by that I went on by taking the situation x_a (less than equal) to x_b where x_a = 1 and x_b = 0, and I think that doesnt work because I'm assuming A is contained in B.2011-11-30
  • 0
    And to to get bijectivity of the function g I was thinking of getting its inverse.2011-11-30
  • 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