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, X ∈ P(S) and X ⊆ S mean the same thing

Cardinality of a power set

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

Or, in English, the size of the power set is equal to 2ⁿ 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 A ∪ B

• A ∪ B = { x

  x ∈ A or x ∈ B }

Intersection

the set containing elements that in both A and B

• A ∩ 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, A – B, is the set containing elements in A but not in B.

• Note that A – B ≠ B – A
• Note that A ∩ B^c = A – B

Complement

The complement of A is A^c. A^c = U – A 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: (A^c)^c = A
6. De Morgan’s laws: (A ∪ B)^c = A^c ∩ B^c and (A ∩ B )^c = A^c ∪ B^c
7. Identity laws: A ∪ ∅ = A and A ∩ U = A
8. Domination laws: A ∪ U = U and A ∩ ∅ = ∅
9. Intersection and union with complement: A ∩ A^c = ∅ and A ∪ A^c = U
10. Alternative representation for set difference: A – B = A ∩ B^c

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 A₁, A₂, …, A_n are pairwise disjoint if and only if A_i ∩ A_j = ∅ whenever i ≠ j

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

Partition

A set of non-empty sets { A₁, A₂, …, A_n } is a partition of a set A if and only if

1. A = A₁ ∪ A₂ ∪ … ∪ A_n
2. A₁, A₂, …, A_n 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 A² = 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 ƒ(x₁) = ƒ(x₂), then x₁ = x₂.

• 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) = x²

If A = { x ∈ ℝ

2 < x < 3 } then

ƒ(A) = { ƒ(x)

x ∈ A }

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

∴ ƒ(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 ∑^b_a, 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×r^j) = a(r^{n + 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) j² = (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 × a_k = c × (∑ a_k)

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