Differences

This shows you the differences between two versions of the page.

--- sav08:playground [2008/03/19 16:02]
vkuncak
+++ sav08:playground [2012/07/27 12:52]
hossein
@@ Line 1: / Line 1: @@
 ====== Playground ======
-Therefore $ subst(sigma)( x ) = x$
-$ sigma rm  {}d{}e{}fined  x$
+===== Problem 1: Linear Extension =====
-$ sigma rm  defined  x$
+Let $r\subseteq A\times A$ be an arbitrary relation and $\leq$ a partial order on $A$.
+a) Assume $a,b\in A$ to be incomparable: $a\not\leq b$ and $b\not\leq a$. Show that the transitive closure of the relation $r_{\text{ex}}$ is a partial order on $A$.
+$r_{\text{ex}} = \{(x,y) | x\leq y\}\cup\{(a,b)\}$
+b) Use (a) to show if $A$ is finite then every order $\leq$ on $A$ has a linear extension.
+A total order $\leq_{1}$ is a linear extension of a partial order $\leq$ if, whenever $x\leq y$ implies that $x\leq_{1} y$.
+c) Use (a) to show there is a finite number of total orders $(A,\leq_1),\cdots,(A,\leq_n)$ such that for all $a,b\in A$ we have
+$a\leq b \Leftrightarrow (a\leq_1b \wedge\cdots\wedge a\leq_n b)$
+d) Show that $\leq_1$ is a linear extension of $\leq$ if and only if $(A,\leq_1)$ is a total order and the identity function is a monotone function from $(A,\leq)$ to $(A,\leq_1)$.
+This is the Proglab poster: {{sav08:proglabresearch.pptx|}}