In mathematics, a join-semilattice (or upper semilattice) is a partially ordered set that has a join (a least upper bound) for any nonempty finite subset. Dually, a meet-semilattice (or lower semilattice) is a partially ordered set which has a meet (or greatest lower bound) for any nonempty finite subset. Every join-semilattice is a meet-semilattice in the inverse order and vice versa. Semilattices can also be defined algebraically: join and meet are associative, commutative, idempotent binary operations, and any such operation induces a partial order (and the respective inverse order) such that the result of the operation for any two elements is the least upper bound (or greatest lower bound) of the elements with respect to this partial order. A lattice is a partially ordered set that is both a meet- and join-semilattice with respect to the same partial order. Algebraically, a lattice is a set with two associative, commutative idempotent binary operations linked by corresponding absorption laws. A set S partially ordered by the binary relation ≤ is a meet-semilattice if For all elements x and y of S, the greatest lower bound of the set {x, y} exists. The greatest lower bound of the set {x, y} is called the meet of x and y, denoted x ∧ y. Replacing "greatest lower bound" with "least upper bound" results in the dual concept of a join-semilattice. The least upper bound of {x, y} is called the join of x and y, denoted x ∨ y. Meet and join are binary operations on S. A simple induction argument shows that the existence of all possible pairwise suprema (infima), as per the definition, implies the existence of all non-empty finite suprema (infima). A join-semilattice is bounded if it has a least element, the join of the empty set. Dually, a meet-semilattice is bounded if it has a greatest element, the meet of the empty set. Other properties may be assumed; see the article on completeness in order theory for more discussion on this subject.

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Cours associés (2)
CS-101: Advanced information, computation, communication I
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
CS-550: Formal verification
We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to u
Séances de cours associées (15)
Lattices : propriétés et fonctions thêta
Explore les réseaux dans Rd, les matrices de Gram, les fonctions thêta et les propriétés modulaires.
Lattices pour l'interprétation abstraite
Couvre les treillis, l'interprétation abstraite, l'analyse des points de fixation, la logique de Hoare et les ordres partiels avec des éléments extrêmes.
Propriétés des nombres réels
Explique les propriétés des sous-ensembles de nombres réels, y compris Supremum, Infimum, intervalles, ensembles ouverts et ensembles fermés.
Afficher plus
Publications associées (22)

Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization

Volkan Cevher, Kimon Antonakopoulos, Efstratios Panteleimon Skoulakis, Leello Tadesse Dadi, Ali Kavis

We propose an adaptive variance-reduction method, called AdaSpider, for minimization of L-smooth, non-convex functions with a finite-sum structure. In essence, AdaSpider combines an AdaGrad-inspired [Duchi et al., 2011, McMahan & Streeter, 2010], but a fai ...
2022

Shannon Bounds on Lossy Gray-Wyner Networks

Michael Christoph Gastpar, Erixhen Sula

The Gray-Wyner network subject to a fidelity criterion is studied. Upper and lower bounds for the trade-offs between the private sum-rate and the common rate are obtained for arbitrary sources subject to mean-squared error distortion. The bounds meet exact ...
2022

Feedback and Common Information: Bounds and Capacity for Gaussian Networks

Erixhen Sula

Network information theory studies the communication of information in a network and considers its fundamental limits. Motivating from the extensive presence of the networks in the daily life, the thesis studies the fundamental limits of particular network ...
EPFL2021
Afficher plus
Personnes associées (2)
Concepts associés (17)
Free lattice
In mathematics, in the area of order theory, a free lattice is the free object corresponding to a lattice. As free objects, they have the universal property. Because the concept of a lattice can be axiomatised in terms of two operations and satisfying certain identities, the of all lattices constitute a variety (universal algebra), and thus there exist (by general principles of universal algebra) free objects within this category: lattices where only those relations hold which follow from the general axioms.
Join and meet
In mathematics, specifically order theory, the join of a subset of a partially ordered set is the supremum (least upper bound) of denoted and similarly, the meet of is the infimum (greatest lower bound), denoted In general, the join and meet of a subset of a partially ordered set need not exist. Join and meet are dual to one another with respect to order inversion. A partially ordered set in which all pairs have a join is a join-semilattice. Dually, a partially ordered set in which all pairs have a meet is a meet-semilattice.
Completeness (order theory)
In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set (poset). The most familiar example is the completeness of the real numbers. A special use of the term refers to complete partial orders or complete lattices. However, many other interesting notions of completeness exist. The motivation for considering completeness properties derives from the great importance of suprema (least upper bounds, joins, "") and infima (greatest lower bounds, meets, "") to the theory of partial orders.
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.