Wk 0: The Function and the Field

Question 1

Set

Answer 1

an unordered collection of objects

Question 2

Cardinality

Answer 2

If a set S is not infinite, we use |S| to denote the number of elements or cardinality of the set

Question 3

Cartesian Product

Answer 3

A x B is the set of all pairs (a,b) where a ∈ A and b ∈ B

Question 4

Cardinality of A x B

Answer 4

If A and B are finite sets then |A x B| = |A| x |B|

Question 5

Function (informally)

Answer 5

For each input element in a set A, a function assigns a single output element from another set B

Question 6

Domain of a function

Answer 6

Set A which contains input elements

Question 7

Co-domain of a function

Answer 7

Set B from which all outputs are chosen

Question 8

Function (formal)

Answer 8

A set of pairs (a,b) no two of which have the same first element

Question 9

Image (of an input)

Answer 9

The output of a given input. The image of q under a function f is denote f(q)

Question 10

f(q) = r or q ↦ r

Answer 10

q maps to r under f

Question 11

f: D → F

Answer 11

f is a function with domain D and co-domain F

Question 12

T/F: All elements of the co-domain are images of elements in the domain

Answer 12

FALSE. There might be elements in the co-domain that are not images of any elements in the domain

Question 13

Caesar’s cryptosystem

Answer 13

Each letter is mapped to one three places ahead

Question 14

Image (of a function)

Answer 14

The set of all images of inputs. written Im f

Question 15

Range

Answer 15

Ambiguous - can refer to co-domain or image

Question 16

F^D

Answer 16

For sets F and D, F^D denotes all functions from D to F

Question 17

|F^D| (prop.)

Answer 17

|F^D| = |F|^|D|

Question 18

Identity function

Answer 18

For any domain D, maps each domain element to itself. id_D: D → D

Question 19

Functional composition

Answer 19

For functions f: A→B and g: B→C, the functional composition of f and g is the function (g ∘ f): A→C defined by (g ∘ f)(x) = g(f(x))

Question 20

Prop. Associativity of function composition

Answer 20

h ∘ (g ∘ f) = (h ∘ g) ∘ f

Question 21

Functional inverses

Answer 21

Functions f and g are functional inverses if f ∘ g and g ∘ f are defined and are identity functions

Question 22

Invertible function

Answer 22

A function that has an inverse

Question 23

One-to-one

Answer 23

f: D→F st f(x) = f(y) implies x = y

Question 24

Onto

Answer 24

f: D→F st ∀ z ∈ F, ∃ a ∈ D st f(a) = z

Question 25

Prop. Invertible functions are one-to-one

Answer 25

TRUE. To prove: Assume false and f^-1 contradicts definition of function

Question 26

Prop. Invertible functions are onto

Answer 26

TRUE. To prove: Assume false and f^-1 contradicts definition of inverse

Question 27

Function Invertibility Theorem

Answer 27

A function f is invertible ⇔ it is one-to-one and onto

Question 28

Procedure

Answer 28

A description of a computation that, given an input, produces an output

Question 29

Computational problem

Answer 29

An input-output specification that a procedure might be required to satisfy

Question 30

Procedure vs. Computational problem

Answer 30

1) Functions / CPs don’t tell us how
2) Many procedures may exist for same spec
3) CP may allow several diff outputs for same input

Question 31

Uniform distribution

Answer 31

pdf which assigns the same probability to each outcome

Question 32

Probability distribution function (pdf)

Answer 32

1) Assigns a nonnegative probability to each possible outcome
2) Probabilities of all possible outcomes must sum to 1

Question 33

Translation of complex number

Answer 33

f(z) = z + z₀

Question 34

Scaling (of a complex number)

Answer 34

Multiplication by a scalar

Question 35

Reflection (of a complex number)

Answer 35

Multiplication by -1

Question 36

Rotation (of a complex number)

Answer 36

f(z) = z * e^{τ<strong>i</strong>} does rotation by an angle τ in radians

Question 37

Euler’s formula

Answer 37

For any real number θ, e^iθ is the point z on the unit circle with argument θ

Question 38

GF(2)

Answer 38

Galois Field 2; contains elements 0 and 1

Question 39

Addition in GF(2)

Answer 39

XOR

Question 40

Multiplication in GF(2)

Answer 40

Same as integer multiplication

Question 41

one-time pad

Answer 41

If each bit is encrypted with its own one-bit key, it is unbreakable

Question 42

Argument of z ∈ ℂ

Answer 42

Angle in radians between z arrow and 1 + 0i arrow

Question 43

z = re^{θ<strong>i</strong>}

Answer 43

• r is the absolute value of z
• θ is the argument of z