0

I need to check my homework. I'm not good at discrete mathematics and I need to have this homework correct.

Let $S=\{1,2,\ldots,100\}^2$. The partial order $\le_S$ is defined as follows: for $\langle a,b\rangle,\langle x,y\rangle\in S$, $\langle a,b\rangle\le_S\langle x,y\rangle\iff a\le x\land b\le y$.

And I have to find the longest chain and the longest antichain. The minimal element is ordered pair (1,1) and the maximal element is (100,100). I suppose the longest antichain are ordered pairs (1,100), (2,99), ..., (100,1). Am I right? Can I write this result using following formula? $$\alpha(\{1, 2, ..., 100\}^2,\le S)=\bigcup_{i=1}^{100}(i,101-i)$$ The longest chain goes from minimal element (1,1) to maximal element (100,100). I think there is a lot of longest chains. As an example I chose this one - (1,1), (1,2), …, (1,99), (1,100), (2,100), …, (99,100), (100,100). I think it has length of 199 ordered pairs. Am I right? Can I write this result using following formula? $$\omega(\{1, 2, ..., 100\}^2,\le S)=\bigcup_{i=1}^{100}(1,i) \cup \bigcup_{i=2}^{100}(i,100)$$ Thank you very much for your help.

Speedding
  • 357
  • FYI, the mathematical assertion $$(S,\le ) = {1, 2, ..., 100}^2 \iff a\le x \land b \le y$$ might be one of the most ill-composed one can imagine. Please reread (and rewrite) your question. – Did Oct 20 '16 at 09:01
  • I hope it's better now. – Speedding Oct 20 '16 at 09:05
  • @Speedding: It’s really not; see my answer for a way to write what I think you’re trying to express. By the way, are you required to prove that your antichain and chain are longest possible, or just to identify them? – Brian M. Scott Oct 20 '16 at 09:06
  • I am required to prove that, but ofc I have no idea how should I do that. – Speedding Oct 20 '16 at 12:39

1 Answers1

0

You have correctly identified the longest antichain in $S$, but your notation for it is incorrect. It is not the union of the ordered pairs $\langle i,101-i\rangle; it is the set of those ordered pairs,

$$\big\{\langle i,101-i\rangle:i\in\{1,2,\ldots,100\}\big\}\;.$$

You have also correctly identified one of the longest chains, all of which do indeed have $199$ elements, but you’ve made the same mistake in your notation; it should be

$$\big\{\langle 1,i\rangle:i\in\{1,2,\ldots,100\}\big\}\cup\big\{\langle i,100\rangle:i\in\{2,3,\ldots,100\}\big\}\;.$$

As Did notes in the comments, your description of the partial order is very badly written. I suspect that it is supposed to be something like this:

Let $S=\{1,2,\ldots,100\}^2$. The partial order $\le_S$ is defined as follows: for $\langle a,b\rangle,\langle x,y\rangle\in S$, $\langle a,b\rangle\le_S\langle x,y\rangle\iff a\le x\land b\le y$.

Brian M. Scott
  • 616,228