Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Extension linéaire
Résumé
Dans la branche des mathématiques de la théorie des ordres, une extension linéaire d'un ordre partiel est un ordre total (ou ordre linéaire) qui est compatible avec l'ordre partiel. Un exemple classique est l'ordre lexicographique des ensembles totalement ordonnés qui est une extension linéaire de leur ordre produit.
Étant donnés des ordres partiels quelconques ≤ et ≤* sur un ensemble X, ≤* est une extension linéaire de ≤ si et seulement si (1) ≤* est un ordre total et (2) pour tout x et y dans X, si , alors . C'est cette deuxième propriété qui conduit les mathématiciens à décrire ≤* comme une extension de ≤.
De façon équivalente, une extension linéaire peut être considérée comme une bijection croissante d'un ensemble partiellement ordonné vers un ordre total sur le même ensemble.
L'affirmation que tout ordre partiel peut être étendu en un ordre total est connu comme le principe d'extension d'ordre. Une preuve utilisant l'axiome du choix a d'abord été publiée par Edward Marczewski en 1930 : voir Théorème d'extension de Szpilrajn. Marczewski a écrit que le théorème avait déjà été prouvé par Stefan Banach, Kazimierz Kuratowski et Alfred Tarski, en utilisant également l'axiome du choix, mais que les preuves n'avaient jamais été publiées.
Dans la théorie des ensembles axiomatique moderne, le principe d'extension d'ordre est lui-même pris comme un axiome, de même statut ontologique que l'axiome du choix. Le principe d'extension d'ordre est impliqué par le théorème de l'idéal premier dans une algèbre de Boole ou le théorème de compacité (équivalent), mais la réciproque est fausse
L'application du principe d'extension d'ordre à un ordre partiel dans lequel chaque couple d'éléments sont incomparables montre que (en vertu de ce principe) tout ensemble peut être totalement ordonné. et c'est une version faible du théorème de Zermelo. Cependant, il existe des modèles de la théorie des ensembles dans lesquels le principe de classement est vrai alors que le principe d'extension d'ordre ne l'est pas.
Source officielle
À 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.
Proximité ontologique
Séances de cours associées (2)
Integers: Bien commander et induction
Explore bien l'ordre, l'induction, la division euclidienne, et la factorisation primaire en entiers.
Effets anharmoniques dans les solides
Explore les effets anharmoniques dans les solides, y compris la dilatation thermique, la conductivité et la diffusion des phonons.
Publications associées (10)
Personnes associées (4)
Concepts associés (11)
Product order
In mathematics, given a partial order and on a set and , respectively, the product order (also called the coordinatewise order or componentwise order) is a partial ordering on the Cartesian product Given two pairs and in declare that if and Another possible ordering on is the lexicographical order, which is a total ordering. However the product order of two total orders is not in general total; for example, the pairs and are incomparable in the product order of the ordering with itself.
Series-parallel partial order
In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations. The series-parallel partial orders may be characterized as the N-free finite partial orders; they have order dimension at most two. They include weak orders and the reachability relationship in directed trees and directed series–parallel graphs. The comparability graphs of series-parallel partial orders are cographs.
Order dimension
In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller dimension of the partial order. first studied order dimension; for a more detailed treatment of this subject than provided here, see . The dimension of a poset P is the least integer t for which there exists a family of linear extensions of P so that, for every x and y in P, x precedes y in P if and only if it precedes y in all of the linear extensions.