|, ||, |||, ||||| . The Non-Metaphysics of Unprediction. Thought of the day 67.1

1*pYpVJs_n4yh_3fnGaCbwKA

The cornerstone of Hilbert’s philosophy of mathematics was the so-called finitary standpoint. This methodological standpoint consists in a restriction of mathematical thought to objects which are “intuitively present as immediate experience prior to all thought,” and to those operations on and methods of reasoning about such objects which do not require the introduction of abstract concepts, in particular, require no appeal to completed infinite totalities.

Hilbert characterized the domain of finitary reasoning in a well-known paragraph:

[A]s a condition for the use of logical inferences and the performance of logical operations, something must already be given to our faculty of representation, certain extra-logical concrete objects that are intuitively present as immediate experience prior to all thought. If logical inference is to be reliable, it must be possible to survey these objects completely in all their parts, and the fact that they occur, that they differ from one another, and that they follow each other, or are concatenated, is immediately given intuitively, together with the objects, as something that can neither be reduced to anything else nor requires reduction. This is the basic philosophical position that I consider requisite for mathematics and, in general, for all scientific thinking, understanding, and communication. [Hilbert in German + DJVU link here in English]

These objects are, for Hilbert, the signs. For the domain of contentual number theory, the signs in question are sequences of strokes (“numerals”) such as

|, ||, |||, ||||| .

The question of how exactly Hilbert understood the numerals is difficult to answer. What is clear in any case is that they are logically primitive, i.e., they are neither concepts (as Frege’s numbers are) nor sets. For Hilbert, the important issue is not primarily their metaphysical status (abstract versus concrete in the current sense of these terms), but that they do not enter into logical relations, e.g., they cannot be predicated of anything.

Sometimes Hilbert’s view is presented as if Hilbert claimed that the numbers are signs on paper. It is important to stress that this is a misrepresentation, that the numerals are not physical objects in the sense that truths of elementary number theory are dependent only on external physical facts or even physical possibilities. Hilbert made too much of the fact that for all we know, neither the infinitely small nor the infinitely large are actualized in physical space and time, yet he certainly held that the number of strokes in a numeral is at least potentially infinite. It is also essential to the conception that the numerals are sequences of one kind of sign, and that they are somehow dependent on being grasped as such a sequence, that they do not exist independently of our intuition of them. Only our seeing or using “||||” as a sequence of 4 strokes as opposed to a sequence of 2 symbols of the form “||” makes “||||” into the numeral that it is. This raises the question of individuation of stroke symbols. An alternative account would have numerals be mental constructions. According to Hilber, the numerals are given in our representation, but they are not merely subjective “mental cartoons”.

One version of this view would be to hold that the numerals are types of stroke-symbols as represented in intuition. At first glance, this seems to be a viable reading of Hilbert. It takes care of the difficulties that the reading of numerals-as-tokens (both physical and mental) faces, and it gives an account of how numerals can be dependent on their intuitive construction while at the same time not being created by thought.

Types are ordinarily considered to be abstract objects and not located in space or time. Taking the numerals as intuitive representations of sign types might commit us to taking these abstract objects as existing independently of their intuitive representation. That numerals are “space- and timeless” is a consequence that already thought could be drawn from Hilbert’s statements. The reason is that a view on which numerals are space- and timeless objects existing independently of us would be committed to them existing simultaneously as a completed totality, and this is exactly what Hilbert is objecting to.

It is by no means compatible, however, with Hilbert’s basic thoughts to introduce the numbers as ideal objects “with quite different determinations from those of sensible objects,” “which exist entirely independent of us.” By this we would go beyond the domain of the immediately certain. In particular, this would be evident in the fact that we would consequently have to assume the numbers as all existing simultaneously. But this would mean to assume at the outset that which Hilbert considers to be problematic.  Another open question in this regard is exactly what Hilbert meant by “concrete.” He very likely did not use it in the same sense as it is used today, i.e., as characteristic of spatio-temporal physical objects in contrast to “abstract” objects. However, sign types certainly are different from full-fledged abstracta like pure sets in that all their tokens are concrete.

Now what is the epistemological status of the finitary objects? In order to carry out the task of providing a secure foundation for infinitary mathematics, access to finitary objects must be immediate and certain. Hilbert’s philosophical background was broadly Kantian. Hilbert’s characterization of finitism often refers to Kantian intuition, and the objects of finitism as objects given intuitively. Indeed, in Kant’s epistemology, immediacy is a defining characteristic of intuitive knowledge. The question is, what kind of intuition is at play? Whereas the intuition involved in Hilbert’s early papers was a kind of perceptual intuition, in later writings it is identified as a form of pure intuition in the Kantian sense. Hilbert later sees the finite mode of thought as a separate source of a priori knowledge in addition to pure intuition (e.g., of space) and reason, claiming that he has “recognized and characterized the third source of knowledge that accompanies experience and logic.” Hilbert justifies finitary knowledge in broadly Kantian terms (without however going so far as to provide a transcendental deduction), characterizing finitary reasoning as the kind of reasoning that underlies all mathematical, and indeed, scientific, thinking, and without which such thought would be impossible.

The simplest finitary propositions are those about equality and inequality of numerals. The finite standpoint moreover allows operations on finitary objects. Here the most basic is that of concatenation. The concatenation of the numerals || and ||| is communicated as “2 + 3,” and the statement that || concatenated with ||| results in the same numeral as ||| concatenated with || by “2 + 3 = 3 + 2.” In actual proof-theoretic practice, as well as explicitly, these basic operations are generalized to operations defined by recursion, paradigmatically, primitive recursion, e.g., multiplication and exponentiation. Roughly, a primitive recursive definition of a numerical operation is one in which the function to be defined, f , is given by two equations

