1
$\begingroup$

Currently working on some set theory problems, in particular I need to prove that

$|[0, 1]^\mathbb{N}| = |\{0, 1\}^{\mathbb{N} \times \mathbb{N}}|$

First let me say I'm not looking for a solution to the problem, as this is an assignment question, I only provide it as context for the level of understanding I'm at.

All I know, is that $\{0, 1\}^{\mathbb{N} \times \mathbb{N}}$ is the set of all functions $F:\mathbb{N} \times \mathbb{N} \rightarrow \{0, 1\}$

I'm not sure what such a function would look like. My initial thought was that it maps a pair of natural numbers, to an ordered pair of the form (0, 1) but I realized pretty quickly that doesn't make much sense. Does it map a pair of natural numbers, to a pair of strings of 0s and 1s of any size?

If someone could give me an example of a function, and point me to a good resource for some of this notation, that'd be fantastic. My textbook seems to mostly take the notation for granted.

$\endgroup$
  • $\begingroup$ $\{0, 1\}^{\mathbb{N}}$ denotes the set of all sequences consisting only of $0$'s and $1$'s. $\endgroup$ – Thomas Shelby Dec 6 '18 at 4:19
  • 1
    $\begingroup$ Unfortunately not. I think, though, that your first comment answered my question. It seems my original interpretation was correct. $\endgroup$ – Sunwar Dec 6 '18 at 4:27
2
$\begingroup$

A function $F:\mathbb{N}\times \mathbb{N} \to \{0,1\}$ (“from $\mathbb{N}\times \mathbb{N}$ to $\{0,1\}$”) assigns to each element of the set $\mathbb{N}\times \mathbb{N}$, ordered pairs of integers, an element in the set {0,1}, either 0 or 1. So if $m$ and $n$ are natural numbers, $F((m,n))=0$ or $F((m,n))=1$.

Some examples: let $F:\mathbb{N}\times \mathbb{N} \to \{0,1\}$ be given by $(m,n)\mapsto 0$. On the left of “$\to$”, we have the domain of our function. On the right, we have our codomain. On the left of “$\mapsto$”, we have some arbitrary element in the domain. On the right, we have the explicit element in the codomain that $(m,n)$ will map to. So, in particular, $F((m,n))=0$ for all natural numbers $m,n$.

Let $F: \mathbb{N}\times \mathbb{N} \to \{0,1\}$ be given by $(m,n)\mapsto 1$ if $m=n$ and $(m,n)\mapsto 0$ if $m\not = n$.

Visually for these examples, we can think of

0,0,0, ...

0,0,0, ...

...

...

0,0,0, ...

...

and

1,0,0, ...

0,1,0, ...

0,0,1, ...

...

...

0,0,0, ...

...

where the locations represent elements in $\mathbb{N}\times \mathbb{N}$, i.e.

(1,1), (1,2), (1,3), ...

(2,1), (2,2), (2,3), ...

...

...

($m$,1), ($m$,2), ... , ($m$,$n-1$), ($m$, $n$), ...

...

and the values that appear in those locations represent the element of $\{0,1\}$ which $F$ maps its location to.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.