Wk 0: The Function and the Field Flashcards
Set
an unordered collection of objects
Cardinality
If a set S is not infinite, we use |S| to denote the number of elements or cardinality of the set
Cartesian Product
A x B is the set of all pairs (a,b) where a ∈ A and b ∈ B
Cardinality of A x B
If A and B are finite sets then |A x B| = |A| x |B|
Function (informally)
For each input element in a set A, a function assigns a single output element from another set B
Domain of a function
Set A which contains input elements
Co-domain of a function
Set B from which all outputs are chosen
Function (formal)
A set of pairs (a,b) no two of which have the same first element
Image (of an input)
The output of a given input. The image of q under a function f is denote f(q)
f(q) = r or q ↦ r
q maps to r under f
f: D → F
f is a function with domain D and co-domain F
T/F: All elements of the co-domain are images of elements in the domain
FALSE. There might be elements in the co-domain that are not images of any elements in the domain
Caesar’s cryptosystem
Each letter is mapped to one three places ahead
Image (of a function)
The set of all images of inputs. written Im f
Range
Ambiguous - can refer to co-domain or image
FD
For sets F and D, FD denotes all functions from D to F
|FD| (prop.)
|FD| = |F||D|
Identity function
For any domain D, maps each domain element to itself. idD: D → D
Functional composition
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))
Prop. Associativity of function composition
h ∘ (g ∘ f) = (h ∘ g) ∘ f
Functional inverses
Functions f and g are functional inverses if f ∘ g and g ∘ f are defined and are identity functions
Invertible function
A function that has an inverse
One-to-one
f: D→F st f(x) = f(y) implies x = y
Onto
f: D→F st ∀ z ∈ F, ∃ a ∈ D st f(a) = z
Prop. Invertible functions are one-to-one
TRUE. To prove: Assume false and f-1 contradicts definition of function
Prop. Invertible functions are onto
TRUE. To prove: Assume false and f-1 contradicts definition of inverse
Function Invertibility Theorem
A function f is invertible ⇔ it is one-to-one and onto
Procedure
A description of a computation that, given an input, produces an output
Computational problem
An input-output specification that a procedure might be required to satisfy
Procedure vs. Computational problem
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
Uniform distribution
pdf which assigns the same probability to each outcome
Probability distribution function (pdf)
1) Assigns a nonnegative probability to each possible outcome
2) Probabilities of all possible outcomes must sum to 1
Translation of complex number
f(z) = z + z0
Scaling (of a complex number)
Multiplication by a scalar
Reflection (of a complex number)
Multiplication by -1
Rotation (of a complex number)
f(z) = z * eτ<strong>i</strong> does rotation by an angle τ in radians
Euler’s formula
For any real number θ, eiθ is the point z on the unit circle with argument θ
GF(2)
Galois Field 2; contains elements 0 and 1
Addition in GF(2)
XOR
Multiplication in GF(2)
Same as integer multiplication
one-time pad
If each bit is encrypted with its own one-bit key, it is unbreakable
Argument of z ∈ ℂ
Angle in radians between z arrow and 1 + 0i arrow
z = reθ<strong>i</strong>
- r is the absolute value of z
- θ is the argument of z
