3
$\begingroup$

How can I calculate the cardinality of $\left(\{1,2,3\}^{\mathbb{N}} - \{1,2\}^{\mathbb{N}}\right)\cap\mathcal{P}(\mathbb{N}\times\mathbb{N}).$ where $A^B$ is the set of all functions $f\colon B\to A$.

thanks

  • 0
    תודה, אקח לתשומת ליבי.2011-02-11

2 Answers 2

2

Since the set of all functions from $\mathbb{N}$ to $\{1,2,3\}$ has cardinality $2^{\aleph_0}$, you certainly know that you have at most $2^{\aleph_0}$ elements in your difference.

So to show that $\{1,2,3\}^{\mathbb{N}} - \{1,2\}^{\mathbb{N}}$ has cardinality exactly $2^{\aleph_0}$, it is enough to produce $2^{\aleph_0}$ functions from $\mathbb{N}$ to $\{1,2,3\}$ whose image is not contained in $\{1,2\}$.

Now, hopefully you agree that there are just as many functions from $\mathbb{N}$ to $\{1,2\}$ as there are from $\mathbb{N}-\{1\}$ to $\{1,2\}$? Now, take a function from $\mathbb{N}-\{1\}$ to $\{1,2\}$, and extend it to all of $\mathbb{N}$ in such a way that you guarantee the image includes $3$. That will produce at least $2^{\aleph_0}$ functions in $\{1,2,3\}^{\mathbb{N}}$ that are not in $\{1,2\}^{\mathbb{N}}$.

  • 0
    @Nir: To conclude something about cardinality, you'll have to show that this correspondence is injective (different functions from $\mathbb{N}$ to $\{1,2\}$ yield different functions from $\mathbb{N}$ to $\{1,2,3\}$ whose image includes $3$) (easy); that will not show the cardinality of the set you want is *exactly* $2^{\aleph_0}$, it will show it is **at least** that.2011-02-11
2

So you have all the functions from $\mathbb{N} \to \{1,2,3\}$ that are not in $\mathbb{N} \to \{1,2\}$? Each of these functions is a subset of P($\mathbb{N} \times \mathbb{N}$), so that part is not important. Hint: you just need one 3 in the image to take it out of $\mathbb{N} \to \{1,2\}$

  • 1
    @Nir Avnon: Don't say "group"; that means something else. And the usual terminology in English is "cardinality", not "power" (the "power of a set" is likely to be confused with the set of all subsets of the set, which is called the power set).2011-02-11