We usually think of mathematics as being founded on "axioms". You prove something by starting with axioms (or with theorems that other people have already proven) and using valid logic to derive whatever you can.
People usually say that axioms are self-evident propositions, or even just assumptions, but I think it makes a lot more sense to think of them as definitions. Let's define 4 as 3 + 1, 3 as 2 + 1, and 2 as 1 + 1. Let's also define (x + y) + z as x + (y + z). Now, it's possible that our definitions contradict each other—maybe we've defined the same thing twice, in incompatible ways. But more on that in a moment. Look what we can derive from these definitions:
4 = 3 + 1 (by definition of 4) = (2 + 1) + 1 (by definition of 3) = 2 + (1 + 1) (by definition of +) = 2 + 2 (by definition of 2)
Boom. We've proven that 2 + 2 = 4, using nothing but definitions. Now there's just one question: what if our definitions contradict each other?
Well, in all likelihood, they don't contradict each other. In mathematics, the "standard" set of basic axioms, ZFC, has been around for a while, and nobody has ever found a contradiction in it. It's likely that nobody will.
So, math may have paradoxes, but only in the sense of things that are true but counterintuitive. We haven't managed to prove any actual contradictions. And it is possible to define everything in mathematics without circularity. You can define things circularly (a la "What the Tortoise Said to Achilles"), but you don't have to.