infinite possibilities

• to compare sizes of undisclosed size sets, assign them as pairs
• injective: a function that is one-to-one, and only one-to-one (if 2 inputs have the same output, they are actually the same input)
• Surjective: All outputs have an input
• Bijective: both one to one and all outputs have an input
• If there is an injection from n (list of n elements) to X, X has at least n elements
• If there is a surjection from set of length n to X, X has at most n elements
• If there is a bijection from a set of n elements to X, X has exactly n elements
• Injective function: assigns unique output value to each input value
• Surjective function: every output is mapped to at least once
• Bijective: both injective and surjective
• Injection means there is a surjection in the opposite direction (X -> Y, Y<-X)
• If there is no injection in one direction, there is always an injection in the opposite direction (eg. x1 and 2 both map to y1, but in reverse this is not an issue)
• If there is an injection both directions, there is a bijection
• size of all even numbers = size of all natural numbers actually
• A set X is countable if there is a surjection ℕ -> X
• A set X is infinite if there is an injection ℕ -> X
• every formal language is countable, but there are uncountably many languages (powerset of a countable alphabet = more than ℕ)