The well-known Liar's Paradox "This statement is false" leads to a recursive contradiction: If the statement is interpreted to be true then it is actually false, and if it is interpreted to be false then it is actually true. The statement is a paradox where neither truth value can be assigned to it.

However, "This statement is true" also leads to a paradox where either truth value can be assigned to it with equal validity. If the statement is perceived to be true then it is actually true, and if the statement is perceived to be false then it is actually false.

These two statements demonstrate two different classes of paradox.

The same paradox states exist in set theory. Consider "The set of all sets that do not contain themselves" leads to the former paradox (neither solution is valid), and "the set of all sets that do contain themselves" leads to the latter paradox (either solution is valid.)

My question is: How many classifications of paradox exist? Is there any development in classifying types of paradoxes and applying them to mathematical logic, computer science, and set theory? What implications would classes of paradoxes have on Gödel's incompleteness theorems--could a system that allows and classifies paradoxes be demonstrably consistent?

-
Classes are in the eye of the beholder. I would regard the two statements you describe as being in the same class of paradox called "self-referential paradoxes." Also, the title of the question does not really reflect the question being asked. –  Qiaochu Yuan Aug 31 '11 at 17:41
Well, I understand a paradox to mean a statement that is at first sight absurd, but which seems to have evidence to confirm it. It would then seem that two paradoxes (i.e., four oxen), would be equivalent if the evidence that (seems to) confirm one , confirms also the other. This approach is used to deal with the confirmation paradox, i.e., that the same evidence that confirms "all non-blue things are non parrots" also should confirm the statement "all parrots are blue" –  gary Aug 31 '11 at 17:56
@Qiaochu Yuan: The title has been changed. –  oosterwal Aug 31 '11 at 17:57
@gary: I think the OP is interested in logical paradoxes, that is, statements which cannot be uniquely assigned a consistent truth value (or something like that). –  Qiaochu Yuan Aug 31 '11 at 18:00
If you accept that "paradox" means "can derive $P\wedge\neg P$", you might be interested in the different paraconsistent logics. –  Xodarap Sep 2 '11 at 19:18

Here is a preliminary version of a paper by Noson Yanofsky on paradox and self-reference that may be of interest. There is also a final version in the Bulletin Of Symbolic Logic.

-
+1 - That paper gives me a lot of information and additional references. Thank you. –  oosterwal Sep 1 '11 at 14:02
second link is same as the first link...Did you mean to link projecteuclid.org/euclid.bsl/1058448677 ? –  Memming Apr 8 at 15:57
@Memming That's what I wanted. Thanks. –  Jay Apr 10 at 22:53

Paradoxes arise any time you try to make deductions from an inconsistent set of axioms. The Liar paradox is just a paradox derived from a pair of axioms (namely, 1="All Cretans are liars." and 2="A Cretan said, "All Cretans are liars.") that should be assumed to be true, a priori, because all of the inference rules of logic are truth-preserving transformations. There is no rule of logic that allows you to assume that any statement is false! If you don't start with a true statment and apply a truth-preserving transformation, you are just breaking the rules of logic! So, you have no warrant to expect the result to be true. The feeling that there is a paradoxical conclusion arises when your intuition tells you one thing and your brain tells you something else. If you break the rules of logic, your intuition tells you that there is something fishy while your head keeps telling you that you did everything right.

The statement, "This statement is false," is an example of a paradox arising from a single axiom.

Arrow's Impossibility Theorem is a case where any two of three given axioms are consistent, but the set of three axioms as a whole leads to a contradiction. We don't ordinarily think of this as a paradox, but it really is a case of what we might call cyclic self-reference, and hence another class of paradox.

So, my answer is that your hunch is right: there is an infinite heirarchy of paradox classes according to the maximum number of axioms in any given set of axioms and inference rules that don't lead to a contradiction. I don't know, but I can imagine that there may be more complicated cases that might be mapped on graphs that are not simple polygons.

-
It's simply not true that if you start with a false statement, and apply a truth-preserving transformation you break the rules of logic. Consider (p^~p) in classical propositional logic. Now, apply the transformation "from x, infer x". From this, given (p^~p) we can infer (p^~p). In fact, in classical logic, one could argue that all truth-preserving transformation work precisely because you can either start with a false statement or a true statement (as long as it qualifies as one of the two) and derive a true statement. If not, their corresponding formula would not qualify as valid. –  Doug Spoonwood Sep 2 '11 at 19:58

The problems is that the actual axiomatization of set theory and logic makes impossible paradox to exist, -or better said we hope that-. Now, I can say that the variation of the liar paradox of the form "This statement cannot be proven" give rise to Gödel theorems when it is correctly formalised. I recomend you to read about non-classical logics because this are the only ones which can deal with paradoxes in some sense, otherwise there is not such a logic-mathematical possibility (I think).

-