Monthly Archives: March 2015

Hávamál 77 in Wendoth

Lately I’ve been working on a conlang called Wendoth, and I’ve translated Stanza 77 of the Hávamál into it. The original poem goes like this:

Deyja fé, (‘Cattle die,’)
deyja frændr, (‘kinsmen die,’)
deyr sjálfr et sama; (‘you yourself die,’)
ek veit einn, (‘I know one thing’)
at aldri deyr: (‘which never dies:’)
dómr um dauðan hvern. (‘the judgement of a dead man’s life.’)

Like the original stanza, the translated stanza has six lines, with every third line having three feet and the other lines having two feet; also, each foot is an anapest, and it has an AACBBC rhyme scheme. It goes like this:

Kejazang ouųt-thash; (‘Cattle die,’)
kashewoq ouyehąsh; (‘kinsmen die;’)
ndaidh shuųzh thash ouųt aųpnin sum; (‘at some time, everyone dies,’)
cai mangedh qe, asfą, (‘but one thing, however,’)
xaidh shuųzh ouyehą: (‘never dies:’)
gaxaihi seb andresh įwanum. (‘the respect that we give to the virtuous.’)

This is written in the language’s idosyncratic orthography. An IPA transcription is given below, showing the syllable breaks with dots (.) and the foot breaks with bars (|).

kʲə.ɣʲaˈzˠaŋ |aṳ.ṵt̪.ˈθasʲ
kʲa.sʲə.ˈwoq |aṳ.lʲə.ˈʁa̰sʲ
n̪d̪ai̤ð sʲṳː.ˈṵzʲ |θasʲ aṳ.ˈṵt̪ |aṵp.ni̤n ˈsˠṳm
xʲai̤ ma.ˈŋəð |qə asˠ.ˈfa̰
χai̤ð sʲṳː.ˈṵzʲ |aṳ.lʲəˈʁa̰
gʲa.χai̤.ˈʁi̤ |sˠəb an̪d̪.ˈrəsʲ |ḭː.lˠa.ˈnṳm

Glosses of each line are given below.

Kejazang auųt-thash;
kejazang hau -Į  -ta tha      -sha 
cattle   INCH-ACC-to come.NPST-GEN 
'Cattle die,'

The word kejazang is a shortening of earlier *kejazohang < Pre-Wendoth kiɣe-za ran ‘domestic aurochs’ (literally ‘aurochs that are kept’). auųt-thash, literally ‘come to a finish’, is an idiomatic expression meaning ‘die’. The more usual way of expressing ‘die’ in Wendoth is with the word auyehą, literally ‘start to be dead’, which is used in the next line. Also, the more usual word order here would be to put the adverbial expression auųt after the verb thash, but it has been put before the verb here so that the final -ash rhymes with the -yąsh of the second line (a and ą are not the same phoneme, but they differ only in phonation, and differences in phonation are ignored for rhyming purposes).

kashewoq ouyehąsh;
kashewoko hou -yehą   -sha
kinsman   INCH-be_dead-GEN
'kinsmen die;'

The word kashewoq is a compound noun: kashe- ‘blood’ + woko- ‘friend’. The -k- of woko- alternates between its light realisation, -k-, and its heavy realisation, -q-; as no suffix has been added, it is realised as -q.

ndaidh shuųzh thash ouųt aųpnin sum;
ndai-edha    shu -Į  -zha  tha      -sha hou -Į  -ta
some-ABS.NOM time-ACC-from come.NPST-GEN INCH-ACC-to
paųn-ina     sum
all -NOM.HUM person
'at some time, everyone dies;'

The noun shu refers to a period of time. In this sentence, it appears in the accusative case as the object of the postposition -zha. -zha is used for various purposes, but when its object is in the accusative case it can be glossed as ‘from’. It is used here because the period of time referred to is in the future; if the period of time was in the past -ta ‘to’ would be used.

As there is no rhyming requirement here, the usual word order is used for the phrase thash auųt. Auyehą could just as well be used here, but using thash auųt avoids repetition.

