jump to navigation

Infinity symbol II October 20, 2009

Posted by David Pierce in Uncategorized.
1 comment so far

I note a sighting of what we know as the symbol for infinity. The example accompanies a hexagram or Star of David. These symbols are to be seen on a stone in the garden of the archeological museum in Tire, Izmir province, Turkey (a couple of dolmuş rides away from the Nesin Mathematics Village).

infinity sign and hexagram

infinity sign and hexagram

Completions and the Archimedean property August 28, 2009

Posted by David Pierce in Uncategorized.
5 comments

In an ordered Abelian group, one positive element can be described as infinite with respect to another if the former exceeds every integral multiple of the other. If there are no such elements, the group can be called Archimedean.

Non-Archimedean ordered Abelian groups exist: for example, the group of ordered pairs (x,y) of integers, with the left-lexicographic ordering, so that (x,y)<(a,b) if and only if either x<a, or else x=a and y<b.

The main point of this article is to observe that an ordered
Abelian group is Archimedean if and only if it has a completion.
I do not know of a reference for this result, though I can well imagine that a reference exists.

The observation about completeness arises from considering that the field of real numbers is complete in two ways:

  1. It is complete as an ordered field, because every nonempty
    subset with an upper bound has a least upper bound.

  2. It is complete as a valued field, because every Cauchy
    sequence (with respect to the absolute value function) converges.

In sense (2), the field of real numbers is just one example of a
complete field. The complex numbers compose another such field,
as do the p-adic completions of the field of rational numbers.
Every valued field has a completion.

In sense (1) however, the field of real numbers is unique.
I have encountered at least one mathematician who seemed not to
be aware of this, or to have forgotten it, having apparently
confused completeness of valued fields with completeness of
ordered fields.

Possibly the distinction between ordered fields and valued fields
is like that between induction and completion: a distinction that
may be overlooked in one’s early education and then never
returned to.

At the end of his book Calculus, Michael Spivak constructs
the field of real numbers and proves its uniqueness (up to
isomorphism). It was from Spivak’s book that, as a student, I
first learned of the uniqueness of the real field. Spivak
praises the “one truly first-rate idea” in its construction:
Dedekind’s notion of a cut. Yet Spivak is disparaging of
the “drudgery” of going through the details of the construction.

I revisited the construction recently, in a course on
non-standard analysis at the Nesin Mathematics Village. If the
construction of the real numbers was going to be drudgery, I
wanted to see what more general results could be found in the
process.

The Dedekind cut construction gives a completion to every
ordered set (that is, totally ordered set). Indeed, let A be
such a set, and if x is in A, let (x) be the set of elements of A
that are less than or equal to x. Such sets compose a basis for
a topology on A. A cut of A can be defined as a nonempty closed
set in this topology, except A itself, unless this has a greatest
element. Let c(A) be the set of cuts of A. Then:

  1. The set c(A) is ordered by inclusion
    and is complete with
    respect to this ordering.
  2. The ordered set A embeds in c(A) under the map taking x to (x).

Again, an ordered Abelian group is Archimedean if, for any two
positive elements a and b, some multiple of a exceeds b. In
other words, a and b have a ratio in the sense of
Definition 4 of Book V of Euclid’s Elements. Indeed, the
positive part of an Archimedean ordered Abelian group would seem
to be just the set of magnitudes that have a ratio to some given
magnitude: the set is closed under addition, and under
subtraction of a lesser magnitude from a greater.

For any ordered Abelian group A, Archimedean or not, one can take
the completion of the underlying ordered set, and then extend the
definition of addition to the completion. One way to do this is
to define the sum of non-empty proper closed subsets X and Y of A
as the closure of the set of sums x+y, where x is in X and y is
in Y. Then c(A) becomes an Abelian monoid.

However, if A is a not Archimedean, then A cannot be complete,
since if the set of integral multiples of a positive element a is
bounded above by b, then b-a is also an upper bound. In c(A),
the set of multiples of a does have a supremum, c; but then c+a =
c.

Among Archimedean ordered Abelian groups, the group of integers
is the only discrete example, and this is complete. If A is a
dense Archimedean ordered Abelian group, then c(A) is the same.
If A and B are complete dense ordered Abelian groups, with
positive elements a and b respectively, then there is a unique
isomorphism from A to B taking a to b. The idea is that the
ordered field of rational numbers embeds in A under the map
taking 1 to a; then this map extends uniquely to the completion
of the rational field, which is the real field.

