Introduction to Discrete Structures Summary 2019
Check the summary of Logic and Set Theory for the pre-knowledge of this subject.
Note: the first paragraph repeats what has been taught in Logic and Set Theory but this has also has been
included in the first week of this course hence the repetition. Also: on the left the lecture number is shown.
1 There are several proving techniques. Direct proof is the most basic approach: logically combine
definitions and theorems (forward reasoning) and simplify the goal (backwards reasoning) until the proof is
finished. For proof by case distinction each possible configurations is distinguished for a certain situation
and it is proven that the statement holds for each separately; this is useful when there is a small number of
configurations. An integer n is a perfect square if there exists another integer k such that k2 = n. Proof by
contradiction is done by assuming the negation, showing that this is impossible and ensuring that the
assumption is the only thing that could be wrong; this is useful when the negation has a ‘there exists’
quantifier. The theorem called the pigeonhole principle states that if n items are put into m containers and
n > m, then there must exist a container that contains more than one item. This is a version of proof by
contradiction. For proof by induction you prove one (or more) simple base cases explicitly and then prove
that if the claim holds for k, then it also holds for k + 1. This is useful if you need to prove infinitely many
cases. For proving the step case (k holds implies that k + 1 also holds) the value of k can be restricted in
the inductive hypothesis (e.g. Step: Assume k ≥ 1. IH: 1 ≤ k’ ≤ k).
2 Elements (x) are part of sets (X), so x ∈ X. Know the following definitions: - |X| is the size of set X
- X ⊆ Y if x ∈ X implies x ∈ Y – X = Y if X ⊆ Y and Y ⊆ X – X ∪ Y = {z | z ∈ X or z ∈ Y}
– X ∩ Y = {z | z ∈ X and z ∈ Y} – X\Y is setminus
– P(X) is the powerset – capital versions of ∪ and ∩ to take union/intersection of multiple set.
Associativity means that for any three sets A, B, C it is (A ∪ B) ∪ C = A ∪ (B ∪ C). Distributivity means
that for any three sets X, Y, Z we have X ∩ (Y ∪ Z) = (X ∩ Y) ∪ (X ∩ Z) and X ∪ (Y ∩ Z) = (X ∪ Y) ∩ (X ∪
Z). De Morgan Laws mean that for any sets X, A, B it is X \ (A ∪ B) = (X \ A) ∩ (X \ B) and X \ (A ∩ B) =
(X \ A) ∪ (X \ B). For two sets X and Y, we define their Cartesian product X × Y as X × Y = {(x, y) | x ∈ X,
y ∈ Y} and is thus the set of all ordered pairs with the first element in X and the second element in Y. A
function (or mapping/map) from set X to set Y is a set of ordered pairs (x, y) with x ∈ X and y ∈ Y (so f ⊆
(X × Y)) with the property that for each x ∈ X there is exactly one pair in f whose first component is x. In this
situation, a function f: X → Y, X is the domain of f and Y is the range of f. If (x, y) ∈ f, we write f(x) = y. We
say f maps x to y and y (so f(x)) is the image of x (under f). Functions can be represented by their graph:
an (x, y)-diagram. Let there be the functions f: X → Y and g: Y → Z which gives the composition of the
functions h: X → Z via h(x) = g(f(x)) (= (g ○ f)(x) = g ○ f) for each x ∈ X. The composition of functions is
associative but not commutative. A function f: X → Y is called injective if x ≠ y implies f(x) ≠ f(y), surjective
if for every y ∈ Y there exists an x ∈ X with f(x) = y and bijective if f is injective and surjective. An important
property that allows us to solve counting problems (e.g. knowing |Y| by making a bijection with an easy |X|)
is that if f: X → Y is a bijection, then |X| = |Y|. The properties of functions are as follows: Let f: X → Y and
g: Y → Z be functions. Then: - if f, g are injective then g ○ f is also injective – if f, g are surjective then g ○ f
is also surjective – if f, g are bijective then g ○ f is also a bijection – for any function f: X → Y there exists a
set Z, an injective function h: Z → Y and a surjective function g: X → Z such that f = h ○ g.
The inverse function of f (denoted as f -1) is the function g: Y → X (g(y) = x) with the bijection f: X → Y. A
relation between two sets X and Y is a subset R ⊆ X × Y of the Cartesian product. If X = Y then there is a
relation on X: R ⊆ X × X. For (x, y) ∈ R we say that x and y are related and we write xRy. Every function is
a relation but not every relation is a function. Relations can be illustrated using diagrams, arrows (for (x, y)
∈ R), loops (for x = y) and adjacency matrices. Let X, Y, Z be sets, let R ⊆ X × Y and S ⊆ Y × Z. The
concatenation of R and S is the following relation T ⊆ X × Z: for x ∈ X and z ∈ Z: xTz if and only if there
exists a y ∈ Y with xRy and ySz (thus T = R ○ S). Warning: the relation corresponding to the function g ○ f
is F ○ G. The properties of relations are as follows: A relation R on a set X is reflexive if xRx for all x ∈ X,
irreflexive if there is no x ∈ X with xRx, symmetric if xRy implies yRx for all x, y ∈ X, antisymmetric if xRy
and yRx implies x = y and transative if xRy and yRz implies xRz for all x, y, z ∈ X. For a relation R the
inverse relation R-1 is defined by R-1 = {(y, x) : (x, y) ∈ R}. For a set X the symbol Δx denotes the diagonal
relation (on X): Δx = {(x, x) : x ∈ X} which is also the smallest reflexive relation on X.
1
by Isabel Rutten
, Introduction to Discrete Structures Summary 2019
The characterization of properties is the following proposition: a relation R on a set X is:
- reflexive if and only if Δx ⊆ R – irreflexive if and only if R ∩ Δx = ∅ – symmetric if and only if R = R-1
– antisymmetric if and only if R ∩ R-1 ⊆ Δx – transative if and only if R ○ R ⊆ R.
When we call two objects equivalent (≡) we consider them as equal. A relation R on a set X is an
equivalence relation (≡) if it is reflexive, symmetric and transative. For an equivalence relation R on X
and an element x ∈ X, let R[x] = {y ∈ x : xRy} be the equivalence class of x. Theorem: For every
equivalence relation R on a set X it holds that: - R[x] = ∅ for all x ∈ X – for any two elements x, y ∈ X either
R[x] = R[y] or R[x] ∩ R[y] = ∅ – an equivalence relation is uniquely determined by its equivalence classes.
Note: from here on are the new subjects explained.
3 An ordering relation on a set X is a reflexive, antisymmetric, transative relation on X. A partially ordered
set (poset) is a pair (X,R) where X is a set and R is an ordering relation on X. We often use notation ≤ and
≼. Given an ordering ≼, we can derive the following relations:
- strict inequality: ≺ as a ≺ b if and only if a ≼ b and a =/ b
– inverse ordering: ≽ as a ≽ b if and only if b ≼ a
Proposition: If R is an ordering on a set X and Y ⊆ X, then R ∩ (Y × Y) is an ordering
on Y. In total orderings, also called linear orderings, any two elements are
comparable: for any two elements x and y either x ≼ y or y ≼ x. Examples of partial
orderings are Δx, divisors, inclusion of subsets and domination orderings. Orderings
can be represented using diagrams but not the arrows and loops. Let (X, ≼) be a poset.
An element x ∈ X is an immediate predecessor of element y ∈ X if x ≺ y and there is
no t ∈ X with x ≺ t ≺ y; this is written as x ⊲ y. Theorem: Let (X, ≼) be a finite poset
and let ⊲ be the corresponding “immediate predecessor” relation. Then for any x, y ∈ X, Fig. 1: Example of
x ≺ y holds if and only if there is a chain of elements x1, x2, …, xk ∈ X such that x ⊲ x1 ⊲ Hasse Diagram: the
… ⊲ xk ⊲ y (possibly k = 0, i.e., x … y). From right to left (⇐), this statement is easily divisibility relation
proven. However, from left to right (⇒) we need induction and transitivity. A Hasse
diagram (see fig. 1) consists of points and segments (arrows without arrow heads) and can be used to
draw the “immediate predecessor” relation. Every linear ordering is also a (partial) ordering but not every
(partial) ordering is a linear ordering (e.g. divisibility in N). Let (X, ≼) be an ordered set. An element a ∈ X is
called a minimal element of (X, ≼) if there is no x ∈ X such that x ≺ a. A maximal element a is defined
analogously (there is no x ≻ a). Theorem: Every finite (so not infinite!) partially
ordered set (X, ≼), with |X| ≥ 1, has at least one minimal element. This can be
proven by checking for every element or by contradiction over distance between
elements. Theorem: Let (X, ≼) be a finite partially ordered set. Then there exists
a linear ordering ≤ of X such that x ≼ y implies x ≺ y. In other words: each partial
ordering can be extended to a linear ordering. This can be proven by induction
on n = |X|. Let (X, ≼) be an ordered set. An element a ∈ X is called a smallest Fig. 2: An embedding
element of (X, ≼) if for every x ∈ X we have x ≼ a. A largest element is
defined analogously (x ≽ a). Note: smallest ≠ minimal and largest ≠
maximal! Let (X, ≼) and (X’, ≼’) be ordered sets. A mapping f: X → X’ is
called an embedding of (X, ≼) into (X’, ≼’) (see fig. 2) if the following
conditions hold: - f is injective – f(x) ≼’ f(y) is and only if x ≼ y.
If an embedding is surjective (and thus bijective), then it is an
isomorphism. Theorem: For every ordered set (X, ≼) there exists an embedding into the ordered Fig. 3: Bn
set (2x, ⊆). This is proven by checking the two conditions of an embedding. The ordered sets (2x,
⊆) contain a copy of every ordered set. For X = {1, 2, …, n} the set (2x, ⊆) is often denoted by Bn (see fig.
3). Let P = (X, ≼) be a poset. Elements x, y are called comparable if either x ≼ y or y ≼ x. Elements x, y
with neither x ≼ y nor y ≼ x are called incomparable. A set A ⊆ X is called a chain in P if every two of its
elements are comparable (in P). We use 𝜔(P) = max{|A| : A chain in P} to denote the maximum size of a
chain in P. A set A ⊆ X is called independent in P if any two of its elements are incomparable.
Independent sets are also called antichains. The set of all minimal elements in P is independent.
2
by Isabel Rutten
