Matthew Palmer — Notes

Discrete Maths (MATH1081): Section 1 — Sets, Functions, and Sequences

Sets

a set is a collection of objects, which are called the ‘elements’ of the set

Cardinality

the cardinality of a set is the number of elements in the set

Empty set

Universal set

the universal set is the set containing all elements of all sets needed to discuss a topic

Basic notation

The following format is used to indicate a set

S = { xA … }

which is read as “x is an element of A (x ∈ A) such that (|) some property is true ().

For example, S = { x ∈ ℤ | –2 < x < 5 } which is equal to { –1, 0, 1, 2, 3, 4 }.

Venn diagrams

Subset

A is a subset of B if and only if every element of A is also an element of B

The following properties are useful:

The subset relationship only exists between two sets, i.e. for A ⊆ B, A must be a set.

Proving A is a subset of B

  1. Show that any element of A is also an element of B
  2. “Let x ∈ LHS” and work to show that x ∈ RHS also.
  3. “Thus we have shown that any element of the LHS is also an element of the RHS, therefore LHS ⊆ RHS”

Proving A is a proper subset of B

  1. Prove A ⊆ B as above
  2. Then find one or more example of an element that is in B but not in A

Proving A = B

  1. Show A ⊆ B and B ⊆ A, i.e. two iterations of the process above

Power set

The power set of a set is the set of all subsets of the set.

For example,

P({ 0, 1, 2 }) = {
                    ∅,
                    { 0 }, { 1 }, { 2 },
                    { 0, 1 }, { 1, 2 },
                    { 0, 1, 2 },
                 }

Note: For a set X, XP(S) and XS mean the same thing

Cardinality of a power set

If | A | = n then | P(A) | = 2n

Or, in English, the size of the power set is equal to 2n where n is the number of elements in the set.

Set algebra

Union

The union of the sets A and B is the set that contains the elements that are either in A or in B, or in both.

Intersection

the set containing elements that in both A and B

Disjoint sets

two sets are disjoint if their intersection is the empty set (i.e. they have no elements in common)

Set difference

The difference of A and B, AB, is the set containing elements in A but not in B.

Complement

The complement of A is Ac. Ac = UA is the set of elements in U but not in A.

Laws of set algebra

  1. Commutative laws: A ∪ B = B ∪ A and A ∩ B = B ∩ A
  2. Associative laws: A ∪ (B ∪ C) = (A ∪ B) ∪ C and A ∩ (B ∩ C) = (A ∩ B) ∩ C
  3. Distribute laws: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
  4. Idempotent laws: A ∪ A = A and A ∩ A = A
  5. Double complement laws: (Ac)c = A
  6. De Morgan’s laws: (A ∪ B)c = Ac ∩ Bc and (A ∩ B )c = Ac ∪ Bc
  7. Identity laws: A ∪ ∅ = A and A ∩ U = A
  8. Domination laws: A ∪ U = U and A ∩ ∅ = ∅
  9. Intersection and union with complement: A ∩ Ac = ∅ and A ∪ Ac = U
  10. Alternative representation for set difference: A – B = A ∩ Bc

Keep in mind: the property of duality (‘dual’) means that you can swap ∩ and ∪, and swap ∅ and U. This helps you to remember less, which is good.

Generalised union and intersection

See your textbook or course notes for this stuff; it’s hard to write in HTML.

Disjoint

As above,

two sets are disjoint if their intersection is the empty set (i.e. they have no elements in common)

Pairwise disjoint

Sets A1, A2, …, An are pairwise disjoint if and only if Ai ∩ Aj = ∅ whenever i ≠ j

(i.e. any 2 sets have no overlapping elements)

Partition

A set of non-empty sets { A1, A2, …, An } is a partition of a set A if and only if 1. A = A1 ∪ A2 ∪ … ∪ An 2. A1, A2, …, An are pairwise disjoint

(i.e. all of the sets combine to produce the whole, but none of the sets have the same elements)

Cartesian product

A × B is the cartesian product is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.

For example,

let A = { 1, 2 }
let B = { 2, 3 }
then
A × B = { (1, 2), (1, 3), (2, 2), (2, 3) }

We can also think of these as xy co-ordinate pairs, and they can be sketched on a number plane as such.

Functions