cai mangedh qe, asfą,
cai mang-edha    qe    safą
but one -ABS.NOM thing however
'but one thing, however,'

The most usual place to put asfą would be immediately after cai, but as it is an adverb, it can be placed in many different positions. Here, it has been placed at the end to allow for a rhyme of with the next line.

xaidh shuųzh ouyehą:
xai-edha    shu -ų  -zha  hou  -yehą
no -ABS.NOM time-ACC-from INCH-be_dead
'never dies:'

The determiner xaI- ‘no’ is considered the antonym of maI- ‘some’, and therefore has probably acquired the same vowel by analogy. It probably originates from the negative particle xe ‘not’.

gaxaihi seb andresh įwanum.
gaxaihi seb        FEL-rem -sha įwan   -nu -ma
respect 1p.INCL.PL ndo-give-GEN be_good-NOM-DAT
'the respect that we give to the virtuous.'

There are two first-person plural pronouns in Wendoth: seb and eq. seb is used to include the addressee, and is therefore most appropriate here, while eq is used to exclude the addressee. The ndo- prefix on the verb rem- ‘give’ here is an argument reference marker used to refer to things like thoughts, feelings and opinions. It is used here to indicate that the verb is relativised. Usually, a relativised verb comes immediately after its head noun, so that seb here should come after andresh rather than before it. But the order can vary, and it has been varied here in order to fit the meter.

The suffix -nu is a nominaliser that turns a veb meaning ‘to X’ into a noun meaning ‘a person who Xes’. Thus įwanu means ‘good person’, or, to be more precise, ‘virtuous person’.

Advertisements

Some thoughts on how people come up with mathematical proofs

Everyone who has studied mathematics and tried to prove things themselves will have realised that the process is quite different from what you might imagine from the proofs given in textbooks. In textbooks, proofs are made up of a sequence of statements which are, roughly, ordered by implication: the proof begins with the hypotheses of the theorem, and the statements derive conclusions from these hypotheses and from the conclusions of previous statements until finally the statement that is to be proved is concluded. But when you are coming up with a proof yourself, you can’t just derive things from the hypotheses without bearing in mind what conclusion you’re aiming for. After all, there are infinitely many statements that could be derived from the hypothesis and only some of these will help lead you towards the inclusion. Instead, you often have to work backwards, trying to find hypotheses that imply the desired conclusion, so that you can aim to conclude the statements of these hypotheses from your original hypotheses, rather than aiming for the desired conclusion directly. Of course, you have to bear in mind what the original hypotheses are while doing this. So you end up constantly alternating between working forwards and working backwards until finally everything links up somewhere in the middle. Deduction can be thought of, in metaphorical terms, as a kind of journey. In the textbooks, you have a group of people, corresponding to the hypotheses, travelling towards their destination, which corresponds to the conclusion. But deduction as a mental process is more like a meeting between two parties.

I thought it might be interesting, therefore, to try and write down how I came up with a proof, to show you how the process works. The thing I’m going to prove is the following statement.

Theorem 1. There is a rational number between every pair of distinct real numbers.

The proof will be different, of course, depending on how you define the real numbers. My proof will use the axiomatic definition of the real numbers. In case you are not familiar with this, the axiomatic definition is the one where we don’t really worry about what the real numbers are; we just list some of the most essential properties of the real numbers, and see what we can prove if we assume that these properties hold. These assumed properties are called our axioms. Although this might seem philosophically dubious, if we can prove something from the axioms, then we can be quite sure that it is a true fact about the real numbers, regardless of how we define them, because we can always be sure that the axioms hold. After all, the axioms are the most essential properties of the real numbers. If we were to define the ‘real numbers’ in such a way that not all of the axioms held, it could be reasonably argued that these objects were not, in fact, real real numbers. (This is kind of like what I was talking about in the above paragraph. Rather than going directly from a more concrete definition of the real numbers to the Theorem 1, we are just going to prove that certain hypotheses—the axioms—imply Theorem 1, and we can be satisfied with that since we can assume that given any concrete definition, we will be able to derive the axioms.)