Consequently, for every real number a greater than 1, the
additive group of real numbers is isomorphic to the
multiplicative group of positive real numbers under a map taking
1 to a: this is the map commonly denoted by x |—> ax. One
shows that multiplication distributes over addition on the
positive reals, then on all reals, and so the reals compose a
complete ordered field, which must be unique, because the
underlying group is unique as a dense complete ordered Abelian
group.

Infinity symbol April 8, 2009

Posted by David Pierce in Uncategorized.
4 comments

Why is infinity denoted by a lemniscate?

Lemniscates (figure-eights)

In a recent talk in Ankara, Sasha Borovik used a photograph like those in his post Manifestation of Infinity. How does infinity appear in a picture of a ferry approaching a dock? One person in the audience suggested that a pair of tires on the side of the ferry formed the infinity symbol.

I speculate that the lemniscate is the simplest shape suggesting endlessness that will not be confused with the symbol for emptiness: the zero. That the zero is naturally a symbol for emptiness is suggested in the eighth Oxherding picture, Bull and Self Transcended:

[picture: an empty circle]

Whip, rope, person, and bull — all merge in No-Thing.
This heaven is so vast no message can stain it.
How may a snowflake exist in a raging fire?
Here are the footprints of the patriarchs.

Comment: Mediocrity is gone. Mind is clear of limitation. I seek no state of enlightenment. Neither do I remain where no enlightenment exists. Since I linger in neither condition, eyes cannot see me. If hundreds of birds strew my path with flowers, such praise would be meaningless.

(English text by Reps and Senzaki.)

How significant the lemniscate may be in the East, I do not know. I was able to find, on one yoga website, a suggestion to visualize a figure-eight while practicing Spinal Breath:

There are a variety of practices with awareness moving up and down the spine with the breath. One may do this practice between particular energy centers (chakras) or form different shapes of the visualized flow, including elliptical or a figure-eight…

The most straight forward, and yet completely effective method is to:

  • Imagine the breath flowing from the top of the head, down to the base of the spine on exhalation, and to
  • Imagine the flow coming from the base of the spine to the top of the head on inhalation.
  • This may be done lying down, or in a seated meditation posture.

One may simply experience the breath, or may be aware of a thin, milky white stream flowing in a straight line, up and down. This practice is very subtle when experienced at its depth, and can turn into a profoundly deep part of meditation practice.

Induction and recursion II May 28, 2008

Posted by David Pierce in Uncategorized.
3 comments

Formal logic provides examples of structures that allow proof by induction, but not necessarily definition by recursion. Let us consider, for example, the propositional logic that is apparently due to Łukasiewicz. We first define the (well-formed) formulas of the logic. We start with some set of so-called propositional variables. Then the set of formulas is the smallest set of strings that contains these variables and is closed under certain formation rules, namely:

  1. the singulary operation converting a string S to its negation, ~S;
  2. the binary operation converting a pair (S, T) of strings to the implication, (S → T).

The set of theorems of the logic is the smallest set of formulas that contains all of the axioms and is closed under a certain rule of inference. The axioms are the formulas of any of three forms:

  1. (F → (G → F))
  2. ((F → (G → H)) → ((F → G) → (F → H)))
  3. ((~F → ~G) → (G → F))

Here F and G stand for formulas. The rule of inference is detachment (or modus ponens), the binary operation that converts a pair (F, (F → G)) of formulas into the formula G. As stated, this is only a partial operation; we can make it total by having it convert (F, H) to F whenever H does not have the form (F → G) for some formula G.
The “inductive” definition of theorems is thus similar to the inductive definition of formulas. In each case, we start with a set and close under one or more operations. Immediately, proof by induction is possible on the set so defined. For example, we can prove inductively that each formula features as many left as right brackets. A feature of theorems that is proved by induction will be given in a moment.
However, unlike the formation rules for formulas, our rule of inference for theorems is not obviously well-defined. To see that it is well-defined, we must establish “unique readability” of formulas, namely:

  1. each formula is exactly one of the following: a variable, a negation, or an implication;
  2. the formation rules are injective.

Here injectivity of the formation rules corresponds to injectivity of the successor-operation on the set of natural numbers. The partition of the set of formulas into variables, negations, and implications corresponds to the partition of the set of natural numbers into the successors and the initial number (zero or one, as one prefers).
Unique readability of formulas allows recursive definitions. Indeed, the definition of the rule of detachment can be understood as recursive: If we denote this operation by D, then we have

  1. D(F, P) = F for all propositional variables P;
  2. D(F, ~G) = F;
  3. D(F, (F → G)) = G;
  4. D(F, (H → G)) = F if H is not F.

