Set Theory Lecture 5

Question 1

What is a function?

Answer 1

A binary relation where each element in the domain maps to at most one element in the codomain.

Question 2

What is the domain of a function?

Answer 2

The set of all possible inputs for the function.

Question 3

What is the codomain of a function?

Answer 3

The set of all possible outputs that the function could map to.

Question 4

What is the range (image) of a function?

Answer 4

The actual set of outputs produced by applying the function to elements in the domain.

Question 5

When is a function called total?

Answer 5

If its domain of definition is the entire set A.

Question 6

When is a function called surjective?

Answer 6

If its range is equal to the codomain.

Question 7

What is an injective function?

Answer 7

A function where no two different inputs map to the same output.

Question 8

What is a surjective function?

Answer 8

A function where every element in the codomain is mapped by at least one element in the domain.

Question 9

What is a bijective function?

Answer 9

A function that is both injective and surjective.

Question 10

What is an example of an injective function?

Answer 10

f(x) = 3x - 1 over the real numbers.

Question 11

What is an example of a surjective function?

Answer 11

f(x) = |3x - 1| over the non-negative real numbers.

Question 12

What is an example of a bijective function?

Answer 12

f(x) = x + 1 over the integers.

Question 13

What is function composition?

Answer 13

Applying one function to the output of another function.

Question 14

What is the notation for function composition?

Answer 14

(g ◦ f)(x) = g(f(x)).

Question 15

What is an inverse function?

Answer 15

A function that reverses the effect of another function.

Question 16

When does a function have an inverse?

Answer 16

If and only if it is bijective.

Question 17

What is the inverse of a bijection?

Answer 17

A function that maps elements in the codomain back to their original elements in the domain.

Question 18

What is a counting argument in set theory?

Answer 18

A method for comparing the sizes of sets using functions.

Question 19

What does it mean for two sets to have the same cardinality?

Answer 19

There exists a bijection between them.

Question 20

What is an example of two sets with the same cardinality?

Answer 20

The set of natural numbers and the set of even natural numbers.

Question 21

What does the Cantor–Schröder–Bernstein theorem state?

Answer 21

If there are injections from A to B and B to A, then there exists a bijection between A and B.

Question 22

What is a countably infinite set?

Answer 22

A set that has the same cardinality as the natural numbers.

Question 23

What does it mean for a set to be countable?

Answer 23

It is either finite or countably infinite.

Question 24

What is an example of a countably infinite set?

Answer 24

The set of integers.

Question 25

What is an uncountable set?

Answer 25

A set that is not countable, meaning it has strictly greater cardinality than the natural numbers.

Question 26

What is an example of an uncountable set?

Answer 26

The set of real numbers in the interval (0,1).

Question 27

What proof technique shows that (0,1) is uncountable?

Answer 27

Cantor's diagonalization argument.

Question 28

What is the idea behind Cantor's diagonalization argument?

Answer 28

It constructs a number that is not in any supposed enumeration of (0,1), proving the set is uncountable.

Question 29

What does the diagonalization argument show about real numbers?

Answer 29

There are more real numbers than natural numbers, proving the existence of different sizes of infinity.

Question 30

What is the significance of countability in computer science?

Answer 30

It determines whether a set can be systematically enumerated, affecting computability and algorithm design.