Jump to content

antichain

From Wiktionary, the free dictionary

English

[edit]
English Wikipedia has an article on:
Wikipedia

Etymology

[edit]

From anti- +‎ chain.

Noun

[edit]

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, Springer, 5th Edition, page 199,
      In 1928 Emanuel Sperner asked and answered the following question: Suppose we are given the set . Call a family of subsets of [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 of all -sets satisfies the antichain property with . Looking at the maximum of the binomial coefficients (see page 14) we conclude that there is an antichain of size . Sperner's theorem now asserts that there are no larger ones.

Derived terms

[edit]

Translations

[edit]

Anagrams

[edit]