Quote of the Day

"It is not … the object of logic to determine whether conclusions be true or false; but whether what are asserted to be conclusions are conclusions." – Augustus DeMorgan

Don't Ask Alice - Part the Second

This is the second installment on Dodgson's unsolved sorites - for the first go here: Don't ask Alice, I don't think she'll know. This was the first of Dodgson's sorites I solved. I was unfamiliar with them until I ran across a reference to this sorites by Steven Den Beste, who cited it as an example of problems which were too complex or laborious to solve. Having done research on this topic spurred by Brown's book Laws of Form, and having found the proper form of his suggestion for inference and proven a theorem, I decided to attempt a solution. In 30 minutes I found one and e-mailed Den Beste asking if it was correct. To my surprise, he replied that he did not know because neither Dodgson nor anyone else he was aware of had ever provided a solution; he did however point me to an on-line version of Dodgson's Symbolic Logic, where I discovered all eight of his unsolved problems, and began work on them.

So, without further preamble, here is the second of Dodgson's [hitherto] unsolved sorites:

(1) A logician who eats pork-chops for supper, will probably lose money;
(2) A gambler, whose appetite is not ravenous, will probably lose money;
(3) A man who is depressed, having lost money and likely to lose more, always rises at 5 a.m.;
(4) A man, who neither gambles nor eats pork-chops for supper, is sure to have a ravenous appetite;
(5) A lively man, who goes to bed before 4 a.m., had better take to cab-driving;
(6) A man with a ravenous appetite, who has not lost money and does not rise at 5 a.m., always eats pork-chops for supper;
(7) A logician, who is in danger of losing money, had better take to cab-driving;
(8) An earnest gambler, who is depressed though he has not lost money, is in no danger of losing any;
(9) A man, who does not gamble and whose appetite is not ravenous, is always lively;
(10) A lively logician, who is really in earnest, is in no danger of losing money;
(11) A man with a ravenous appetite has no need to take to cab-driving, if he is really in earnest;
(12) A gambler, who is depressed though in no danger of losing money, sits up till 4 a.m.;
(13) A man, who has lost money and does not eat pork-chops for supper, had better take to cab-driving, unless he gets up at 5 a.m.;
(14) A gambler, who goes to bed before 4 a.m., need not take to cab-driving, unless he has a ravenous appetite;
(15) A man with a ravenous appetite, who is depressed though in no danger of losing money, is a gembler.
Univ. "men"; a = earnest; b = eating pork-chops for supper; c = gamblers; d=getting up at 5; e = having lost money; h = having a ravenous appetite; k = likely to lose money; l = lively; m = logicians; n = men who had better take to cab-driving; r = sitting up till 4.

The solution proceeds exactly as the first problem. Using the classes Dodgson suggested, write the premises as the conjunction:
ρ(M^~B^~K) · ρ(C^~HK) · ρ(LE^~K^~D) · ρ(CBH)ρ(L^~RN) · ρ(H^~EDB) · ρ(M^~K^~N) · ρ(A^~C^~LEK^~) · ρ(CHL) · ρ(L^~M^~A^~K^~) · ρ(A^~H^~N^~) · ρ(C^~LKR) · ρ(E^~BDN) · ρ(C^~RHN^~) · ρ(H^~LKC)
Applying the theorem, canceling those terms which appear both complemented and uncomplemented (shown underlined above), produces the conclusion:

ρ(M^~DRA^~),   or in conventional symbolic notation:
M·¬D·¬R ⇒ ¬A ,   with the interpretation:
"A logician who goes to bed before 4 a.m. and doesn't rise at 5 a.m. is not earnest." (there are, of course, other equivalent symbolic representations and interpretations of this expression). Q.E.D.

An exhaustive analysis of this sorites discovers that if premises can be used more than once (perfectly allowable logically) then these 15 premises are redundant; the set {1, 2, 4, 6, 7, 9, 10, 11, 13, 14} is sufficient for the conclusion. It appears Dodgson was at the limit of his compositional skills with this problem.

Quote of the Day