The axioms we will use mostly consist of elementary algebraic facts that you learn in school, such as the fact that adding 0 to a number doesn’t change it, or the fact that the product of two positive numbers is positive. I assume the reader is familiar with these facts. The only axiom which will be new to you, unless you’ve taken a course in real analysis, is the axiom of completeness. The axiom of completeness is a bit complicated, so I won’t tell you what it is here; instead, I’ll just assume a weaker form of the axiom called the axiom of Archimedes. The axiom of Archimedes is simply the statement that no real number is greater than every integer. The axiom of completeness implies the axiom of Archimedes, but the axiom of Archimedes does not imply the axiom of completeness. However, the axiom of Archimedes is all we need to prove Theorem 1; we won’t need to use the full axiom of completeness.

Now we know, more or less, exactly what we’re trying to prove. It’s always very important to make sure you know this before trying to make a proof, otherwise the attempt will be hopeless. Let’s finally make a start on the proof itself. The statement to be proven is that there is a rational number between every pair of distinct real numbers. The natural way to carry out the proof of a statement like this is to show how, given two distinct real numbers a and b, we can find a rational number r between a and b. For example, we might be able to find a formula for r in terms of a and b. It’s not immediately obvious how we might find such a formula, though. It’s easy to give a formula for a real number between a and b; for example, (a + b) / 2 is a real number between a and b. The problem is in making sure that the number is rational. There aren’t any ways of combining arbitrary real numbers using simple arithmetic operations that will ensure that the result is rational.

Let’s think about what it means for a number to be rational. It means that it can be expressed as a fraction with an integral numerator and an integral denominator. In other words, r is rational if and only if there are two integers m and n such that r = m / n. In fact, because we can cancel out the common factors of m and n if they have any, and we can transfer a minus sign in n up to m, we can express every rational number as a fraction whose numerator and denominator have no common factors and whose denominator is positive. So what we’re looking for is a number of the form m / n, where m and n are integers with no common factors and n is positive, which is between a and b.

As a and b are distinct, one of them must be greater than the other. Let’s assume that b is the greater one. This assumption does not limit us in any way; if b is actually the smaller one, then we can just swap the names of a and b. Then, if m / n is to be between a and b, that means that a < m / n < b. Now, it’s always convenient to get rid of divisions if we can help it. And since n is positive, we can multiply the parts of any inequality by n, and the inequality will still hold; in fact, it will also imply the old one. So, the inequality a < m / n < b is equivalent to the inequality n a < m < n b. Hence, in order to prove Theorem 1, we can prove the following equivalent theorem (which we’ll call a lemma, actually, since that’s the usual term for theorems you are only interested in so that you can prove other theorems with them).

Lemma 1. For every pair of distinct real numbers a and b, there is an integer between n a and n b for some positive integer n.

The difference between Theorem 1 and Lemma 1 is minor; the two are completely logically equivalent statements; and yet Lemma 1 a lot easier to think about, visually. If you had never been told that there is a rational number between every pair of distinct real numbers before, you’d probably be somewhat unsure if it was true. But if you think about what Lemma 1 means, it isn’t too difficult to see that it’s true. Think about the distance between n a and n b on the number line, given an arbitrary positive integer n. This is n b - n a (using the fact that b is greater than a). But this can also be written as n (b - a). So it’s the distance between a and b, enlarged by a factor of n. Now, all the statement requires is that there is an integer somewhere in the n (b - a)-width interval between n a and n b for some positive integer n. In particular, it doesn’t matter how big n needs to be. So the question becomes: is it possible to enlarge the gap between a and b so much that there is at least one integer within the enlarged gap, if we restrict ourselves to integral scale factors, but allow the scale factor to be as large as we like? Well, if the distance between n a and n b (where n is the scale factor) is greater than 1, there will have to be an integer in the interval between n a and n b. And the distance between n a and n b is proportional to n. So, if we can make n as large as we like, we can make the distance between n a and n b as large as we like; in particular we can make it greater than to 1. And then we’re done! (Note that I’ve tacitly relied on the axiom of Archimedes here—can you see why? If not, I’ll explain how shortly.)

