Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.


share|cite|improve this question
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. – Asaf Karagila Feb 11 '11 at 15:14
היי אסף, למעשה זה ממש כך, העתקתי את הסימנים מהשאלה. הפונקציות מ-N ל - {1,2,3} פחות הפונקציות מ -N ל- {1,2} חיתוך עם קבוצת החזקה של NXN – user6163 Feb 11 '11 at 15:37
Nir, it's not the notation but the terminology. – Asaf Karagila Feb 11 '11 at 15:40
תודה, אקח לתשומת ליבי. – user6163 Feb 11 '11 at 17:42
up vote 2 down vote accepted

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}}$.

share|cite|improve this answer
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 א. – user6163 Feb 11 '11 at 18:08
@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. – Arturo Magidin Feb 11 '11 at 18:18

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\}$

share|cite|improve this answer
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? – user6163 Feb 11 '11 at 15:17
$|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}}$ – Ross Millikan Feb 11 '11 at 15:30
@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). – Arturo Magidin Feb 11 '11 at 17:37
Thanks arturo.. – user6163 Feb 11 '11 at 17:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.