In mathematics and logic, what is the difference between a counter-intuitive statement and a paradox?
For example, what differs something like the Banach-Tarski theorem or Gabriel's horn from something like Russell's paradox?
logicparadoxesphilosophyterminology
In mathematics and logic, what is the difference between a counter-intuitive statement and a paradox?
For example, what differs something like the Banach-Tarski theorem or Gabriel's horn from something like Russell's paradox?
The idea behind a "collection" is simply a notion of a bunch of mathematical objects which are collected into one big pile. Think of it as a big bin full of trash, diamonds and empty bottles of beer, it doesn't have to make sense what is in this collection, it's just a collection.
One of the problem to explain these things to people who are not mathematicians (or trying to "outsmart a set theorist", as I ran into several of those) is that the notion of a collection is not fully formal unless you already know what sets and class are, and even then it's not exactly what we mean.
Let me start over now. Doing mathematics we often have an idea of an object that we wish to represent formally, this is a notion. We then write axioms to describe this notion and try to see if these axioms are self-contradictory. If they are not (or if we couldn't prove that they are) we begin working with them and they become a definition. Mathematicians are guided by the notion but they work with the definition. Rarely the notion and the definition coincide, and you have a mathematical object which is exactly what our [the mathematicians] intuition tells us it should be.
In this case, a collection is a notion of something that we can talk about, like a mystery bag. We might know that all the things inside this mystery bag are apples, but we don't know which kind; we might know they are all Granny Smith, but we cannot guarantee that none of them is rotten. A collection is just like that. We can either know something about its elements or we don't, but we know that it has some.
Mathematician began by describing these collections and calling them sets, they did that in a relatively naive way, and they described the axioms in a rather naive way. To the non-mathematician (and to most of the non-set theorists) everything is still a set, and we can always assume that there is a set theorist that assured that for what we need this is true. Indeed, if we just wanted to discuss the real numbers, there is no worry at all we can assume everything we work with is a set.
This naive belief can be expressed as every collection is a set. It turned out that some collections cannot be sets, this was expressed via several paradoxes, Cantor's paradox; Russell's paradox; and other paradoxes. The exact meaning is that if we use that particular axiomatic description of "what is a set" then we can derive from it contradiction, which is to say that these axioms are inconsistent.
After this happened several people began working on ways to eliminate this problem. One method in common was to limit the way we can generate collections which are sets. This means that you can no longer derive such contradiction within the theory, namely you cannot prove that such collection even exists - or rather you can prove it doesn't.
The common set theory nowadays called ZFC (named after Zermelo and Fraenkel, the C denotes the axiom of choice) is relatively close to the naive way from which set theory emerges, and it still allows us to define collections which are not sets, though, for example "the collection of all sets". These collections are called classes, or rather proper classes.
What is definable? This is a whole story altogether, but essentially it means that we can describe it with a single formula (perhaps with parameters) of one free variable. "$x$ is taller than 1.68m" is an example to such formula, and it defines the class of all people taller than said height.
So in ZFC we may define a collection which is not a set, like the collection of all the singletons, or the collection of all sets. These are not sets because they are too big, in some sense, to be sets, but they are classes, proper classes. We can talk about collections which are not definable but that requires a lot more background in logic and set theory to get into.
Classes are collections which can be defined, sets are particular classes which are relatively small and there are classes which are not sets. Collections is a notion which is expressed via both these mathematical objects, but need not be well-defined otherwise.
Of course when we say defined we mean in the context of a theory, e.g. ZFC. In this sense, sets are things which "really exist" whereas classes are collections we can talk about despite their possible nonexistence.
One last thing remains, families. Well, as you remarked families are functions. But functions are sets, so families are sets. We can make a slight adjustment to this, and we can, in fact, talk about class functions, and an index which is not a set but a proper class. We, therefore, can talk about families which are classes.
Generally, speaking, if so, a family is a correspondence from one collection into another which uses one collection as indices for elements from another collection.
As Kaveh says in a comment, the issue is not going to be choice. Usually, when we examine what goes wrong when we try to formalize a "nonconstructive" classical proof in a constructive system, the problem that we discover is that the proof is already nonconstructive before the axiom of choice is invoked.
In this case, the issue is that the entire concept of partitions and equivalence classes, which underlies the usual proof of the Banach-Tarski paradox, behaves very differently in constructive systems.
Consider the simpler case of a Vitali set in the real line. Two reals are defined to be equivalent if their difference is rational. That is a perfectly good definition in constructive systems, but it is easy to miss the fact that it involves an implicit universal quantifier over the rationals (or the ability to tell whether an arbitrary real is rational). In this particular case, standard methods show that it will not be possible to prove constructively[1] that "for all reals $x$ and $y$, either $x$ is equivalent to $y$ or $x$ is not equivalent to $y$". Thus it is no longer possible to prove that two equivalence classes $[x]$ and $[y]$ are disjoint or identical, that is, impossible to prove that the equivalence classes form a partition of the real line. But that fact is crucial for the usual proof that the Vitali set is nonmeasurable. The same sort of problem is easy to spot in the usual proof of the Banach-Tarski paradox.
Best Answer
A counter-intuitive statement is either true or false like a normal statement, but surprising in the sense that one would expect a different outcome.
A paradox is undefined, in the sense that if one accepts it, it would be in contradiction to some other statement (an antinomy). It gives the dilemma to drop either the paradox or those statements which are in contradiction to the paradox (in that case it would be either true or false).