Section 1 - Fundamental Concepts

Question 1

Cardinality

Answer 1

The number of elements in a set X if X is finite. Denoted |X|

|X| = infinity if X is not finite

Question 2

Subset

Answer 2

If X and Y are sets, then X is said to be a subset of Y if every element of X is an element of Y

Question 3

Cartesian Product

Answer 3

X x Y = {(x, y) | x∈X and y∈Y}

Question 4

Image

Answer 4

If f: X -> Y is a function, its image is: Image(f) = {y∈Y | ∃x∈X such that f(x) = y}

Question 5

Identity Function

Answer 5

If X is a non-empty set, then the identity function on X is the function: 1: X -> X

Question 6

Injectivity

Answer 6

If ∀x1, x2 ∈ X, the equality f(x1) = f(x2) implies that x1 = x2

Question 7

Surjectivity

Answer 7

If y∈Y, ∃x∈X such that f(x) = y

Question 8

Bijectivity

Answer 8

A function that is injective and surjective. ∀y∈Y, ∃x∈X such that f(x) = y

Question 9

Equivalence Relation

Answer 9

A binary relation is called an equivalence relation if all of the following hold:
- Reflexivity
- Symmetry
- Transitivity

Question 10

Reflexivity

Answer 10

∀a∈A, a~a

Question 11

Symmetry

Answer 11

∀a,b∈A, if a~b, then b~a

Question 12

Transitivity

Answer 12

∀a,b,c∈A, if a~b and b~c, then a~c

Question 13

Equivalence Classes

Answer 13

If ~ is an equivalence relation on a set A, then for a∈A, the equivalence class of a is the set: [a] = {b∈A | b~a}