At this point, I’m pretty much convinced that Theorem 1 can be proven, but what I said above wasn’t really up to the usual standards for a proof, it was more of an intuitive justification. We need to state precisely how Theorem 1 follows from the axioms. The chief weak point in the reasoning above is the statement that as long as the distance between n a and n b is greater than to 1, there is an integer in the interval between n a and n b. It probably seems pretty obvious that this is true; in general, for every pair of real numbers x and y such that x < y and y - x > 1, there is an integer k such that x < k < y, or so you would think based on intuition. But I can’t immediately see how it follows from the axioms. So let’s try and prove it. The first thing that occurs to me is that we can easily find an integer k such that x < k. Because the existence of such an integer is more or less exactly what the axiom of Archimedes asserts. If there was no such integer, then x would be greater or equal to every integer, and hence x + 1 would be greater than every integer, but the axiom of Archimedes states that no real number is greater than every integer. So the question is, of these integers k such that x < k, how can we find one which is less than y? Well, we’re pretty sure that what we’re trying to prove is true, so there must be at least one integer k' which is greater than x but less than y. Therefore, the least integer k such that x < k must also be less than y, because it is less than k'. So, if we let k' be this least integer, we should be able to prove that k' < y, somehow. But how? A useful thing to do in this kind of situation is to remember what assumptions we have made. If the statement you’re trying to prove can be false if one your assumptions does not hold, you’re going to have to make use of that assumption in the proof; otherwise, your proof would work just as well at proving the statement without making that assumption, yet the statement is not true without that assumption. So we’re necessarily going to have to use the fact that k' is the least integer k such that x < k, because there are integers k such that x < k but y \le k (since the axiom of Archimedes ensures that there are integers greater than y, and y is greater than x). And we’re going to have to use the fact that y - x > 1 at some point, of course. Any ideas? Here’s something: we can rearrange the inequality y - x > 1 to get y > x + 1. Now, let’s suppose that, counter to what we suspect is true, y \le k. Then, since x + 1 is less than y, we have x < k as well. Rearranging this, we have x < k - 1. But if x < k - 1, then k is not the least integer k such that x < k. So our supposition that y \le k leads to an inevitable contradiction. We can therefore conclude that, in fact, k < y, which is what we needed to prove.

So, now let’s return to Lemma 1 and prove it with greater rigour. Remember, we need to find a positive integer n such that there is an integer between n a and n b. The first thing we need to do is to decide what value of n to use. We want the distance between n a and n b, n (b - a), to be greater than 1, i.e. n (b - a) > 1. Dividing both sides of this inequality by b - a (which we can do because a < b, so b - a is positive) we get n > 1 / (b - a). Can we find a positive integer n greater than 1 / (b - a)? Yes, of course we can, by the axiom of Archimedes. The axiom of Archimedes ensures that there is an integer greater than 1 / (b - a); it doesn’t say anything about whether it’s positive; but since 1 / (b - a) is positive, it has to be positive. So we have our value of n. Of course we don’t know exactly what it is, but we know that a value which will work exists. Now, since the distance between n a and n b is greater than 1, we can immediately conclude that there is an integer between n a and n b by what we proved above. This completes the proof of Lemma 1, and thereby Theorem 1.

Just to be totally sure, let’s write the proof out, textbook style.

Theorem. For every pair of distinct real numbers a and b, there is a rational number r such that a < r < b.

Proof. Suppose a and b are real numbers and a < b. Since b - a is positive, 1 / (b - a) exists, and in fact is positive, and by the axiom of Archimedes there is an integer n such that 1 / (b - a) < n. Since 1 / (b - a) is positive, n has to be positive. Also, since b - a is positive, we can multiply both sides of the inequality by b - a to get 1 < n (b - a) = n b - n a. It follows that there is an integer m such that n a < m < n b. Since n is positive, we can divide each part of this inequality by n to get a < m / n < b. As m and n are both integers, m / n is rational.

