World Library  
Flag as Inappropriate
Email this Article

Covering relation

Article Id: WHEBN0014835049
Reproduction Date:

Title: Covering relation  
Author: World Heritage Encyclopedia
Language: English
Subject: Outline of logic, IT
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

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.

Definition

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

Let x and y be elements of X.

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

When x\lessdot 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, 2, …, 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.
  • 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

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.