"Deduction is, or ought to be, an exact science, and should be treated in the same cold and unemotional manner." - Sherlock Holmes (Sir Arthur Conan Doyle, The Sign of Four) -

Don't Ask Alice, I Don't Think She'll Know

Charles Dodgson (a.k.a. Lewis Carroll) is today remembered for his books Alice in Wonderland and Through the Looking Glass. Few are aware that he was a logician and prolific author of many logic puzzles, and was the master composer of sorites. He explained his elementary methods in his book, Symbolic Logic, of which I have a copy of the 4th (last) Edition. There are hundreds of exercises in the book for which he helpfully provided the answers.

He was planning on writing a sequel demonstrating more advanced methods, and as a teaser gave eight problems in the appendix for which he provided no solutions, dying before the new book was published. He commented:

"I will conclude with eight Problems, as a taste of what is coming ... I shall be very glad to receive, from any Reader, who thinks he has solved any one of them ..., what he conceives to be its complete Conclusion."

Unfortunately, his solutions are lost, and I am unaware of anyone solving these puzzles - they are generally considered too complex or not worth the labor required.

This belief is misfounded. Using a simple boolean notation and a remarkable theorem first suggested by G. Spencer Brown, later corrected and proven by me, I will present the solutions to these problems. Beginning at the beginning with the first problem:

All the boys, in a certain School, sit together in one large room every evening. They are of no less the five nationalities - English, Scotch [sic], Welsh, Irish, and German. One of the Monitors (who is a great reader of Wilkie Collins' novels) is very observant, and takes MS. notes of almost everything that happens, with the view of being a good sensational witness, in case any conspiracy to commit murder should be on foot. The following are some of his notes: -
(1) Whenever fome of the English boys are singing "Rule Britannia", and some not, some of the Monitors are wide-awake;
(2) Whenever some of the Scotch [sic] are dancing reels, and some of the Irish fighting, some of the Welsh are eating toasted cheese;
(3) Whenever all the Germans are playing chess, some of the Eleven are not oiling their bats;
(4) Whenever some of the Monitors are asleep, and some not, some of the Irish are fighting;
(5) Whenever some of the Germans are playing chess, and none of the Scotch [sic] are dancing reels, some of the Welsh are not eating toasted cheese;
(6) Whenever some of the Scotch [sic] are not dancing reels, and some of the Irish not fighting, some of the Germans are playing chess;
(7) Whenever some of the Monitors are awake, and some of the Welsh are eating toasted cheese, none of the Scotch [sic] are dancing reels;
(8) Whenever some of the Germans are not playing chess, and some of the Welsh are not eating toasted cheese, none of the Irish are fighting;
(9) Whenever all the English are singing "Rule Britannia", and some of the Scotch [sic] are not dancing reels, none of the Germans are playing chess;
(10) Whenever some of the English are singing "Rule Britannia", and some of the Monitors are asleep, some of the Irish are not fighting;
(11) Whenever some of the Monitors are awake, and some of the Eleven are not oiling their bats, some of the Scotch [sic] are dancing reels;
(12) Whenever some of the English are singing "Rule Britannia", and some of the Scotch [sic] are not dancing reels, ****
Here the MS. breaks off suddenly. The Problem is to complete the sentence, if possible.

The solution proceeds as follows: recognize the following classes: E - English, S - Scotch, W - Welsh, I - Irish, G - German, M - monitors, L - the team of eleven, A - those awake, R - those singing 'Rule Britannia', D - those dancing reels, T - those eating toasted cheese, C - those playing chess, O - those oiling bats, and F - those fighting, and write the 11 premises as the conjunction:
ρ(ρ(E^~R^~)ρ(E^~R)ρ(M^~A^~)^~) · ρ(ρ(S^~D^~)ρ(I^~F^~)ρ(W^~T^~)^~) · ρ(ρ(G^~C)^~ρ(L^~O)^~) · ρ(ρ(M^~A)ρ(M^~A^~)ρ(I^~F^~)^~) · ρ(ρ(G^~C^~)ρ(S^~D^~)^~ρ(W^~T)^~)) · ρ(ρ(S^~D)ρ(I^~F)ρ(G^~C^~)^~) · ρ(ρ(M^~A^~)ρ(W^~T^~)ρ(S^~D^~)) · ρ(ρ(G^~C)ρ(W^~T)ρ(I^~F^~)) · ρ(ρ(E^~R)^~ρ(S^~D)ρ(G^~C^~)) · ρ(ρ(E^~R^~)ρ(M^~A)ρ(I^~F)^~) · ρ(ρ(M^~A^~)ρ(L^~O)ρ(S^~D^~)^~)
Applying the theorem, canceling those terms which appear both complemented and uncomplemented (shown underlined), produces the conclusion :
ρ(ρ(E^~R^~)ρ(S^~D)ρ(M^~A))
so the complete sentence would be :

