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
    Nir, if you write the question in Hebrew I will translate it properly, and you could learn the names of the terms and make your future questions clearer.2011-02-11
  • 0
    היי אסף, למעשה זה ממש כך, העתקתי את הסימנים מהשאלה. הפונקציות מ-N ל - {1,2,3} פחות הפונקציות מ -N ל- {1,2} חיתוך עם קבוצת החזקה של NXN2011-02-11
  • 0
    Nir, it's not the notation but the terminology.2011-02-11
  • 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
    Ok, so ill do it that way, for each function from N to {1,2} I'll return a function that For n=0 returns 3, and for n>0 you'll get F(n-1), afcourse this is an injective function that covers {1,2,3} and the cardinality is א.2011-02-11
  • 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\}$

  • 0
    ok, so from one side I have this group, which it's power is less than all the functions from N to {1,2,3} on the other side I can argue that the functions from N to {1,2} has less power than our set, I just can't think of a way to do that.. I got a little mess with that. Am I in the right direction?2011-02-11
  • 0
    $|3^{\mathbb{N}}|=|2^{\mathbb{N}}|$, but you were asking about $3^{\mathbb{N}} \setminus 2^{\mathbb{N}}$, which is "most of" $3^{\mathbb{N}}$2011-02-11
  • 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