  Our goal is to show that the standard model-theoretic concept of types can be
applied in the study of order-invariant properties, i.e., properties definable
in a logic in the presence of an auxiliary order relation, but not actually
dependent on that order relation. This is somewhat surprising since
order-invariant properties are more of a combinatorial rather than a logical
object. We provide two applications of this notion. One is a proof, from the
basic principles, of a theorem by Courcelle stating that over trees,
order-invariant MSO properties are expressible in MSO with counting
quantifiers. The other is an analog of the Feferman-Vaught theorem for
order-invariant properties.
