Russell's paradox

3 results back to index

The Haskell Road to Logic, Maths and Programming by Kees Doets, Jan van Eijck, Jan Eijck

Albert Einstein, Charles Babbage, Eratosthenes, functional programming, Georg Cantor, P = NP, Russell's paradox

Not so with the following: small_squares2 = [ n^2 | n <- naturals , n < 1000 ] The way this is implemented, n <- naturals generates the infinite list of natural numbers in their natural order, and n < 1000 tests each number as it is generated for the property of being less than 1000. The numbers that satisfy the test are squared and put in the result list. Unlike the previous implementation small_squares1, the function small_squares2 will never terminate. Example 4.5 (*The Russell Paradox) It is not true that to every property E there corresponds a set {x | E(x)} of all objects that have E. The simplest example was given by Bertrand Russell (1872–1970). Consider the property of not having yourself as a member. Most sets that you are likely to consider have this property: the set of all even natural numbers is itself not an even natural number, the set of all integers is itself not an integer, and so on.

…

Suppose, on the contrary, that R ∈ / R, that is, R is an extraordinary set. Extraordinary sets are the sets that have themselves as a member, so R has itself as a member, i.e., R ∈ R. If R were a legitimate set, this would unavoidably lead us to the conclusion that R ∈ R ⇐⇒ R 6∈ R , which is impossible. You do not have to be afraid for paradoxes such as the Russell paradox of Example 4.5. Only properties that you are unlikely to consider give rise to problems. In particular, if you restrict yourself to forming sets on the basis of a previously given set A, by means of the recipe { x ∈ A | E(x) }, 4.2. PARADOXES, TYPES AND TYPE CLASSES 121 no problems will ever arise.

…

Take B = {x ∈ A | x ∈ / x}. 4.2 Paradoxes, Types and Type Classes It is a well-known fact from the theory of computation that there is no general test for checking whether a given procedure terminates for a particular input. The halting problem is undecidable. Intuitively, the reason for this is that the existence of an algorithm (a procedure which always terminates) for the halting problem would lead to a paradox very similar to the Russell paradox. Here is a simple example of a program for which no proof of termination exists: run :: Integer -> [Integer] run n | n < 1 = error "argument not positive" | n == 1 = [1] | even n = n: run (div n 2) | odd n = n: run (3*n+1) This gives, e.g.: STAL> run 5 [5,16,8,4,2,1] STAL> run 6 [6,3,10,5,16,8,4,2,1] STAL> run 7 [7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1] 122 CHAPTER 4.

Types and Programming Languages by Benjamin C. Pierce

Albert Einstein, combinatorial explosion, experimental subject, finite state, functional programming, Henri Poincaré, higher-order functions, Perl 6, power law, Russell's paradox, sorting algorithm, Turing complete, Turing machine, type inference, Y Combinator

The terms "predicative" and "impredicative" originate in logic. Quine (1987) offers a lucid summary of their history: In exchanges with Henri Poincaré...Russell attributed [Russell's] paradox tentatively to what he called a vicious-circle fallacy. The "fallacy" consisted in specifying a class by a membership condition that makes reference directly or indirectly to a range of classes one of which is the very class that is being specified. For instance the membership condition behind Russell's Paradox is non-self-membership: x not a member of x. The paradox comes of letting the x of the membership condition be, among other things, the very class that is being defined by the membership condition.

Is God a Mathematician? by Mario Livio

Albert Einstein, Alvin Toffler, Antoine Gombaud: Chevalier de Méré, Brownian motion, cellular automata, correlation coefficient, correlation does not imply causation, cosmological constant, Dava Sobel, double helix, Edmond Halley, Eratosthenes, Future Shock, Georg Cantor, Gerolamo Cardano, Gregor Mendel, Gödel, Escher, Bach, Henri Poincaré, Isaac Newton, Johannes Kepler, John von Neumann, music of the spheres, Myron Scholes, Plato's cave, probability theory / Blaise Pascal / Pierre de Fermat, Russell's paradox, seminal paper, Thales of Miletus, The Design of Experiments, the scientific method, traveling salesman

Translated by T. Taylor, 1986 (Rochester, Vt.: Inner Traditions). ———. Ca. 300 ADb. On the Pythagorean Life. Translated by J. Dillon and J. Hershbell. (Atlanta: Scholar Press). Irvine, A. D. 2003. “Russell’s Paradox.” In the Stanford Encyclopedia of Philosophy. http://plato.stanford.edu/entries/russell-paradox. Isaacson, W. 2007. Einstein: His Life and Universe (New York: Simon & Schuster). Jaeger, M. 2002. The Journal of Roman Studies, 92, 49. Jeans, J. 1930. The Mysterious Universe (Cambridge: Cambridge University Press). Jones, V. F. R. 1985. Bulletin of the American Mathematical Society, 12, 103.