rasmus/DTU-Noter
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
DTU-Noter/Diskret Mat/Relations/2025-11-20-01017-lecture.typ
Rasmus Rosendahl-Kaa e1a4e65d59 first commit
2025-11-26 15:29:50 +01:00

953 lines
32 KiB
Typst
Raw Permalink Blame History

#import "@local/dtu-template:0.5.1":*
#import "@preview/cetz:0.4.2"
#show: dtu-note.with(
course: "01017",
course-name: "Discrete Mathematics",
title: "Lecture - November 20, 2025",
date: datetime(day: 20, month: 11, year: 2025),
author: "Sebastian Faber Steffensen (s255609)",
semester: "2025 Fall",
)
= Sections 9.5 and 9.6: Relations and Partial Orders
== Introduction to Relations
#definition(
title: "Relation",
)[
Consider a set $S$ and a relation $R$ on $S$. We write $(S, R)$ to denote this structure.
For $a, b in S$, we say "$a$ is related to $b$" and write $a R b$ if the ordered pair $(a, b)$ is in the relation $R$.
In essence, a relation is just a set of ordered pairs: $R subset.eq S times S$.
]
#example(title: "Finite Relation")[
Let $S = {1, 2, 3}$ and suppose $R$ contains the pairs $(1,2)$, $(2,3)$, $(3,2)$, and $(2,2)$.
We can represent this as:
$
R = {(1,2), (2,3), (3,2), (2,2)}
$
This relation can be visualized as a directed graph:
#align(center)[
#cetz.canvas({
import cetz.draw: *
// Define node positions
let node1 = (0, 0)
let node2 = (2, 0)
let node3 = (4, 0)
// Draw nodes
circle(node1, radius: 0.3, fill: white, stroke: black + 1pt, name: "n1")
content(node1, [1])
circle(node2, radius: 0.3, fill: white, stroke: black + 1pt, name: "n2")
content(node2, [2])
circle(node3, radius: 0.3, fill: white, stroke: black + 1pt, name: "n3")
content(node3, [3])
// Draw edges with arrows
// (1,2) - arrow from 1 to 2
line("n1.east", "n2.west", mark: (end: ">", fill: black), stroke: black + 1pt)
// (2,3) - arrow from 2 to 3
line("n2.east", "n3.west", mark: (end: ">", fill: black), stroke: black + 1pt)
// (3,2) - arrow from 3 to 2 (curved to avoid overlap)
bezier("n3.north", "n2.north", (3, 0.8), (2.5, 0.8), mark: (end: ">", fill: black), stroke: black + 1pt)
// (2,2) - self-loop at 2
arc(
(name: "n2", anchor: 90deg),
start: 0deg,
delta: 360deg,
radius: 0.5,
mark: (end: ">", fill: black),
stroke: black + 1pt,
)
})
]
]
=== Common Sets
Throughout this section, we use the following standard sets:
$
ZZ, ZZ_+, NN, QQ, QQ_+, RR, CC
$
We also work with power sets $cal(P)(S)$, which denote the set of all subsets of $S$.
=== Common Relations
Examples of relations include:
$
=, <=, <, >=, >, in, subset.eq, subset, supset.eq, supset, equiv, divides
$
== Equivalence Relations
#definition(
title: "Equivalence Relation",
)[
A relation $R$ on a set $S$ is an *equivalence relation* if and only if $R$ satisfies the following three properties:
+ *Reflexive:* $forall a in S, a R a$
+ *Symmetric:* $forall a, b in S$, if $a R b$ then $b R a$
+ *Transitive:* $forall a, b, c in S$, if $a R b$ and $b R c$ then $a R c$
]
#example(
title: "Classifying Relations",
)[
Let's classify common relations by their properties:
*Reflexive Relations:*
$
=, <=, >=, subset.eq, supset.eq, equiv
$
*Symmetric Relations:*
$
=, equiv
$
*Transitive Relations:*
$
=, <=, >=, subset.eq, supset.eq, equiv, divides
$
Note: The relation $divides$ on $ZZ_+$ is reflexive and transitive, but not symmetric (e.g., $2 divides 4$ but $4 divides.not 2$).
]
#example(title: "Transitivity Visualization")[
If $a R b$ and $b R c$, then by transitivity we must have $a R c$:
#align(center)[
#cetz.canvas({
import cetz.draw: *
// Define node positions in a triangle
let node-a = (1, 1.5)
let node-b = (0, 0)
let node-c = (2, 0)
// Draw nodes
circle(node-a, radius: 0.3, fill: white, stroke: black + 1pt, name: "na")
content(node-a, [$a$])
circle(node-b, radius: 0.3, fill: white, stroke: black + 1pt, name: "nb")
content(node-b, [$b$])
circle(node-c, radius: 0.3, fill: white, stroke: black + 1pt, name: "nc")
content(node-c, [$c$])
// Draw edges with arrows
// aRb - arrow from a to b
line("na.south-west", "nb.north-east", mark: (end: ">", fill: black), stroke: black + 1pt)
// bRc - arrow from b to c
line("nb.east", "nc.west", mark: (end: ">", fill: black), stroke: black + 1pt)
// aRc - arrow from a to c (transitivity)
line("na.south-east", "nc.north-west", mark: (end: ">", fill: black), stroke: black + 1pt)
})
]
]
=== Equivalence Classes
#definition(
title: "Equivalence Class",
)[
If $tilde$ is an equivalence relation on $S$, the *equivalence class* of an element $a in S$ is denoted $[a]_tilde$ and defined as:
$
[a]_tilde = {x in S | x tilde a}
$
This is the set of all elements related to $a$.
]
#example(title: "Congruence Modulo 4")[
Consider the equivalence relation of congruence modulo 4 on $ZZ$:
$
[0]_(mod 4) &= {dots.c, -8, -4, 0, 4, 8, dots.c} \
[1]_(mod 4) &= {dots.c, -7, -3, 1, 5, 9, dots.c} \
[2]_(mod 4) &= {dots.c, -6, -2, 2, 6, 10, dots.c} \
[3]_(mod 4) &= {dots.c, -5, -1, 3, 7, 11, dots.c}
$
These four equivalence classes partition the integers.
]
#theorem(title: "Properties of Equivalence Classes")[
Let $tilde$ be an equivalence relation on $S$. For any $a, b in S$, the following are equivalent:
+ $a tilde b$
+ $[a]_tilde = [b]_tilde$
+ $[a]_tilde inter [b]_tilde eq.not emptyset$
]
#proof(
)[
We prove the cycle of implications: $(1) arrow.r.double (2) arrow.r.double (3) arrow.r.double (1)$.
#align(center)[
#cetz.canvas({
import cetz.draw: *
// Define node positions in a line
let node1 = (0, 0)
let node2 = (4, 0)
let node3 = (8, 0)
// Draw nodes as rectangles with content
rect(
(node1.at(0) - 1, node1.at(1) - 0.3),
(node1.at(0) + 1, node1.at(1) + 0.3),
fill: white,
stroke: black + 1pt,
name: "n1",
)
content(node1, [$a tilde b$])
rect(
(node2.at(0) - 1, node2.at(1) - 0.3),
(node2.at(0) + 1, node2.at(1) + 0.3),
fill: white,
stroke: black + 1pt,
name: "n2",
)
content(node2, [$[a]_tilde = [b]_tilde$])
rect(
(node3.at(0) - 1.2, node3.at(1) - 0.3),
(node3.at(0) + 1.2, node3.at(1) + 0.3),
fill: white,
stroke: black + 1pt,
name: "n3",
)
content(node3, [$[a]_tilde inter [b]_tilde eq.not emptyset$])
// Draw arrows: 1 → 2 → 3 → 1
// Arrow from n1 to n2
line("n1.east", "n2.west", mark: (end: ">", fill: black), stroke: black + 1pt)
// Arrow from n2 to n3
line("n2.east", "n3.west", mark: (end: ">", fill: black), stroke: black + 1pt)
// Arrow from n3 to n1 (curved above to avoid covering text)
bezier("n3.south", "n1.south", (7, -1.5), (1, -1.5), mark: (end: ">", fill: black), stroke: black + 1pt)
})
]
*(3) $arrow.r.double$ (1):* Suppose $[a]_tilde inter [b]_tilde eq.not emptyset$. Then there exists some $x in [a]_tilde inter [b]_tilde$.
#align(center)[
#cetz.canvas({
import cetz.draw: *
// Draw two overlapping circles for Venn diagram
// Circle for [a]
circle((0.5, 0), radius: 1, fill: rgb(100, 150, 255, 100), stroke: black + 1pt, name: "a")
content((0, 0), [$[a]_tilde$])
// Circle for [b]
circle((1.5, 0), radius: 1, fill: rgb(255, 150, 100, 100), stroke: black + 1pt, name: "b")
content((2, 0), [$[b]_tilde$])
// Mark the intersection point with x
content((1, 0), [$x$], fill: white, frame: "circle", stroke: none, padding: 0.15)
})
]
By definition, $x tilde a$ and $x tilde b$. By symmetry, $a tilde x$. By transitivity, $a tilde x$ and $x tilde b$ implies $a tilde b$.
]
#theorem(
title: "Partition Property",
)[
Let $tilde$ be an equivalence relation on a set $S$. The equivalence classes of $tilde$ form a partition of $S$.
That is:
+ Every element $a in S$ belongs to exactly one equivalence class $[a]_tilde$.
+ The equivalence classes are pairwise disjoint: if $[a]_tilde eq.not [b]_tilde$, then $[a]_tilde inter [b]_tilde = emptyset$.
+ The union of all equivalence classes equals $S$.
]
#align(center)[
#cetz.canvas({
import cetz.draw: *
// Draw the outer set S
circle((0, 0), radius: 2.5, stroke: black + 2pt, name: "S")
content((0, -2.8), [$S$])
// Draw disjoint partition subsets that perfectly fill S
circle((-1.2, 1), radius: 0.65, fill: rgb(100, 150, 255, 150), stroke: black + 1pt)
circle((0.5, 1.3), radius: 0.55, fill: rgb(255, 150, 100, 150), stroke: black + 1pt)
circle((1.5, 0.5), radius: 0.6, fill: rgb(150, 255, 150, 150), stroke: black + 1pt)
circle((1.6, -0.8), radius: 0.55, fill: rgb(255, 255, 100, 150), stroke: black + 1pt)
circle((0.6, -1.5), radius: 0.6, fill: rgb(255, 150, 255, 150), stroke: black + 1pt)
circle((-0.8, -1.4), radius: 0.65, fill: rgb(150, 255, 255, 150), stroke: black + 1pt)
circle((-1.6, -0.3), radius: 0.7, fill: rgb(255, 200, 150, 150), stroke: black + 1pt)
circle((0, 0.2), radius: 0.5, fill: rgb(200, 150, 255, 150), stroke: black + 1pt)
circle((-0.3, -0.5), radius: 0.45, fill: rgb(150, 255, 200, 150), stroke: black + 1pt)
})
]
== Partial Orders (Posets)
#definition(title: "Partially Ordered Set (Poset)")[
A relation $R$ on a set $S$ is a *partial order* if $R$ satisfies:
+ *Reflexive:* $forall a in S, a R a$
+ *Antisymmetric:* $forall a, b in S$, if $a R b$ and $b R a$ then $a = b$
+ *Transitive:* $forall a, b, c in S$, if $a R b$ and $b R c$ then $a R c$
We call $(S, R)$ a *partially ordered set* or *poset*.
]
#note-box()[
The key difference between equivalence relations and partial orders is:
- Equivalence relations require *symmetry*
- Partial orders require *antisymmetry*
]
#example(title: "Examples of Partial Orders")[
The following are partial orders:
$
=, <=, >=, subset.eq, supset.eq, divides "(on" ZZ_+)
$
For instance, $(ZZ_+, divides)$ is a poset because:
- $forall a in ZZ_+$: $a divides a$ (reflexive)
- If $a divides b$ and $b divides a$, then $a = b$ (antisymmetric)
- If $a divides b$ and $b divides c$, then $a divides c$ (transitive)
]
=== Notation and Terminology
For a partial order $R$ on $S$, we often use the notation $prec.eq$ instead of $R$, and write $a prec.eq b$ instead of $a R b$.
#note-box(
)[
Different authors may use different symbols such as $<=$ or $subset.sq.eq$ for general partial orders. The symbol $prec.eq$ is commonly used when the specific ordering is understood from context.
]
#definition(title: "Comparable Elements")[
Two elements $a, b in S$ are *comparable* if either $a prec.eq b$ or $b prec.eq a$.
If $a$ and $b$ are not comparable, we say they are *incomparable*.
]
#definition(title: "Total Order (Chain)")[
A partial order $(S, prec.eq)$ is a *total order* or *chain* if every pair of elements is comparable.
That is, for all $a, b in S$, either $a prec.eq b$ or $b prec.eq a$.
]
#definition(title: "Well-Ordered Set")[
A poset $(S, prec.eq)$ is *well-ordered* if every non-empty subset of $S$ has a smallest element (minimum).
]
#example(title: "Incomparable Elements")[
Consider the poset shown below:
#align(center)[
#cetz.canvas({
import cetz.draw: *
// Define node positions as a square
let bl = (0, 0) // bottom left
let br = (2, 0) // bottom right
let tl = (0, 2) // top left
let tr = (2, 2) // top right
// Draw nodes
circle(bl, radius: 0.3, fill: white, stroke: black + 1pt, name: "bl")
content(bl, [$a$])
circle(br, radius: 0.3, fill: white, stroke: black + 1pt, name: "br")
content(br, [$b$])
circle(tl, radius: 0.3, fill: white, stroke: black + 1pt, name: "tl")
content(tl, [$c$])
circle(tr, radius: 0.3, fill: white, stroke: black + 1pt, name: "tr")
content(tr, [$d$])
// Draw arrows
// b.l points to t.l and t.r
line("bl.north", "tl.south", mark: (end: ">", fill: black), stroke: black + 1pt)
line("bl.north-east", "tr.south-west", mark: (end: ">", fill: black), stroke: black + 1pt)
// b.r points to t.r, and t.l
line("br.north", "tr.south", mark: (end: ">", fill: black), stroke: black + 1pt)
line("br.north-west", "tl.south-east", mark: (end: ">", fill: black), stroke: black + 1pt)
// Annotations
content((1, 2.7), [*Maximal elements*])
content((1, -0.7), [*Minimal elements*])
})
]
In this poset:
- $a$ and $b$ are *incomparable* (neither $a prec.eq b$ nor $b prec.eq a$)
- $c$ and $d$ are *incomparable*
- Both $a$ and $b$ are *minimal elements*
- Both $c$ and $d$ are *maximal elements*
]
=== Minimal and Maximal Elements
#definition(title: "Minimal and Maximal Elements")[
Let $(S, prec.eq)$ be a poset.
- An element $a in S$ is *minimal* if there is no element $x in S$ such that $x prec.eq a$ and $x eq.not a$.
- An element $a in S$ is *maximal* if there is no element $x in S$ such that $a prec.eq x$ and $x eq.not a$.
]
#definition(title: "Minimum and Maximum Elements")[
Let $(S, prec.eq)$ be a poset.
- An element $a in S$ is the *minimum* (or *least element*) if $forall x in S, a prec.eq x$.
- An element $a in S$ is the *maximum* (or *greatest element*) if $forall x in S, x prec.eq a$.
]
#note-box()[
Key differences:
- A poset can have multiple minimal/maximal elements
- A poset has at most one minimum/maximum element
- Every minimum is minimal, but not every minimal element is a minimum
]
#example(title: "Ordinal Numbers")[
Consider the ordinal numbers with their natural ordering:
#cetz.canvas({
import cetz.draw: *
let y = 0 // Same y-coordinate for all lines
// First number line: 1, 2, 3, ...
line((0, y), (5, y), stroke: black + 1pt, mark: (end: ">", fill: black))
// Nodes on first line
circle((0.5, y), radius: 0.15, fill: black)
content((0.5, y - 0.4), [1])
circle((1.5, y), radius: 0.15, fill: black)
content((1.5, y - 0.4), [2])
circle((2.5, y), radius: 0.15, fill: black)
content((2.5, y - 0.4), [3])
content((5.3, y), [$dots.c$])
// Second number line: ω, ω+1, ω+2, ...
line((6, y), (11, y), stroke: black + 1pt, mark: (end: ">", fill: black))
// Nodes on second line
circle((6.5, y), radius: 0.15, fill: black)
content((6.5, y - 0.4), [$omega$])
circle((7.5, y), radius: 0.15, fill: black)
content((7.5, y - 0.4), [$omega + 1$])
circle((8.5, y), radius: 0.15, fill: black)
content((8.5, y - 0.4), [$omega + 2$])
content((11.3, y), [$dots.c$])
// Third number line: 2ω, 2ω+1, ...
line((12, y), (17, y), stroke: black + 1pt, mark: (end: ">", fill: black))
// Nodes on third line
circle((12.5, y), radius: 0.15, fill: black)
content((12.5, y - 0.4), [$1w$])
circle((13.5, y), radius: 0.15, fill: black)
content((13.5, y - 0.4), [$2u + 1$])
circle((14.5, y), radius: 0.15, fill: black)
content((14.5, y - 0.4), [$dots.c$])
content((17.3, y), [$dots.c$])
})
This is a well-ordered set where every subset has a minimum element.
]
#theorem(title: "Existence of Minimal Elements")[
Every finite partially ordered set has at least one minimal element.
]
#proof(
)[
Let $(S, prec.eq)$ be a finite poset. Pick any element $x_1 in S$.
- If $x_1$ is minimal, we are done.
- Otherwise, there exists $x_2 prec.eq x_1$ with $x_2 eq.not x_1$.
- If $x_2$ is minimal, we are done.
- Otherwise, continue this process.
Since $S$ is finite, this process must terminate, yielding a minimal element.
Geometrically, we can think of placing elements on a vertical line where if $x prec.eq y$, then $x$ is below $y$:
#align(center)[
#cetz.canvas({
import cetz.draw: *
// Draw x and y nodes vertically
circle((0, 0), radius: 0.3, fill: white, stroke: black + 1pt, name: "x")
content((0, 0), [$x$])
circle((0, 2), radius: 0.3, fill: white, stroke: black + 1pt, name: "y")
content((0, 2), [$y$])
// Arrow from x to y
line("x.north", "y.south", mark: (end: ">", fill: black), stroke: black + 1pt)
})
]
The bottommost element in such a representation is minimal.
]
=== Topological Sorting
#definition(
title: "Topological Sort",
)[
A *topological sort* of a finite poset $(S, prec.eq)$ is a total ordering of the elements that is compatible with the partial order.
That is, we arrange elements in a sequence $a_1, a_2, dots.c, a_n$ such that if $a_i prec.eq a_j$ in the partial order, then $i <= j$ in the sequence.
]
#example(title: "Topological Sort")[
#align(center)[
#cetz.canvas({
import cetz.draw: *
// Draw nodes in a line
circle((0, 0), radius: 0.3, fill: white, stroke: black + 1pt, name: "a")
content((0, 0), [$a$])
circle((2, 0), radius: 0.3, fill: white, stroke: black + 1pt, name: "b")
content((2, 0), [$b$])
circle((4, 0), radius: 0.3, fill: white, stroke: black + 1pt, name: "c")
content((4, 0), [$c$])
circle((6, 0), radius: 0.3, fill: white, stroke: black + 1pt, name: "d")
content((6, 0), [$d$])
// Arrows between nodes
line("a.east", "b.west", mark: (end: ">", fill: black), stroke: black + 1pt)
line("b.east", "c.west", mark: (end: ">", fill: black), stroke: black + 1pt)
line("c.east", "d.west", mark: (end: ">", fill: black), stroke: black + 1pt)
// Annotation
content((3, -1), [Topological sort])
})
]
This represents a compatible total ordering $a prec.eq b prec.eq c prec.eq d$.
]
=== Lexicographic Ordering
#definition(
title: "Lexicographic Order",
)[
Given two partially ordered sets $(S_1, prec.eq_1)$ and $(S_2, prec.eq_2)$, we can define the *lexicographic ordering* $prec.eq$ on $S_1 times S_2$ as follows:
$(a_1, a_2) prec.eq (b_1, b_2)$ if and only if either:
- $a_1 prec.eq_1 b_1$, or
- $a_1 = b_1$ and $a_2 prec.eq_2 b_2$
]
#example(title: "Alphabetical Ordering")[
The lexicographic order generalizes alphabetical ordering. With letters ordered as $A < B < C < dots.c < Z$:
$
"ANNA" < "ANNI" < "JOHN"
$
This is because:
- "ANNA" vs "ANNI": First three letters match, but N < N is false and the fourth letter A < I
- "ANNI" vs "JOHN": First letter A < J
]
== Hasse Diagrams
#definition(
title: "Hasse Diagram",
)[
A *Hasse diagram* is a visual representation of a finite poset that simplifies the traditional directed graph by:
+ Removing all self-loops (reflexivity is implicit)
+ Removing all transitive edges (transitivity is implicit)
+ Removing all arrows (direction is upward by convention)
+ Positioning elements so that if $x prec.eq y$, then $x$ is below $y$
]
#example(title: "Poset ${1,2,3,4}$ with $<=$")[
First, the complete directed graph:
#align(center)[
#cetz.canvas({
import cetz.draw: *
// Draw nodes vertically
circle((0, 0), radius: 0.3, fill: white, stroke: black + 1pt, name: "n1")
content((0, 0), [1])
circle((0, 1.5), radius: 0.3, fill: white, stroke: black + 1pt, name: "n2")
content((0, 1.5), [2])
circle((0, 3), radius: 0.3, fill: white, stroke: black + 1pt, name: "n3")
content((0, 3), [3])
circle((0, 4.5), radius: 0.3, fill: white, stroke: black + 1pt, name: "n4")
content((0, 4.5), [4])
// 1 points to 2 (direct)
line("n1.north", "n2.south", mark: (end: ">", fill: black), stroke: black + 1pt)
// 1 points to 3 (transitive)
bezier("n1.east", "n3.east", (0.8, 1.5), mark: (end: ">", fill: black), stroke: black + 1pt)
// 1 points to 4 (transitive)
bezier("n1.east", "n4.east", (1.2, 2.25), mark: (end: ">", fill: black), stroke: black + 1pt)
// 2 points to 3 (direct)
line("n2.north", "n3.south", mark: (end: ">", fill: black), stroke: black + 1pt)
// 2 points to 4 (transitive)
bezier("n2.east", "n4.east", (0.8, 3.0), mark: (end: ">", fill: black), stroke: black + 1pt)
// 3 points to 4 (direct)
line("n3.north", "n4.south", mark: (end: ">", fill: black), stroke: black + 1pt)
// Self-loops
arc(
(name: "n1", anchor: 180deg),
start: 90deg,
delta: 270deg,
radius: 0.4,
mark: (end: ">", fill: black),
stroke: black + 1pt,
)
arc(
(name: "n2", anchor: 180deg),
start: 90deg,
delta: 270deg,
radius: 0.4,
mark: (end: ">", fill: black),
stroke: black + 1pt,
)
arc(
(name: "n3", anchor: 180deg),
start: 90deg,
delta: 270deg,
radius: 0.4,
mark: (end: ">", fill: black),
stroke: black + 1pt,
)
arc(
(name: "n4", anchor: 180deg),
start: 90deg,
delta: 270deg,
radius: 0.4,
mark: (end: ">", fill: black),
stroke: black + 1pt,
)
})
]
The corresponding Hasse diagram (with redundant information removed):
#align(center)[
#cetz.canvas({
import cetz.draw: *
// Draw nodes vertically
circle((0, 0), radius: 0.3, fill: white, stroke: black + 1pt, name: "n1")
content((0, 0), [1])
circle((0, 1.5), radius: 0.3, fill: white, stroke: black + 1pt, name: "n2")
content((0, 1.5), [2])
circle((0, 3), radius: 0.3, fill: white, stroke: black + 1pt, name: "n3")
content((0, 3), [3])
circle((0, 4.5), radius: 0.3, fill: white, stroke: black + 1pt, name: "n4")
content((0, 4.5), [4])
// Simple edges (no transitive or reflexive edges) using curves
bezier("n1.east", "n2.east", (0.6, 0.75), stroke: black + 1pt)
bezier("n2.east", "n3.east", (0.6, 2.25), stroke: black + 1pt)
bezier("n3.east", "n4.east", (0.6, 3.75), stroke: black + 1pt)
})
]
The Hasse diagram is much cleaner while preserving all ordering information.
]
#example(title: "Power Set Hasse Diagrams")[
*Hasse diagram for* $(cal(P)({1,2}), subset.eq)$:
#align(center)[
#cetz.canvas({
import cetz.draw: *
// Define node positions as a diamond (square rotated 45 degrees)
let bottom = (0, 0)
let left = (-1.5, 1.5)
let right = (1.5, 1.5)
let top = (0, 3)
// Draw nodes
circle(bottom, radius: 0.3, fill: white, stroke: black + 1pt, name: "empty")
content(bottom, [$emptyset$])
circle(left, radius: 0.3, fill: white, stroke: black + 1pt, name: "n1")
content(left, [${1}$])
circle(right, radius: 0.3, fill: white, stroke: black + 1pt, name: "n2")
content(right, [${2}$])
circle(top, radius: 0.3, fill: white, stroke: black + 1pt, name: "n12")
content(top, [${1,2}$])
// Draw edges (using curves for aesthetics)
bezier("empty.north-west", "n1.south-east", (-0.7, 0.75), stroke: black + 1pt)
bezier("empty.north-east", "n2.south-west", (0.7, 0.75), stroke: black + 1pt)
bezier("n1.north-east", "n12.south-west", (-0.7, 2.25), stroke: black + 1pt)
bezier("n2.north-west", "n12.south-east", (0.7, 2.25), stroke: black + 1pt)
})
]
*Hasse diagram for* $(cal(P)({1,2,3}), subset.eq)$:
#align(center)[
#cetz.canvas({
import cetz.draw: *
// Define node positions as a 3D cube (isometric view)
// Bottom: empty set
let empty = (0, 0)
// Layer 1: single elements (arranged in triangle)
let n1 = (-2, 1.5)
let n2 = (2, 1.5)
let n3 = (0, 2.2)
// Layer 2: pairs (arranged in triangle)
let n12 = (0, 3)
let n13 = (-2, 3.5)
let n23 = (2, 3.5)
// Top: full set
let n123 = (0, 5)
// Draw shaded faces to break optical illusion
// Right face: n2, n12, n123, n23
line(n2, n12, n123, n23, close: true, fill: rgb(200, 200, 255, 100), stroke: none)
// Left face: n1, n12, n123, n13
line(n1, n12, n123, n13, close: true, fill: rgb(255, 200, 200, 100), stroke: none)
// Floor face: empty, n1, n12, n2
line(empty, n1, n12, n2, close: true, fill: rgb(200, 255, 200, 100), stroke: none)
// Draw nodes - bottom layer
circle(empty, radius: 0.3, fill: white, stroke: black + 1pt, name: "empty")
content(empty, [$emptyset$])
circle(n1, radius: 0.3, fill: white, stroke: black + 1pt, name: "n1")
content(n1, [${1}$])
circle(n2, radius: 0.3, fill: white, stroke: black + 1pt, name: "n2")
content(n2, [${2}$])
circle(n3, radius: 0.3, fill: white, stroke: black + 1pt, name: "n3")
content(n3, [${3}$])
// Draw nodes - top layer
circle(n12, radius: 0.3, fill: white, stroke: black + 1pt, name: "n12")
content(n12, [${1,2}$])
circle(n13, radius: 0.3, fill: white, stroke: black + 1pt, name: "n13")
content(n13, [${1,3}$])
circle(n23, radius: 0.3, fill: white, stroke: black + 1pt, name: "n23")
content(n23, [${2,3}$])
circle(n123, radius: 0.3, fill: white, stroke: black + 1pt, name: "n123")
content(n123, [${1,2,3}$])
// Draw edges from empty set to single elements
line("empty.north-west", "n1.south-east", stroke: black + 1pt)
line("empty.north-east", "n2.south-west", stroke: black + 1pt)
line("empty.north", "n3.south", stroke: black + 1pt)
// Draw edges from single elements to pairs
line("n1.north-east", "n12.south-west", stroke: black + 1pt)
line("n1.north", "n13.south", stroke: black + 1pt)
line("n2.north-west", "n12.south-east", stroke: black + 1pt)
line("n2.north", "n23.south", stroke: black + 1pt)
line("n3.north-west", "n13.south-east", stroke: black + 1pt)
line("n3.north-east", "n23.south-west", stroke: black + 1pt)
// Draw edges from pairs to full set
line("n12.north", "n123.south", stroke: black + 1pt)
line("n13.north-east", "n123.south-west", stroke: black + 1pt)
line("n23.north-west", "n123.south-east", stroke: black + 1pt)
})
]
Notice how the structure forms a cube, reflecting the Boolean lattice structure of power sets.
]
= Exercises
== Section 9.5
=== 11
_Show that the relation $R$ consisting of all pairs $(x, y)$ such that $x$ and $y$ are bit strings of length three or more that agree in their first three bits is an equivalence relation on
the set of all bit strings of length three or more_
#solution[
For this we need to show $R$ is reflexive, symmetric and transitive.
+ *Reflexive:* Every bit string in $R$ of length three or more, agrees with itself in the first three bits. Hence $(x,x) in R$ for all $x$.
+ *Symmetric:* For all $a$ and $B$ in $R$ of length three of more that agrees with their first three bits, $a$ agress with $b$ in its first three digits, and also vice verca (because the first three digits are the same).
+ *Transistive:* Same as before, if $a$ and $b$ agree in their first three digits and so does $b$ and $c$, then so does $a$ and $c$ because they must have the same first three digits.
]
=== 30
_What are the equivalence classes of these bit strings for the equivalence relation in Exercise 11?_
/ a): 010
/ b): 1011
/ c): 11111
/ d): 01010101
#solution[
/ a): It would consist of all bit strings starting with $010$. So like $0100001, 010110, 010111, "etc."$
/ b): It would consist of all bit strings starting with $101$.
/ c): It would consist of all bit strings starting with $111$
/ d): Same as a) because here its first three digits are $010$
]
=== 35
_What is the congruence class $[n]_5$ (that is, the equivalence class of $n$ with respect to congruence modulo $5$) when $n$ is:_
/ a): 2?
/ b): 3?
/ c): 6?
/ d): -3?
#solution[
/ a): ${dots, -8, -3, 2, 7, 12, dots}$
/ b): ${dots, -7, -2, 3, 8, 13, dots}$
/ c): ${dots, -9, -4, 1, 6, 11}$
/ d): Samme som a)?
]
=== 45
_Which of these are partitions of the set $ZZ times ZZ$ of ordered pairs of integers?
/ a): the set of pairs $(x, y)$, where $x$ or $y$ is odd; the set of pairs $(x, y)$, where $x$ is even; and the set of pairs $(x, y)$, where $y$ is even
/ b): the set of pairs $(x, y)$, where both $x$ and $y$ are odd; the set of pairs $(x, y)$, where exactly one of $x$ and $y$ is odd; and the set of pairs $(x, y)$, where both $x$ and $y$ are even
/ c): the set of pairs $(x, y)$, where $x$ is positive; the set of pairs $(x, y)$, where $y$ is positive; and the set of pairs $(x, y)$, where both $x$ and $y$ are negative
/ d): the set of pairs $(x, y)$, where $3 divides y$ and $3 divides y$; the set of pairs $(x, y)$, where $3 divides x$ and $3 divides.not y$; the set of pairs $(x, y)$, where $3 divides.not x$ and $3 divides y$; and the set of pairs $(x, y)$, where $3 divides.not x$ and $3 divides.not y$
/ e): the set of pairs $(x, y)$, where $x > 0$ and $y > 0$; the set of pairs $(x, y)$, where $x > 0$ and $y ≤ 0$; the set of pairs $(x, y)$, where $x ≤ 0$ and $y > 0$; and the set of pairs $(x, y)$, where $x ≤ 0$ and $y ≤ 0$
/ f): the set of pairs $(x, y)$, where $x eq.not 0 $and $y eq.not 0$; the set of pairs $(x, y)$, where $x = 0$ and $y eq.not 0$; and the set of pairs $(x, y)$, where $x eq.not 0$ and $y eq.not 0$
_
#solution[
For them to be partitions, they need to uphold:
+ Every element $a in S$ belongs to exactly one equivalence class $[a]_tilde$.
+ The equivalence classes are pairwise disjoint: if $[a]_tilde eq.not [b]_tilde$, then $[a]_tilde inter [b]_tilde = emptyset$.
+ The union of all equivalence classes equals $S$.
/ a): Not this one as there is an intersection between the sets (when $x$ is even, and $y$ is odd. This set is in the first two)
/ b): This is a partition, as there is no overlap between them (you have three sets containing only even x and y, only odd x and y, and all the other cases where one of x and y is odd).
/ c): Not this one, as the set of pairs where $x$ is positive can contain positive $y$, so there's overlap.
/ d): This is a partition, same reason as b).
/ e): This is a partition, same reason as b)
]
=== 1
=== 7
== Section 9.6
=== 3
_ Is $(S, R)$ a poset if $S$ is the set of all people in the world
and $(a, b) in R$, where $a$ and $b$ are people, if
/ a): $a$ is taller than $b$?
/ b): $a$ is not taller than $b$?
/ c): $a = b$ or $a$ is an ancestor of $b$?
/ d): $a$ and $b$ have a common friend?
_
#solution[
For this to be true it needs to follow:
+ *Reflexive:* $forall a in S, a R a$
+ *Antisymmetric:* $forall a, b in S$, if $a R b$ and $b R a$ then $a = b$
+ *Transitive:* $forall a, b, c in S$, if $a R b$ and $b R c$ then $a R c$
/ a): This isn't reflective as $a$ is not taller than $a$
/ b): This is reflective, for the reason as in a). This wouldn't be antisymmetric as people can exist that are the exact same height.
/ c): This is reflective. This is also antisymmetric as the only way for $a R b$ and $b R a$ is if the first condition of $a = b$ is met. This would also be transitive as if $a$ is an ancestor of $b$, who is an ancestor of $c$, then $a$ is also an ancestor of $c$.
/ d): This is reflective as your friends are all common friends with yourself. This wouldn't be antisymmetric as when you have a common friend with someone, they also have that same common friend with you
]
=== 19
_Find the lexicographic ordering of the bit strings $0, 01, 11, 001, 010, 011, 0001, "and" 0101$ based on the ordering $0 < 1$._
#solution[
$0<0001<001<01<010<0101<011<11$
]
=== 33
_Answer these questions for the poset $({3, 5, 9, 15, 24, 45}, divides)$.
/ a): Find the maximal elements.
/ b): Find the minimal elements.
/ c): Is there a greatest element?
/ d): Is there a least element?
/ e): Find all upper bounds of ${3, 5}$.
/ f): Find the least upper bound of ${3, 5}$, if it exists.
/ g): Find all lower bounds of ${15, 45}$.
/ h): Find the greatest lower bound of ${15, 45}$, if it exists.
_
#solution[
The poset would include ${(3, 9), (3, 15), (3,24), (3,45), (5,15), (5,45), (9,45)}$
/ a): 24 and 45. They can't divide any number.
/ b): 3 and 5. They arent divisible by any number.
/ c): No. The closest would be 45, but it isnt divisible by 24.
/ d): No. The closest would be 3, but it doesnt divide 5.
/ e): $(15, 45)$
/ f): 15
/ g): $(3,5, 15)$
/ h): 15
]
=== 1
=== 15
=== 20
Reference in New Issue View Git Blame Copy Permalink