I'm trying to find the cardinality of a certain set and I'm stuck. The problem is, we haven't learned about cardinality nor about any of its rules and equalities. We are asked to find a set whose "cardinality" is equal to the given set, and prove the sets are equivalent by finding a bijective and surjective function between them. The question is:
"Let $\mathcal{P}(\mathbb{N}) $ be the power set of $\mathbb{N}$. We define the following subset, $B \subseteq \mathcal{P}(\mathbb{N}) $, in the following way:
$B=\lbrace A \in \mathcal{P}(\mathbb{N}) |$ if $p\in A$ is a prime number then $\forall n\in \mathbb{N} \Rightarrow$ $n\cdot p\in A \rbrace$
What is the cardinality of $B$? Prove your claim by finding an appropriate bijective and surjective function."
As I'd stated before, we cannot use any equalities associated with cardinalities. All we can do is guess and try to prove. I would appreciate any hints as to how to define an appropriate function.
An alternative answer. Let $C=\{n\in\mathbb N\mid n\text{ is composite}\}$.
Then $C$ is countably infinite, and $\mathcal P(C)\subseteq B$, since every subset of $C$ specifically contains no primes, so satisfies the condition for $B$.
Since $C$ has the same cardinality as $\mathbb N$, $\mathcal P(C)=\mathcal P(\mathbb N)$, and $$|\mathcal P(\mathbb N)|=|\mathcal P(C)|\leq |B|\leq |\mathcal P(\mathbb N)|$$
A fully-defined bijection is a bit more painful. I will assume $\mathbb N$ does not include $0$.
Let $P$ be the primes.
Given a pair $x=(S,T)$ where $S\subsetneq P$ and $T\subseteq \mathbb N$ we first define $A_S=\cup_{p\in S} p\mathbb N$. Then enumerate:
$$\mathbb N\setminus (A_S\cup P)=\{1=b_S(1)<b_S(2)<\cdots<b_S(n)<\cdots \}$$ This set is alway infinite since $S\neq P$, so if $p\notin S$, then no power of $p$ is in $A_S$.
Now define $Q_x=A_S\cup b_s(T)$. Show that $Q_x\in B$ and $x\mapsto Q_x$ is one-to-one.
What elements of $B$ are not covered by this function?
Only the cases where all primes are in the set. There are only two such elements, $\mathbb N$ and $\mathbb N\setminus\{1\}$.
Now, $\mathcal P(P)\setminus\{P\}$ can be explicitly seen to be the same cardinality as $\mathcal P(P)$. For example, by defining $f:\mathcal P(P)\to \mathcal P(P)\setminus\{P\}$ so that:
$$f(S)=\begin{cases} \{2\}&S=P\\ \{p_{n+1}\}&S=\{p_{n}\}\\ S&\text{otherwise} \end{cases}$$
Similarly, define a bijection between $B$ and $B\setminus\{\mathbb N,\mathbb N\setminus\{1\}\}$.
Finally, the last trick is to find a bijection between $\mathcal P(\mathbb N)$ and $\mathcal P(P)\times\mathcal P(\mathbb N)$.
In general, $\mathcal P(A)\times\mathcal P(B)$ is easily seen to be the same cardinality as $\mathcal P(A\dot\cup B)$, where $A\dot\cup B$ is the disjoint union of $A,B$. It's easy to show that $P\dot\cup \mathbb N$ has the same cardinality as $\mathbb N$. So we have this chain of bijections:
$$\mathcal P(\mathbb N)\to \mathcal P(P)\times\mathcal P(\mathbb N)\to (\mathcal P(P)\setminus\{P\})\times \mathcal P(\mathbb N)\to B\setminus\{\mathbb N,\mathbb N\setminus\{1\}\}\to B$$
The last is the only one we haven't defined. It's done much the way that we defined $f$ - enumerate some infinite set of elements $b_1,b_2,\dots \in B\setminus\{\mathbb N,\mathbb N\setminus\{1\}\}$, then define $$g(b)=\begin{cases} \mathbb N&b=b_1\\ \mathbb N\setminus \{1\}&b=b_2\\ b_n&b=b_{n+2}\\ b&\text{otherwise} \end{cases}$$