Does the following conditions ensure the infinite set B is enumerable?

67 Views Asked by At

Let $B$ be an infinite set.

Suppose we take input set as $B$ and output set as $\mathbb{N}$

(1) $∀\ b∈ B, ∃!\ n∈ \mathbb{N}, \text{output $(b)$ is $n$}$

This ensures $f:B→N$ exist.

(2) $∀\ n∈ \mathbb{N}, ∃!\ b∈ B, f(b)=n$

Does this ensure $B$ is enumerable ?

1

There are 1 best solutions below

0
On BEST ANSWER

If there exists a function with the attributes (1) and (2) you stipulated, then $B$ is indeed enumerable (i.e. “countable”). But note that this is not determined by $B$ alone. The countability of $B$ also depends on what functions are assumed to exist.

If you’re working in a set theory like $\mathsf{ZFC}$, it’s possible that in one model of $\mathsf{ZFC}$, call it $\mathfrak{M}_{1}$, the requisite function exists (thus “according to $\mathfrak{M}_{1}$$B$ is countable), but in a transitive submodel $\mathfrak{M}_{2}$ no such function exists (thus “according to $\mathfrak{M}_{2}$$B$ is uncountable)

This “relativity” of notions like countability is one tricky aspect of set theory that’s not always well explained in introductory treatments (but it follows as a consequence of the Lowenheim-Skolem theorem on the existence of countable models)