HOME Mathematics Computer Science
One-way Functions
Prerequisites
Show All
Hide All
Sets
Show/Hide

Introduction
  • A set is a collection of elements, such as:
    • A = {1, 2, 3, 4, 5}
  • A set does not have order:
    • {1, 2, 3, 4, 5} is the same as {5, 4, 3, 2, 1}
    • It is convenient to write the elements of a set in consecutive order, but this is only for convenience.
  • Every element in a set is unique, multiples of the same element are ignored:
    • The set {1, 2, 2} has a size of 2, and is the same as {1, 2}
Notation
  • It is common for sets to be denoted by a uppercase letter, and for its elements to be wrapped in curly braces:k

    LaTeX: \mathbf{A} = \{ 1, 2, 3, 4, 5 \}
  • Sets can also be defined using set builder notation:
    • A rule is used to show which elements are members of the set:
    • The set A defined above would contain all even integers between 0 and 2000.
    • The format of the rule is: (formula: conditions) or (formula| conditions).
    • If it is not specified as a condition, then it is assumed that a is a real number.
Elements in a set
  • Elements in a set are usually represented by a lowercase letter.
  • To demonstrate that an element is part of a set, we use the set membership symbol:

    LaTeX: \mathbf{a} \in \mathbf{A}
  • This can also be done with proper elements:

    LaTeX: \1 \in \{ 1, 2, 3, 4, 5 \}
  • To show that an element is not part of a set, we use the 'not member of' symbol:

    LaTeX: 6 \notin \{ 1, 2, 3, 4, 5 \}
The Empty Set

The Empty Set (or Null Set) is a set containing no items. It is represented by the empty set symbol:


LaTeX: \varnothing = \{\}
Code
A = frozenset([1, 2, 3, 4, 5])

print(1 in A) # prints 'True'
print(6 not in A) # prints 'True'
Ordered Pairs
Show/Hide

Introduction
  • An ordered pair is simply a pair of objects, e.g. (a, b)
  • In an ordered pair, the order matters:
    LaTeX:
    (\mathbf{a}, \mathbf{b})\neq (\mathbf{b}, \mathbf{a}) 
    \text{ unless } 
    \mathbf{a} = \mathbf{b}
    
  • This contrasts with the unordered pair, in which (a, b) = (b, a) regardless of the values of a and b.
  • An ordered pair is not a type of set. An ordered pair may contain duplicate elements, and its order is important.
Notation
Ordered Pairs are represented by a comma separated pair of elements wrapped in brackets:
a = (1, 2)
LaTeX: \mathbf{a} = (1, 2)
Code
a = (1, 2)
print(a)
Functions
Show/Hide

Introduction
  • A function is mapping between two sets:
  • The first set (denoted by X) is called the domain.
  • The second set (denoted by Y) is called the codomain.
  • Each mapping can be represented as an ordered pair, e.g. (a, 1). The set of all ordered pairs for the entire function is called the graph of the function, and is given the name G.
  • For each element x in X, there exists a unique y in Y.
    • X is called the 'argument', 'input', or 'preimage'
    • y is called the 'value', 'ouput', or 'image'
  • In the above example, not all elements of Y were mapped to from X. The subset of Y that has mappings from X is called the range.
    • This is also called the image of the function, and is denoted:
Functional Notation
  • One common way to denote functions is using the functional notation.


    LaTeX: \mathbf{y} = f(\mathbf{x})
  • This is pronounced 'F of X'
  • It is commonly used in areas of Mathematics which do not have a basis in set theory (such as calculus).
Arrow Notation
  • Another way to denote functions is using arrow notation.


    LaTeX: f\colon \mathbf{X} \to \mathbf Y
  • This is pronounced 'the function f from set X to set Y.
  • It is commonly used in areas of Mathematics which have a basis in set theory.
Code
def f(x):
    graph = {
        'a': 1,
        'b': 3,
        'c': 1
    }

    return graph.get(x)


y = f('a')
print(y)
Injections, Surjections, and Bijections
Show/Hide

Introduction
  • Functions can be classified by how they map elements between the domain and codomain.
  • Three types of mappings are:
    • Injective
    • Surjective
    • Bijective
Injective Mapping
  • An injective mapping is when each element in the codomain is mapped to by at most one element from the domain.
  • Another way of saying this is that no two elements in the domain map to the same element in the codomain.
  • Example of an injective mapping:
  • This type of mapping is also called 'one-to-one'.
Surjective Mapping
  • A surjective mapping is when each element in the codomain is mapped to by at least one element from the domain.
  • Another way of saying this is that the codomain and image (range) of the function are the same.
  • Example of a surjective mapping:
  • This type of mapping is also called 'onto'.
Bijective Mapping
  • A bijective mapping is when the mapping is both injective and surjective.
  • Another way of saying this is that each element in the codomain is mapped to by exactly one element in the domain.
  • Example of a bijective mapping:
  • This type of mapping is also called a 'one-to-one correspondence'.
Inverse Functions
Show/Hide

Introduction
  • If f is a function, then its inverse function g is defined as the reverse of the mapping created by f.
  • If g is an inverse of f then:
  • and:
Example
  • To find the inverse of a function given as an equation, we can simply solve for y
Notation
To denote that a function is an inverse of another, two different notations are commonly used:
  • If the function is representedby the letter f then its inverse is can be denoted using a superscript of -1

    LaTeX: f^{-1}(x)
  • If the function is represented by the letter f then its inverse is can be denoted using the letter g

    LaTeX: g(x)
Properties
  • If the original function is a bijection then its inverse will also be a bijection.
  • If the original function is not a bijection then there is no guarantee that it has an inverse.
    • If it is not injective then there may be two elements in the domain that map to the same element in the codomain.
    • If it is not surjective then there may be an element in the codomain that is not mapped to from the domain.

One-way Functions

Introduction
  • One way functions are a special subset of functions in which it is easy to compute y given x but very hard to compute x given y
  • For example:

    LaTeX: f(x) = 7^x \mod 23
    We can calculate values for f(x) very easily:
    However given a specific value for y it is difficult to find a corresponding x without computing each possible value of x and seeing if it results in a matching y.
Code
Notice in the code below, the function f() has a much smaller complexity than function g()
def f(_x):
    return 7**_x % 23


def g(_y):
    for i in range(10*1000):
        if f(i) == _y:
            return i

    raise Exception("x is not in testable domain")


x = 8
y = f(x)
print("The image of " + str(x) + " is " + str(y))  # prints The image of 8 is 12

y = 12
x = g(y)

print("The preimage of " + str(y) + " is " + str(x))  # prints The preimage of 12 is 8
Related