So, in the end, the proof is just 7 sentences. If you followed this through to the end, you can probably see what I mean about the textbook proofs making things look a lot simpler. And even the description I’ve given in this post has omitted some of the messier details of the process. For example, as I wrote it I made occasional minor errors, mainly to do with strict and non-strict inequalities (for example, I originally only proved that there was an integer between any two real numbers separated by a distance greater than or equal to to 1, which is true, but not sufficient to imply Theorem 1 as the integer might be equal to one of the two real numbers). I opted to correct those rather than leaving them in and making things more confusing. So, hopefully, this has given you some insight into how mathematicians come up with proofs, if you didn’t know much about it already. Bear in mind, though, that this is a pretty straightforward undergraduate-level theorem. Professional mathematicians have to deal with proofs that are much, much, harder and more complicated.

Large and small sets

For some infinite sets {S = \{x_1, x_2, x_3, \dotsc\}} of positive integers, the sum of the reciprocals of the members of {S}, i.e.

\displaystyle \frac 1 {x_1} + \frac 1 {x_2} + \frac 1 {x_3} + \dotsb,

diverges. Such sets are said to be large. For example, {\mathbb N}, the set of all the positive integers, is large, because the harmonic series diverges. On the other hand, for some infinite sets {S} the sum of the reciprocals of the members of {S} converges instead; such sets are said to be small. For example, for every integer {p} greater than 1, the set of all the positive integral {p}th powers is small, because the series

\displaystyle 1 + \frac 1 {2^p} + \frac 1 {3^p} + \dotsb

converges. There is thus an interesting distinction between two different sizes of infinite sets of positive integers. Let’s have a look at some other infinite sets of positive integers and see whether they are large or small.

For every positive integer {m}, the set of all the positive integral multiples of {m} is easily seen to be large, due to the fact that the harmonic series diverges, and dividing the harmonic series by {m} yields the series

\displaystyle \frac 1 m + \frac 1 {2 m} + \frac 1 {3 m} + \dotsb.

In fact, this proof can easily be generalised to show that for every set {S} of positive integers and every positive integer {m}, {\{m n : n \in S\}} is large if and only if {S} is large.

What about the set {S} of all the positive integers which are not multiples of {m}? The sum of the reciprocals of the members of {S} can be written as the difference

\displaystyle \left( 1 + \frac 1 2 + \frac 1 3 + \dotsb \right) - \left( \frac 1 m + \frac 1 {2 m} + \frac 1 {3 m} + \dotsb \right).

The minuend and subtrahend of this difference are both equal to {\infty}, so the sum of the reciprocals of the members of {S} cannot be immediately seen from writing it like this. However, if we take out the factor of {1 / m} from the subtrahend, we get

\displaystyle \left( 1 + \frac 1 2 + \frac 1 3 + \dotsb \right) - \frac 1 m \left( 1 + \frac 1 2 + \frac 1 3 + \dotsb \right),

and then we can remove the common factor of {1 + 1 / 2 + 1 / 3 + \dotsb} to get

\displaystyle \left( 1 + \frac 1 2 + \frac 1 3 + \dotsb \right) \left( 1 - \frac 1 m \right).

It is easy to see that the value of this expression is also {\infty}. So {S} is large, as well.

In fact, for every finite set of pairwise coprime positive integers {p_1}, {p_2}, … and {p_{\ell}}, the set {S} of all the positive integers which are not multiples of any of these integers is large, too. This is because, if we let {H} be the value of the harmonic series, then, using the inclusion-exclusion principle, the sum of the reciprocals of the members of {S} can be written as

\displaystyle H - \sum_{k} \frac H k + \sum_{k_1, k_2} \frac H {k_1 k_2} - \dotsb + \frac {(-1)^{\ell} H} {k_1 k_2 \dotsm k_{\ell}},

in which, for every integer j such that 1 \le j \le \ell, the jth term is a sum over all the finite sets of j integers k such that 1 \le k \le \ell. By factorising this expression, we can rewrite it as

