\documentstyle[12pt]{article}
\begin{document}
\title{Russell's Paradox}
\author{John T. Baldwin and Olivier Lessmann
\\
Department of Mathematics, Statistics, and Computer Science 
\\University of Illinois at Chicago
\\Chicago, IL 60680}
\maketitle


  
  
  Russell's paradox is based on examples like this: `Consider the
  collection of barbers who shave exactly those men who do not shave
  themselves.' Suppose there is a barber in this collection who does not
  shave himself; then by the definition of the collection, he must shave
  himself. On the other hand, no barber in the collection can shave himself.
  
  Bertrand Russell's discovery of this paradox in 1903 dealt a blow to one of
  his fellow mathematicians. In the late 1800s Gottlob Frege tried to develop
  a foundation for all of mathematics using symbolic logic. He established a
  correspondence between formal expressions (such as `<I>x=2</I>') and mathematical
  properties (such as `even numbers'). In Frege's development, one could
  freely use any property to define further properties.
  
  Russell's paradox demonstrated a fundamental limitation of such a system.
  In modern terms, it is best described in terms of sets, using so-called
  'set-builder' notation. For example, we can describe the collection of
  numbers 4, 5 and 6 by saying that x is the collection of integers n
which are
  greater than 3 and less than 7; we write this formally as 
<I>x = { n: n </I> is an
  integer and <I>} 3 < n < 7} </I>. The objects don't have to be numbers. 
We might
  let  <I>y ={x: x  </I> is a male resident of the United States <I>}  </I>. 
Seemingly, any
  description of <I>x</I> could fill the space after the colon. 
But Russell (and
  independently, Ernst Zermelo) noticed that <I>x = {a: a </I> 
is not in <I> a}</I> leads to
  a contradiction in the same way as the description of the barber. Is 
<I>x</I>
  itself in the set <I>x</I>? Either answer leads to a contradiction.
  
  When Russell discovered this paradox, Frege immediately saw that it had a
  devastating effect for his system. He was unable to resolve the paradox and
  there have been many further attempts in the last century to avoid it.
  
  Russell's own answer was to elaborate a `theory of types.' The problem in
  the paradox, he reasoned, is that we are confusing a description of sets of
  numbers with a description of sets of sets of numbers. So Russell
  introduced a hierarchy of objects: numbers, sets of numbers, sets of sets
  of numbers, etc. This system served as vehicle for the first formalizations
  of the foundations of mathematics and is still used in some philosophical
  investigations and in branches of computer science.
  
  Zermelo's solution to Russell's paradox is to replace the axiom: 
`for every
  formula <I>A(x)</I> there is a set <I>y = {x: A(x)}</I>' by the axiom, 
`for every formula
  <I>A(x)</I> and every set <I>b</I> there is a set <I>y = 
{x: x \in b </I> and 
<I> A(x)}</I>.'
  
  What became of the effort to develop a logical foundation for all of
  mathematics? Mathematicians now recognize that the field can be formalized
  in the so-called Zermelo-Fraenkel set theory. The formal language contains
  symbols $\in$ for in, <I>=</I> for equality and $\emptyset$ to denote the set
  with no elements. So one can write formulas such as 
<I>B(x)</I>: if <I>y</I>
 is in <I>x</I> then
  <I>y</I> is empty. In set-builder notation we could write this as 
<I>y = {x : x = \emptyset}</I> or more simply as <I> y = {\emptyset}</I>. 
Russell's paradox becomes: let <I> y = {x: x \not \in x}</I>, is 
<I>y \in y</I>?
  
  Russell's and Frege's correspondence on Russell's discovery of the paradox
  can be found in "From Frege to Godel, a Source Book in Mathematical Logic,
  1879-1931," edited by Jan van Heijenoort, Harvard University Press, 1967.
  
  
 \end{document}