antichain

English

Etymology

Etymology tree

Proto-Indo-European *h₂ent-

Proto-Indo-European *-s

Proto-Indo-European *h₂énts

Proto-Indo-European *-i

Proto-Indo-European *h₂énti

Ancient Greek ᾰ̓ντῐ́ (ăntĭ́)

Ancient Greek ἀντι- (anti-)der.

English anti-

Proto-Italic *katesnā

Latin catēna

Old French chaeinebor.

Middle English cheyne

English chain

English antichain

From anti- + chain.

Noun

antichain (plural antichains)

1. (set theory, order theory, graph theory) A subset, A, of a partially ordered set, (P, ≤), such that no two elements of A are comparable with respect to ≤.
   • 1997, Winfried Just, Martin Weese, Discovering Modern Set Theory II: Set-Theoretic Tools for Every Mathematician, American Mathematical Society, page 140:

     First of all, Zorn's Lemma implies that every uncountable antichain in T is contained in a maximal uncountable antichain. So it suffices to make sure that T has no maximal uncountable antichains.

   • 2013, Vijay K. Garg, Maximal Antichain Lattice Algorithms for Distributed Computations, Proceedings, Davide Frey, Michel Raynal, Saswati Sarkar, Rudrapatna K. Shyamasundar, Prasun Sinha (editors), Distributed Computing and Networking: 14th International Conference, ICDCN, Springer, LNCS 7730, page 245,

     We first define three different but isomorphic lattices: the lattice of maximal antichain ideals, the lattice of maximal antichains and the lattice of strict ideals.

   • 2014, Martin Aigner, Günter M. Ziegler, Proofs from THE BOOK, 5th edition, Springer, page 199:

     In 1928 Emanuel Sperner asked and answered the following question: Suppose we are given the set $N=\{1,2,3,\dots ,n\}$. Call a family $ℱ$ of subsets of $N$^{[i.e., F ⊆ the power set P(N), which has partial order ⊆]} an antichain if no set of $ℱ$ contains another set of the family $ℱ$. What is the size of a largest antichain? Clearly, the family ${ℱ}_k$ of all $k$-sets satisfies the antichain property with $|{ℱ}_k|=(\genfrac{}{}{0ex}{}{n}{k})$. Looking at the maximum of the binomial coefficients (see page 14) we conclude that there is an antichain of size $(\genfrac{}{}{0ex}{}{n}{[n/2]})={max}_k(\genfrac{}{}{0ex}{}{n}{k})$. Sperner's theorem now asserts that there are no larger ones.

Derived terms

• maximal antichain

Translations

subset of a partially ordered set

• Finnish: antiketju
• Italian: anticatena f
• Spanish: anticadena f

Anagrams

• anti-China