'Whenever some of the English are singing "Rule Britannica", and some of the Scotch [sic] are not dancing reels, all of the Monitors are awake.' Q.E.D.

I will not go into the details of the notation or the transcription of the premises, for that would require far too much space and time. The purpose of this calculation is to show that the solution to such a seemingly complex problem is actually quite simple if the proper methods are available.

Quote of the Day

"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." - John Von Neumann -

Romanorum computus

"... it is easy to understand that although addition of Roman numerals is quite satisfactory, multiplication and division are essentially impossible." - An overview of Egyptian mathematics

This is the conventional wisdom concerning Roman arithmetic, but it can not be correct since the Romans were great engineers and administrators of a large empire, and these tasks are impossible without efficient methods of multiplication and division. In fact, the previous great empire of Egypt had efficient methods prior to 1850 BCE - a fact known from the Rhind papyrus which is the earliest extant description of their arithmetical methods. It is likely that the Greeks and Romans were aware of these methods and adopted some form of them, since the Egyptian numerals were similar to the later Roman numerals.

Symbol	Value
I	1 (one) (unus)
V	5 (five) (quinque)
X	10 (ten) (decem)
L	50 (fifty) (quinquaginta)
C	100 (one hundred) (centum)
D	500 (five hundred) (quingenti)
M	1000 (one thousand) (mille)

Basically, a Roman number is an abbreviated hash count, where letters are used to stand for a group of hashes as shown in the table. Numerals larger than 5,000 are constructed by placing a bar above these symbols to indicate multiplication of the symbol's value by 1,000, i.e. V(overbar) = 5,000 &tc. A Roman number consists of a string of symbols beginning with the largest symbols followed by symbols of smaller and smaller value. The Romans did not use the modern subtractive notation, so 4 was written as IIII, not IV, 9 as VIIII, not IX, and so on. Addition is then a simple process: simply combine the two number strings, re-arrange the numerals from high to low, and combine any possible groups of symbols and replace by higher value symbols. For example:
CXVI (116) + XXIIII (24) = CXVIXXIIII = CXXXVIIIII = CXXXX (140)
where the base ten values are show in parenthesis, and the group VIIIII has been replaced by X. Subtraction is not much more difficult: eliminate common symbols in both the minuend and subtrahend (indicated below by the strike-thrus), expand symbols in the minuend as necessary to produce the remaining symbols in the subtrahend, complete the elimination, and combine any possible group of symbols, e.g.:
DCCXXVIII (728) - LI (51) = DCCXXVIII - LI = DCLLXXVII - L = DCLXXVII (677)
It is evident that these processes are applicable to any numbers, no matter how large.

Neither of these operations provides any clue as to how multiplication and division could be done. It was certainly not done by the algorithms here, for the number of additions or subtractions for any large multiplier is prohibitive. A Different Kind of Multiplication suggests that they used a form of peasant multiplication.

(1)			(2)
XXVII	(27)	*	LXXXII	(82)
XIII	(13)	*	CLXIIII	(164)
VI	(6)		CCCXXVIII	(328)
III	(3)	*	DCLVI	(656)
I	(1)	*	MCCCXII	(1312)

