[Math] Proving the dual and self-dual of a poset.

order-theoryproof-writingrelations

The dual of a poset $(S \leq)$ is the poset $(S, \geq)$, where for all $x,y \in S$ $x \leq y$ if and only if $ y \geq x$. A poset is self-dual if it is isomorphic to its dual.

Questions:

  1. Verify that the dual of a poset is indeed a poset.

Attempt:

Given a poset $(S ,\leq)$, we can define its dual $(S, \geq)$

Using the definition $(x,y) \in S \leftrightarrow (y,x) \in R$,

we have $(R, \subseteq)$ and its dual is $(R, \supseteq)$

  1. Show that for any set $X$, the poset $(P(X) \subseteq)$ is self-dual.

Note: The $P(X)$ is the power set X

Attempt:

For any X, we have a poset isomorphism such that

$(P(X) ,\subseteq) \rightarrow ((P(X) ,\supseteq)$

$X \rightarrow X' = \alpha ' (x)$

If $X \subseteq Y \rightarrow X^c \supseteq Y^c$, then this map preserves the poset relation and it's an isomorphism. Therefore, $(X \subseteq)$ is self dual if it's isomorphic to its dual.

I'm not sure if this is correct or I should expand my proof further. It seems that I only have a part of it. Like for example on the first question.. wouldn't the last line be $(S, \subseteq)$ and it's dual is $(S \supseteq)$ because we are dealing with the poset $ (S \leq)$ and $(S \geq)$. There's a biconditional statement to begin with which produces two statements.

a. If the dual of a poset $(S \leq)$ is the poset $(S, \geq)$, where for all $x,y \in S$ $x \leq y$, then $ y \geq x$.

b. If $ y \geq x$, then the dual of a poset $(S \leq)$ is the poset $(S, \geq)$, where for all $x,y \in S$ $x \leq y$.

A poset is a partially ordered set if S is a set and R is a partial order on S -> that's the pair $(S,R)$

So the order relation R is a partial order if it's also reflexive, so wouldn't the reflexive definition apply to the first problems?

Best Answer

Not bad, there is a couple of details missing. I will not write a complete solution. This is a very important part of your mathematical training, you are just entering your rigorous stage.

Regarding 1., you need to check that the dual of a poset satisfies the conditions in the definition of the poset. That means reflexivity, antisymmetry and transitivity of $\leq$. I think that you are confused because the proof is completely trivial: just write down the conditions for $(A,\leq)$, turn all the $\leq$ (because that is how $\geq$ is defined, right?) and you are done.

Regarding 2., looks good to me, but I will nitpick anyway.

  • You write $X \subseteq Y \rightarrow X^c \supseteq Y^c$ You should write $A \subseteq B \Rightarrow A^c \supseteq B^c$, because it is confusing to use $X$ for a general element of $P(X)$.
  • Now, how do you know that $A \subseteq B \Rightarrow A^c \supseteq B^c$? Write down what $\subseteq$ and $~^c$ mean and prove the implication.
  • The last thing you need to check is that $A\mapsto A^c$ is a bijection. Hint: what happens if you compose this map with itself?

BTW, just to stimulate your brain and show you that this stuff can be actually integesting: suppose that you are given a finite poset, not a diagram but just the set of pairs that is the relation $\leq$. Is it possible to check fast that the poset is self-dual? Speaking in complexity-theory language, is this a NP-complete problem or not? I think that this is an open problem.

Related Question