Partial orders.html (6216B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.0.3 (456341)"/><meta name="keywords" content="sets"/><meta name="altitude" content="-2.172817707061768"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-02-22 14:42:21 +0000"/><meta name="latitude" content="52.33466509195276"/><meta name="longitude" content="4.86638665785288"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-02-26 20:46:09 +0000"/><title>Partial orders</title></head><body><div>partial order on V: relation R of type V × V. satisfies reflexivity, anti-symmetry, transitivity</div><div>example: relation ≤ is partial order on N</div><div><ul><li>∀n: n ≤ n (reflexivity)</li><li>∀m, n: m≤n ∧ n≤m ➝ m = n (anti-symmetry)</li><li>∀k, m, n: k≤m ∧ m≤n ➝ k≤n (transitivity)</li></ul><div><br/></div></div><div>example: the relation ⊆ is partial order on P(V)</div><div><ul><li>∀A: A ⊆ A (reflexivity)</li><li>∀A,B: A ⊆ B ∧ A ➝ A = B (anti-symmetry)</li><li>∀A,B,C: A ⊆ B ∧ B ⊆ C ➝ A ⊆ C (transitivity)</li></ul><div><br/></div><div><span style="font-weight: bold;">linear ordering relations</span></div><div>partial order R on set V, then:</div><div><ul><li>x, y ∈ V are <span style="text-decoration: underline;">comparable</span> if x R y or y R x</li><li>R is <span style="text-decoration: underline;">linear/total order</span> if all x,y ∈ V are comparable</li></ul><div><br/></div></div><div>e.g. relation ≤ on N: for all n,m in N — n ≤ m or m ≤ n — <span style="text-decoration: underline;">total</span></div><div>e.g. relation ⊆ on P({1,2}): {1} is not a subset of {2}, {2} is not a subset of {1} — <span style="text-decoration: underline;">not total</span></div><div><br/></div><div><span style="font-weight: bold;">strict partial ordering relations</span></div></div><div>if partial order R on set V, then <span style="text-decoration: underline;">strict partial order</span> S corresponding to R is defined by</div><div>x S y ⟷ x R y and x ≠ y</div><div><br/></div><div>a strict partial order is irreflexive, anti-symmetric, transitive</div><div><br/></div><div><span style="font-weight: bold;">Hasse diagrams</span></div><div>apparently a partial ordering relation is complicated as fuck:</div><div><br/></div><div><img src="Partial%20orders.resources/screenshot.png" height="370" width="617"/><br/></div><div><br/></div><div>so get rid of some arrows and make a Hasse diagram — omit reflexivity and transitivity</div><div>the arrows create chains that split and merge, elements in the same chain are comparable</div><div><br/></div><div><img src="Partial%20orders.resources/screenshot_1.png" height="330" width="434"/><br/></div><div><br/></div><div>Algorithm:</div><div><ol><li>For all x ∈ V — G<span style="vertical-align: sub;">x</span> := {y : y ≠ x and x R y}</li><li>For all x ∈ V — H<span style="vertical-align: sub;">x</span> := G<span style="vertical-align: sub;">x </span>\ {z : z ∈ G<span style="vertical-align: sub;">y</span> for a y ∈ G<span style="vertical-align: sub;">x</span>}</li><li>For all x ∈ V — draw and arrow from x to every y ∈ H<span style="vertical-align: sub;">x</span></li></ol></div><div><br/></div><div><span style="font-size: 14px;">example:</span></div><div><img src="Partial%20orders.resources/screenshot_2.png" height="214" width="475"/><br/></div><div><br/></div><div><span style="font-weight: bold;">Cartesian order on A × B</span></div><div><a<span style="vertical-align: sub;">1</span>, b<span style="vertical-align: sub;">1</span>> ≤ <<span style="font-size: 14px;">a</span><span style="font-size: 14px; vertical-align: sub;">2</span><span style="font-size: 14px;">, b</span><span style="font-size: 14px; vertical-align: sub;">2</span><span style="font-size: 14px;">> ⟷ a1 ≤</span><span style="font-size: 14px; vertical-align: sub;">A</span><span style="font-size: 14px;"> a</span><span style="font-size: 14px; vertical-align: sub;">2</span><span style="font-size: 14px;"> and b</span><span style="font-size: 14px; vertical-align: sub;">1</span><span style="font-size: 14px;"> ≤</span><span style="font-size: 14px; vertical-align: sub;">B</span><span style="font-size: 14px;"> b</span><span style="font-size: 14px; vertical-align: sub;">2</span></div><div>ordered by points, if both are smaller</div><div>cartesian order on A × B is a partial order</div><div><br/></div><div><img src="Partial%20orders.resources/screenshot_3.png" height="241" width="569"/><br/></div><div><br/></div><div><span style="font-weight: bold;">Lexicographic order on A × B</span></div><div><a<span style="font-size: 11.666666030883789px;">1, </span>b<span style="font-size: 14px;">1</span><span style="font-size: 14px;">></span><span style="font-size: 14px;"> ≤ <a2, b2> ⟷ (a1 <A a2) ∨ (a1 = a2 ∧ b1 ≤B b2)</span></div><div>like in a dictionary</div><div>lexicographic order on A× B is a partial order, total if ≤A on A and ≤B on B are total</div><div><br/></div><div><img src="Partial%20orders.resources/screenshot_4.png" height="248" width="610"/><br/></div><div><br/></div><div><span style="font-weight: bold;">Minimal and maximal elements</span></div><div>(V, ≤) is a partially ordered set, A ⊆ V, m ∈ A</div><div><br/></div><div>m is:</div><div><ul><li>largest element of A — if ∀a ∈ A : a ≤ m</li><li>smallest element of A — if ∀a ∈ A : m ≤ a</li><li>maximal element of A — if ∀a ∈ A : (M ≤ a ➝ m = a) — no outgoing arrows on Hasse diagram</li><li>minimal element of A — if ∀a ∈ A : (a ≤ m ➝ a = m) — no incoming arrows on Hasse diagram</li></ul><div><br/></div></div><div>Every maximum of A is a maximal element of A.</div><div>If A has a maximum, it is the only maximal element.</div><div><br/></div><div><br/></div><div><br/></div></body></html>