Consider the problem XXVII (27) x LXXXII (82). Form two columns with the two numbers as the first line (the table will be smaller if the smaller number is in the first column). For the next line, in the first column halve the number above, ignoring any remainder, and in the second column double the number above. Continue this process until only 1 remains in the first column. For all lines for which the number in column one is odd (indicated by the *), add together the corresponding numbers in column two, thusly:
LXXXII+CLXIIII+DCLVI+MCCCXII = MDCCCCCLLLXXXXXVIIIIIIIII = MMCCXIIII (2214)
That this is the correct answer can be easily verified by the reader, and the labor involved is only slightly more than the modern manual method of multiplication using arabic numerals. Dr. David P. Stern, the author of A Different Kind of Multiplication, opines:

"It was probably discovered by trial and error, and it always worked, though the Romans did not know why."

That they didn't know why is probably true, but it is more likely that they learned the method from some other group - perhaps the Greeks - though not the Egyptians, because they used a slightly different method discussed below.

The reason it always works is as follows. Many will recognize that repeated division by 2, keeping track of the remainders, is the method to convert any number to base-2 notation. If the number is even, there is no remainder (i.e., a remainder of 0), while if odd there is a remainder of 1. Reading from the bottom up in column one of the previous table and writing a 1 for the odd numbers and 0 for the even:
11011₂ = 1x2⁴+1x2³+1x2¹+1x2⁰ = 16+8+2+1 = 27
we see that 11011₂ is the correct base-2 representation of 27. If we now multiply by 82:
82x(1x2⁴+1x2³+1x2¹+1x2⁰) = 82x2⁴+82x2³+82x2¹+82x2⁰
because multiplication is distributive. Now:
82x2⁴ = 82x16 = 1312
82x2³ = 82x8 = 656
82x2¹ = 82x2 = 164
82x2⁰ = 82x1 = 82
It is clear that the doubling in column two produces precisely the power of 2 factors that when added together give the correct result. Unfortunately, this does not explain how the Romans would have divided.

(1)		(2)
1	*	82
2	*	164
4		328
8	*	656
16	*	1312
32		2624

The answer is, I believe, a feature of the method used by the Egyptians, which allows for both multiplication and division. The Egyptian method again used two columns, but started with 1 in the first column, the larger number in the second, and doubled both until the result in column one was greater than the smaller factor (in what follows, base-10 notation will be used). Starting with the smaller factor, we repeatedly subtract the largest number in column one less than the remainder until we get 0: 27-16=11, 11-8=3, 3-2=1, 1-1=0 keeping track of the numbers used (marked by the *), and then add the corresponding numbers from column two to get the product as before. This seems little different from and slightly more work than peasant multiplication, but there is a difference - it also allows division. Consider the problem 2250/82 - I have selected a dividend slightly larger than 2214 so there will be a remainder. If from the dividend we repeatedly subtract the largest number in column two less than the remainder: 2250-1312=938, 938-656=282, 282-164=118, 118-82=36, and then add the corresponding numbers from column one, 16+8+2+1=27, then 2250/82 = 27 with a remainder of 36. The suggestion that the Egyptian method is equally useful for division is an original one which I have seen nowhere else.

As to what method the Romans actually used, the answer is no one knows for sure. The age of the peasant method and the presence of the 5 factor symbols in the Roman numerals, facilitating halving and doubling, argues for the use of the peasant method, but leaves the explanation of division unresolved. What is amazing is the fact that nearly 4,000 or more years ago some unknown mathematical genius discovered that any number can be represented as a sum of powers of two, that multiplication is distributive, and combined these insights into efficient algorithms for multiplication and division, reducing them to the simpler operations of doubling, adding, and subtracting.

Quote of the Day

My strange behavior as a child is easily explained: I was training to become a strange adult. - Ashleigh Brilliant -

Rooting for Old Squares

It is not commonly known that there exists an algorithm for manually calculating square roots which is somewhat similar to long division. This method was taught in public high schools until at least the 1930's, when my father learned it, and later passed it on to me. The existence of such a method was never mentioned in my high school in the 1960's and it is certainly unknown and ignored today with the availability of modern calculators. It is best illustrated by example, and I arbitrarily decided to find the meaningless square root of the current year number, 2007, as shown and explained in what follows:

		(ii)	(iii)	(iv)	(v)	(vi)	(vii)	(viii)
		4	4.	7	9	9	5	5   ...
	√	20^	07.	00^	00^	00^	00^	00^ ...	(i)
	-	16							(ii)
		4	07
