Functions

Question 1

Set/Object

Answer 1

A set is a collection of objects, the objects in a set are called elements.

Question 2

Natural Numbers

Answer 2

{1, 2, 3, 4, . . .}

Question 3

Integers

Answer 3

{. . . , −2, −1, 0, 1, 2, 3, . . .}

Question 4

Rational Numbers

Answer 4

a/b where a and b are integers and b is non zero

Question 5

Real Numbers

Answer 5

e, pi ect

Question 6

Complex Numbers

Answer 6

a + bi where a and b are real numbers

Question 7

Empty Set

Answer 7

A set with no object within

Question 8

Sets A, B are equal if…

Answer 8

if a is in A then a is in B AND if b is in B then b is in A

Question 9

does order of elements in a set matter?

Answer 9

no

Question 10

is the empty set unique?

Answer 10

yes, for all empty sets share the same elements completely

Question 10

does a set with repeated elements differ from one without?

Answer 10

no

Question 11

can a set have a set inside of it?

Answer 11

yes

Question 12

conclusion given from the fact that sets A = B and B = C

Answer 12

A = C , as all elements in A are in B which are in C, so it remains that the elements within all of them are identical, so the sets are identical

Question 13

B subset A

Answer 13

every element of A is an element of B -> if a is in A then a is in B

Question 14

The union A ∪ B

Answer 14

{x : x ∈ A or x ∈ B} meaning elements x such that x is an element of A or an element of B

Question 15

The power set P(A) of A

Answer 15

the set of all subsets of A

Question 15

The intersection A ∩ B

Answer 15

{x : x ∈ A and x ∈ B} meaning elements x such that x is an element of A and an element of B

Question 15

set difference A \ B

Answer 15

A \ B = {a ∈ A : a̸ ∈ B} meaning the set containing elements a that are in set A but not set B

Question 16

(De Morgan’s Laws). Let A, B, C be sets. Then… (intersect)

Answer 16

A \ (B ∩ C) = (A \ B) ∪ (A \ C) meaning the set A - the intersection of B and C is equal to the union of sets A-B and A-C

Question 16

(De Morgan’s Laws). Let A, B, C be sets. Then… (union)

Answer 16

A \ (B ∪ C) = (A \ B) ∩ (A \ C) meaning the set A minus the unions of set B and C is equal to the intersection of sets A-B and A-C

Question 17

direct product (or cartesian product) A × B

Answer 17

A × B = {(a, b) : a ∈ A, b ∈ B} meaning the set of ordered pairs containing first element a from A and b from B

Question 18

If A, B are sets then a function f from A to B is a rule which

Answer 18

to each a ∈ A, assigns an element f (a) of B, called the value of f at a. We write f : A → B
set A is called the domain of f , the set B is called the codomain of f

Question 19

Two functions f : A → B and g : C → D are equal if and only if

Answer 19

A = C, B = D
and f (a) = g(a) for every a ∈ A

Question 20

statement

Answer 20

sentence which is either true or false but not both

Question 21

contrapositive

Answer 21

The contrapositive of the statement ‘A =⇒ B’ is ‘not(B) =⇒ not(A)’

Question 22

converse

Answer 22

The converse of the statement ‘A =⇒ B’ is ‘B =⇒ A’

Question 23

Proof by Contradiction

Answer 23

assume that the hypothesis H is true but the conclusion C is false

Question 24

(Euclid’s Lemma). Suppose a, b, c are non-zero integers.

Answer 24

if a is coprime to b and a | bc, then a | c If p is prime and p | bc then p | b or p | c

Question 25

(x + y)^p ≡ (modular arithmetic)

Answer 25

≡ x^p + y^p (mod p)

Question 26

Fermat’s Little Theorem

Answer 26

a^p ≡ a (mod p)

Question 27

If a ∈ Z and p does not divide a then

Answer 27

a^(p−1) ≡ 1 (mod p)

Question 28

Suppose a ∈ Z and n ∈ N. Let d be the gcd of a and n

Answer 28

