# 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

• a ∈ A means that ‘a’ is an element of A (A is the set)
• sets are equal if and only if they have the same elements
• order and repetition don’t matter for sets
• note that a set doesn’t equal its elements, i.e. {a} ≠ a

### Cardinality

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

• cardinality is denoted by |A|

### Empty set

• the empty set is denoted by {} or ∅

### Universal set

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

• denoted by U
• e.g. U might be ℝ in Calculus, or ℂ in algebra

### Basic notation

The following format is used to indicate a set

 S = { x ∈ A … }

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

• when solving a problem using Venn diagrams, you must state what each of the subsets means before you draw the diagram
• note that often you can use inclusion-exclusion principle (covered later) rather than Venn Diagrams

### Subset

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

• A ⊆ B indicates that A is a subset of the set B
• A is the proper subset of B, A ⊂ B, if A ⊆ B but A ≠ B

The following properties are useful:

• if A = B then A ⊆ B and B ⊆ A
• if A ⊂ B then A ⊆ B
• if A ⊆ B and B ⊆ A then A = B (this is used to prove that two sets are equal)
• A is a proper subset of B if it is a subset of B and B has at least one element that is not also in A

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.

• given a set A, then power set of A is the set of all of the subsets of the set S
• the power set of S is denoted by P(S)

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.

• denoted by AB
•  A ∪ B = { x x ∈ A or x ∈ B }

#### Intersection

the set containing elements that in both A and B

• AB

#### 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.

• Note that ABBA
• Note that ABc = A – 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.

• Note that A2 = A × A

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.

• recall from Calculus that increasing functions (ƒ′(x) > 0) are one-to-one and that the horizontal line test can be used

### 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)).

• for proofs involving composition you will possibly need to “take f (or g) of both sides”

### 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)

• g is called the inverse function of ƒ, written as ƒ–1

### Composition of a function and its inverse

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

• ƒ-1 ∘ ƒ is the function i—called the identity function. It does nothing.

### 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 ℤ.

• more or less a list
• order and repetition important
• finite sequence is called a string

### 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

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

• too confusing and awkward to write in HTML; see your course notes or textbook

### Telescoping sums

• write out sums in full so that you can identify which of the terms cancel and then you can easily add the rest
• i.e. manually expand then see what you can get rid of
• watch out for negatives
• try to make the expression being summed the same in the two sequences

∏ means product