  We introduce the notion of decomposition space as a general framework for
incidence algebras and M\"obius inversion: it is a simplicial infinity-groupoid
satisfying an exactness condition weaker than the Segal condition, which
expresses decomposition. We work on the objective level of homotopy linear
algebra with coefficients in infinity-groupoids, developed along the way. To
any (complete) decomposition space there is associated an incidence (co)algebra
(with coefficients in infinity-groupoids), shown to satisfy a sign-free version
of the M\"obius inversion principle. Examples of decomposition spaces beyond
Segal spaces are given by the Waldhausen S-construction and by Schmitt
restriction species. Imposing certain homotopy finiteness conditions yields the
notion of M\"obius decomposition space, an extension of the notion of M\"obius
category of Leroux. We take a functorial viewpoint throughout, emphasising
conservative ULF functors, and show that most reduction procedures in the
classical theory are examples of this notion, and in particular that many are
examples of decalage of decomposition spaces. Our main theorem concerns the
Lawvere-Menni Hopf algebra of M\"obius intervals, which contains the universal
M\"obius function (but does not come from a M\"obius category): we establish
that M\"obius intervals form a decomposition space, which is in some sense
universal.
  NOTE: The notion of decomposition space was arrived at independently by
Dyckerhoff and Kapranov (arXiv:1212.3563) who call it unital 2-Segal space. Our
theory is quite orthogonal to theirs.
