0

In a poset $P = (S,\leq)$, we say that a chain is any sequence $x_1,x_2,\ldots,x_k$ of distinct elements in $S$,such that $x_1\leq x_2\leq\ldots\leq x_k$.

For example, consider the poset $P = (P(A),\subseteq)$, where $A = \{1,2,\ldots,n\}$. One example of a chain here could be the sequence $\emptyset$, $\{2, 5\}$, $\{1, 2, 5\}$, $\{1, 2, 3, 4, 5\}$, because $$\emptyset\subseteq \{2, 5\} \subseteq \{1,2,5\} \subseteq \{1,2,3,4,5\}.$$ So, the question is... What is the largest number of elements you can have in a chain, in the poset $P = (P(A),\subseteq)$ defined in this problem? Prove that your claim is correct.

Mundron Schmidt
  • 7,993
Duncan Alf Zhang
  • 23
  • 1
    It would have been a much more interesting if we allow $|A|=\kappa$ to be any cardinal, instead of restricting it to a finite number. – Kenny Lau Sep 15 '17 at 11:20
  • @Arthur the interestingness is that for finite $n$ the answer is $n+1$ whereas for infinite $\kappa$ the answer is $2^\kappa$... – Kenny Lau Sep 15 '17 at 11:24
  • @KennyLau You're right, that is interesting. At any rate, i believe that keeping things finite will be enough for this question. – Arthur Sep 15 '17 at 11:31
  • 2
    Let's make this an interesting problem. How many maximal chains (chains of length 6) are there in P(A)? – William Elliot Sep 15 '17 at 11:32
  • @WilliamElliot each chain is defined by the order of removing the elements from $A$ itself, so the number is same as the number of bijections $A \to A$, i.e. $|A|! = 5! = 120$. – Kenny Lau Sep 15 '17 at 11:34

0 Answers0