2 Sets and Functions

Question 1

Definition 2.1:
Sets

Answer 1

A collection of things, called its elements. 𝑥∈𝐴 := 𝑥 is an element of the set 𝐴.

Question 2

Definition 2.5:
Subsets

Answer 2

Let 𝐴 and 𝐵 be sets.
- 𝐴 is a subset of 𝐵 (𝐴⊆𝐵) if every element of 𝐴 also lies in 𝐵.
- 𝐴 is empty if 𝐴 has no elements, i.e. 𝑎∈𝐴 is never true.

Question 3

Lemma 2.8

There can only be one

Answer 3

If 𝐴 is empty, then 𝐴⊆𝐵 for any set 𝐵. In particular, there is precisely one empty set, denoted ∅.

Question 4

Definition 2.9:
Power set

Answer 4

For any set 𝐴, the power set, denoted P(𝐴), is the set of all subsets of 𝐴. Thus 𝐵∈P(𝐴)⟺𝐵⊆𝐴.
i.e. B an element of P(A) iff B is a subset of A

Question 5

Definition 2.12:
Cardinality of a finite set

Answer 5

Let 𝐴 be a set containing only finitely many elements. The cardinality of 𝐴, denoted |𝐴|, is the number of elements in 𝐴.

Question 6

Definition 2.17:
Unions, intersections and differences

Answer 6

Given sets 𝐴 and 𝐵
- union 𝐴∪𝐵 = {𝑥∣𝑥∈𝐴 or 𝑥∈𝐵};
- intersection 𝐴∩𝐵 = {𝑥∣𝑥∈𝐴 and 𝑥∈𝐵} = {𝑥∈𝐴∣𝑥∈𝐵} = {𝑥∈𝐵∣𝑥∈𝐴}
- difference 𝐴∖𝐵={𝑥∈𝐴∣𝑥∉𝐵}
- In the special case where 𝐵⊆𝐴, the difference 𝐴∖𝐵 is called the complement of 𝐵 in 𝐴.

Question 7

Definition 2.20
Cartesian product

Answer 7

The Cartesian product of sets 𝐴1,…,𝐴𝑛 for some 𝑛≥1 is 𝐴1×⋯×𝐴𝑛 = { (𝑎1,…,𝑎𝑛) ∣ 𝑎𝑖∈𝐴𝑖 for 𝑖=1,…,𝑛 }.

E.g. For 𝐴={1,3} and 𝐵={4,5},
𝐴×𝐵={(1,4),(1,5),(3,4),(3,5)}.

Question 8

Definition 2.20
Cartesian powers

Answer 8

The Cartesian powers of a set 𝐴 are defined to be 𝐴^𝑛 = { (𝑎1,…,𝑎𝑛) ∣ 𝑎𝑖∈𝐴 for 𝑖=1,…,𝑛 }.

E.g. For 𝐴={1,3},
𝐴^2={(1,1),(1,3),(3,1),(3,3)}.

Question 9

Definition 2.23
Function

Answer 9

Given sets 𝐴 and 𝐵, a function (also called a map) 𝑓:𝐴→𝐵 is a rule that assigns to every element 𝑎∈𝐴, a unique element 𝑓(𝑎)∈𝐵.
We call 𝐴 the domain of 𝑓 and 𝐵 the codomain of 𝑓.

Question 10

Definition 2.25:
Graph of a function

Answer 10

Given a function 𝑓:𝐴→𝐵, the graph of 𝑓 is the subset of 𝐴×𝐵 given by Graph(𝑓) = { (𝑎,𝑏)∈𝐴×𝐵 ∣ 𝑏=𝑓(𝑎) }.

Question 11

Definition 2.28:
Identity map

Answer 11

Let 𝐴 be a be set.
The identity map id𝐴 is the map whose domain and codomain both equal 𝐴, and where id𝐴(𝑎)=𝑎 for all 𝑎∈𝐴.

Question 12

Definition 2.28:
Composition

Answer 12

