  This is the first in a series of papers devoted to the theory of
decomposition spaces, a general framework for incidence algebras and M\"obius
inversion, where algebraic identities are realised by taking homotopy
cardinality of equivalences of $\infty$-groupoids. A decomposition space is a
simplicial $\infty$-groupoid satisfying an exactness condition, weaker than the
Segal condition, expressed in terms of active and inert maps in Delta. Just as
the Segal condition expresses composition, the new condition expresses
decomposition, and there is an abundance of examples in combinatorics. After
establishing some basic properties of decomposition spaces, the main result of
this first paper shows that to any decomposition space there is an associated
incidence coalgebra, spanned by the space of 1-simplices, and with coefficients
in $\infty$-groupoids. We take a functorial viewpoint throughout, emphasising
conservative ULF functors; these induce coalgebra homomorphisms. Reduction
procedures in the classical theory of incidence coalgebras are examples of this
notion, and many are examples of decalage of decomposition spaces. An
interesting class of examples of decomposition spaces beyond Segal spaces is
provided by Hall algebras: the Waldhausen S-construction of an abelian (or
stable infinity) category is shown to be a decomposition space. Note: The
notion of decomposition space was arrived at independently by Dyckerhoff and
Kapranov (arXiv:1212.3563) who call them unital 2-Segal spaces. Our theory is
quite orthogonal to theirs: the definitions are different in spirit and
appearance, and the theories differ in terms of motivation, examples and
directions.
