A Universe of Sorts

§ A natural vector space without an explicit basis

On learning about infinite dimensional vector spaces, one learns that we need to use the axiom of choice to assert that every such vector space has a basis; indeed, it's equivalent to the AoC to assert this. However, I had not known any "natural" examples of such a vector space till I studied the proof of the barvinok algorithm. I produce the example here. Consider a space such as

S \equiv \mathbb R^3

. Now, consider the vector space spanned by the indicator functions of polyhedra in

S

. that's a mouthful, so let's break it down. A polyhedra is defined as a set of points that is defined by linear inequalities:

P \equiv \{ x \in S : a_i \cdot x \leq b_i, i \in [1\dots n] \}

, for all

a_i \in S

b \in \mathbb R

. The indicator functions are of the form:

[poly]: S \rightarrow \mathbb R; [poly](x) \equiv \begin{cases} 1 & x \in poly \\ 0 & \text{otherwise} \end{cases}

we can define a vector space of these functions over

\mathbb R

, using the "scaling" action as the action of

\mathbb R

on these functions: The vector space

V

is defined as the span of the indicator functions of all polyhedra. It's clearly a vector space, and a hopefully intuitive one. However, note that the set we generated this from (indicators of polyhedra) don't form a basis since they have many linear dependencies between them. For example, one can write the equation:

*---*   *-*   *-*   *
|###|   |#|   |#|   |
|###| = |#| + |#| - |
|###|   |#|   |#|   |
*---*   *-*   *-*   *