I'm trying to solve a problem in which this notation occurs. On the one hand, I have the question of what it means that a function f is an element of {0,1} ^ N and what {0,1} ^ N means.
Thank you in advance!
Asked
Active
Viewed 687 times
0
-
2It means that $f$ is an application from your set $N$ into the set ${0,1}$. – Tito Eliatron Nov 02 '20 at 19:32
-
1what is $N$ in your example? – supinf Nov 02 '20 at 19:39
2 Answers
3
It means that $f$ is a boolean function [the image is $\{0,1\}$], where the domain $S$ has $N$ elements.
The function $f$ can be thought of as a vector of length $N$ as well, where writing $S=\{s_1,\ldots, s_n\}$, then $f$ can be written $f=(f(s_1),f(s_2),\ldots, f(s_n))$.
Mike
- 20,434
2
$X^Y$ denotes the set of functions from $Y$ to $X$. If you have $\lbrace 0,1 \rbrace^{\mathbb{N}}$, this denotes "functions" from $\mathbb{N}$ to $\lbrace 0,1 \rbrace$, i.e. the set of sequences of $0$ and $1$.
TheSilverDoe
- 29,720
-
You could add that it is also equipotent to $\mathcal P(\mathbb N)$ since we can describe elements in subsets of $\mathbb N$ with $0$ (does not belong to) or $1$ (belongs to) for membership. – zwim Nov 02 '20 at 19:44
-
@zwim I would not say that it is $\mathcal{P}(\mathbb{N})$. It is in bijection with $\mathcal{P}(\mathbb{N})$, yes, but formally, these two sets are not the same (one has functions as elements, the other has subsets of $\mathbb{N}$). – TheSilverDoe Nov 02 '20 at 19:46
-
-
1I know, that was I wanted to write in the first place, but you reacted too quickly. – zwim Nov 02 '20 at 19:51