A function ƒ from a set X to a set Y is a subset of X × Y with the property that for each x ∈ X, there is exactly one ordered pair (x, y) ∈ ƒ.

Takeaways from that definition’s mess:

  1. a function is a set.
  2. each x value can only be paired with one y value.

The function

ƒ : X → Y

has X as the domain and Y as the codomain (the codomain is the set containing all of the y values that could occur).

Floor and ceiling

For any x ∈ ℝ,

Floor: the largest integer that is less than or equal to x. Written as ⌊x⌋.


Ceiling: the smallest integer that is greater than or equal to x. Written as ⌈x⌉.

For example, ⌊π⌋ = 3, ⌈π⌉ = 4

Range

The range of a function ƒ : X → Y is the set of all y ∈ Y such that there is an ordered pair (x, y) in ƒ. That is, { y ∈ Y | (x, y) ∈ ƒ for some x ∈ X }

More or less, the set of all the y values that actually occur.

One-to-one

A function ƒ is one-to-one (or injective) if and only if for each y in the codomain there is only one (i.e. one or none at all) ordered pair (x, y) in ƒ.

i.e., ƒ is one-to-one means that if ƒ(x1) = ƒ(x2), then x1 = x2.

Onto

A function ƒ : X → Y is onto (or surjective) if and only if for every element y ∈ Y there is an element x ∈ X with y = ƒ(x).

i.e., a function is onto if its range equals its codomain.

Bijection

A function is a bijection if it is both one-to-one and onto.

Composition of functions

Let g : X → Y and ƒ : Y → Z. Then the composition of ƒ and g, ƒ ∘ g, is the function from X to Z defined by (ƒ ∘ g)(x) = ƒ(g(x)).

Inverse functions

Let ƒ : X → Y. If ƒ is a bijection, then there is a function g : Y → X which, given any y ∈ Y, g(y) is the element x ∈ X such that y = ƒ(x). i.e., g(y) = x and y = ƒ(x)

Composition of a function and its inverse

If ƒ “does something” to a variable, then ƒ-1 “undoes” it.

Applying a function to many elements

Let ƒ be a function from X to Y. If A ⊆ X, then ƒ(A) = { ƒ(x) x ∈ A}
If B ⊆ Y, then ƒ–1(B) = { x ∈ X ƒ(x) ∈ B}, i.e. the set of all x that produce elements of B.

This is kind of hard to understand. Consider an example.

Let ƒ : ℝ → ℝ, ƒ(x) = x2

If A = { x ∈ ℝ 2 < x < 3 } then
ƒ(A) = { ƒ(x) x ∈ A }

(Note: ƒ(x) = 2, y = 2)

∴ ƒ(A) = { x2 2 < x < 3}
  = { y ∈ ℝ 4 < y < 9 }

And the inverse,

If B = { y ∈ ℝ 1 ≤ y < 16 } then
ƒ–1(B) = { x ∈ X ƒ(x) ∈ B}

and so

ƒ–1(B) = { x ∈ ℝ 1 ≤ x2 < 16}
  = { x ∈ ℝ –4 < x ≤ –1 } ∪ { x ∈ ℝ 1 ≤ x < 4 }

Sequences and summations

Note: For these sections, I write ∑(a, b) ƒ(x) for a sum from a to b, because writing it out properly is almost impossible. The best approximation is ∑ba, which doesn’t look great.

Sequence

A sequence is a function with domain a subset of ℤ.

Basic sums

Memorise these:

∑(j = 0, n) a×rj) = a(rn + 1 – 1) ÷ (r – 1)

∑(j = 1, n) 1 = 1 + 1 + … + 1 [n times] = n

∑(j = 0, n) j = (1/2) × n(n + 1)

∑(j = 1, n) j2 = (1/6) × n × (n + 1) × (2n + 1)

Note: for these last two, j = 0 and j = 1 give the same result.

Also note,

25 × ∑(k = 1, 12) 1 = 25 × 12 not 25 × 1

Addition of sums

Without adding excessive notation, the following are true

∑ (a + b) = ∑ a + ∑ b

∑ (a – b) = ∑ a – ∑ b

Multiplication by a constant

∑ c × ak = c × (∑ ak)

i.e., we can pull out a constant factor

Shifting the index of summation

Telescoping sums

∏ means product