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
alternate positive and non-positive values by parity
inject into $ℕ \times ℕ$ and apply Schröder and Bernstein
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 apply Schröder and Bernstein $(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

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 ℝ?

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 $ℝ$ ?