Logic & Sets

Table of Contents

Partial orders

partial order on V: relation R of type V × V. satisfies reflexivity, anti-symmetry, transitivity

example: relation ≤ is partial order on N

example: the relation ⊆ is partial order on P(V)

linear ordering relations

partial order R on set V, then:

e.g. relation ≤ on N: for all n,m in N — n ≤ m or m ≤ n — total

e.g. relation ⊆ on P({1,2}): {1} is not a subset of {2}, {2} is not a subset of {1} — not total

strict partial ordering relations

if partial order R on set V, then strict partial order S corresponding to R is defined by

x S y ⟷ x R y and x ≠ y

a strict partial order is irreflexive, anti-symmetric, transitive

Hasse diagrams

apparently a partial ordering relation is complicated as fuck:

screenshot.png

so get rid of some arrows and make a Hasse diagram — omit reflexivity and transitivity

the arrows create chains that split and merge, elements in the same chain are comparable

screenshot.png

Algorithm:

  1. For all x ∈ V — Gx := {y : y ≠ x and x R y}
  2. For all x ∈ V — Hx := Gx \ {z : z ∈ Gy for a y ∈ Gx}
  3. For all x ∈ V — draw and arrow from x to every y ∈ Hx

example: screenshot.png

Cartesian order on A × B

<a1, b1> ≤ <a2, b2> ⟷ a1 ≤A a2 and b1 ≤B b2

ordered by points, if both are smaller

cartesian order on A × B is a partial order

screenshot.png

Lexicographic order on A × B

<a1, b1> ≤ <a2, b2> ⟷ (a1 <A a2) ∨ (a1 = a2 ∧ b1 ≤B b2)

like in a dictionary

lexicographic order on A× B is a partial order, total if ≤A on A and ≤B on B are total

screenshot.png

Minimal and maximal elements

(V, ≤) is a partially ordered set, A ⊆ V, m ∈ A

m is:

Every maximum of A is a maximal element of A. If A has a maximum, it is the only maximal element.