By the way, quick history of Russell's paradox and related matters, with possible application to the original topic. :)

Russell first pointed out his namesake paradox in Frege's attempt to axiomatize set theory. So yes, it was a mathematical statement, and, really, it's pretty simple to state it. Why nobody noticed before this paradox before then, I have no idea, but it does seem to be worth noting that nobody noticed it until someone actually attempted to sit down and actually formalize set theory.

However, Russell was not the first to notice a paradox in naïve set theory. (Not sure to what extent you can talk about paradoxes in something that hasn't been formalized, but it's pretty clear what's meant, I think.) Cesare Burali-Forti noticed earlier that considering the set of all ordinals leads to a paradox. And yet, despite this, people still continued using naïve set theory until Russell! Part of this may have been that, IIRC, Burali-Forti was convinced that what he found could not actually be a paradox, even though, well, in math, a paradox is always a paradox unless you can knock out one of the suppositions. I have to wonder if perhaps his reaction on finding this may have been along the lines of "...but somebody would have noticed". :)

I don't count a statement of the form "x such that x is not a member of x" as mathematical, because my intuition doesn't want me to talk about sets being members of themselves unless I have a mathematical formalism for sets and set membership for which that works.

The problem is, how do you exclude it from working? If you're just working in first-order logic and you've got a "membership" predicate, of course it's a valid sentence. Russell and Whitehead tried to exclude it from working with a theory of types, but, I hear that has philosophical problems. (I admit to not having read their actual axioms or justification for such. I imagine the problem is basically as follows - it's easy enough to be clear about what you mean for finite types, but how do you specify transfinite types in a way that isn't circular?) The modern solution with ZFC is not to bar such statements; with the axiom of foundation, such statements are perfectly sensible, they're just false. Replace it with an antifoundational axiom and they won't always be false. However, in either case - or without picking a case at all - Russell's paradox still holds; allowing there to be sets that are members of themselves, does not allow there to be a set of all such sets. That is always paradoxical.

It's also not happy about the quantification of x in that sentence; it's a recursive quantification. Let's put it this way: Any computer program I have ever written to handle quantification would crash or loop forever if you tried to give it such a statement.

It's not recursive unless you're already working from a framework where there are objects and sets of objects and sets of etc. In the framework of first-order logic, there are just sets, period. Quantification is over the entire set-theoretic universe. No recursion, just universality. In ZFC sets can indeed be classified into this hierarchy, but that's a consequence of the axiom of foundation, not a feature of the logic.

Let's put it this way: Any computer program I have ever written to handle quantification would crash or loop forever if you tried to give it such a statement.

What encoding scheme would you use to encode arbitrary, possibly infinite, sets in a computer?

Russell's paradox, as usually stated, doesn't actually prove anything, because it's usually given as a statement in English about set theory.

It is presented that way to make a point that naive set theory isn't workable.

I don't know whether Russell originally stated it in mathematical terms, in which case it would prove something. I've read numerous accounts of it, yet never seen > a mathematical presentation. Google fails me at present

It is presented rigorously in most intro set theory text books. In ZFC or any other standard set of set theory axioms, Russell's paradox ceases to be a paradox and the logic is instead a theorem of the form "For any set A, there exists a set B such B is not an element of A."

I don't count a statement of the form "x such that x is not a member of x" as mathematical, because my intuition doesn't want me to talk about sets being members of themselves unless I have a mathematical formalism for sets and set > membership for which that works. It's also not happy about the quantification of x in that sentence; it's a recursive quantification. Let's put it this way: Any computer program I have ever written to handle quantification would crash or loop forever if you tried to give it such a statement.

Well, a standard formalism (again such as ZFC) is perfectly happy talking about sets that recur on themselves this way. Indeed, it is actually difficult to make a system of set theory that doesn't allow you to at least talk about sets like this.

I'm curious, do you consider Cantor's diagnolization argument to be too recursive? What about Turing's Halting Theorem?