Size of the Hypothesis Space

Question

(I'm asking the same question as the one linked below, I simply don't have enough reputation to comment yet, but hopefully, this one will more clearly explain what me and the other asker both mean)

Let's say I have 2 possible binary features, $x_0$ and $x_1$. Each of them can take on 2 values, either a $0$ or a $1$. Finally, I have 2 possible labels: $y$ can either be a $0$ or a $1$.

This means there are 4 possible data points: $00$ , $01$ , $10$ , $11$ ,

And there are 2 possible labels: $0$ or $1$

The equation for the hypothesis space I've often seen says the size of it would be: $2^4$, since there are 2 possible labels and 4 possible data points.

But that doesn't make any sense, shouldn't we multiply the number of possible data points by the number of possible labels instead, leaving us with a hypothesis space of 8 and not 16?

$[00]0$, $[01]0$, $[10]0$, $[11]0$, $[00]1$, $[01]1$, $[10]1$, $[11]1$

Look at the cited question to see what I mean (but it's not just the cited question that says this, I've seen it everywhere)

abeltre1, How to calculate hypothesis space, URL (version: 2017-09-13): https://stats.stackexchange.com/q/303002

Answer 1

A hypothesis is a function $h:\mathcal{X} \to \mathcal{Y}$, where $\mathcal{X}$ is the feature space (the set of all possible inputs) and $\mathcal{Y}$ is the label space (the set of all possible outputs). In your example, $$ \begin{align} \mathcal{X} & = \{0,1\}^2 = \{(0,0), (0,1), (1,0), (1,1)\}, \\ \mathcal{Y} & = \{0,1\}. \end{align} $$ So a single hypothesis $h$ needs to assign a binary label to all 4 points in $\mathcal{X}$. This means that you can identify a particular hypothesis by a 4-digit binary number. For example, the hypothesis $h_{1011}$ would assign 1 to (0,0), 0 to (0,1), 1 to (1,0), and 1 to (1,1). It should be clear that the total number of hypotheses is equal to the number of 4-digit binary strings, which is $2^4$.