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.

 

Liarís Paradox

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.

 

A formal treatment

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.

 

 

Russellís Paradox

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.

 

Membership in R

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.

 

Analyzing the set expression of R

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.

 

 

Comparing the two paradoxes

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.

 

What to do about the set R

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.

 

Final Thoughts 

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