f(0, m) = g(m)

f(n′, m) = h(n, m, f(n, m)),

where g and h are functions already defined, and n′ is the successor numeral to n. For instance, if we accept the function g(m) = m (the constant function) and h(n, m, k) = m + k as finitary, then the equations above define a finitary function, in this case, multiplication f (n, m) = n × m. Similarly, finitary judgments may involve not just equality or inequality but also basic decidable properties, such as “is a prime.” This is finitarily acceptable as long as the characteristic function of such a property is itself finitary: For instance, the operation which transforms a numeral to | if it is prime and to || otherwise can be defined by primitive recursion and is hence finitary. Such finitary propositions may be combined by the usual logical operations of conjunction, disjunction, negation, but also bounded quantification. The problematic finitary propositions are those that express general facts about numerals such as that 1 + n = n + 1 for any given numeral n. It is problematic because, for Hilbert it is from the finitist point of view incapable of being negated. By this he means that the contradictory proposition that there is a numeral n for which 1 + n ≠ n + 1 is not finitarily meaningful. A finitary general proposition is not to be understood as an infinite conjunction but only as a hypothetical judgment that comes to assert something when a numeral is given. Even though they are problematic in this sense, general finitary statements are of particular importance to Hilbert’s proof theory, since the statement of consistency of a formal system T is of such a general form: for any given sequence p of formulas, p is not a derivation of a contradiction in T. Even though in general existential statements are not finitarily meaningful, they may be given finitary meaning if the witness is given by a finitary function. For instance, the finitary content of Euclid’s theorem that for every prime p there is a prime > p, is that given a specific prime p one can produce, by a finitary operation, another prime > p (viz., by testing all numbers between p and p! + 1.).

Finite Fields

gf256-x11B

A finite field is a field with a finite field order (i.e., number of elements), also called a Galois field. The order of a finite field is always a prime or a power of a prime. For each prime power, there exists exactly one (with the usual caveat that “exactly one” means “exactly one up to an isomorphism“) finite field GF(p^n), often written as Fpn in current usage.

Theorem:

Let E be a finite field of characteristic p.

1. The cardinality of E is

|E| = pn, for some n ≥ 1. It is denoted E = Fpn

Furthermore, E is the splitting field for the separable polynomial f(X) = Xpn − X

over Fp, so that any finite field with pn elements is isomorphic to E. In fact, E coincides with the set of roots of f.

Proof:

1. Let Fp be the finite field with p elements, given by the integers modulo p. Since E has characteristic p, it contains a copy of Fp. Thus E is a field extension of Fp, and we may see E as a vector space over Fp. If the dimension is n, then let α1,…,αn be a basis. Every x in E can be written as

x = x1α1 +···+ xnαn

and there are p choices for each xi, thus a total of pn different elements in E.

2. Let E× be the multiplicative group of non-zero elements of E. If α ∈ E×, then

αpn−1 = 1

by Lagrange’s Theorem, so that

αpn

∀ α in E (including α = 0). Thus each element of E is a root off, and f is separable.

Now f has at most pn distinct roots, and we have already identified the pn elements of E as roots of f.

Corollary: If E is a finite field of characteristic p, then E/Fp is a Galois extension, with cyclic Galois group, generated by the Frobenius automorphism

σ : x → σ(x) = xp, x ∈ E

Proof:

By the above proposition, we know that E is a splitting field for a separable polynomial over Fp, thus E/Fp is Galois.

Since xp = x ∀ x in Fp, we have that

Fp ⊂ F(⟨σ⟩)

that is Fp is contained in the fixed field of the cyclic subgroup generated by the Frobenius automorphism σ. But conversely, each element fixed by σ is a root of Xp − X so F(⟨σ⟩) has at most p elements. Consequently

Fp = F(⟨σ⟩)

and

Gal(E/Fp) = ⟨σ⟩

This can be generalized when the base field is larger than Fp.

Corollary: Let E/F be a finite field extension with |E| = pn and |F| = pm. Then E/F is a Galois extension and m|n. Furthermore, the Galois group is cyclic, generated by the automorphism

τ : x → τ(x) = xpm, x ∈ E

Proof:

If the degree [E : F] = d, then every x in E can be written as

x = x1α1 +···+ xdαd and there are pm choices for each xi, thus a total of

(pm)d = pn different elements in E, so that

d = m/n

and

m|n

The same proof as for the above corollary holds for the rest.

Thus a way to construct a finite field E is, given p and n, to construct E = Fpn as a splitting field for Xpn − X over Fp

Theorem:

If G is a finite subgroup of the multiplicative group of an arbitrary field, then G is cyclic. Thus in particular, the multiplicative group E× of a finite field E is cyclic.

Proof:

The proof relies on the following fact: if G is a finite abelian group, it contains an element g whose order r is the exponent of G, that is, the least common multiple of the orders of all elements of G.

Assuming this fact, we proceed as follows: if x ∈ G, then its order divides r and thus

xr = 1

Therefore each element of G is a root of Xr − 1 and

|G| ≤ r

Conversely, |G| is a multiple of the order of every element, so |G| is at least as big as their least common multiple, that is

and

|G| ≥ r |G| = r

Since the order of |G| is r, and it coincides with the order of the element g whose order is the exponent, we have that G is generated by g, that is G = ⟨g⟩ is cyclic. Since E× is cyclic, it is generated by a single element, say α : E = Fp(α) and α is called a primitive element of E. The minimal polynomial of α is called a primitive polynomial.