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

Ais a subset ofBif 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

- Show that any element of A is also an element of B
- “Let
*x*∈ LHS” and work to show that x ∈ RHS also. - “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

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

#### Proving A = B

- 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| =nthen |P(A) | = 2^{n}

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

### Set algebra

#### Union

The union of the sets

AandBis the set that contains the elements that are either inAor inB, 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

AandB,A–B, is the set containing elements inAbut not inB.

- Note that
*A*–*B*≠*B*–*A* - Note that
*A*∩*B*^{c}= A – B

#### Complement

The complement of A is A

^{c}. A^{c}=U–Ais the set of elements inUbut not inA.

### Laws of set algebra

- Commutative laws: A ∪ B = B ∪ A and A ∩ B = B ∩ A
- Associative laws: A ∪ (B ∪ C) = (A ∪ B) ∪ C and A ∩ (B ∩ C) = (A ∩ B) ∩ C
- Distribute laws: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
- Idempotent laws: A ∪ A = A and A ∩ A = A
- Double complement laws: (A
^{c})^{c}= A - De Morgan’s laws: (A ∪ B)
^{c}= A^{c}∩ B^{c}and (A ∩ B )^{c}= A^{c}∪ B^{c} - Identity laws: A ∪ ∅ = A and A ∩
*U*= A - Domination laws: A ∪
*U*=*U*and A ∩ ∅ = ∅ - Intersection and union with complement: A ∩ A
^{c}= ∅ and A ∪ A^{c}=*U* - 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

_{1}, A_{2}, …, 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

_{1}, A_{2}, …, A_{n}} is a partition of a setAif and only if 1.A= A_{1}∪ A_{2}∪ … ∪ A_{n}2. A_{1}, A_{2}, …, 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
^{2}= 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 isexactly oneordered pair (x,y) ∈ ƒ.

Takeaways from that definition’s mess:

- a function is a set.
- 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 tox. Written as ⌊x⌋.

Ceiling: the smallest integer that is greater than or equal tox. 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

yin 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*_{1}) = ƒ(*x*_{2}), then *x*_{1} = *x*_{2}.

- 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 withy= ƒ(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 ƒ andg, ƒ ∘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 elementx∈ X such thaty= ƒ(x). i.e.,g(y) =xandy= ƒ(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 allxthat produce elements of B.

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

Let ƒ : ℝ → ℝ, ƒ(

x) =x^{2}

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

ƒ(A) = { ƒ( x)x∈ A }(Note: ƒ(

x) =^{2},y=^{2})

∴ ƒ(A) = { x^{2}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 ≤ x^{2}< 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

^{2}= (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

not25 × 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**