maths.free › Combinatorics & Graph Theory › Partially Ordered Sets › Additional Concepts for Posets
Additional Concepts for Posets
We say (X,P) and (Y,Q) are isomorphic, and write (X,P) \cong(Y,Q) if there exists a bijection (11 and onto map) f:X\to Y so that x_1\le x_2 in P if and only if f(x_1)\le f(x_2) in Q.
Additional Concepts for Posets
We say \((X,P)\) and \((Y,Q)\) are isomorphic, and write \((X,P) \cong(Y,Q)\) if there exists a bijection (11 and onto map) \(f:X\to Y\) so that \(x_1\le x_2\) in \(P\) if and only if \(f(x_1)\le f(x_2)\) in \(Q\). In this definition, the map \(f\) is called an isomorphism from \(\bfP\) to \(\bfQ\). In , the first two posets are isomorphic.
An isomorphism from \(\bfP\) to \(\bfP\) is called an automorphism of \(\bfP\). An isomorphism from \(\bfP\) to a subposet of \(\bfQ\) is called an embedding of \(\bfP\) in \(\bfQ\). In most settings, we will not distinguish between isomorphic posets, and we will say that a poset \(\PXP\) is contained in \(\QYQ\) (also \(\bfQ\) contains \(\bfP\)) when there is an embedding of \(\bfP\) in \(\bfQ\). Also, we will say that \(\bfP\) excludes \(\bfQ\) when no subposet of \(\bfP\) is isomorphic to \(\bfQ\), and we will frequently say \(\bfP=\bfQ\) when \(\bfP\) and \(\bfQ\) are isomorphic.
With the notion of isomorphism, we are lead naturally to the notion of an unlabeled posets, and in , we show a diagram for such a poset.
Note that the poset shown in has the property that there is only one maximal point. Such a point is sometimes called a one, denoted not surprisingly as\(1\). Also, there is only one minimal point, and it is called a zero, denoted\(0\).
The dual of a partial order \(P\) on a set \(X\) is denoted by \(P^d\) and is defined by \(P^d=\{(y,x):(x,y)\in P\}\). The dual of a poset \(\PXP\) is denoted by \(\bfP^d\) and is defined by \(\bfP^d=(X,P^d)\). A poset \(\bfP\) is self-dual if \(\bfP=\bfP^d\).
Condensed: the full section is in Keller & Trotter, Applied Combinatorics.
Nu jij. Geen rekenmachine regelt deze, maar de stukken ervan zijn berekenbaar. Probeer er een hieronder, of typ je eigen.
Praktijk (1)
Probeer ze eerst op papier. Onthul het antwoord om te controleren; geverifieerde kunnen worden geopend in de oplossing voor elke stap.
-
Look at the four claims Bob makes in . For each claim, briefly discuss reasons why you think that Bob is correct or incorrect. Alice is correct that two of Bob's claims are correct, but try to avoid process of elimination as your justification for one of the claims being correct/incorrect!
Hier gebruikte symbolen
Tik op elk symbool voor de volledige definitie, een afbeelding en wat elke letter erin betekent.
Vragen die mensen stellen
Permutation or combination?
Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).
What is a graph in this sense?
Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.
Delen van deze pagina zijn aangepast van Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Gecondenseerd en opnieuw verklaard, fouten zijn van ons.
Meer in Combinatorics & Graph Theory
The counting principlesPigeonhole principle and inclusion, exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs