1
$\begingroup$

I need show that the two given sets: power set of natural numbers and power set of integers, have equal cardinality by describing a bijection from one to the other (describe the bijection with formula). Thanks in advance

$\endgroup$
5
$\begingroup$

Basically, given any bijection $f : X \to Y$, there exists a bijection $g : 2^X \to 2^Y$ where $g(A) = \{f(x)\ |\ x \in A\}$.

Hence, let $f$ be some bijection from the natural numbers (suppose they include $0$, but it doesn't matter) to the integers, such as $f(0) = 0$, $f(1) = 1$, $f(2) = -1$, $f(3) = 2$, $f(4) = -2$ etc.

$\endgroup$
4
$\begingroup$

If two sets have the same cardinality, their power sets have the same cardinality.

If $f: A\to B$ is $1-1$ and onto, then there is an obvious map $f^*:\mathcal{P}(A)\to\mathcal{P}(B)$.

$\endgroup$
  • 1
    $\begingroup$ Is there a proof for this "obvious map"? $\endgroup$ – proofy Mar 13 '13 at 14:50
  • $\begingroup$ I was leaving it to you to define the map and prove that it is $1-1$ and onto works. @proofy $\endgroup$ – Thomas Andrews Mar 13 '13 at 15:20
3
$\begingroup$

Once you have a bijection between the naturals and the integers, a bijection between the power sets is to apply the $\mathbb N \leftrightarrow \mathbb Z$ bijection ot the elements of the sets of naturals to get sets of integers.

$\endgroup$
3
$\begingroup$

You can use something similar to the function used to show that natural and integers have the same cardinality, that is

$f(x) = \begin{cases} \frac{x}{2} \iff \text{x is even} \\ -\lfloor\frac{x}{2}\rfloor \iff \text{x is odd} \end{cases}$

now, for a given set $A$ of naturals, you iterate $f$ to all his elements and obain the correspondant set $B$ of integers

$\endgroup$
  • $\begingroup$ It's the kind of answer I was looking for, thank you! $\endgroup$ – proofy Mar 13 '13 at 15:04
  • $\begingroup$ -3/2 is not an integer, which would be the result of f(3) in your scenario. Why not simply $-\dfrac{x+1}{2}$? $\endgroup$ – KeithS Mar 13 '13 at 16:17
  • $\begingroup$ In this "scenario" f(3)=-1 which is integer...simply note that he used floor in his notation $\endgroup$ – proofy Mar 13 '13 at 16:23
  • $\begingroup$ The floor notation is there for a reason :) $\endgroup$ – kaharas Mar 13 '13 at 18:02
2
$\begingroup$

There is a bijection between $\mathbb{N}$ and $\mathbb{Z}$. Let's call it f. So, there is a bijection between their power sets, by replacing each element in a set with its image under f.

$\endgroup$
0
$\begingroup$

You know you need a bijection between $\mathbb Z$ and $\mathbb N$, which is pretty much the hardest part of this proof. The following are two very simple ones:

$$x \in \mathbb Z; f(x) = \begin{cases} 2x \iff x >= 0 \\ 2x-1 \iff x < 0 \end{cases}$$

$$x \in \mathbb N; g(x) = f^{-1}(x) = \begin{cases} \dfrac{x}{2} \iff x \equiv 0 \pmod{2} \\ -\dfrac{x+1}{2} \iff x \equiv 1 \pmod{2} \end{cases}$$

$f(x)$ maps $\mathbb Z \to \mathbb N$, and $g(x)$ maps $\mathbb N \to \mathbb Z$. The fact that $g(x) = f^{-1}(x)$ is a useful illustration that the functions are invertible and thus the mapping is bidirectional, but it's not necessary for this proof. What is necessary is that for each map, there is no member of the destination set that is not produced by an element of the source set, nor any member of the source set that could produce two members of the destination, or a non-member of the destination. The functions are therefore "1:1 and unto" between the sets and thus valid bijections.

Once these are defined, we know that $|\mathbb Z| = |\mathbb N| = \aleph_0$. Given that fact, this becomes algebraic; the cardinality of the power set of any set $S$ is $|P(S)| = 2^{|S|}$. The equation $h(x) = 2^x$ is perfectly continuous and unambiguous for all $x$, and so if $|S_1| = |S_2|$, then $|P(S_1)|=|P(S_2)|$, therefore $|P(\mathbb Z)|=|P(\mathbb N)|=2^{\aleph_0}=\beth_1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.