2 results back to index

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

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

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 =  | 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.

Is God a Mathematician? by Mario Livio

Amazon: amazon.comamazon.co.ukamazon.deamazon.fr

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.