if d > 1, then there is no b ∈ Z with ab ≡ 1 (mod n) If d = 1, then there exists b ∈ Z with ab ≡ 1 (mod n) If n is a prime and n ∤ a, then there exists b ∈ Z with ab ≡ 1 (mod n) Let b, b′ ∈ Z. If n is a prime and n ∤ a, and ab ≡ ab′ (mod n) then b ≡ b′ (mod n)

Question 29

The identity function

Answer 29

If A is any set, the identity function iA : A → A is given by iA(a) = a, for all a ∈ A

Question 30

Composition

Answer 30

Suppose f : A → B and g : B → C are functions. We define the composition g ◦ f to be the function g ◦ f : A → C given by (g ◦ f )(a) = g (f (a)) , for a ∈ A

Question 31

image of f

Answer 31

{f (a) : a ∈ A}

Question 32

Formal definition of function

Answer 32

f: A -> B is a subset of the direct product A × B with the property that * for each a ∈ A there is a unique b ∈ B such that (a, b) ∈ f .

Question 33

injective

Answer 33

whenever a, a′ ∈ A and a̸ = a′, then f (a)̸ = f (a′) (so f sends distinct elements of A to distinct elements of B)

Question 33

surjective

Answer 33

for every b ∈ B there exists a ∈ A with f (a) = b

Question 34

bijective

Answer 34

f is both surjective and injective

Question 35

Relate surjectivity to the image of a set.

Answer 35

Suppose f : A → B is a function. Recall that the image of f is Im(f ) = {f (a) : a ∈ A} ⊆ B. Then f is surjective if and only if Im(f ) = B

Question 36

To check that a function f : A → B is injective, we need to show that...

Answer 36

for a, a′ ∈ A, if f (a) = f (a′) then a = a′.

Question 37

Inverse Function

Answer 37

g(f (a)) = a and f (g(b)) = b (if theres an inverse then it is unique)

Question 38

f has an inverse if and only if it is a...

Answer 38

bijection

Question 39

A relation R on a set A

Answer 39

subset of the set of ordered pairs, R ⊆ A × A

Question 40

Let A be a set and ∼ a relation on A (reflexive)

Answer 40

for all a ∈ A we have a ∼ a

Question 41

Let A be a set and ∼ a relation on A (symmetric)

Answer 41

for all a, b ∈ A, whenever a ∼ b then b ∼ a

Question 42

Let A be a set and ∼ a relation on A (transitive)

Answer 42

for all a, b, c ∈ A, whenever a ∼ b and b ∼ c then a ∼ c

Question 43

Let A be a set and ∼ a relation on A (equivalence relation)

Answer 43

reflexive, symmetric and transitive

Question 44

partition of a non-empty set A

Answer 44

a set P of non-empty subsets of A (called the parts of the partition), with the property that any element of A is in exactly one of the parts

Question 45

Suppose A is a non-empty set and ∼ is an equivalence relation on A. Let a ∈ A. The equivalence class of a is the set

Answer 45

[a] = {b ∈ A : a ∼ b}

Question 46

If A is a non-empty set and ∼ is an equivalence relation on A, then the set of equivalence classes P = {[a] : a ∈ A} is what?

Answer 46

a partition of A. Moreover, if a, b ∈ A, then a ∼ b ⇔ [a] = [b]

Question 47

(The Inclusion-Exclusion principle). Let A, B, C be finite sets.

Answer 47

|A ∪ B| = |A| + |B| − |A ∩ B|

Question 48

Let A, B be non-empty finite sets

Answer 48

(i) There is an injective map f : A → B if and only if |A| ⩽ |B|. (ii) There is a surjective map g : A → B if and only if |A| ⩾ |B|. (iii) There is a bijection h : A → B if and only if |A| = |B|.

Question 49

Let A, B be non-empty finite sets with |A| = |B| and let f : A → B be a function. Then the following statements are equivalent:

Answer 49

(i) f is injective; (ii) f is surjective; (iii) f is bijective

Question 50

pigeonhole principle

Answer 50

Let n, k be natural numbers with n > k and suppose we have placed n identical balls into k identical boxes. Then there is at least one box in which we placed at least two balls.

Question 51

sets A, B have the same cardinality

Answer 51

bijection, f : A → B. In this case we write |A| = |B| An infinite set X is countable if there is a bijection f : N → X, that is, |N| = |X|. Otherwise, X is called uncountable