Set Theory Lecture 5 Flashcards
What is a function?
A binary relation where each element in the domain maps to at most one element in the codomain.
What is the domain of a function?
The set of all possible inputs for the function.
What is the codomain of a function?
The set of all possible outputs that the function could map to.
What is the range (image) of a function?
The actual set of outputs produced by applying the function to elements in the domain.
When is a function called total?
If its domain of definition is the entire set A.
When is a function called surjective?
If its range is equal to the codomain.
What is an injective function?
A function where no two different inputs map to the same output.
What is a surjective function?
A function where every element in the codomain is mapped by at least one element in the domain.
What is a bijective function?
A function that is both injective and surjective.
What is an example of an injective function?
f(x) = 3x - 1 over the real numbers.
What is an example of a surjective function?
f(x) = |3x - 1| over the non-negative real numbers.
What is an example of a bijective function?
f(x) = x + 1 over the integers.
What is function composition?
Applying one function to the output of another function.
What is the notation for function composition?
(g ◦ f)(x) = g(f(x)).
What is an inverse function?
A function that reverses the effect of another function.
When does a function have an inverse?
If and only if it is bijective.
What is the inverse of a bijection?
A function that maps elements in the codomain back to their original elements in the domain.
What is a counting argument in set theory?
A method for comparing the sizes of sets using functions.
What does it mean for two sets to have the same cardinality?
There exists a bijection between them.
What is an example of two sets with the same cardinality?
The set of natural numbers and the set of even natural numbers.
What does the Cantor–Schröder–Bernstein theorem state?
If there are injections from A to B and B to A, then there exists a bijection between A and B.
What is a countably infinite set?
A set that has the same cardinality as the natural numbers.
What does it mean for a set to be countable?
It is either finite or countably infinite.
What is an example of a countably infinite set?
The set of integers.
What is an uncountable set?
A set that is not countable, meaning it has strictly greater cardinality than the natural numbers.
What is an example of an uncountable set?
The set of real numbers in the interval (0,1).
What proof technique shows that (0,1) is uncountable?
Cantor’s diagonalization argument.
What is the idea behind Cantor’s diagonalization argument?
It constructs a number that is not in any supposed enumeration of (0,1), proving the set is uncountable.
What does the diagonalization argument show about real numbers?
There are more real numbers than natural numbers, proving the existence of different sizes of infinity.
What is the significance of countability in computer science?
It determines whether a set can be systematically enumerated, affecting computability and algorithm design.