\displaystyle H \left( 1 - \frac 1 {p_1} \right) \left( 1 - \frac 1 {p_2} \right) \dotsm \left( 1 - \frac 1 {p_{\ell}} \right),

and it is easy to see that the value of this expression is {\infty}.

Generalising from this, one might expect that if we let {P = \{p_1, p_2, p_3, \dotsc\}} be the prime numbers, so that the members of {P} are pairwise coprime and every integer is a multiple of a member of {P}, then

\displaystyle   H \left( 1 - \frac 1 {p_1} \right) \left( 1 - \frac 1 {p_2} \right) \left( 1 - \frac 1 {p_3} \right) \dotsm = 1. \ \ \ \ \ (1)

To prove this rigorously, all that is needed is to note that for every positive integer {n},

\displaystyle H \left( 1 - \frac 1 {p_1} \right) \left( 1 - \frac 1 {p_2} \right) \dotsm \left( 1 - \frac 1 {p_n} \right) = 1 + K,

where {K} is the sum of the reciprocals of the integers greater than 1 which are not multiples of any of the first {n} prime numbers. The least such integer is {p_{n + 1}}, so {K} is smaller than the sum of the reciprocals of the integers greater than or equal to {p_{n + 1}}. Therefore,

\displaystyle H \left( 1 - \frac 1 {p_1} \right) \left( 1 - \frac 1 {p_2} \right) \dotsm \left( 1 - \frac 1 {p_n} \right) < 1 + \frac 1 {p_{n + 1}} + \frac 1 {p_{n + 1} + 1} + \frac 1 {p_{n + 1} + 2} + \dotsb.

As {n} tends towards positive infinity, the sum of the reciprocals of the integers greater than or equal to {p_{n + 1}} tends towards 0, because it can be written as {H - H_{p_{n + 1} - 1}}, which is less than {H - H_n}, and by definition {H_n} tends towards {H} as {n} tends towards positive infinity. So the right-hand side of the inequality above tends towards 1, and an application of the squeeze theorem completes the proof.

Rearranging (1) to solve for {H} yields

\displaystyle H = \left( \frac 1 {1 - 1 / p_1} \right) \left( \frac 1 {1 - 1 / p_2} \right) \left( \frac 1 {1 - 1 / p_3} \right) \dotsm,

so we now have a way of expressing the harmonic series as an infinite product. This is quite interesting in its own right, but it can also be used to prove a rather surprising result. By taking the natural logarithm of both sides, we see that

\displaystyle \ln H = \ln \left( \frac 1 {1 - 1 / p_1} \right) + \ln \left( \frac 1 {1 - 1 / p_2} \right) + \ln \left( \frac 1 {1 - 1 / p_3} \right) + \dotsb.

The natural logarithm of {\infty} is {\infty}, so this means the series on the right-hand side diverges. For every positive integer {n}, the {n}th term of the series on the right-hand side, {\ln (1 / (1 - 1 / p_n))}, can also be written as {\ln (1 + 1 / (p_n - 1))}, and this number is less than or equal to {1 / (p_n - 1)} (in general, for every real number {x} greater than {-1}, {\ln (1 + x) \le x}). If {n} is greater than 1, then this number, in turn, is less than or equal to {1 / p_{n - 1}}, because {p_n - 1} is greater than or equal to {p_{n - 1}}. And {1 / (2 - 1)}, i.e. 1, is less than or equal to 1. So, by the comparison test, the series

\displaystyle 1 + \frac 1 {p_1} + \frac 1 {p_2} + \frac 1 {p_3} + \dotsb

diverges, too. This shows that the set consisting of 1 as well as all the prime numbers is large, but it is then an immediate consequence that the set of all the prime numbers, not including 1, is large (since we can subtract 1 from the above series and the value of the result will still have to be {\infty}).

This is a rather interesting and surprising result. The set of all the prime numbers is large, but for every positive integer {p}, the set of all the positive integral {p}th powers is small, which means that, in a certain sense, there are more prime numbers than positive integral {p}th powers.