PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Medium Entry average rating: No information on entry rating
antichain (Definition)

A subset $A$ of a poset $(P,<_P)$ is an antichain if no two elements are comparable. That is, if $a,b\in A$ then $a\nless_P b$ and $b\nless_P a$

A maximal antichain of $T$ is one which is maximal.

In particular, if $(P,<_P)$ is a tree then the maximal antichains are exactly those antichains which intersect every branch, and if the tree is splitting then every level is a maximal antichain.




"antichain" is owned by Henry.
(view preamble | get metadata)

View style:

See Also: tree (set theoretic), Aronszajn tree

Also defines:  antichain, maximal antichain
Log in to rate this entry.
(view current ratings)

Cross-references: level, branch, intersect, tree, comparable, poset, subset
There are 16 references to this entry.

This is version 3 of antichain, born on 2002-07-26, modified 2002-08-18.
Object id is 3212, canonical name is Antichain.
Accessed 8406 times total.

Classification:
AMS MSC05C05 (Combinatorics :: Graph theory :: Trees)
 03E05 (Mathematical logic and foundations :: Set theory :: Other combinatorial set theory)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)