-1

Consider $f: \mathcal P(\mathbb N) \to \{g: \mathbb N \to \{0, 1\}\}$. I'll try to define $f$ in a such a way that it's a bijection.

Cardinality of each element in $\mathcal P(\mathbb N)$ will determine the number of $1$s in a binary string. The value of an element of $X \in \mathcal P(\mathbb N)$ will determine the position of $1$ in a binary string.

By definition(?) of set, each element of $\mathcal P(\mathbb N)$ is unique so every element of $\mathcal P(\mathbb N)$ will be mapped to a unique binary string. This makes $f$ injective.

The string of $0$s is mapped to the empty set and the string of $1$s is mapped to $\mathbb N.$ The rest of the binary strings have at least one $1$. By definition, $f$ maps every $n$-set to a binary string with $n$ $1$s which means $f$ is surjective.

Does such an $f$ work and is it a bijection?

Edit:

I am not asking for a reference to a proof of an existence of $f$. I am just interested if my own thoughts make sense.

user1097750
  • 123
  • 1
    Does this answer your question? Bijection $f:\mathcal{P}(A)\to(A\to {0,1})$ – Anne Bauval Oct 29 '22 at 21:56
  • @AnneBauval, No because my question asked if my own thoughts about this problem made sense. – user1097750 Oct 29 '22 at 22:08
  • Yes: it confirms your "own thoughts", offering the usual much shorter description of $f$ ($f(A)$ is simply the characteristic function of $A$), and answers your 2 questions: this $f$ even "works" for any set (not only $\Bbb N$), and it is a bijection (a real proof is given). – Anne Bauval Oct 30 '22 at 02:25
  • 1
    Your "proof" of injectivity was not correct: "each element of $\mathcal P(\mathbb N)$ is unique" means nothing and the rest of the sentence only means that $f$ is well defined. Your proof of surjectivity was incomplete. Your argument is not sufficient. – Anne Bauval Oct 30 '22 at 02:32
  • If an element in the power set is unique, then there are at least two $x, y \in \mathcal P(\mathbb N) $ with $x \ne y $. They map to binaries $a, b$ with $a \ne b.$ – user1097750 Oct 30 '22 at 12:38

1 Answers1

1

Yes, this is exactly a method you can use to describe such a bijection.

You can see the same method described here on this masterclass by Augustin Rayo.

yolo
  • 509
  • 1
    Your link does not deal with the OP's very basic question, but (among others) to the more intricate problem of equipotency between $\mathcal P(\mathbb N)$ and $[0,1].$ – Anne Bauval Oct 30 '22 at 02:42