Misplaced Pages

#550449

108-431: A partially ordered set (poset) consists of a set of elements together with a binary relation x ≤ y on pairs of elements that is reflexive ( x ≤ x for every x ), transitive (if x ≤ y and y ≤ z then x ≤ z ), and antisymmetric (if both x ≤ y and y ≤ x hold, then x = y ). The usual numeric orderings on the integers or real numbers satisfy these properties; however, unlike

216-485: A {\displaystyle {\tfrac {b}{a}}} ⁠ or ⁠ − b − a , {\displaystyle {\tfrac {-b}{-a}},} ⁠ depending on the sign of a . If b, c, d are nonzero, the division rule is Thus, dividing ⁠ a b {\displaystyle {\tfrac {a}{b}}} ⁠ by ⁠ c d {\displaystyle {\tfrac {c}{d}}} ⁠

324-405: A n . {\displaystyle {\tfrac {-b^{n}}{-a^{n}}}.} ⁠ A finite continued fraction is an expression such as where a n are integers. Every rational number ⁠ a b {\displaystyle {\tfrac {a}{b}}} ⁠ can be represented as a finite continued fraction, whose coefficients a n can be determined by applying

432-452: A ≤ b . {\displaystyle a\leq b.} A convex set in a poset P is a subset I of P with the property that, for any x and y in I and any z in P , if x ≤ z ≤ y , then z is also in I . This definition generalizes the definition of intervals of real numbers . When there is possible confusion with convex sets of geometry , one uses order-convex instead of "convex". A convex sublattice of

540-396: A , {\displaystyle \lim _{i\to \infty }a_{i}=a,} and lim i → ∞ b i = b , {\displaystyle \lim _{i\to \infty }b_{i}=b,} and for all i , {\displaystyle i,} a i ≤ b i , {\displaystyle a_{i}\leq b_{i},} then

648-405: A , b ) : a ≤ b } {\displaystyle \{(a,b):a\leq b\}} is a closed subset of the topological product space P × P . {\displaystyle P\times P.} Under this assumption partial order relations are well behaved at limits in the sense that if lim i → ∞ a i =

756-404: A , b , c ∈ P , {\displaystyle a,b,c\in P,} it must satisfy: A non-strict partial order is also known as an antisymmetric preorder . An irreflexive , strong , or strict partial order is a homogeneous relation < on a set P {\displaystyle P} that is transitive , irreflexive , and asymmetric ; that is, it satisfies

864-418: A R b {\displaystyle aRb} and b R c {\displaystyle bRc} then a R c . {\displaystyle aRc.} A term's definition may require additional properties that are not listed in this table. In mathematics , especially order theory , a partial order on a set is an arrangement such that, for certain pairs of elements, one precedes

972-467: A and b are coprime integers and b > 0 . This is often called the canonical form of the rational number. Starting from a rational number ⁠ a b , {\displaystyle {\tfrac {a}{b}},} ⁠ its canonical form may be obtained by dividing a and b by their greatest common divisor , and, if b < 0 , changing the sign of the resulting numerator and denominator. Any integer n can be expressed as

1080-667: A category where, for objects x {\displaystyle x} and y , {\displaystyle y,} there is at most one morphism from x {\displaystyle x} to y . {\displaystyle y.} More explicitly, let hom( x , y ) = {( x , y )} if x ≤ y (and otherwise the empty set ) and ( y , z ) ∘ ( x , y ) = ( x , z ) . {\displaystyle (y,z)\circ (x,y)=(x,z).} Such categories are sometimes called posetal . Posets are equivalent to one another if and only if they are isomorphic . In

1188-426: A lattice L is a sublattice of L that is also a convex set of L . Every nonempty convex sublattice can be uniquely represented as the intersection of a filter and an ideal of L . An interval in a poset P is a subset that can be defined with interval notation: Whenever a ≤ b does not hold, all these intervals are empty. Every interval is a convex set, but the converse does not hold; for example, in

SECTION 10

#1732765393551

1296-412: A numerator p and a non-zero denominator q . For example, ⁠ 3 7 {\displaystyle {\tfrac {3}{7}}} ⁠ is a rational number, as is every integer (for example, − 5 = − 5 1 {\displaystyle -5={\tfrac {-5}{1}}} ). The set of all rational numbers, also referred to as " the rationals ",

1404-410: A one-to-one correspondence , so for every strict partial order there is a unique corresponding non-strict partial order, and vice versa. A reflexive , weak , or non-strict partial order , commonly referred to simply as a partial order , is a homogeneous relation ≤ on a set P {\displaystyle P} that is reflexive , antisymmetric , and transitive . That is, for all