Let 𝐴,𝐵,𝐶 be sets.
Given functions 𝑓:𝐴→𝐵 and 𝑔:𝐵→𝐶, their composition (𝑔∘𝑓):𝐴→𝐶, which we read as ‘𝑔 follows 𝑓’, is the function given by (𝑔∘𝑓)(𝑎)=𝑔(𝑓(𝑎)) for 𝑎∈𝐴.
We do not consider 𝑔∘𝑓, unless the codomain of 𝑓 and the domain of 𝑔 coincide.

Question 13

Definition 2.30:
Function spaces

Answer 13

Let 𝐴 and 𝐵 be sets. The set of functions from 𝐴 to 𝐵 is denoted 𝐵^𝐴 = {functions 𝐴→𝐵}.
Equivalently, 𝐵^𝐴 = {𝐺⊆𝐴×𝐵 ∣ 𝐺 is the graph of a function 𝑓:𝐴→𝐵}

The vertical line test (check if it is a function).

Question 14

Definition 2.33:
Image of a function

Answer 14

Let 𝑓:𝐴→𝐵 be a function. The image of 𝑓, denoted Im(𝑓), is the subset of 𝐵 given by
Im(𝑓) = {𝑏∈𝐵 ∣ 𝑏=𝑓(𝑎) for some 𝑎∈𝐴} = {𝑓(𝑎) ∣ 𝑎∈𝐴}.

Question 15

Definition 2.34:
Injective

Answer 15

If whenever 𝑎,𝑎′∈𝐴 satisfy 𝑓(𝑎)=𝑓(𝑎′), it follows that 𝑎=𝑎′.

If there is a solution, then it is unique.

For 𝑓:ℝ→ℝ, horizontal line cuts graph of 𝑓 in at most 1 point.

Question 16

Definition 2.34:
Surjective

Answer 16

If for all 𝑏∈𝐵, there exists 𝑎∈𝐴 such that 𝑏=𝑓(𝑎). i.e. Im(𝑓)=𝐵.

Every 𝑏 can be written as a function of 𝑎.

Question 17

Definition 2.34:
Bijective

Answer 17

If 𝑓 is both injective and surjective.

A unique solution exists for all 𝑏∈𝐵.

For 𝑓:ℝ→ℝ, horizontal line cuts graph of 𝑓 in exactly 1 point.

Question 18

Definition 2.41:
Left-inverse

Answer 18

Let 𝑓:𝐴→𝐵 and 𝑔:𝐵→𝐴 be functions.
Then 𝑔 is a left inverse of 𝑓 if 𝑔∘𝑓=id𝐴.

Question 19

Definition 2.41:
Right-inverse

Answer 19

Let 𝑓:𝐴→𝐵 and 𝑔:𝐵→𝐴 be functions.
Then 𝑔 is a right inverse of 𝑓 if 𝑓∘𝑔=id𝐵.

Question 20

Definition 2.41:
Two-sided inverse

Answer 20

Let 𝑓:𝐴→𝐵 and 𝑔:𝐵→𝐴 be functions.
Then 𝑔 is a two-sided inverse of 𝑓 if 𝑔∘𝑓=id𝐴 and 𝑓∘𝑔=id𝐵.

Question 21

Definition 2.53:
Finite set

Answer 21

A set 𝐴 is finite if 𝐴=∅ or if there exists 𝑛∈ℕ and a bijective map 𝑓:{1,…,𝑛}→𝐴.

The cardinality of 𝐴 is defined to be 0 when 𝐴=∅, and it is |𝐴|:=𝑛 when there is a bijective map 𝑓:{1,…,𝑛}→𝐴.

Question 22

Definition 2.61:
Countable sets

Answer 22

The set 𝐴 is countably infinite if there is a bijection 𝑓:ℕ→𝐴.
𝐴 is countable if 𝐴 is finite or countably infinite.

Question 23

Definition 2.62 preface:
Binary relation

Answer 23

A binary relation ∼ on a set 𝐴 is a property that any given pair of elements of 𝐴 (𝑎,𝑏∈𝐴) either satisfy (𝑎∼𝑏), or they do not satisfy (𝑎≁𝑏).

