Lesson test: Counting the infinite

Sign in

Libre University uses your GitHub account. Signing in is only needed to sit a final test, so the score is kept on your profile.

Counting the infinite

1.[1p]
What does $| A | \leq | B |$ mean for sets $A$ and $B$ ?

There is an injection $A \to B$

Correct

There is a surjection $A \to B$

The answer is: There is an injection $A \to B$

$A$ is a subset of $B$

The answer is: There is an injection $A \to B$

There is a bijection from $A$ to a proper subset of $B$ and none to $B$

The answer is: There is an injection $A \to B$

2.[1p]
The set $ℕ ∖ {1}$ is the same size as $ℕ$ .

True

Correct

False

The answer is: True

3.[1p]
The bijection $f : ℕ \to ℤ$ has $f (n) = \frac{n}{2}$ for even $n$ and $f (n) = \frac{1 - n}{2}$ for odd $n$ . Which natural number $n$ has $f (n) = - 4$ ?

CorrectNot quite: 9

4.[2p]
Evaluate the pairing function $p (m, n) = \frac{(m + n - 2) (m + n - 1)}{2} + m$ at $(m, n) = (4, 7)$ .

CorrectNot quite: 49

5.[3p]
Which of these sets are countable?

Select all that apply

$ℤ$

Correct

$ℕ \times ℕ$

Correct

$ℚ$

Correct

$ℤ \times ℤ$

Correct

$(0, 1)$

The answer is: $ℤ$ , $ℕ \times ℕ$ , $ℚ$ , $ℤ \times ℤ$

$ℝ$

The answer is: $ℤ$ , $ℕ \times ℕ$ , $ℚ$ , $ℤ \times ℤ$

$P (ℕ)$

The answer is: $ℤ$ , $ℕ \times ℕ$ , $ℚ$ , $ℤ \times ℤ$

6.[2p]
Match each result to the idea that proves it.

$ℤ$ is countable
$ℕ \times ℕ$ is countable
$ℚ$ is countable
$(0, 1)$ is uncountable
$| A | < | P (A) |$

the set of elements not in their own image
change the $n$ th digit of the $n$ th number
inject into $ℕ \times ℕ$ , and so into $ℕ$
alternate positive and non-positive values by parity
list the pairs diagonal by diagonal

Show the answer

$ℤ$ is countable: alternate positive and non-positive values by parity $ℕ \times ℕ$ is countable: list the pairs diagonal by diagonal $ℚ$ is countable: inject into $ℕ \times ℕ$ , and so into $ℕ$ $(0, 1)$ is uncountable: change the $n$ th digit of the $n$ th number $| A | < | P (A) |$ : the set of elements not in their own image

7.[2p]
In the diagonal argument for $(0, 1)$ , why are the new digits chosen from $4$ and $5$ rather than any digit different from the diagonal one?

So the new number has only one decimal expansion and cannot be a listed number written another way

Correct

So the new number is rational and therefore not on the list

The answer is: So the new number has only one decimal expansion and cannot be a listed number written another way

So the new number is smaller than every number on the list

The answer is: So the new number has only one decimal expansion and cannot be a listed number written another way

Because the diagonal digits of a list can never be $4$ or $5$

The answer is: So the new number has only one decimal expansion and cannot be a listed number written another way

8.[2p]
Put the lines of the proof that no function $F : A \to P (A)$ is surjective in order.

Otherwise $d \notin D$ , so $d \notin F (d)$ , which is the condition for $d \in D$ .
Suppose $D = F (d)$ for some $d \in A$ .
Let $D = {a \in A : a \notin F (a)}$ , a subset of $A$ .
Both cases are contradictions, so $D$ is not a value of $F$ .
If $d \in D$ , then $d \notin F (d) = D$ by the definition of $D$ .

Show the answer

a, b, c, d, e

9.[1p]
What is known about the continuum hypothesis, that every infinite set of reals is either countable or the same size as $ℝ$ ?

It can be neither proved nor disproved from the usual axioms of set theory

Correct

Cantor proved it in 1878

The answer is: It can be neither proved nor disproved from the usual axioms of set theory

Gödel disproved it in 1940

The answer is: It can be neither proved nor disproved from the usual axioms of set theory

It is an open problem that most mathematicians expect to be proved

The answer is: It can be neither proved nor disproved from the usual axioms of set theory

10.[1p]
The map $F (m, n) = 2^{m - 1} (2 n - 1)$ is a bijection $ℕ \times ℕ \to ℕ$ . Which natural number is $F (3, 2)$ ?

CorrectNot quite: 12

