3 results back to index

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

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.

Ordinary sets are the sets that do not have themselves as a member, so R does not have itself as a member, i.e., R ∈ / R. 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. Example 4.6 There is no set corresponding to the property F (x) :≡ there is no infinite sequence x = x0 3 x1 3 x2 3 . . ..

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. SETS, TYPES AND LISTS We say that a procedure diverges when it does not terminate or when it aborts with an error.

pages: 647 words: 43,757

Types and Programming Languages by Benjamin C. Pierce

The polymorphism found in ML, on the other hand, is often called predicative (or stratified), because the range of type variables is restricted to monotypes, which do not contain quantifiers. 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. Russell and Poincaré came to call such a membership condition impredicative, and disqualified it as a means of specifying a class.

pages: 315 words: 93,628

Is God a Mathematician? by Mario Livio

Beauchamp (Oxford: Oxford University Press). Iamblichus. Ca. 300 ADa. Iamblichus’ Life of Pythagoras. 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. Joost-Gaugier, C. L. 2006. Measuring Heaven: Pythagoras and His Influence on Thought and Art in Antiquity and the Middle Ages (Ithaca: Cornell University Press).