The paradox of Bertrand Russell he formulated in 1918, I believe, has undermined the attempt to found mathematics on a strictly logical basis. I remember that an intuitive way of putting the paradox was this "In a village there is only one barber, a well-shaven man, who shaves all and only the men of the village who do not shave themselves. Who shaves the barber? ». Now since I believe that paradox is equivalent to a situation of contradiction and therefore that describes a set that can not logically exist, as stated by the American logician Willard Quine, why then it had such a high impact and relevance?
For hundreds of years, mathematicians had played fast and loose with logic. They rarely wrote down axioms, or checked that what they were doing was logically sound beyond the gut check. This had been slowly causing problems, at different rates in different fields, causing people to create set theory, a common framework that all mathematicians could agree upon and (in principle) formulate their arguments inside of.
However, the rules of set theory had big problems. Russel’s paradox showed that the rules of set theory actually proved a contradiction, and so this unifying theory for mathematics turned out to prove everything (theorem: If A is inconsistent, then A proves P for every P). That very much would not do. What followed was a frantic effort to save set theory (while other mathematicians tried to destroy it) that resulted in a new set of axioms, now called ZFC, which aren’t obviously contradictory (but by Godel, we can’t prove within ZFC that ZFC isn’t contradictory).
This is important structurally. It may sound like a jovial riddle, but from a structural point of view it demonstrates the inevitability of contradictions and paradoxes in any logical system strong enough to encompass mathematics. The immediate problem demonstrated by the paradox stems from allowing predicates to take predicates as arguments. Here the barber is a function that composes "Shaves(x, y)" with "!Shaves(x, x)" to yield "b = Shaves(x, !Shaves(y, y))" (note: not actual predicate logic notation!). It cannot return a definite answer to the question of whether the barber shaves himself, because there's no consistent truth table when b also is the input.
Since mathematical functions often take other functions as arguments, this means, in practice, that a formal logic cannot be simultaneously mathematically complete, meaning it is able to express every meaningful statement of mathematics, sound, meaning it doesn't express falsehoods, and decidable, meaning everything it says has a definite value.
The discovery of this paradox led to the formulation of First Order Logic, an important system that is sound, but that is not strong enough to encompass mathematics (because it forbids predicates that take other predicates as arguments).