11.[1p]
A union of countably many countable sets is countable.

True

Correct

False

The answer is: True

12.[2p]
Why must transcendental numbers exist?

The algebraic numbers are countable and $ℝ$ is not

Correct

Every polynomial with integer coefficients has a transcendental root

The answer is: The algebraic numbers are countable and $ℝ$ is not

$π$ and $e$ were shown to be transcendental before Cantor's work

The answer is: The algebraic numbers are countable and $ℝ$ is not

The diagonal argument, applied to a list of the rationals, produces one

The answer is: The algebraic numbers are countable and $ℝ$ is not

13.[3p]
Which of these sets have the same size as $ℝ$ ?

Select all that apply

$(0, 1)$

Correct

$P (ℕ)$

Correct

$ℝ \times ℝ$

Correct

The set of irrational numbers

Correct

$ℚ$

The answer is: $(0, 1)$ , $P (ℕ)$ , $ℝ \times ℝ$ , The set of irrational numbers

The set of real algebraic numbers

The answer is: $(0, 1)$ , $P (ℕ)$ , $ℝ \times ℝ$ , The set of irrational numbers

14.[2p]
What does the Schröder and Bernstein theorem say?

If there are injections $A \to B$ and $B \to A$ , then there is a bijection $A \to B$

Correct

If there is an injection $A \to B$ , then there is a surjection $A \to B$

The answer is: If there are injections $A \to B$ and $B \to A$ , then there is a bijection $A \to B$

If $A \subseteq B$ and $A$ is infinite, then $| A | = | B |$

The answer is: If there are injections $A \to B$ and $B \to A$ , then there is a bijection $A \to B$

Every set is strictly smaller than its power set

The answer is: If there are injections $A \to B$ and $B \to A$ , then there is a bijection $A \to B$

1.[1p] What does |A|≤|B| mean for sets A and B?

2.[1p] The set ℕ∖{1} is the same size as ℕ.

3.[1p] The bijection f:ℕ→ℤ has f(n)=n2 for even n and f(n)=1−n2 for odd n. Which natural number n has f(n)=−4?

4.[2p] Evaluate the pairing function p(m,n)=(m+n−2)(m+n−1)2+m at (m,n)=(4,7).

5.[3p] Which of these sets are countable?

6.[2p] Match each result to the idea that proves it.

7.[2p] In the diagonal argument for (0,1), why are the new digits chosen from 4 and 5 rather than any digit different from the diagonal one?

8.[2p] Put the lines of the proof that no function F:A→P(A) is surjective in order.

9.[1p] What is known about the continuum hypothesis, that every infinite set of reals is either countable or the same size as ℝ?

10.[1p] The map F(m,n)=2m−1(2n−1) is a bijection ℕ×ℕ→ℕ. Which natural number is F(3,2)?

11.[1p] A union of countably many countable sets is countable.

12.[2p] Why must transcendental numbers exist?

13.[3p] Which of these sets have the same size as ℝ?

14.[2p] What does the Schröder and Bernstein theorem say?

1.[1p]
What does $| A | \leq | B |$ mean for sets $A$ and $B$ ?

2.[1p]
The set $ℕ ∖ {1}$ is the same size as $ℕ$ .

3.[1p]
The bijection $f : ℕ \to ℤ$ has $f (n) = \frac{n}{2}$ for even $n$ and $f (n) = \frac{1 - n}{2}$ for odd $n$ . Which natural number $n$ has $f (n) = - 4$ ?

4.[2p]
Evaluate the pairing function $p (m, n) = \frac{(m + n - 2) (m + n - 1)}{2} + m$ at $(m, n) = (4, 7)$ .

5.[3p]
Which of these sets are countable?

6.[2p]
Match each result to the idea that proves it.

7.[2p]
In the diagonal argument for $(0, 1)$ , why are the new digits chosen from $4$ and $5$ rather than any digit different from the diagonal one?

8.[2p]
Put the lines of the proof that no function $F : A \to P (A)$ is surjective in order.

9.[1p]
What is known about the continuum hypothesis, that every infinite set of reals is either countable or the same size as $ℝ$ ?

10.[1p]
The map $F (m, n) = 2^{m - 1} (2 n - 1)$ is a bijection $ℕ \times ℕ \to ℕ$ . Which natural number is $F (3, 2)$ ?

11.[1p]
A union of countably many countable sets is countable.

12.[2p]
Why must transcendental numbers exist?

13.[3p]
Which of these sets have the same size as $ℝ$ ?

14.[2p]
What does the Schröder and Bernstein theorem say?