A binary relation ∼ is determined completely by the set {(𝑎,𝑏)∈𝐴×𝐴∣𝑎∼𝑏} of pairs that satisfy the relation.

A binary relation on a set 𝐴 is a subset of 𝐴×𝐴 (comprising the pairs (𝑎,𝑏) for which 𝑎∼𝑏).

Question 24

Definition 2.62:
Equivalence relation

Answer 24

A binary relation ∼ on a non-empty set 𝐴 is an equivalence relation if it is reflexive (R), symmetric (S) and transitive (T).

Question 25

Definition 2.62: **Reflexive**

Answer 25

∼ is reflexive if for 𝑎∈𝐴, we have 𝑓(𝑎)=𝑓(𝑎), so 𝑎∼𝑎

Question 26

Definition 2.62: **Symmetric**

Answer 26

∼ is symmetric if: 𝑎∼𝑏 ⇒ 𝑏∼𝑎 for all 𝑎,𝑏∈𝐴. | for 𝑎,𝑏∈𝐴, if 𝑓(𝑎)=𝑓(𝑏), then 𝑓(𝑏)=𝑓(𝑎).

Question 27

Definition 2.62: **Transitive**

Answer 27

∼ is transitive if: (𝑎∼𝑏 and 𝑏∼𝑐) ⇒ 𝑎∼𝑐 for all 𝑎,𝑏,𝑐∈𝐴.

Question 28

Definition 2.64: **Equivalence classes**

Answer 28

Let ∼ be an equivalence relation on 𝐴. For each 𝑎∈𝐴, the equivalence class of 𝑎 is **[𝑎] = { 𝑥∈𝐴 ∣ 𝑥∼𝑎 }.** Let 𝐴/∼ = { [𝑎] ∣ 𝑎∈𝐴 } denote the set of equivalence classes. | [𝑎] is the set of elements in 𝐴 where 𝑥∼𝑎.

Question 29

Definition 2.67: **Partition of a set**

Answer 29

A partition of a set 𝐴 is a set of pairwise disjoint non-empty subsets of 𝐴 whose union is 𝐴. i.e. a set {𝐴_𝑖}_(𝑖∈𝐼) of non-empty subsets 𝐴_𝑖⊆𝐴 such that 𝐴=⋃_(𝑖∈𝐼)𝐴_𝑖 and (𝐴_𝑖)∩(𝐴_𝑗)=∅ for all 𝑖,𝑗∈𝐼 with 𝑖≠𝑗.

Question 30

Definition 2.71: **The set of permutations on 𝑛 letters**

Answer 30

For 𝑛∈ℕ, a bijective map 𝜎:{1,…,𝑛}→{1,…,𝑛} is called a permutation on 𝑛 letters. Let 𝑆_𝑛 denote the set of all permutations on 𝑛 letters.

Question 31

Definition 2.75: **Cyclic permutations**

Answer 31

For 𝑚<𝑛, an 𝑚-cycle in 𝑆𝑛 is a permutation 𝜎∈𝑆𝑛 that cyclically permutes 𝑚 elements of {1,…,𝑛} and fixes the remaining elements. We write 𝜎 = ( 𝑎,𝜎(𝑎),…,𝜎^(𝑚−1)(𝑎) ).

Question 32

Definition 2.75: **Transpositions**

Answer 32

A 2-cycle (permutation).

Question 33

Definition 2.78: **Even and odd permutations**

Answer 33

A permutation is [odd/even] if it can be written as the composition of an [odd/even] number of transpositions.

Question 34

Definition 2.79: **Sign of a permutation**

Answer 34

Let sign:𝑆𝑛→{1,−1} be the function defined by sending a permutation 𝜎 whose 𝑘 orbits are cycles of lengths 𝑚1,…,𝑚𝑘 to sign(𝜎) = (−1)^[ (𝑚1−1)+(𝑚2−1)+⋯+(𝑚𝑘−1) ].