In this 2nd lecture of the Elliptic Curve Cryptography hosted by Privacy Scaling Ethereum, we continued to see maps and specifically we saw Cantor’s Theorem. Furthermore, we go over the first notion of what a group is, saw some famous groups and Fermat’s Little Theorem.
Cantor’s Theorem
There is no surjective map from the natural numbers to the real numbers.
For any set X, the power set of X(i.e., the set of subsets of X), is larger (has a greater cardinality) than X. Cantor’s Theorem tells us that no matter how large a set we have, we may consider a set that is still larger. This is trivial if the set in question has finitely many members, but not at all obvious if our set is infinite. The theorem implies that there is no largest cardinal number (colloquially, “there’s no largest infinity”).
Cantor discovered that no matter what set you start with, any attempt to form a one-to-one match-up of the elements of the set to the subsets of the set must leave some subset unmatched.
The proof uses a technique that Cantor originated called diagonalization, which is a form of proof by contradiction.
Groups
A group is a set G together with a binary operation (a function from the cartesian product to G):
u: G x G ---> G
(x, y) ---> u((x, y))and a chosen unit element e (in G) such that these conditions are met:
- Unitarity
- Associativity
- Existense of Inverse
The general idea is that for a group to be a group, we need to check:
- the binary operation is associative
- the existence of a neutral element (in which the binary operation has no effect)
- the existence of an inverse — this is the most complex part. We used Fermat’s Little Theorem for proving so in a group of prime fields with mod p as the binary operation
Famous Groups
- Trivial group
- Complex group with the unit circle and multiplication
Fermat’s Little Theorem
Fermat’s little theorem states that if p is a prime number, then for any integer a, the number ap − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed:
a^p = a (mod p)From Wikipedia, Fermat’s little theorem is the basis for the Fermat primality test ( a probabilistic test to determine whether a number is a probable prime) and is one of the fundamental results of elementary number theory.
Notions of type of functions (ex. injective, surjective) are closed under composition. Example, if f and b are both injective, then g composed f is also injective.