84		-3	36						(iii)
			71	00
887		-	62	09					(iv)
			8	91	00
8949			-8	05	41				(v)
				85	59	00
89589			-	80	63	01			(vi)
				4	95	99	00
895985				-4	47	99	25		(vii)
					47	99	75	00
8959905				-	44	79	95	25	(viii)
					3	19	79	75

i)  Split the number into 2 digit groups in both directions from the decimal point (indicated by the carat _^).
ii)  For the leftmost group (20), find the largest integer whose square is less than or equal to the group (4); write it above the group; square it (16), write below, and subtract to find the remainder. Bring down the next group of digits.
iii)  Double the digit of the root (2x4=8) and write it next to the remainder. Find the largest integer ? such that 8? x ? ≤ 407; in this case 4, which is written above. Multiply 84 x 4 = 336, write below the remainder, subtract, and bring down the next group of digits.
iv)  Double the digits of the root (2x44=88) and write it next to the remainder. Find the largest integer ? such that 88? x ? ≤ 7100; in this case 7, which is written above. Multiply 887 x 7 = 6209, write below the remainder, subtract, and bring down the next group of digits.
v)  Double the digits of the root (2x447=894) and write it next to the remainder. Find the largest integer ? such that 894? x ? ≤ 89100; in this case 9, which is written above. Multiply 8949 x 9 = 80541, write below the remainder, subtract, and bring down the next group of digits.
vi)  Double the digits of the root (2x4479=8958) and write it next to the remainder. Find the largest integer ? such that 8958? x ? ≤ 855900; in this case 9, which is written above. Multiply 89589 x 9 = 806301, write below the remainder, subtract, and bring down the next group of digits.
vii)  Double the digits of the root (2x44799=89598) and write it next to the remainder. Find the largest integer ? such that 89598? x ? ≤ 4959900; in this case 5, which is written above. Multiply 895985 x 5 = 4479925, write below the remainder, subtract, and bring down the next group of digits.
viii)  Double the digits of the root (2x447995=895990) and write it next to the remainder. Find the largest integer ? such that 895990? x ? ≤ 4959900; in this case 5, which is written above. Multiply 8959905 x 5 = 44799525, write below the remainder, subtract, and continue as required.
The process terminates when the remainder is zero and all remaining groups are also zero, otherwise it can be continued indefinitely.

Why does this curious process work? The doubling might raise the suspicion of some relation to Newton's method, but this is incorrect. An analysis can begin by considering the successive steps as generating a sequence of approximations to the square root, i.e.: {x₁, x₂, x₃, x₄, ...} = {40, 44, 44.7, 44.79, ...} and examining their error:
2007 - 40² = 407
2007 - 44² = 71
2007 - 44.7² = 8.91
2007 - 44.79² = 0.8559
...
Thus, on comparison with the example calculation above, the method correctly produces, in the form of the remainder, the error after each step. More generally, consider some number, n, and a series of approximations to its square root, {x₁, x₂, x₃, x₄, ...}. For some approximation, x_i, the error is (n-x_i²), the next digit of the approximation would be (x_i+1-x_i}, and the doubled multiplicative term is then (2x_i+(x_i+1-x_i)), so the remainder for the (i+1) approximation is calculated by the method as:
(n-x_i²)-(2x_i+(x_i+1-x_i))·(x_i+1-x_i) = (n-x_i²) - (x_i+x_i+1)·(x_i+1-x_i) = (n-x_i²) - (x_i+1²-x_i²) = (n-x_i+1²)
This shows that the method rests on an algebraic identity which correctly produces the remainder assuming the correct digit of the next approximation is found. The origin or author of this method is unknown to me, but it seems likely to have followed the introduction of arabic numerals.

Quote of the Day

"Well," he said, "I say now, as I said then, that a man should keep his little brain attic stocked with all the furniture that he is likely to use, and the rest he can put away in the lumber room of his library, where he can get it if he wants it." - Sherlock Holmes (The Five Orange Pips) -