Virtual Labs

Diagonalization

Which of these is an infinite set?

a: all rational numbers from

1

1

billion Explanation

Explanation

b: all real numbers from

5

10

Explanation

c: integers smaller than

2^{10}

Explanation

d: all of the above Explanation

Explanation

Consider a function where no two elements of the domain map to the same element in the co-domain and where the size of the domain and the co-domain is the same. Such function is ______.

a: injective Explanation

Explanation

b: surjective Explanation

Explanation

c: bijective Explanation

Explanation

d: none of these Explanation

Explanation

Consider a function where two elements of the domain may map to the same element in the co-domain and where the size of the domain and the co-domain is the same. Such function is ______.

a: injective Explanation

Explanation

b: surjective Explanation

Explanation

c: bijective Explanation

Explanation

d: none of these Explanation

Explanation

Consider a function where every element of the co-domain is mapped by some element of the domain. Such function is ______.

a: injective Explanation

Explanation

b: surjective Explanation

Explanation

c: bijective Explanation

Explanation

d: none of these Explanation

Explanation

A function

f(x)=4x

maps the set

\{1,2,3,4\}

to the set

\{1,2,...,16\}

. The function is ______.

a: injective Explanation

Explanation

b: surjective Explanation

Explanation

c: bijective Explanation

Explanation

d: none of these Explanation

Explanation

Let

A

be an infinite set and

B

be a finite set. Which statement must be true?

a: There exists a bijection from

A

B

Explanation

b: There exists a surjection from

A

B

Explanation

c: There exists an injection from

B

A

Explanation

d: There exists a bijection from

B

A

Explanation

Using Cantor's diagonalization method, which statement is true?

a: Every infinite set is countable Explanation

Explanation

b: The set of all infinite binary strings is countable Explanation

Explanation

c: The set of all finite binary strings is uncountable Explanation

Explanation

d: The set of all infinite binary strings is uncountable Explanation

Explanation

f: A \rightarrow B

is surjective and

|A| = |B|

, what can we conclude?

f

must be injective Explanation

Explanation

f

might be injective Explanation

Explanation

f

cannot be injective Explanation

Explanation

d: None of the above Explanation

Explanation

Given sets

A

and

B

where

|A| = \aleph_0

and

|B| = 2^{\aleph_0}

, which statement is true?

a: There exists a bijection between

A

and

B

Explanation

b: There exists a surjection from

A

B

Explanation

c: There exists an injection from

B

A

Explanation

d: None of the above Explanation

Explanation

Let

f: \mathbb{N} \rightarrow \mathbb{Q}

be a function. Which statement must be false?

f

could be injective Explanation

Explanation

f

could be surjective Explanation

Explanation

f

could be bijective Explanation

Explanation

f

must be neither injective nor surjective Explanation

Explanation

A

and

B

are sets with

|A| = |B|

, and

f: A \rightarrow B

is injective but not surjective, what can we conclude?

a: This is impossible Explanation

Explanation

A

and

B

must be finite Explanation

Explanation

A

and

B

must be infinite Explanation

Explanation

B

must be countable Explanation

Explanation