IMHO mathematics is more or less a formalization of practical intuitions

The mathematics used for describing the universe most certainly are, by construction; but any particular mathematical structure is not linked to or unique to this universe. That is, the properties of the universe force us to use one specific mathematical structure to describe it, but that doesn't mean that this is the only possible mathematical structure. This paper explains something similar, in a better way.

For example the concept of natural numbers [...] [and] Set theory

The exact properties of the natural numbers are defined by a set of axioms, and there is no reason why mathematicians in a universe without practical intuition of the natural numbers (work with me...) couldn't still propose the axioms and derive the consequences of them (prime numbers etc.). And similarly with set theory (This actually provides a good example: infinite sets don't have a physical basis but we can still work with them abstractly).