Another example of a recursively defined function on formulas is a truth-assignment. Consider the set {true, false} as the two-element field {1, 0}. Given a function φ from the set of propositional variables into the this field, we have a unique function Φ on the set of all formulas that agrees with φ on the variables, that takes ~F to 1 + Φ(F), and that takes (F → G) to 1 + Φ(F) + Φ(F)Φ(G).
By induction, every theorem takes the value 1 under every truth-assignment. But the truth-assignment is not recursively defined on the set of theorems: it is recursively defined on the set of formulas. Since the rule of detachment is not injective, we do not automatically have recursively defined functions on the set of theorems.
As far as I know, we do not have an efficient algorithm to determine whether a given formula is indeed a theorem: this lack of an algorithm would appear to be connected to the non-injectivity of the rule of detachment. A formula carries within itself the method of its construction; but a theorem does not carry within itself its proof, and indeed it will have infinitely many proofs.

Dante’s universe as 3-sphere April 22, 2008

Posted by David Pierce in Uncategorized.
4 comments

The quotations about the universe as an infinite sphere remind me of another kind of sphere that is beyond our usual powers of imagination.
In the one-hundred cantos of the Divine Comedy, Dante travels from the central point of the earth out into the heavens. He passes through the spheres of

  1. the moon,
  2. Mercury,
  3. Venus,
  4. the sun,
  5. Mars,
  6. Jupiter,
  7. Saturn,
  8. the fixed stars,
  9. the Primum Mobile.

In this ninth sphere, he sees another point, surrounded by circles or spheres. These spheres are angels, named from inside to outside:

  1. Seraphim,
  2. Cherubim,
  3. Thrones,
  4. Dominions,
  5. Virtues,
  6. Powers,
  7. Principalities,
  8. Archangels,
  9. Angels.

These are named in Canto XXVIII of the Paradiso, where Dante reports (text from the Princeton Dante Project):

16 I saw a point that flashed a beam of light
17 so sharp the eye on which it burns
18 must close against its piercing brightness.
19 The star that, seen from here below, seems smallest
20 would seem a moon if put beside it,
21 as when one star is set beside another.
22 As near, perhaps, as a halo seems to be
23 when it encircles the light that colors it,
24 where the vapor that forms it is most dense,
25 there whirled about that point a ring of fire
26 so quick it would have easily outsped
27 the swiftest sphere circling the universe.
28 This point was encircled by another ring,
29 and that by the third, the third by the fourth,
30 the fourth by the fifth, and the fifth by the sixth.
31 Higher there followed the seventh, now spread so wide
32 that the messenger of Juno, in full circle,
33 would be unable to contain its size.
34 And so, too, the eighth and ninth,
35 each one revolving with diminished speed
36 the farther it was wheeling from the first.
37 And that one least removed from the blazing point of light
38 possessed the clearest flame, because, I think,
39 it was the one that is the most intruthed by it.
40 My lady, who saw me in grave doubt
41 yet eager to know and comprehend, said:
42 ‘From that point depend the heavens and all nature.
43 ‘Observe that circle nearest it,
44 and understand its motion is so swift
45 because it is spurred on by flaming love.’
46 And I to her: ‘If the universe were arranged
47 in the order I see here among these wheels
48 I would be content with what you’ve set before me.
49 ‘However, in the world of sense we see
50 the farther from the center they revolve
51 the more divinity is in their orbits.

Beatrice then explains that the innermost rings of angels correspond to the outermost heavenly spheres: so n corresponds to 10-n in the lists above.

In a lecture given in Ankara a while back, Piergiorgio Odifreddi suggested (as I recall) that the two spheres or rather balls—of the heavens, and of the angels—should be considered as identified along the 2-spheres that are their boundaries, so that a 3-sphere is obtained, with Lucifer and God as antipodal points.
I note Dante’s description of the latter Point in lines 11–12 of Canto XXX:

1 About six thousand miles away from here
2 the sixth hour burns and even now this world
3 inclines its shadow almost to a level bed,
4 when, deep in intervening air, above us,
5 begins such change that here and there,
6 at our depth, a star is lost to sight.
7 And, as that brightest handmaid of the sun advances,
8 the sky extinguishes its lights,
9 even the most beautiful, one by one.
10 Not otherwise the victory that revels
11 in eternal joy around the point that overcame me
12 and seems enclosed by that which it encloses
13 little by little faded from my sight,
14 so that, compelled by seeing nothing and by love,
15 I turned my eyes to gaze on Beatrice.

As a symbol for a world that cannot be fully comprehended, the three-dimensional surface of a four-dimensional body may serve as well as something infinite in extent.

