Is this a Powerset? What does is actually look like?

Question

So I'm working on a homework problem and it tells us function $f: \mathbb{N} \to \mathscr{P(\mathbb{N})}$ is given by $f(n)=\left\{kn | k\in \mathbb{N} \right\} = \left\{n, 2n, 3n, ...\right\}$. What does this even mean? I've tried looking through the textbook and there was mention of the Powerset with this notation but I can't tell if this is still referring to that. If it is, does that the codomain of $f(n)$ is basically the subsets $\left\{ \left\{1,2,3,...\right\}, \left\{2,4,6,...\right\}, \left\{3,6,9,...\right\},... \right\}$? And if so, I know that the Powerset has cardinality $2^n$ but what does that mean for a set of sets like this?

Answer 1

The codomain of $f$ is $\mathcal P(\mathbb N)$, because we have defined $f$ to be a function $\mathbb N\to\mathcal P(\mathbb N)$. In general, for a function $g\colon A \to B$, the codomain of $g$ is $B$.

Saying that $f$ is a function from $\mathbb N$ to $\mathcal P(\mathbb N)$ means that $f$ is a function that takes in an element of $\mathbb N$ (i.e., a natural number) and returns an element of $\mathcal P(\mathbb N)$ (i.e., a set of natural numbers).

The image of $f$ is the set of all values that $f$ can take: in this case, the image of $f$ is: $$ \{\{1,2,3,\dots\},\{2,4,6,\dots\},\{3,6,9,\dots\},\cdots\} $$ as you worked out. The image of $f$ is not equal to the codomain of $f$, since some elements of $\mathcal P(\mathbb N)$, such as $\{2,3,5,7,\dots\}$, do not arise from applying $f$ to some natural number. We say that $f$ is not surjective.

---

If $X$ is a finite set of order $n$, then $\mathcal P(X)$ has order $2^n$. However, $\mathbb N$ is an infinite set, so this result doesn't apply immediately.

There is still something we can say, however. For finite sets, we observe that $2^n$ is the number of functions from a set $X$ of size $n$ to a set $\{a,b\}$ of size $2$: we have two choices for each element of $X$. If we write $[X\to\{a,b\}]$ for this set of functions, then there is a natural one-to-one mapping between $[X\to\{a,b\}]$ and $\mathbb P(X)$: given some subset $Y\subset X$, we can form the function that sends $x$ to $a$ if $x\in Y$ and sends $x$ to $b$ if $x\not\in Y$.

Going in the other direction, if we have some function $g\colon X\to\{a,b\}$ then we can form the set of all $x\in X$ such that $g(x)=a$. These two procedures are inverse to each other.

Since $[X\to\{a,b\}]$ has size $2^n$.

Exactly the same thing can be done if $X$ is an infinite set. We sometimes like to say that the size of the set of natural numbers $\mathbb N$ is something called $\aleph_0$. We can then define $2^{\aleph_0}$ to be the size of the set $[\mathbb N\to\{a,b\}]$ by analogy with the finite case.

Then we can form exactly the same one-to-one correspondence as above, and this gives us justification to say that the size of the powerset $\mathbb P(\mathbb N)$ is equal to the size of $[\mathbb N\to\{a,b\}]$: $$ |\mathcal P(\mathbb N)| = 2^{|\mathbb N|} $$

and similarly if we replace $\mathbb N$ with any set.

Answer 2

The function $f$ assigns to each natural number $n$ a subset of $\mathbb{N}$. The description of $f$ says that $f(n)$ is the set of multiples of $n$. So, for instance, $f(1)=\mathbb{N}$ and $f(2)$ is the set of positive even integers.

The codomain of $f$ is the set $\mathscr{P(\mathbb{N})}$, that is, the set of subsets of $\mathbb{N}$ (also called its powerset).