Practice: Ordinals and cardinals

Ordinals and cardinals

Warm-upHuman

Which of these ordinals are equal to $\omega$ ? Select all.

Choose all that apply

Ordinals and cardinals

CoreHuman

Write $(\omega + 3) \cdot 2$ in the form $\omega \cdot 2 + k$ with $k$ a natural number. What is $k$ ?

Ordinals and cardinals

CoreHuman

Write $2 \cdot (\omega + 3)$ in the form $\omega + k$ with $k$ a natural number. What is $k$ ?

Ordinals and cardinals

CoreHuman

In the proof that a strictly increasing $f : W \to W$ on a well-order satisfies $x \le f(x)$ , we take the least $m$ with $f(m) < m$ . Why does this lead to a contradiction?

Choose one

Because

f(f(m)) < f(m)

, so

f(m)

is a smaller element with the same propertyBecause

f

is surjective, so

m = f(y)

for some

y

Because

f(m) < m

contradicts

f

being increasingBecause

W

is finite

Ordinals and cardinals

CoreHuman

Which of these statements are provable in ZF, without the axiom of choice? Select all.

Choose all that apply

If

|A| \le |B|

and

|B| \le |A|

then

|A| = |B|

There is no surjection

A \to \mathcal P(A)

For every set

A

there is an ordinal that does not inject into

A

For all sets

A, B

:

|A| \le |B|

or

|B| \le |A|

Every infinite set has an aleph as its cardinality

Ordinals and cardinals

CoreHuman

What is the cardinality of $\R \times \N$ ?

Choose one

2^{\aleph_0}

\aleph_0

2^{\aleph_0} \cdot \aleph_0

, which is larger than

2^{\aleph_0}

2^{2^{\aleph_0}}

Ordinals and cardinals

CoreFormal

Which Lean statement correctly formalises Cantor's theorem for a type α?

Choose one

∀ f : α → Set α, ¬ Function.Surjective f∀ f : α → Set α, ¬ Function.Injective f∀ f : Set α → α, ¬ Function.Surjective f∃ f : α → Set α, ¬ Function.Surjective f

Ordinals and cardinals

StretchHuman

Here is a faulty argument. “(1) The map $n \mapsto n + 1$ together with $\omega \mapsto 0$ is a bijection from $\omega + 1$ to $\omega$ . (2) So $\omega + 1$ and $\omega$ have the same cardinality. (3) So $\omega + 1$ and $\omega$ are isomorphic well-orders. (4) Hence $\omega + 1 = \omega$ by uniqueness of order types.” Which step is wrong?

Choose one

Step (1)Step (2)Step (3)Step (4)

Ordinals and cardinals

StretchComputational

Represent an ordinal below $\omega^\omega$ by its list of coefficients, lowest power first: [c0, c1, ..., ck] stands for $\omega^k c_k + \cdots + \omega c_1 + c_0$ (so [3, 0, 2] is $\omega^2 \cdot 2 + 3$ , and [] is $0$ ), with no trailing zeros. Write ord_add(a, b) computing the ordinal sum $a + b$ . Rule: the terms of $a$ below the leading power of $b$ are absorbed, the coefficients at the leading power of $b$ add up, and the higher terms of $a$ remain.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.