Induction and recursion March 6, 2008

Posted by David Pierce in Uncategorized.
6 comments

I have been invited to comment here on the distinction between proof by induction and definition by recursion. These have been confused since Guiseppe Peano published (in 1889) what came to be called the Peano Axioms. It might appear that both induction and recursion involve infinite sets; but only recursion necessarily does.

Writing before Peano, Richard Dedekind (1887) was clear about the distinction. He defined a simply infinite system as a system (i.e. set) with a base-element and a transformation (i.e. function) into itself such that:

  1. the base-element is not the transform (i.e. image under the transformation) of any element;
  2. distinct elements have distinct transforms (in Dedekind’s terminology, the transformation is similar);
  3. proof by induction is possible: a subset containing the base-element and closed under the transformation is the whole set.

Peano also wrote down these conditions, but in a new logical symbolism, and they came to be known as the Peano axioms. But unlike Dedekind, Peano apparently thought that these axioms immediately allowed the definition of addition. Indeed, let the base-element be 1, and the transformationbe φ. We define n+1 as φ(n) and, assuming n+m has been defined, we define n+φ(m) as φ(n+m).

This is a recursive definition. Is it justified? If so, which of the three axioms are required, and how?

The definition of addition can be justified by induction alone. Likewise, multiplication. Edmund Landau published the proof (due to Kalmár) in 1929. But Landau did not dwell on the sufficiency of induction, or on what Dedekind had observed: a system that admits proof by induction may be finite, so that not all recursive definitions work.

Finite rings provide examples. In the ring of integers modulo p, or Z/(p), let 0 be taken as the base-element, and let the transformation be addition of the generator 1. No proper subset of the group contains 0 and is closed under the transformation: proof by induction is possible here. From this, addition and multiplication can be recovered.

However, exponentiation as a binary operation cannot be defined on this ring. Superficially, the attempted definition parallels those of addition and multiplication: n0 = 1, and if nm has been defined, then nm+1 = nm·n. But this definition fails. Indeed, assuming p is prime and n is not 0, by Fermat’s Theorem we must have np-1 = 1; but then n = np = n0 = 1, which is absurd unless p is 2.

Fermat’s Theorem is that we have exponentiation as a function from Z/(p) × Z/(p-1) into Z/(p); but to prove this, we need more than that the ring Z/(p) and the group Z/(p-1) admit proof by induction.

Though distinguishing between definition and proof, Dedekind spoke of definition by induction rather than definition by recursion. If Ω is a set with distinguished element ω and transformation θ into itself, then, from a simply infinite system as above, into Ω, there is a unique transformation ψ such that ψ(1) = ω and ψφ = θψ. For Dedekind, this is a theorem about simply infinite systems.

According to Saunders Mac Lane in Mathematics, form and function (1986), Lawvere first “made explicit” that this Recursion Theorem implies the three Peano Axioms listed above. The equivalence of the Theorem and the Axioms is also discussed in the first edition of Mac Lane and Birkhoff’s Algebra (1967). Nonetheless, although that text introduces the natural numbers (starting with 0) as satisfying the Peano axioms, the writers then immediately use the natural numbers to index iterations of an operation f on a set: f 0 is the identity, and f n+1 is f f n. This is a recursive definition, so one might expect it to be justified to the reader by means of the Recursion Theorem. But this theorem is stated about 40 pages later, as the Peano–Lawvere Axiom, from which the Peano Axioms are shown to follow; the converse is only to be found in “many [other] texts on foundations”.

Indeed, Stoll’s Set theory and logic (1963) is one such text. However, other texts continue to give the impression that “definition by induction” is permitted by the possibility of proof by induction. Other confusions are found in elementary texts, such as the suggestion that “strong induction” or the “well-ordering principle” are equivalent to (ordinary) induction. To me, it is important to get these things straight, if only because the attentive student might be confused (as I once was). Landau confessed to having been mistaken about what was possible with induction. Who has noted since how it is possible to go astray?

References:

  1. Richard Dedekind, Essays on the theory of numbers (Dover, 1963)
  2. Edmund Landau, Foundations of analysis (Chelsea, 1966)
  3. Saunders Mac Lane, Mathematics, form and function (Springer, 1986)
  4. Saunders Mac Lane and Garrett Birkhoff, Algebra (Macmillan, 1967)
  5. Robert R. Stoll, Set theory and logic (Dover, 1979)
  6. Jean van Heijenoort, editor, From Frege to Gödel, a source book in mathematical logic 1879–1931 (Harvard, 1967)