Notes – On the Liar’s Paradox and Russell’s Paradox
A paradox happens when a proposal that makes perfect sense leads to an unsatisfying conclusion. Paradoxes have a way of making us question our core beliefs. Two such paradoxes are the liar’s paradox and Russell’s paradox. This page compares the two puzzles and tries to show how they are alike and how they are different.
This analysis was spurred by a continuing response to Russell’s paradox, and the analysis has taken on different forms, most of which have been discarded. At one point I thought that the confusion involved the law of the excluded middle, and that experiment has started a new exploration for me in the area of constructive logic. I also considered enhancing the definition of R. Only after a reminder by David Gries (if I interpreted his response correctly) did I realize that the problem is concerned more with a loose interpretation of set membership than with the form of the problem.
The Liar’s Paradox is a very old puzzle that deals with the truth or falseness of the following statement.
This statement is false.
If the statement is false, then, it must be true. If true, then it must be false. The truth or falseness of ‘This statement is false’ does not appear to be derivable, leading to the paradox.
There are many versions of the liar’s paradox, but they all have a form similar to the statement above. In any form, the liar’s paradox seems to stir discussions even today after at least two thousand years of debate.
Analysis of the truth-teller’s statement
This statement is true
may help to explain the liar’s paradox, because the truth-teller’s statement evokes much less anxiety but is a statement of essentially the same form as the liar’s statement.
Suppose that the letter s represents the truth-teller’s statement:
s = {This statement is true}
The letter s is simple expression representing an instance of the set of statements. The statement s represents the idea that
s º true
Therefore, the statement s is equivalent to
s º true
or
s º (s º true)
which is a theorem.
What does the expression
s º (s º true)
mean? The expression only means that representation of statement s is at least consistent and usable, but the expression
s º true
does not explain whether s is true or false.
Applying the same line of reasoning to the liar’s statement
This statement is false
yields the following interpretation of the liar’s statement.
s º false
If the expression is a good representation of the liar’s statement then
s º (s º false)
Evaluation of the expression
s º (s º false)
yields
s ºØs
which is false.
Therefore, the expression
s º false
doesn’t represent the liar’s statement, and, as in the truth-teller’s statement, the expression
s º false
also does not help to derive the logical value of the statement s.
In summary, the obvious interpretation of the liar’s statement can’t be used to represent the liar’s statement suggesting that the liar’s statement is not supported by any traditional system of logic.
Bertrand Russell proposed the interesting set of all sets that are not members of themselves. If a set is not a member of itself, then it is a member of Russell’s hypothetical set. The set in question may be defined simply as
R = {x|xÏx}
The paradox arises when one tries to determine whether R is a member of set R. If R is a member of R, then it must not be a member of R, but if it is not a member of R, then it is. The paradox raises a lot of debate, because it questions the foundations of set theory and in turn questions the foundations of mathematics.
One response concludes that set theory needs strong typing. A set is somehow different from an element, for example. The problem with strong typing is the many examples of sets that make perfectly good elements.
Another response concludes that the definition of R is not well-defined, because self-membership leads to a contradictory result.
There are no hard rules about the content of objects in a set, so sets can have other sets as members. The goal is to derive a member of the set R and validate the existence of the set and better understand the characteristics of R, so we need to find a set that has the characteristics that imply membership to R.
One of the most interesting sets is the null set. The null set
Æ = {}
is empty. That is, the null set has no members.
The set containing the null set
A = {{}}
is not empty, because the null set is a member. The set A is not empty, so set A is a member of the set of non-empty sets. The set of non-empty sets is not empty; A is a member. So the set of non-empty sets is a member of the set of non-empty sets.
The null set is a member of the set of empty sets, so the set of empty sets is not empty; the null set is a member. So the set of empty sets is not a member of the set of empty sets. However, the set of empty sets is a member of Russell’s set R.
Two sets have been demonstrated; one is a member of itself, and the other is not a member of itself.
As noted above, the set R has members. The membership of the set of empty sets to the set R can be verified using the set expression for R. The set of empty sets may be defined as
E = {x|x.cardinality = 0} where x.cardinality represents the number of elements in the set x.
The test of membership to R is the evaluation of
E Î R
º(set expression)
(x Ï x)[x := E]
º(substitution)
E Ï E
º(definition of Ï)
Ø(E Î E)
º(set expression)
Ø(x.cardinality = 0)[x := E]
º(substitution)
Ø(E.cardinality = 0)
º(E contains at least one element)
Ø(false)
º(negation)
true
So R is non-empty and has at least one verifiable member.
Suppose that b is a member of R.
bÎR º bÏb[b := R]
The test for membership in R leads to a false result. The problem: The axioms of set theory assert the truth of
RÎR º RÏR
Russell’s set is the counter example to the notion that the set expression must always determine set membership. Clearly, set membership of R in R is not well-defined. Though some element memberships to set R can be determined as demonstrated above.
Set membership can be undefined in other ways. It is not clear whether the set of all sets containing themselves is a member of the set.
Suppose that Q = {x|xÎx}.
One can show that the set of non-empty sets is a member of Q, but is Q a member of Q?
Evaluate
Q Î Q
º(set definition)
(x Î x)[x := Q]
º(substitution)
Q Î Q
So there is not enough information to show that Q is a member of Q.
Just as the liar’s paradox has a complementary form in the truth-teller’s statement, Russell’s paradox has a complementary form in the set of sets containing themselves. In the case of the liar’s paradox, the liar’s side results in a contradiction and the truth-teller’s side does not provide enough information. In the case of Russell’s paradox, the Russell side leads to a contradiction and the complementary form does not provide enough information.
It should be noted that if the form of the two paradoxical forms were not so problematic, there would not be enough information to reach a conclusion.
It would be tempting to redefine R as
R = {x|xÏx Ù x¹R}
The revised definition clears up the self-referencing problem, because the exclusion of R in the definition overrides the contradiction problem. The elephant in the room is the possibility of other sets might also lead to a contradiction, given that the set R is an example.
It would also be tempting to say that R in the paradoxical form doesn’t exist. One can show that R is not a member of the universal set of discourse. Unfortunately, there is that false expression
RÎR º RÏR
in the middle of the analysis, so any other conclusion is not credible.
Russell’s paradox shows that some expressions do not form well-defined sets, but even as a poorly defined set, there is a valid subset of R, because there is at least one well-defined member of R.
I am not sure that the definition of the subset is derivable, and if there is no other use for Russell’s set, it has generated a great deal of discussion.
The analysis on this page does not really determine the existence or non-existence of the set R. This analysis only shows that the set R is not compatible with the system of logic used herein; or, from a different perspective, the system of logic used on this page does not have the tools needed to describe this problem in a meaningful way.
References:
Gries, David and Schneider, Fred B., 1993, A Logical Approach to Discrete Math, New York, NY: Springer-Verlag
http://plato.stanford.edu/entries/russell-paradox/
http://en.wikipedia.org/wiki/Law_of_excluded_middle
http://en.wikipedia.org/wiki/Liar_paradox
http://www.iep.utm.edu/p/par-liar.htm