Covering relation

Covering relation
The Hasse diagram of the power set of three elements, partially ordered by inclusion.

In mathematics, especially order theory, the covering relation of a partially ordered set is the binary relation which holds between comparable elements that are immediate neighbours. The covering relation is commonly used to graphically express the partial order by means of the Hasse diagram.

Contents

Definition

Let X be a set with a partial order ≤. As usual, let < be the relation on X such that x < y if and only if x ≤ y and x ≠ y.

Let x and y be elements of X.

Then y covers x, written x <· y, if x < y and there is no element z such that x < z < y. Equivalently, y covers x if the interval [xy] is the two-element set {x, y}.

When x <· y, it is said that y is a cover of x. Some authors also use the term cover to denote any such pair (x, y) in the covering relation.

Examples

  • In a finite linearly ordered set 1,… n, i + 1 covers i for all i between 1 and n − 1 (and there are no other covering relations).
  • In the Boolean algebra of the power set of a set S, a subset B of S covers a subset A of S if and only if B is obtained from A by adding one element not in A.
  • In Young's lattice, formed by the partitions of all nonnegative integers, a partition λ covers a partition μ if and only if the Young diagram of λ is obtained from the Young diagram of μ by adding an extra cell.
  • The Hasse diagram depicting the covering relation of a Tamari lattice is the skeleton of an associahedron.
  • On the real numbers with the usual total order ≤, the cover set is empty: no number covers another.

Properties

  • If a partially ordered set is finite, its covering relation is the transitive reduction of the partial order relation. Such partially ordered sets are therefore completely described by their Hasse diagrams. On the other hand, in a dense order, such as the rational numbers with the standard order, no element covers another.

References


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Covering space — A covering map satisfies the local triviality condition. Intuitively, such maps locally project a stack of pancakes above an open region, U, onto U. In mathematics, more specifically algebraic topology, a covering map is a continuous surjective… …   Wikipedia

  • covering bone — dermal bone (any of the the superficial bones in Teleostomi derived from the dermis and overlying the deeper elements of the skull. Primitive fishes have more dermal bones than higher ones, e.g. the armour of Ostracodermi. Dermal bones are a form …   Dictionary of ichthyology

  • floor covering — Finish material on floors, including wood strips, parquet, linoleum, vinyl, asphalt tile, rubber, cork, epoxy resins, ceramic tile, and carpeting. Wood strip flooring, attached to a subfloor of plywood, is most popular, especially for residences …   Universalium

  • Dedekind–MacNeille completion — The Hasse diagram of a partially ordered set (left) and its Dedekind–MacNeille completion (right). In order theoretic mathematics, the Dedekind–MacNeille completion of a partially ordered set (also called the completion by cuts or normal… …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • Outline of logic — The following outline is provided as an overview of and topical guide to logic: Logic – formal science of using reason, considered a branch of both philosophy and mathematics. Logic investigates and classifies the structure of statements and… …   Wikipedia

  • Directed acyclic graph — An example of a directed acyclic graph In mathematics and computer science, a directed acyclic graph (DAG i …   Wikipedia

  • Cover — or covers may refer to: Contents 1 Science and technology 2 Deception and concealment 3 Mathematics …   Wikipedia

  • Semimodular lattice — This article is about generalizations of modularity in terms of the atomic covering relation. For M symmetry, the generalization of modularity in terms of modular pairs, see modular lattice. The centred hexagon lattice S7, also known as D2, is… …   Wikipedia

  • Distributive lattice — In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”