1512-406: A rational point is a point with rational coordinates (i.e., a point whose coordinates are rational numbers); a rational matrix is a matrix of rational numbers; a rational polynomial may be a polynomial with rational coefficients, although the term "polynomial over the rationals" is generally preferred, to avoid confusion between " rational expression " and " rational function " (a polynomial

1620-446: A ≠ 0 , then If ⁠ a b {\displaystyle {\tfrac {a}{b}}} ⁠ is in canonical form, the canonical form of the result is ⁠ b n a n {\displaystyle {\tfrac {b^{n}}{a^{n}}}} ⁠ if a > 0 or n is even. Otherwise, the canonical form of the result is ⁠ − b n −

1728-473: A Hasse diagram, actually the corresponding strict order is shown. Standard examples of posets arising in mathematics include: One familiar example of a partially ordered set is a collection of people ordered by genealogical descendancy. Some pairs of people bear the descendant-ancestor relationship, but other pairs of people are incomparable, with neither being a descendant of the other. In order of increasing strength, i.e., decreasing sets of pairs, three of

1836-553: A central role in the field of formal concept analysis . The Dedekind–MacNeille completion of a partially ordered set S is the smallest complete lattice with S embedded in it, in the sense that, if L is any lattice completion of S , then the Dedekind–MacNeille completion is a partially ordered subset of L . When S is finite, its completion is also finite, and has the smallest number of elements among all finite complete lattices containing S . The partially ordered set S

1944-407: A cut correspond to the elements with subscript 0 in an antichain, and the elements in the upper set of a cut correspond to the elements with subscript 1 in an antichain. Jourdan et al. describe an algorithm for finding maximal antichains that, when applied to the problem of listing all cuts in P , takes time O ( c ( nw + w )) , an improvement on the algorithm of Ganter & Kuznetsov (1998) when

2052-415: A different partially ordered set. If P is any partially ordered set, let Q be a partial order whose elements contain two copies of P : for each element x of P , Q contains two elements x 0 and x 1 , with x i < y j if and only if x < y and i < j . Then the cuts in P correspond one-for-one with the maximal antichains in Q : the elements in the lower set of

2160-440: A function compare : P × P → { < , > , = , | } {\displaystyle {\text{compare}}:P\times P\to \{<,>,=,\vert \}} that returns one of four codes when given two elements. This definition is equivalent to a partial order on a setoid , where equality is taken to be a defined equivalence relation rather than set equality. Wallis defines

2268-536: A map g : N → P ( N ) {\displaystyle g:\mathbb {N} \to \mathbb {P} (\mathbb {N} )} that is order-preserving, order-reflecting, and hence an order-embedding. It is not an order-isomorphism (since it, for instance, does not map any number to the set { 4 } {\displaystyle \{4\}} ), but it can be made one by restricting its codomain to g ( N ) . {\displaystyle g(\mathbb {N} ).} Fig. 7b shows

SECTION 20

#1732765393551

2376-408: A matrix that specifies all pairwise comparisons between elements. Nourine & Raynaud (1999) show how to compute this covering graph efficiently; more generally, if B is any family of sets, they show how to compute the covering graph of the lattice of unions of subsets of B . In the case of the Dedekind–MacNeille lattice, B may be taken as the family of complement sets of principal ideals, and

2484-522: A more general notion of a partial order relation as any homogeneous relation that is transitive and antisymmetric . This includes both reflexive and irreflexive partial orders as subtypes. A finite poset can be visualized through its Hasse diagram . Specifically, taking a strict partial order relation ( P , < ) {\displaystyle (P,<)} , a directed acyclic graph (DAG) may be constructed by taking each element of P {\displaystyle P} to be

2592-527: A node and each element of < {\displaystyle <} to be an edge. The transitive reduction of this DAG is then the Hasse diagram. Similarly this process can be reversed to construct strict partial orders from certain DAGs. In contrast, the graph associated to a non-strict partial order has self-loops at every node and therefore is not a DAG; when a non-strict order is said to be depicted by

2700-745: A non-strict partial order is a non-strict partial order, and the dual of a strict partial order is a strict partial order. The dual of a dual of a relation is the original relation. Given a set P {\displaystyle P} and a partial order relation, typically the non-strict partial order ≤ {\displaystyle \leq } , we may uniquely extend our notation to define four partial order relations ≤ , {\displaystyle \leq ,} < , {\displaystyle <,} ≥ , {\displaystyle \geq ,} and > {\displaystyle >} , where ≤ {\displaystyle \leq }

2808-509: A pair ( m, n ) is denoted ⁠ m n . {\displaystyle {\tfrac {m}{n}}.} ⁠ Two pairs ( m 1 , n 1 ) and ( m 2 , n 2 ) belong to the same equivalence class (that is are equivalent) if and only if This means that if and only if Every equivalence class ⁠ m n {\displaystyle {\tfrac {m}{n}}} ⁠ may be represented by infinitely many pairs, since Each equivalence class contains

2916-416: A partial order relation R {\displaystyle R} is defined by letting R op {\displaystyle R^{\text{op}}} be the converse relation of R {\displaystyle R} , i.e. x R op y {\displaystyle xR^{\text{op}}y} if and only if y R x {\displaystyle yRx} . The dual of

3024-485: A partial order should not be confused with the particular class of partial orders known as the interval orders . [REDACTED] Media related to Hasse diagrams at Wikimedia Commons; each of which shows an example for a partial order Rational number In mathematics , a rational number is a number that can be expressed as the quotient or fraction ⁠ p q {\displaystyle {\tfrac {p}{q}}} ⁠ of two integers ,

3132-413: A poset P , {\displaystyle P,} notably: As another example, consider the positive integers , ordered by divisibility: 1 is a least element, as it divides all other elements; on the other hand this poset does not have a greatest element. This partially ordered set does not even have any maximal elements, since any g divides for instance 2 g , which is distinct from it, so g

3240-444: A poset, the smallest element, if it exists, is an initial object , and the largest element, if it exists, is a terminal object . Also, every preordered set is equivalent to a poset. Finally, every subcategory of a poset is isomorphism-closed . If P {\displaystyle P} is a partially ordered set that has also been given the structure of a topological space , then it is customary to assume that { (

3348-409: A positive denominator—by changing the signs of both its numerator and denominator. Two fractions are added as follows: If both fractions are in canonical form, the result is in canonical form if and only if b, d are coprime integers . If both fractions are in canonical form, the result is in canonical form if and only if b, d are coprime integers . The rule for multiplication is: where

Dedekind–MacNeille completion - Misplaced Pages Continue

3456-438: A rational least upper bound, but in the real numbers it has the least upper bound π . A given partially ordered set may have several different completions. For instance, one completion of any partially ordered set S is the set of its downwardly closed subsets ordered by inclusion . S is embedded in this (complete) lattice by mapping each element x to the lower set of elements that are less than or equal to x . The result

3564-750: A set P {\displaystyle P} are closely related. A non-strict partial order ≤ {\displaystyle \leq } may be converted to a strict partial order by removing all relationships of the form a ≤ a ; {\displaystyle a\leq a;} that is, the strict partial order is the set < :=   ≤   ∖   Δ P {\displaystyle <\;:=\ \leq \ \setminus \ \Delta _{P}} where Δ P := { ( p , p ) : p ∈ P } {\displaystyle \Delta _{P}:=\{(p,p):p\in P\}}

3672-509: A subset of N {\displaystyle \mathbb {N} } and its isomorphic image under g . The construction of such an order-isomorphism into a power set can be generalized to a wide class of partial orders, called distributive lattices ; see Birkhoff's representation theorem . Sequence A001035 in OEIS gives the number of partial orders on a set of n labeled elements: Note that S ( n , k ) refers to Stirling numbers of

3780-503: A unique canonical representative element . The canonical representative is the unique pair ( m, n ) in the equivalence class such that m and n are coprime , and n > 0 . It is called the representation in lowest terms of the rational number. The integers may be considered to be rational numbers identifying the integer n with the rational number ⁠ n 1 . {\displaystyle {\tfrac {n}{1}}.} ⁠ A total order may be defined on

3888-516: Is a distributive lattice and is used in Birkhoff's representation theorem . However, it may have many more elements than are needed to form a completion of S . Among all possible lattice completions, the Dedekind–MacNeille completion is the smallest complete lattice with S embedded in it. For each subset A of a partially ordered set S , let A denote the set of upper bounds of A ; that is, an element x of S belongs to A whenever x

3996-506: Is a non-strict partial order relation on P {\displaystyle P} , < {\displaystyle <} is the associated strict partial order relation on P {\displaystyle P} (the irreflexive kernel of ≤ {\displaystyle \leq } ), ≥ {\displaystyle \geq } is the dual of ≤ {\displaystyle \leq } , and > {\displaystyle >}

4104-435: Is a non-strict partial order. Thus, if ≤ {\displaystyle \leq } is a non-strict partial order, then the corresponding strict partial order < is the irreflexive kernel given by a < b  if  a ≤ b  and  a ≠ b . {\displaystyle a<b{\text{ if }}a\leq b{\text{ and }}a\neq b.} Conversely, if <

4212-407: Is a rational expression and defines a rational function, even if its coefficients are not rational numbers). However, a rational curve is not a curve defined over the rationals, but a curve which can be parameterized by rational functions. Although nowadays rational numbers are defined in terms of ratios , the term rational is not a derivation of ratio . On the contrary, it is ratio that

4320-460: Is a strict partial order, then the corresponding non-strict partial order ≤ {\displaystyle \leq } is the reflexive closure given by: a ≤ b  if  a < b  or  a = b . {\displaystyle a\leq b{\text{ if }}a<b{\text{ or }}a=b.} The dual (or opposite ) R op {\displaystyle R^{\text{op}}} of

4428-522: Is a subposet of P {\displaystyle P} and furthermore, for all x {\displaystyle x} and y {\displaystyle y} in X ∗ {\displaystyle X^{*}} , whenever x ≤ y {\displaystyle x\leq y} we also have x ≤ ∗ y {\displaystyle x\leq ^{*}y} , then we call P ∗ {\displaystyle P^{*}}

Dedekind–MacNeille completion - Misplaced Pages Continue

4536-516: Is an extension that is also a linear (that is, total) order. As a classic example, the lexicographic order of totally ordered sets is a linear extension of their product order. Every partial order can be extended to a total order ( order-extension principle ). In computer science , algorithms for finding linear extensions of partial orders (represented as the reachability orders of directed acyclic graphs ) are called topological sorting . Every poset (and every preordered set ) may be considered as

4644-430: Is an ordered pair P = ( X , ≤ ) {\displaystyle P=(X,\leq )} consisting of a set X {\displaystyle X} (called the ground set of P {\displaystyle P} ) and a partial order ≤ {\displaystyle \leq } on X {\displaystyle X} . When the meaning is clear from context and there

4752-426: Is any finite set of objects, and A is any finite set of unary attributes for the objects in O , then one may form a partial order of height two in which the elements of the partial order are the objects and attributes, and in which x ≤ y when x is an object that has attribute  y . For a partial order defined in this way, the Dedekind–MacNeille completion of S is known as a concept lattice , and it plays

4860-623: Is called order-preserving , or monotone , or isotone , if for all x , y ∈ S , {\displaystyle x,y\in S,} x ≤ y {\displaystyle x\leq y} implies f ( x ) ≼ f ( y ) . If ( U , ≲) is also a partially ordered set, and both f : S → T {\displaystyle f:S\to T} and g : T → U {\displaystyle g:T\to U} are order-preserving, their composition g ∘ f : S → U {\displaystyle g\circ f:S\to U}

4968-463: Is called a subposet of another poset P = ( X , ≤ ) {\displaystyle P=(X,\leq )} provided that X ∗ {\displaystyle X^{*}} is a subset of X {\displaystyle X} and ≤ ∗ {\displaystyle \leq ^{*}} is a subset of ≤ {\displaystyle \leq } . The latter condition

5076-443: Is called an order-embedding of ( S , ≤) into ( T , ≼) . In the latter case, f is necessarily injective , since f ( x ) = f ( y ) {\displaystyle f(x)=f(y)} implies x ≤ y  and  y ≤ x {\displaystyle x\leq y{\text{ and }}y\leq x} and in turn x = y {\displaystyle x=y} according to

5184-505: Is called an extension of another partial order ≤ {\displaystyle \leq } on X {\displaystyle X} provided that for all elements x , y ∈ X , {\displaystyle x,y\in X,} whenever x ≤ y , {\displaystyle x\leq y,} it is also the case that x ≤ ∗ y . {\displaystyle x\leq ^{*}y.} A linear extension

5292-499: Is derived from rational : the first use of ratio with its modern meaning was attested in English about 1660, while the use of rational for qualifying numbers appeared almost a century earlier, in 1570. This meaning of rational came from the mathematical meaning of irrational , which was first used in 1551, and it was used in "translations of Euclid (following his peculiar use of ἄλογος )". This unusual history originated in

5400-730: Is equal to the complement of ≤ {\displaystyle \leq } if, and only if , ≤ {\displaystyle \leq } is a total order. Another way of defining a partial order, found in computer science , is via a notion of comparison . Specifically, given ≤ , < , ≥ ,  and  > {\displaystyle \leq ,<,\geq ,{\text{ and }}>} as defined previously, it can be observed that two elements x and y may stand in any of four mutually exclusive relationships to each other: either x < y , or x = y , or x > y , or x and y are incomparable . This can be represented by

5508-463: Is equivalent to multiplying ⁠ a b {\displaystyle {\tfrac {a}{b}}} ⁠ by the reciprocal of ⁠ c d : {\displaystyle {\tfrac {c}{d}}:} ⁠ If n is a non-negative integer, then The result is in canonical form if the same is true for ⁠ a b . {\displaystyle {\tfrac {a}{b}}.} ⁠ In particular, If

SECTION 50

#1732765393551

5616-523: Is equivalent to the requirement that for any x {\displaystyle x} and y {\displaystyle y} in X ∗ {\displaystyle X^{*}} (and thus also in X {\displaystyle X} ), if x ≤ ∗ y {\displaystyle x\leq ^{*}y} then x ≤ y {\displaystyle x\leq y} . If P ∗ {\displaystyle P^{*}}

5724-437: Is greater than or equal to every element in A . Symmetrically, let A denote the set of lower bounds of A , the elements that are less than or equal to every element in A . Then the Dedekind–MacNeille completion of S consists of all subsets A for which it is ordered by inclusion: A ≤ B in the completion if and only if A ⊆ B as sets. An element x of S embeds into the completion as its principal ideal ,

5832-400: Is join-dense and meet-dense in the Dedekind–MacNeille completion; that is, every element of the completion is a join of some set of elements of S , and is also the meet of some set of elements in S . The Dedekind–MacNeille completion is characterized among completions of S by this property. The Dedekind–MacNeille completion of a Boolean algebra is a complete Boolean algebra ; this result

5940-459: Is known as the Glivenko–Stone theorem , after Valery Ivanovich Glivenko and Marshall Stone . Similarly, the Dedekind–MacNeille completion of a residuated lattice is a complete residuated lattice. However, the completion of a distributive lattice need not itself be distributive, and the completion of a modular lattice may not remain modular. The Dedekind–MacNeille completion is self-dual:

6048-492: Is no ambiguity about the partial order, the set X {\displaystyle X} itself is sometimes called a poset. The term partial order usually refers to the reflexive partial order relations, referred to in this article as non-strict partial orders. However some authors use the term for the other common type of partial order relations, the irreflexive partial order relations, also called strict partial orders. Strict and non-strict partial orders can be put into

6156-397: Is not in the poset); on the other hand 2 is a lower bound of the subset of powers of 2, which does not have any upper bound. If the number 0 is included, this will be the greatest element, since this is a multiple of every integer (see Fig. 6). Given two partially ordered sets ( S , ≤) and ( T , ≼) , a function f : S → T {\displaystyle f:S\to T}

6264-455: Is not maximal. If the number 1 is excluded, while keeping divisibility as ordering on the elements greater than 1, then the resulting poset does not have a least element, but any prime number is a minimal element for it. In this poset, 60 is an upper bound (though not a least upper bound) of the subset { 2 , 3 , 5 , 10 } , {\displaystyle \{2,3,5,10\},} which does not have any lower bound (since 1

6372-448: Is not true. For example, let P = (0, 1) ∪ (1, 2) ∪ (2, 3) as a subposet of the real numbers. The subset (1, 2) is a bounded interval, but it has no infimum or supremum in  P , so it cannot be written in interval notation using elements of  P . A poset is called locally finite if every bounded interval is finite. For example, the integers are locally finite under their natural ordering. The lexicographical order on

6480-413: Is order-preserving, too. A function f : S → T {\displaystyle f:S\to T} is called order-reflecting if for all x , y ∈ S , {\displaystyle x,y\in S,} f ( x ) ≼ f ( y ) implies x ≤ y . {\displaystyle x\leq y.} If f is both order-preserving and order-reflecting, then it

6588-399: Is sometimes used. In a partially ordered set S , define a cut to be a pair of sets ( A , B ) for which A = B and A = B . If ( A , B ) is a cut then A satisfies the equation ( A ) = A , and conversely if ( A ) = A then ( A , A ) is a cut. Therefore, the set of cuts, partially ordered by inclusion on the lower set of the cut (or the reverse of the inclusion relation on

SECTION 60

#1732765393551

6696-590: Is the disjoint union of two partially ordered sets, with no order relation between elements of one set and elements of the other set. The examples use the poset ( P ( { x , y , z } ) , ⊆ ) {\displaystyle ({\mathcal {P}}(\{x,y,z\}),\subseteq )} consisting of the set of all subsets of a three-element set { x , y , z } , {\displaystyle \{x,y,z\},} ordered by set inclusion (see Fig. 1). There are several notions of "greatest" and "least" element in

6804-538: Is the identity relation on P × P {\displaystyle P\times P} and ∖ {\displaystyle \;\setminus \;} denotes set subtraction . Conversely, a strict partial order < on P {\displaystyle P} may be converted to a non-strict partial order by adjoining all relationships of that form; that is, ≤ := Δ P ∪ < {\displaystyle \leq \;:=\;\Delta _{P}\;\cup \;<\;}

6912-412: Is the injective hull of  S . Several researchers have investigated algorithms for constructing the Dedekind–MacNeille completion of a finite partially ordered set. The Dedekind–MacNeille completion may be exponentially larger than the partial order it comes from, and the time bounds for such algorithms are generally stated in an output-sensitive way , depending both on the number n of elements of

7020-424: Is the ordinal sum (or linear sum ), Z = X ⊕ Y , defined on the union of the underlying sets X and Y by the order a ≤ Z b if and only if: If two posets are well-ordered , then so is their ordinal sum. Series-parallel partial orders are formed from the ordinal sum operation (in this context called series composition) and another operation called parallel composition. Parallel composition

7128-502: Is the defined as the quotient set by this equivalence relation, ⁠ ( Z × ( Z ∖ { 0 } ) ) / ∼ , {\displaystyle (\mathbb {Z} \times (\mathbb {Z} \backslash \{0\}))/\sim ,} ⁠ equipped with the addition and the multiplication induced by the above operations. (This construction can be carried out with any integral domain and produces its field of fractions .) The equivalence class of

7236-430: Is the dual of < {\displaystyle <} . Strictly speaking, the term partially ordered set refers to a set with all of these relations defined appropriately. But practically, one need only consider a single relation, ( P , ≤ ) {\displaystyle (P,\leq )} or ( P , < ) {\displaystyle (P,<)} , or, in rare instances,

7344-412: Is the set of rational numbers , viewed as a totally ordered set with the usual numerical order, then each element of the Dedekind–MacNeille completion of Q {\displaystyle \mathbb {Q} } may be viewed as a Dedekind cut , and the Dedekind–MacNeille completion of Q {\displaystyle \mathbb {Q} } is the total ordering on the real numbers , together with

7452-407: Is true for its opposite. A nonzero rational number ⁠ a b {\displaystyle {\tfrac {a}{b}}} ⁠ has a multiplicative inverse , also called its reciprocal , If ⁠ a b {\displaystyle {\tfrac {a}{b}}} ⁠ is in canonical form, then the canonical form of its reciprocal is either ⁠ b

7560-462: The Euclidean algorithm to ( a, b ) . are different ways to represent the same rational value. The rational numbers may be built as equivalence classes of ordered pairs of integers . More precisely, let ⁠ ( Z × ( Z ∖ { 0 } ) ) {\displaystyle (\mathbb {Z} \times (\mathbb {Z} \setminus \{0\}))} ⁠ be

7668-402: The algebraic closure of ⁠ Q {\displaystyle \mathbb {Q} } ⁠ is the field of algebraic numbers . In mathematical analysis , the rational numbers form a dense subset of the real numbers. The real numbers can be constructed from the rational numbers by completion , using Cauchy sequences , Dedekind cuts , or infinite decimals (see Construction of

7776-394: The complement of > {\displaystyle >} . The relation > {\displaystyle >} is the converse of the irreflexive kernel of ≤ {\displaystyle \leq } , which is always a subset of the complement of ≤ {\displaystyle \leq } , but > {\displaystyle >}

7884-422: The field of rationals or the field of rational numbers is usually denoted by boldface Q , or blackboard bold ⁠ Q . {\displaystyle \mathbb {Q} .} ⁠ A rational number is a real number . The real numbers that are rational are those whose decimal expansion either terminates after a finite number of digits (example: 3/4 = 0.75 ), or eventually begins to repeat

7992-456: The golden ratio ( φ ). Since the set of rational numbers is countable , and the set of real numbers is uncountable , almost all real numbers are irrational. Rational numbers can be formally defined as equivalence classes of pairs of integers ( p, q ) with q ≠ 0 , using the equivalence relation defined as follows: The fraction ⁠ p q {\displaystyle {\tfrac {p}{q}}} ⁠ then denotes

8100-425: The identity function on S and T , respectively, then S and T are order-isomorphic. For example, a mapping f : N → P ( N ) {\displaystyle f:\mathbb {N} \to \mathbb {P} (\mathbb {N} )} from the set of natural numbers (ordered by divisibility) to the power set of natural numbers (ordered by set inclusion) can be defined by taking each number to

8208-402: The Dedekind–MacNeille completion describes the order relation between its elements in a concise way: each neighbor of a cut must remove an element of the original partial order from either the upper or lower set of the cut, so each vertex has at most n neighbors. Thus, the covering graph has c vertices and at most cn /2 neighbors, a number that may be much smaller than the c entries in

8316-442: The analogous properties of the real numbers . An order-embedding is a function that maps distinct elements of S to distinct elements of L such that each pair of elements in S has the same ordering in L as they do in S . The extended real number line (real numbers together with +∞ and −∞) is a completion in this sense of the rational numbers: the set of rational numbers {3, 3.1, 3.14, 3.141, 3.1415, 3.14159, ...} does not have

8424-888: The antisymmetry of ≤ . {\displaystyle \leq .} If an order-embedding between two posets S and T exists, one says that S can be embedded into T . If an order-embedding f : S → T {\displaystyle f:S\to T} is bijective , it is called an order isomorphism , and the partial orders ( S , ≤) and ( T , ≼) are said to be isomorphic . Isomorphic orders have structurally similar Hasse diagrams (see Fig. 7a). It can be shown that if order-preserving maps f : S → T {\displaystyle f:S\to T} and g : T → U {\displaystyle g:T\to U} exist such that g ∘ f {\displaystyle g\circ f} and f ∘ g {\displaystyle f\circ g} yields

8532-400: The augmented partial order, except for the one whose two sets intersect in the new element, is either a cut from the previous partial order or is formed by adding the new element to one or the other side of a cut from the previous partial order, so their algorithm need only test pairs of sets of this form to determine which ones are cuts. The time for using their method to add a single element to

8640-450: The cartesian product N × N {\displaystyle \mathbb {N} \times \mathbb {N} } is not locally finite, since (1, 2) ≤ (1, 3) ≤ (1, 4) ≤ (1, 5) ≤ ... ≤ (2, 1) . Using the interval notation, the property " a is covered by b " can be rephrased equivalently as [ a , b ] = { a , b } . {\displaystyle [a,b]=\{a,b\}.} This concept of an interval in

8748-446: The completion of a partial order is O ( cnw ) where w is the width of the partial order, that is, the size of its largest antichain . Therefore, the time to compute the completion of a given partial order is O ( cn w ) = O( cn ) . As Jourdan, Rampon & Jard (1994) observe, the problem of listing all cuts in a partially ordered set can be formulated as a special case of a simpler problem, of listing all maximal antichains in

8856-405: The completion of the dual of a partial order is the same as the dual of the completion. The Dedekind–MacNeille completion of S has the same order dimension as does S itself. In the category of partially ordered sets and monotonic functions between partially ordered sets, the complete lattices form the injective objects for order-embeddings , and the Dedekind–MacNeille completion of S

8964-512: The equivalence class of ( p, q ) . Rational numbers together with addition and multiplication form a field which contains the integers , and is contained in any field containing the integers. In other words, the field of rational numbers is a prime field , and a field has characteristic zero if and only if it contains the rational numbers as a subfield. Finite extensions of ⁠ Q {\displaystyle \mathbb {Q} } ⁠ are called algebraic number fields , and

9072-492: The fact that ancient Greeks "avoided heresy by forbidding themselves from thinking of those [irrational] lengths as numbers". So such lengths were irrational , in the sense of illogical , that is "not to be spoken about" ( ἄλογος in Greek). Every rational number may be expressed in a unique way as an irreducible fraction ⁠ a b , {\displaystyle {\tfrac {a}{b}},} ⁠ where

9180-460: The following conditions for all a , b , c ∈ P : {\displaystyle a,b,c\in P:} A transitive relation is asymmetric if and only if it is irreflexive. So the definition is the same if it omits either irreflexivity or asymmetry (but not both). A strict partial order is also known as an asymmetric strict preorder . Strict and non-strict partial orders on

9288-434: The identity. (A field automorphism must fix 0 and 1; as it must fix the sum and the difference of two fixed elements, it must fix every integer; as it must fix the quotient of two fixed elements, it must fix every rational number, and is thus the identity.) ⁠ Q {\displaystyle \mathbb {Q} } ⁠ is a prime field , which is a field that has no subfield other than itself. The rationals are

9396-434: The input partial order, and on the number c of elements of its completion. Ganter & Kuznetsov (1998) describe an incremental algorithm, in which the input partial order is built up by adding one element at a time; at each step, the completion of the smaller partial order is expanded to form the completion of the larger partial order. In their method, the completion is represented by an explicit list of cuts. Each cut of

9504-869: The non-strict and strict relations together, ( P , ≤ , < ) {\displaystyle (P,\leq ,<)} . The term ordered set is sometimes used as a shorthand for partially ordered set , as long as it is clear from the context that no other kind of order is meant. In particular, totally ordered sets can also be referred to as "ordered sets", especially in areas where these structures are more common than posets. Some authors use different symbols than ≤ {\displaystyle \leq } such as ⊑ {\displaystyle \sqsubseteq } or ⪯ {\displaystyle \preceq } to distinguish partial orders from total orders. When referring to partial orders, ≤ {\displaystyle \leq } should not be taken as

9612-484: The orderings on the numbers, a partial order may have two elements that are incomparable : neither x ≤ y nor y ≤ x holds. Another familiar example of a partial ordering is the inclusion ordering ⊆ on pairs of sets. If S is a partially ordered set, a completion of S means a complete lattice L with an order-embedding of S into L . A complete lattice is a lattice in which every subset of elements of L has an infimum and supremum ; this generalizes

9720-426: The other. The word partial is used to indicate that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. Partial orders thus generalize total orders , in which every pair is comparable. Formally, a partial order is a homogeneous binary relation that is reflexive , antisymmetric , and transitive . A partially ordered set ( poset for short)

9828-450: The poset of divisors of 120, ordered by divisibility (see Fig. 7b), the set {1, 2, 4, 5, 8} is convex, but not an interval. An interval I is bounded if there exist elements a , b ∈ P {\displaystyle a,b\in P} such that I ⊆ [ a , b ] . Every interval that can be represented in interval notation is obviously bounded, but the converse

9936-541: The possible partial orders on the Cartesian product of two partially ordered sets are (see Fig. 4): All three can similarly be defined for the Cartesian product of more than two sets. Applied to ordered vector spaces over the same field , the result is in each case also an ordered vector space. See also orders on the Cartesian product of totally ordered sets . Another way to combine two (disjoint) posets

10044-466: The rational number ⁠ n 1 , {\displaystyle {\tfrac {n}{1}},} ⁠ which is its canonical form as a rational number. If both fractions are in canonical form, then: If both denominators are positive (particularly if both fractions are in canonical form): On the other hand, if either denominator is negative, then each fraction with a negative denominator must first be converted into an equivalent form with

10152-401: The rational numbers, that extends the natural order of the integers. One has If The set ⁠ Q {\displaystyle \mathbb {Q} } ⁠ of all rational numbers, together with the addition and multiplication operations shown above, forms a field . ⁠ Q {\displaystyle \mathbb {Q} } ⁠ has no field automorphism other than

10260-407: The real numbers ). The term rational in reference to the set ⁠ Q {\displaystyle \mathbb {Q} } ⁠ refers to the fact that a rational number represents a ratio of two integers. In mathematics, "rational" is often used as a noun abbreviating "rational number". The adjective rational sometimes means that the coefficients are rational numbers. For example,

10368-399: The result may be a reducible fraction —even if both original fractions are in canonical form. Every rational number ⁠ a b {\displaystyle {\tfrac {a}{b}}} ⁠ has an additive inverse , often called its opposite , If ⁠ a b {\displaystyle {\tfrac {a}{b}}} ⁠ is in canonical form, the same

10476-413: The same authors showed that the algorithm could be made fully incremental (capable of adding elements to the partial order one at a time) with the same total time bound. Partially ordered set All definitions tacitly require the homogeneous relation R {\displaystyle R} be transitive : for all a , b , c , {\displaystyle a,b,c,} if

10584-492: The same finite sequence of digits over and over (example: 9/44 = 0.20454545... ). This statement is true not only in base 10 , but also in every other integer base , such as the binary and hexadecimal ones (see Repeating decimal § Extension to other bases ). A real number that is not rational is called irrational . Irrational numbers include the square root of 2 ( ⁠ 2 {\displaystyle {\sqrt {2}}} ⁠ ), π , e , and

10692-406: The second kind . The number of strict partial orders is the same as that of partial orders. If the count is made only up to isomorphism, the sequence 1, 1, 2, 5, 16, 63, 318, ... (sequence A000112 in the OEIS ) is obtained. A poset P ∗ = ( X ∗ , ≤ ∗ ) {\displaystyle P^{*}=(X^{*},\leq ^{*})}

10800-405: The set ↓ x of elements less than or equal to x . Then (↓ x ) is the set of elements greater than or equal to x , and ((↓ x )) = ↓ x , showing that ↓ x is indeed a member of the completion. The mapping from x to ↓ x is an order-embedding. An alternative definition of the Dedekind–MacNeille completion that more closely resembles the definition of a Dedekind cut

10908-404: The set of its prime divisors . It is order-preserving: if x divides y , then each prime divisor of x is also a prime divisor of y . However, it is neither injective (since it maps both 12 and 6 to { 2 , 3 } {\displaystyle \{2,3\}} ) nor order-reflecting (since 12 does not divide 6). Taking instead each number to the set of its prime power divisors defines

11016-427: The set of the pairs ( m, n ) of integers such n ≠ 0 . An equivalence relation is defined on this set by Addition and multiplication can be defined by the following rules: This equivalence relation is a congruence relation , which means that it is compatible with the addition and multiplication defined above; the set of rational numbers ⁠ Q {\displaystyle \mathbb {Q} } ⁠

11124-415: The smallest field with characteristic zero. Every field of characteristic zero contains a unique subfield isomorphic to ⁠ Q . {\displaystyle \mathbb {Q} .} ⁠ With the order defined above, ⁠ Q {\displaystyle \mathbb {Q} } ⁠ is an ordered field that has no subfield other than itself, and is the smallest ordered field, in

11232-431: The subposet of P {\displaystyle P} induced by X ∗ {\displaystyle X^{*}} , and write P ∗ = P [ X ∗ ] {\displaystyle P^{*}=P[X^{*}]} . A partial order ≤ ∗ {\displaystyle \leq ^{*}} on a set X {\displaystyle X}

11340-403: The two additional values ± ∞ {\displaystyle \pm \infty } . If S is an antichain (a set of elements no two of which are comparable) then the Dedekind–MacNeille completion of S consists of S itself together with two additional elements, a bottom element that is below every element in S and a top element that is above every element in S . If O

11448-444: The unions of subsets of B are complements of the lower sets of cuts. The main idea for their algorithm is to generate unions of subsets of B incrementally (for each set in B , forming its union with all previously generated unions), represent the resulting family of sets in a trie , and use the trie representation to test certain candidate pairs of sets for adjacency in the covering relation; it takes time O ( cn ) . In later work,

11556-480: The upper set), gives an equivalent definition of the Dedekind–MacNeille completion. With the alternative definition, both the join and the meet operations of the complete lattice have symmetric descriptions: if ( A i , B i ) are the cuts in any family of cuts, then the meet of these cuts is the cut ( L , L ) where L = ∩ i A i , and the join is the cut ( U , U ) where U = ∩ i B i . If Q {\displaystyle \mathbb {Q} }

11664-415: The width w is small. Alternatively, a maximal antichain in Q is the same as a maximal independent set in the comparability graph of Q , or a maximal clique in the complement of the comparability graph, so algorithms for the clique problem or the independent set problem can also be applied to this version of the Dedekind–MacNeille completion problem. The transitive reduction or covering graph of

#550449