What is the correct name for the space of genotypes and fitness? I'm looking for a formal definition of the space that consists of the dimensions gene 1-N and the fitness.

In literature there is often the search space mentioned, but it only contains all genes. If I extend the search space by the fitness dimension, how can I call this space?
In the context of evolution and evolutionary algorithms it's called a fitness landscape.  In other areas such as statistical physics it's called an energy landscape.

If you have a continuous landscape (in evolution you typically don't) things are fairly straightforward.  From Wikipedia: 


  In mathematical terms, an energy landscape can be defined as a pair $(X, f)$ consisting of a topological space $X$ representing the physical states or parameters of a system together with a continuous function $f: X → \mathbb{R}$ representing the energies associated to these states or parameters such that the image of $f$ represents a hypersurface in $\mathbb{R}^n$."


In discrete landscapes things are more complicated since we need to specify which states neighbour each other, essentially giving us a graph underlying the set of solutions.  What you end up with is not as clean as you'd like.  It's a triple $(X,N, f)$, where $X$ is the set of solutions (i.e., possible genotypes), $N:X\to 2^X$ is a neighbourhood function, and $f:X\to\mathbb{R}$ is the fitness function.

For a treatment of these discrete fitness landscapes that should satisfy you with regard to mathematical rigour I would direct you to this survey paper by Reidys and Stadler.