"Relativism" is a modern term for one side in one variation of this debate. The traditional names for the sides would be "realism" and "nominalism". And to understand the question they're arguing about, I'll ask a question: is a hot dog a sandwich?
The internet has taught us there are many people who feel strongly that a hot dog is a sandwich, and many other people who feel just a strongly that a hot dog is not a sandwich. They argue about how to define the term "sandwich" -- does "sandwich-ness" come from the presence of bread? Must there be a certain number of pieces of bread? Must the bread be in one of a small set of permitted shapes? What types of things can be in or on the bread?
These people are searching for some thing they can predicate of all sandwiches. Some property that is indisputably possessed in common by every sandwich everywhere. What sort of thing is that?
Anyone who's sat through an intro to philosophy course probably knows Plato's answer. We are, metaphorically, chained to a rock in a cave, facing the back wall. We know there must be a source of brilliant light (perhaps outside the mouth of the cave), since although we can't see it directly we see the light reflected on the cave wall and can tell what direction it's coming from. We know there are other things out there, too, because there are shadows cast on the wall as they move back and forth in front of the light. The metaphor, of course, is that objects in the world are like the shadows cast on the wall of the cave: distorted representations of true forms which exist somewhere else, but that we recognize despite the odd angles or movements they make. Thus we get Plato's theory of forms, which postulates an ethereal-ish realm, inaccessible to us mortals, in which the ideal forms of things exist. We recognize disparate things in this world as sandwiches because they all, to some extent, partake of the Form of Sandwich. Or in cave-metaphor terms, they all are shadows cast on the wall by the Ur-Sandwich moving about in front of the light, and though they may look superficially quite different from each other, we recognize the common origin of them all (Plato had a quasi-religious explanation for our knowledge of the forms and what they were).
To be a realist is to be committed, on some level, to a theory not dissimilar from Plato's. We can dress it up in nicer terminology, and cover up some of the seeming absurdity of there being an ideal Form of Sandwich in some astral plane somewhere, but ultimately this is what realism says. In some cases it's used to talk about properties (such as color: "red" may refer to many different hues, but we use a single umbrella term for all of them -- in what sense do they all share "redness"?). In mathematical realism, it is used to talk about (roughly) theorems of mathematical systems. Mathematical realism is a commitment to the existence of these theorems in some form which is independent of human minds; the theorem would exist, and be a theorem, regardless of whether any human ever discovered or proved it.
In many ways this is a very convenient way to talk about mathematics (as well as to talk about a lot of other things). It allows us to say that "two and two make four" and "deux et deux font quatre" are in some way the same statement, though expressed in different words. It gives us an entity which can tie together many disparate things and serve as the commonality between them all.
But it also seems ludicrous and overcomplex to a lot of people. One of the earliest critiques of Plato's theory of forms was that they must be infinite in number (in brief: given any set of objects and a form they all partake of, it is possible to prove the necessity of another form to tie together the first form and the objects; from there, yet another can be proven as necessary to tie together the objects and the first two, and so on to infinity). Willard Van Orman Quine joked at the proliferation of entities in such systems (leading to absurdities such as the existence of nonexistence), dubbing it "Plato's beard" and claiming that it would dull the edge of Occam's razor.
Enter nominalism. Nominalism, simply put, says that there is no Form of Sandwich, or property of "sandwich-ness", or anything else that all sandwiches have in common apart from being given the label "sandwich" by people. Membership in the set of sandwiches -- or any of the other categories realists invent entities to provide commonality for -- is arbitrary, and we identify membership in that set not by recognizing some common property possessed independently of the label, but by rote memorization or heuristic application of cultural guidelines.
Nominalism, then, would deny that a mathematical theorem has any existence independent of the minds of humans. It does not sit timelessly, waiting to be discovered: it is created, it is invented, by humans, and insofar as it follows rules or has properties, it does so only because humans have constructed it, the rules, and the properties.
After the ever-increasing complexity of realism, nominalism can seem like a breath of fresh air, a welcome clearing of the tangled thicket of strange entities realists sooner or later end up committed to.
But, of course, nominalism comes at a price, and that price turns out to be heavy. A nominalist cannot admit that, say, your vegetable's physical appearance and a mathematical formula have anything truly in common other than a human desire to label them as such. The formula is not a natural thing, to a nominalist, and does not exist independently of the humans who invented it. The realist believes the formula would continue to exist, and the vegetable would continue to follow it, even if all humans suddenly vanished. But the nominalist must deny this, and say that the vegetable only "follows" the formula because humans have said it does, and if the humans all vanished there would no longer be any humans to say things about the vegetable. Similarly, the nominalist must say that spiral galaxies would no longer be spiral, because this is a concept created by humans; absent humans to label them, they would not be spiral in any meaningful sense.
From there, the logical conclusion is more or less absolute cultural relativism. If the vegetable only follows a formula because we say it does, what if some other group of people came along and said it didn't? What if they had an entire belief system, as well-developed and complex as our own, for the vegetable following some quite different formula? Who would be right in that case? Since there is no independently-existing "real" formula for the vegetable to "really" follow, the answer is nobody can say who is right; we can only say that both sets of beliefs about the vegetable are equally human-created and equally believed by their respective groups.
This is, of course, incredibly unsatisfying and at odds with how much we've accomplished by believing that there is real correspondence between mathematics and the physical world. But to some people it's a better option to choose over the mess they feel realism will inevitably land them in.
How does a nominalist account for Godel?
