Prove or disprove:

$(\{1,2,3 \}^{\Bbb N})\setminus (\{ 1,2 \}^{\Bbb N})=\{3\}^{\Bbb N}$

This is what did, since these are the functions from the naturals to x and functions are ordered pairs:

$n\in \Bbb N$

$\{ (n,1 ),(n, 2),(n, 3)\}\setminus\{(n, 1),((n, 2)\}=\{(n, 3)\}=\{3\}^{\Bbb N}$

Is this correct ?


Edit: forgot the $\{\}^{\Bbb N}$

Edit: From the defintion $F\subseteq X(domain) \times Y(range)$

So here: $\Bbb N \times \{1,2,3 \}=\{ (n,1 ),(n, 2),(n, 3)\}$

  • $\begingroup$ Do the parenthesis around $\{1,2,3\}$ and $\{1,2\}$ mean something special? $\endgroup$ Commented Dec 6, 2013 at 16:15
  • $\begingroup$ @Magdiragdag it denotes that it's a set. $\endgroup$
    – GinKin
    Commented Dec 6, 2013 at 16:24
  • $\begingroup$ The $($ and $)$, not the $\{$ and $\}$. But I see you added the $\{ \}^{\mathbb N}$. $\endgroup$ Commented Dec 6, 2013 at 16:42
  • $\begingroup$ Writing $\mathbb N\times \{1,2,3\} = \{(n,1),(n,2),(n,3)\}$ does not make sense -- the left-hand side is a concrete set with infinitely many elements, but the right hand side is not any particular set until you specify a value for $n$ -- and once you do specify a value for $n$ it will be a set with 3 elements, which obviously is not he same as a the infinite set $\mathbb{N}\times\{1,2,3\}$. $\endgroup$ Commented Dec 6, 2013 at 17:24
  • $\begingroup$ @HenningMakholm I see. so how do you approach this: $\Bbb N \times \{1,2,3 \} \setminus \Bbb N \times \{1,2 \}$ ? Does it has a simpler representation ? $\endgroup$
    – GinKin
    Commented Dec 6, 2013 at 17:35

2 Answers 2


It looks like you're confusing yourself at several points by failing to distinguish between a set and its element, as well as between a subset and an element. In particular your comments look like you think $\{1,2,3\}^{\mathbb N}$ and $\mathbb N\times\{1,2,3\}$ are the same set -- but that is completely wrong. From the beginning:

$\{1,2,3\}^{\mathbb N}$ is the set whose elements are all functions $\mathbb N\to\{1,2,3\}$ -- that is, something is an element of $\{1,2,3\}^{\mathbb N}$ if and only if it is a function defined on $\mathbb N$ such that the value of the function is always an element of $\{1,2,3\}$.

Just to have something to speak about, let's write down a few concrete elements of $\{1,2,3\}^{\mathbb N}$:

$$ \begin{align} f(n) =& (n\bmod 3)+1 \\ g(n) =& \begin{cases} 2 & \text{if $n$ is a prime} \\ 3 & \text{otherwise} \end{cases} \\ h(n) =& \min(n,3) \\ k(n) =& 1 \end{align} $$

So we have $\{1,2,3\}^{\mathbb N} = \{f,g,h,k,\ldots\}$.

Formally each of these functions is iself represented by a set, namely $$ \begin{align} f(n) =& \{(1,2), (2,3), (3,1), (4,2), (5,3), (6,1), \ldots \} \\ g(n) =& \{(1,3), (2,2), (3,2), (4,3), (5,2), (6,3), \ldots \} \\ h(n) =& \{(1,1), (2,2), (3,3), (4,3), (5,3), (6,3), \ldots \} \\ k(n) =& \{(1,1), (2,1), (3,1), (4,1), (5,1), (6,1), \ldots \} \end{align}$$

Each of these sets is a subset of $\mathbb N\times \{1,2,3\}$:

$$\mathbb N\times \{1,2,3\} = \{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), \ldots, (42,1), (42,2), (42,3), (43,1), \ldots \}$$

Note that $N\times \{1,2,3\}$ is a very different set from $\{1,2,3\}^{\mathbb N}$. The pair $(2,3)$ is an element of $\mathbb N\times \{1,2,3\}$, but is not an element of $\{1,2,3\}^{\mathbb N}$. On the other hand, $f$ above is an alement of $\{1,2,3\}^{\mathbb N}$ but not an element of $\mathbb N\times\{1,2,3\}$.

It is true that $(2,3)$ is an element of $f$ which itself is an element of $\{1,2,3\}^{\mathbb N}$, but that does not make $(2,3)$ an element of $\{1,2,3\}^{\mathbb N}$.

Every element of $\{1,2,3\}^{\mathbb N}$ is a subset of $\mathbb N\times \{1,2,3\}$, but the converse is not true: there are subsets of $\mathbb N\times\{1,2,3\}$ that are not elements of $\{1,2,3\}^{\mathbb N}$. For example, the empty set, or $\{(1,2), (1,3), (4,2)\}$, or $\mathbb N\times\{1,2,3\}$ itself (every set is a subset of itself).

Now we're ready to look at $\{1,2,3\}^{\mathbb N}\setminus \{1,2\}^{\mathbb N}$. This is, by defintion, the set whose elements is anything that is a function $\mathbb N\to\{1,2,3\}$ but is not also a function $\mathbb N\to\{1,2\}$.

Among our examples above $f$, $g$, and $h$ are elements of $\{1,2,3\}^{\mathbb N}\setminus \{1,2\}^{\mathbb N}$, because they are all in $\{1,2,3\}^{\mathbb N}$ but not in $\{1,2\}^{\mathbb N}$ (they can't be because $f(2)=3\notin\{1,2\}$, for example).

On the other hand, $k$ is not in $\{1,2,3\}^{\mathbb N}\setminus \{1,2\}^{\mathbb N}$, because it is an element of $\{1,2\}^{\mathbb N}$, and therefore becomes excluded by the set difference operation.

NEITHER of our four example functions are members of $\{3\}^{\mathbb N}$ -- in fact the only element of $\{3\}^{\mathbb N}$ is the function that is $3$ everywhere, represented by the set $$ \{(1,3), (2,3), (3,3), (4,3), (5,3), \ldots\}$$

In order to show that two sets are not equal, it suffices to find something that is an element of one but not of the other. Here a possible counterexample could be our $f$, because, as we have seen, it is an element of $\{1,2,3\}^{\mathbb N}\setminus \{1,2\}^{\mathbb N}$ but not of $\{3\}^{\mathbb N}$. So the two sets are not equal.

  • $\begingroup$ You cleared up so many misunderstandings I had. Thank you. $\endgroup$
    – GinKin
    Commented Dec 6, 2013 at 20:05

Informally, the set $\{1,2,3\}^{\mathbb N}$ is the set of infinite sequences $(a_1,a_2,a_3,\ldots)$ where each $a_i$ is equal to $1$, $2$, or $3$.

So you can see right away that your equation can't be valid: the left-hand side is the set of infinite sequences of $1$'s, $2$'s, and $3$'s that contain at least one $3$; and the right-hand side is the sequence $(3,3,3,\ldots)$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .