Definitions S1

Question 1

Empty Set

Answer 1

The unique set that has no elements at all.
Denoted as: ∅
Aka: {x ∈ Z+ | x < 0} = ∅.

Question 2

Equal Sets

Answer 2

2 sets (A + B) are equal (A=B) if they have precisely the same elements.
i.e. A = B means x ∈ A ⇒ x ∈ B, and vice versa.

Question 3

Subset

Answer 3

For sets A and B:
A is a subset of B when every element of A is an element of B.
denoted: A ⊆ B
i.e. x ∈ A ⇒ x ∈ B

Question 4

Proper subset

Answer 4

For sets A and B:
when A is not equal to B, A is a proper subset of B
denoted: A ⊊ B

Question 5

Cardinality

Answer 5

For a finite set X:
cardinality is the number of elements in the set.
denoted: |X|

Question 6

Intersection

Answer 6

For 2 sets A and B:
intersection = the set elements which lie in both A and B.
denoted: A ∩ B
Mathematically: A ∩ B = {x | x ∈ A and x ∈ B}.

Question 7

Disjoint

Answer 7

For sets A and B:
they’re disjoint if they share no elements (A ∩ B = ∅)

Question 8

Union

Answer 8

For sets A and B:
union is the set of elements which lie in A or in B.
denoted: A ∪ B
Mathematically: A ∪ B = {x | x ∈ A or x ∈ B}

Question 9

difference

Answer 9

For 2 sets A and B:
the difference of A and B: the set of elements that lie in A but not B.
denoted: A \ B
Mathematically: A \ B = {x | x ∈ A and x ∉ B}

Question 10

Universal set

Answer 10

a set which has elements of all the related sets, without any repetition of elements

Question 11

Complement

Answer 11

Let A be a set with universal set U:
Complement would be everything outside A.
denoted: Aᶜ
Mathematically: Aᶜ=U\A={x|x ∈ U and x ∉ A}

Question 12

ordered pair

Answer 12

a list of two things enclosed in parentheses and separated by a comma.
i.e. (x,y)

Question 13

Cartesian Product

Answer 13

Given sets X and Y:
Cartesian product is the set of all ordered pairs (x,y) where x ∈ X and y ∈ Y.
denoted: X * Y
Mathematically: X * Y = {(x,y)|x ∈ X, y ∈ Y}

Question 14

Relation

Answer 14

On set X is a subset of X * X
denoted: ~
Mathematically: x ~ y when (x,y) ∈ ~

Question 15

congruence modulo n

Answer 15

a type of relation on Z for each integer n ≠ 0
2 integers are congruent modulo n IOI x - y is divisible by n.
denoted: x ≡ y mod n

Question 16

Reflexive

Answer 16

(suppose ~ is a relation on set X)
~ is reflexive if x ~ x for all x ∈ X

Question 17

Symmetric

Answer 17

(suppose ~ is a relation on set X)
~ is symmetric if x ~ y implies that y ~ x for every x,y ∈ X

Question 18

transitive

Answer 18

(suppose ~ is a relation on set X)
~ is transitive if x ~ y and y ~ z implies x ~ z for all x,y,z ∈ X

Question 19

equivalence relation

Answer 19

a ~ on X is an equivalence relation if it’s reflexive, symmetric and transitive

Question 20

equivalence class

Answer 20

(an equivalence relation on sets)
let ~ be an equivalence relation on X and x ∈ X.
equivalence class of x is:
{ a ∈ X | a ~ x}
denoted: [x]

Question 21

partition

Answer 21

of a set X partition is a set of non-empty subsets of X
s.t. the union of all the subsets equals X
+ the intersection of any 2 different subsets is ∅ (mutually or pairwise disjoint)

Question 22

statement

Answer 22

a mathematical expression that is either definitely true or definitely false

Question 23

logical equivalence

Answer 23

2 statements are logically equivalent if their truth values match up line-for-line in a truth table

Question 24

Fibonacci sequence

Question 25

prime number

Answer 25

a number greater than 1 which is only divisible by 1 and itself

Question 26

rational number

Answer 26

if it can be written as a fraction a/b where a, b ∈ Z

Question 27

function

Answer 27

the assignment of a unique element in one set to each element of a second set.

Question 28

domain and codomain

Answer 28

input = domain output = codomain

Question 29

image of a function

Answer 29

let f: X -> Y be a function: im f = { f(x)|x ∈ X} NB: im f ⊆ Y

Question 30

equal function

Answer 30

Two functions ( f & g) are equal if they have the same domain and codomain and f(x) = g(x) for all x ∈ X

Question 31

identity function

Answer 31

for any set X, the id: X -> X is id (x) = x

Question 32

define composition for functions: f: X -> Y g: Y -> Z

Answer 32

g ◦ f : X -> Z g ◦ f(x) = g ( f(x))

Question 33

for the function f: X -> Y define injective, surjective + Bijective

Answer 33

f is: injective (one-to-one) if (for all a,b ∈ X) f (a) = f (b) then a = b surjective if (for all y ∈ Y) there exists at least one x ∈ X such f (x) = y bijective if f is surjective + injective

Question 34

same size/cardinality of sets

Answer 34

if there is a bijection between them

Question 35

for the function: f: X -> Y define: left inverse, right inverse and inverse

Answer 35

left inverse: a function g: Y -> X s.t: g ◦ f = id_X right inverse: a function h: Y -> X s.t.: f ◦ h = id_Y inverse: a function k: Y -> X which is both a left and right inverse = f is invertible

Question 36

permutation

Answer 36

let X be a set: a permutation is a bijection X -> X

Question 37

powers of permutations

Answer 37

if f ∈ S_n is a permutation, then f^2 = f f = f ◦ f

Question 38

order of a permutation

Answer 38

notation: o (σ) the smallest +ve integer n ∈ N s.t. σ^n = id

Question 39

m-cycle

Answer 39

A permutation written as (a₀, a₁, ..., aₘ₋₁) where: - m > 0 and all aᵢ are distinct integers. - Each element maps to the next: aᵢ → aᵢ₊₁ for i < m–1, and aₘ₋₁ → a₀. - All other elements not in the cycle map to themselves. the cycle has length m.

Question 40

A disjoint collection of cycles

Answer 40

if they share no elements

Question 41

transposition

Answer 41

a 2-cycle. i.e. (2,3)

Question 42

adjacent transposition

Answer 42

a permutation in the form (i, i + 1)

Question 43

odd permutation

Answer 43

if it may be written as an odd number of transpositions

Question 44

even permutation

Answer 44

if it can be written as an even number of permutations

Question 45

sign of a permutation

Answer 45

1 if its even and -1 if its odd denoted: sgn (permutation)