# Boiled or fried!

Brilliant opening paragraph of a ChessBase report on the NH Chess Tournament. The reporter is the ever entertaining Steve Giddins.

It always used to be said that one knows one is getting old, when the policemen start looking younger. But now it would appear that the chess world has developed a new test. Chess is bad enough as it is, with the annual emergence of ever-younger chess talents. In my day, it was a sensation when Nigel Short qualified for the British Championships at the age of 12, but at the time, he was not even an IM, let alone a GM. Nowadays, 12-year old GMs are becoming almost commonplace. I myself never became a GM, but I still have good chances of becoming a GOM – a Grumpy Old Man. Like every such chessplayer, I hate playing against juniors. The grisly sight of a small head, clad in a baseball cap, peering between its own pieces, guzzling Coke, stuffing crisps and breathing through its mouth all at the same time, whilst simultaneously rattling out 25 moves of Najdorf theory – such a sight has always made me sympathize with W. C. Fields, who when asked how he liked children, replied “Boiled or fried!”

Well, what can we say? Srikanth would wholeheartedly agree with W C Fields, I am sure! And what about me, you ask? No way! I am a strict vegetarian, you should know.

# If only I had a sharper wit!

New student (Ananth Shankar) comes and tells me “Excuse me, Hrishikesh tells me to call you sir.”

I came up with the following brilliance thirty seconds too late: “Oh, please don’t! Just call me Suresh.” And have to be content with only posting it on my blog.

One of those near misses …

# Logic on NPR

Was pleasantly surprised to encounter the following logic puzzle in the latest edition of NPR’s Sunday Puzzle Podcast, which is mostly about word puzzles.

A waitress approaches a breakfast table with five logicians, and asks “Do all of you want a coffee?” The first logician says, “I don’t know.” The second, third and fourth also say (in that order), “I don’t know.” The fifth says, “No!” Who does the waitress give coffee to, and why?

# Axiom of Choice and Zorn’s Lemma

The Axiom of Choice (AC) asserts that for all sets ${\mathcal{A}}$ of nonempty sets, there is a choice function ${f:\mathcal{A} \rightarrow \bigcup\mathcal{A}}$ such that for all ${B \in \mathcal{A}}$, ${f(B) \in B}$.

Zorn’s lemma says that for every partially ordered set ${(A, \leq)}$ such that every chain in ${A}$ has an upper bound in ${A}$, there is a maximal element of ${A}$.

The primary aim is to prove that the Axiom of Choice implies Zorn’s Lemma. For this we use the notion of wellordered sets, which are just linearly ordered sets ${A}$ such that every nonempty subset of ${A}$ has a least element.

To gain some intuition about the proof, let us instead try to define a wellordering of a given set, assuming the Axiom of Choice. For a given set ${A}$, consider a choice function for the set of all nonempty subsets of ${A}$. Then one could try to define a wellordering of ${A}$ as follows: pick ${x_{0}=f(A)}$ as the first element, ${x_{1} = f(A\setminus \{x_{0}\})}$ as the second, ${x_{2} = f(A\setminus \{x_{0},x_{1}\})}$ as the third, and so on. But all the ${x_{i}}$‘s might not exhaust all of ${A}$, so one might have to extend this process of building a wellorder by choosing the element following all the ${x_{i}}$‘s to be ${x_{\omega} = f(A \setminus \{x_{0}, x_{1}, \ldots\})}$. Then we continue with ${x_{\omega+1}, x_{\omega+2}}$, and so on. But even this might not exhaust all of ${A}$ and we have to “jump to another limit point” and so on, to form the desired wellorder by a transfinite procedure. But we do not wish to build the machinery (ordinals) necessary to describe such a procedure. And indeed we do not need to, since the problem we are after is slightly different—that of proving Zorn’s Lemma assuming the Axiom of Choice!

Let us keep the above procedure in mind in trying to prove Zorn’s lemma. We are given a partially ordered set ${(A,\leq)}$ each of whose chains has an upper bound. And we suppose, towards a contradiction, that there is no maximal element, and use this to show that there is indeed a chain of ${A}$ with no upper bound in ${A}$. The chain will be built essentially following the intuition in the above paragraph.

To begin with, notice that every chain ${C}$ in ${A}$ has some upper bound (${x}$, say). Now ${x}$ is not a maximal element of ${A}$, and hence there is some ${y \in A}$ such that ${y > x}$. It follows that ${y > z}$ for every ${z \in C}$. The Axiom of Choice allows us to pick one such ${y}$${u(C)}$, say — for each chain ${C\subseteq A}$.

Now we can try to build our desired chain as follows: let ${x_{0} = u(\emptyset)}$ (this is the same as ${f(A)}$!), ${x_{1} = u(\{x_{0}\})}$, ${x_{2} = u(\{x_{1}, x_{2}\})}$, and so on. The ${x_{i}}$‘s form a chain ${C}$, but there is an element ${u(C)}$ that is strictly greater than all the ${x_{i}}$‘s. So we add ${x_{\omega} = u(C)}$ to the end of ${C}$ to get a larger chain. We can repeat this procedure “forever” (even taking into account “jumps to the next limit point”) to get a chain without an upper bound. This is the idea, but let’s do it a little more formally.

Notice that any chain ${C \subseteq A}$ is an initial segment of this chain that we are hoping to build if and only if ${C}$ is well-ordered by ${<}$ and it has the following property:

$\displaystyle \forall x \in C: x = u(\{y \in C \mid y < x\}). \ \ \ \ \ (1)$

Consider the collection ${\mathcal{C}}$ of all chains ${C}$ that are well-ordered by ${<}$ and that satisfy condition (1). (Intuitively, ${\mathcal{C}}$ is just the collection of initial segments of “our big chain”, but we will have to get at it in a slightly roundabout manner.)

Proposition 1 For distinct ${C}$, ${D}$ in ${\mathcal{C}}$, either ${C}$ is an initial segment of ${D}$ or ${D}$ is an initial segment of ${C}$.

Proof: Let us first prove that either ${C \subseteq D}$ or ${D \subseteq C}$. Suppose neither holds. Then consider the least ${x}$ in ${C \setminus D}$, and the least ${y \in D \setminus C}$. Thus ${C' = \{z \in C \mid z < x\} \subseteq D}$ and ${D' = \{z \in D \mid z < y\} \subseteq C}$. Notice that ${x = u(C')}$ and ${y = u(D')}$. Now, since ${D}$ is a total order, either ${y}$ is greater than every element of ${C'}$, or it is less than or equal to some element of ${C'}$ and thus less than ${x}$.

Suppose the former. We claim that ${C'}$ is an initial segment of ${D}$, for if not, there exist ${d < d'}$ in ${D}$ such that ${d' \in C'}$ and ${d \not\in C'}$. But this is a contradiction, since ${d < d' < y}$ and ${y}$ was supposed to be the least element of ${D}$ not in ${C}$, so ${d \in C'}$ after all! But now we have ${\{z \in D \mid z < x\} = C'}$, and ${D}$ has an element ${y}$ greater than everything in ${C'}$, and thus the least such, ${x = u(C')}$, belongs to ${D}$, a contradiction!

Suppose ${y < x}$. Then by arguing just as above, we can show that ${y}$ belongs to ${C}$, a contradiction!

Thus either ${C \subseteq D}$ or ${D \subseteq C}$. Suppose, without loss of generality, that ${C \subseteq D}$. Since ${C}$ and ${D}$ are distinct, there exists a least ${y \in D}$ that is not in ${C}$. We claim that ${C}$ is an initial segment of ${D}$. Suppose not. Then there is a least ${x \in D}$ such that ${x < y}$ and ${x \not\in C}$. But this means that for all ${z < x}$, ${z \in C}$ if and only if ${z \in D}$. But then ${x = u(\{z \in D \mid z < x\}) = u(\{z \in C \mid z < x\}) \in C}$, a contradiction. Thus ${C}$ is an initial segment of ${D}$. $\Box$

Proposition 2 If ${C}$ is an element of ${\mathcal{C}}$, ${C \cup \{u(C)\}}$ is also an element of ${\mathcal{C}}$.

Proof: Of course ${u(C)}$ will be the largest element in ${C \cup \{u(C)\}}$, and it is easy to see that ${<}$ is a well-ordering of this set, and that (1) is satisfied by ${C \cup \{u(C)\}}$. $\Box$

Proposition 3 ${\bigcup\mathcal{C}}$ is an element of ${\mathcal{C}}$.

Proof: Let ${D = \bigcup\mathcal{C} = \{x \mid \exists C \in \mathcal{C}}$ such that ${x \in C\}}$.

We first show that ${<}$ well-orders ${D}$. Suppose there is an infinite descending chain ${x_{0} > x_{1} > \cdots}$ in ${D}$. Let ${C_{i} \in \mathcal{C}}$ such that ${x_{i} \in C_{i}}$, for each ${i}$. Now it is easy to prove that for all ${i}$, ${x_{i} \in C_{0}}$. It is trivially true for ${i = 0}$. Suppose ${x_{j} \in C_{0}}$ and consider ${x_{j+1} \in C_{j+1}}$. Now if ${C_{0}}$ is an initial segment of ${C_{j+1}}$, it follows that ${x_{j+1} \in C_{0}}$ (from ${x_{j} \in C_{0}}$, ${x_{j} > x_{j+1}}$ and ${x_{j+1} \in C_{j+1}}$). If ${C_{j+1}}$ is an initial segment of ${C_{0}}$ then ${C_{j+1} \subseteq C_{0}}$ and hence ${x_{j+1} \in C_{0}}$. But ${C_{0} \in \mathcal{C}}$ and hence ${<}$ is a well-ordering of it, so there cannot be an infinite descending sequence in ${C_{0}}$, and the same holds for ${D}$.

We now show that every ${C \in \mathcal{C}}$ is an initial segment of ${D}$. Clearly ${C}$ is a subset of ${D}$. We need to show that for every ${x,y \in D}$ such that ${x \in C}$ and ${y < x}$, ${y \in C}$. Let ${C'}$ be some element of ${\mathcal{C}}$ such that ${y \in C'}$. Now either ${C'}$ is an initial segment of ${C}$, in which case ${y \in C}$ (since ${C' \subseteq C}$), or ${C}$ is an initial segment of ${C'}$, in which case also ${y \in C}$ (since ${x \in C \cap C'}$ and ${y \in C'}$ such that ${y < x}$).

Now suppose that ${x \in D}$. Let ${C \in \mathcal{C}}$ such that ${x \in C}$. As we have seen many times now, ${\{z \in C \mid z < x\} = \{z \in D \mid z < x\}}$ and since ${C}$ satisfies (1), it follows that ${x = u(\{z \in D \mid z < x\})}$.

Thus ${\bigcup\mathcal{C} \in \mathcal{C}}$. $\Box$

Now we are almost done. We claim that ${D}$ above has to lack an upper bound in ${A}$, contrary to the assumption that every chain has an upper bound. Because if ${D}$ did have an upper bound, then ${u(D)}$ would be an element greater than everything in ${D}$. But then ${D \cup \{u(D)\}}$ would be a chain in ${\mathcal{C}}$. But this leads to an immediate contradiction, because this means that ${u(D) \in \bigcup\mathcal{C} = D}$, but ${u(D)}$ was supposed to be greater than every element of ${D}$!

The upshot of all this is that for every partially ordered set ${A}$, if every chain ${C \subseteq A}$ has an upper bound in ${A}$, then ${A}$ has a maximal element. Thus the Axiom of Choice implies Zorn’s Lemma.

Update: Many thanks to Shreevatsa, as usual, for pointing out a bug in Proposition 1, which has now hopefully been fixed!

# A math problem …

Yesterday, I had a chance to sit through a problem solving session where Abhishek Dang and Ashwin Deopurkar (final year BScM students at CMI) solved some 2009 IMO problems for the benefit of some school students. According to them, the problems were “actually very easy”. In fact, I was surprised to find that I was able to understand the solutions quite well, but that’s more a testament to their impressive skill in exposition than anything else.

Anyway, here is a nice problem. I am writing this (without permission from either of them!) so that I can refer back to it when I want to, and since otherwise I will forget it completely! It will stay here as long as there is a take-down notice from Abhishek! :-) At which point, Shreevatsa will teach me how to make this post private, I am sure!

Determine all functions $f$ from $\mathbb{N}^+$ to $\mathbb{N}^+$ such that for all $a$ and $b$, the numbers $a, f(b)$ and $f(b+f(a)-1)$ form the three sides of a non-degenerate triangle.

Here is the solution as described by Abhishek.

Take $a = 1$ and let $f(1) = r$. Then we know that for all $b: 1, f(b)$, and $f(b+r-1)$ form the sides of a non-degenerate triangle. In particular, this means that $f(b) + 1 > f(b+r-1)$, i.e. $f(b) \geq f(b+r-1)$ and $f(b+r-1)+1 > f(b)$, i.e. $f(b+r-1) \geq f(b)$. Thus $\forall b: f(b) = f(b+r-1)$. But notice that this says that either $r = 1$ or $f$ is a periodic function. But if $f$ is a periodic function, it is bounded. But then we can choose $a$ large enough (say more than twice the largest value that $f$ can take) so that there is no $b$ for which $a, f(b), f(b+f(a) - 1)$ form a triangle. Thus, it has to be the case that $r = 1$.

Now we have determined that $f(1) = 1$. Let’s play around a little more to gain more information about $f.$ We could try to set $b = 1$ and see what we can learn. Well, in that case $f(b) = 1$ and thus we conclude that for all $a: 1, a, f(f(a))$ form the sides of a nondegenerate triangle. Arguing as before, we see that for all $a: a = f(f(a))$. But this easily implies that $f$ is a bijection from the positive integers to itself.

What more? Try $a = 2$. Let $f(2) = r$. We know that $r > 1$ since $f(1) = 1$ and $f$ is a bijection. Let $r-1 = d$. Now we see that for all $b: 2, f(b), f(b+d)$ form the sides of a nondegenerate triangle. But this means that for all $b: f(b) - 1 \leq f(b+d) \leq f(b)+1$. In particular, since $f$ is a bijection (and $d \neq 0$), we know that for all $b$, either $f(b+d) = f(b)-1$ or $f(b+d) = f(b)+1$.

Now consider the value of $f$ on $1, 1+d, 1+2d, \ldots$. It is an easy proof by induction (using the fact that $f$ is injective) that $f(1+(i-1)d) = i$. But this would mean that $f$ is a bijection between $\{1+(i-1)d \mid i \in \mathbb{N}^+\}$ and $\mathbb{N}^+$, and this can happen only if $d = 1$. And it follows that $f$ is the identity!

Nice, wasn’t it?

# Tattvakaumudī: avatārika

I was planning a different post altogether, but got into a long discussion with Shreevatsa, in the course of which I promised to post a translation of the introductory remarks in the tattvakaumudī by vācaspati miśra. This is an important work in the sāńkhya tradition of Indian philosophy. This work must have been written some time in the 9th or 10th century AD. It is in the form of a commentary on another work (in verse form) called the sāńkhyakārikā by īśvarakṛṣṇa, whose date is not conclusively known. Here goes …

In this world, intelligent people pay attention to those who explain things that are desired to be known by them. Those who set out to explain things that are not desired to be known by them are rejected like a mad man, with the thought: “Here is one neither worldly-wise, nor fit to study lofty things!” Therefore, if the present work has to find acceptance, it should explain things that help one in attaining the supreme goal in life. With this in mind, the work starts by saying that a knowledge of the things it explains are a means of attaining mokṣa, with a view to inducing intelligent people to consider it.

dṛṣṭe sāpārthā cennaikāntātyantatobhāvāt ||

Since men are tormented by the three kinds of sorrows, there is a desire to know the means by which they can be overcome. If it be claimed that a wish to study the śāstra for this purpose is unnecessary, as there are other evident means for overcoming sorrow, we claim that it is not so, for it is not clear that the other means definitely remove sorrows, or that the relief is not temporary.

There will not be a desire to study a work of śāstra in any of the following cases: 1) there is no duḥkham (sorrow or pain) in the world, 2) there is sorrow but it is not sought to be overcome, 3) it is sought to be overcome but there are no means for that, 4) even when there are means for it, the teaching of the śāstra does not contribute anything towards it, and 5) there exist alternate, easier means for overcoming sorrow.

By the words duḥkhatrayābhighātāt (in the verse) it is sought to establish that neither is there not sorrow, nor is it not sought to be overcome. duḥkhatrayam means the triad of sorrows. They are ādhyātmikam (sorrow caused by oneself), ādhibhautikam (sorrow caused by Nature), and ādhidaivikam (sorrow caused by the denizens of the other worlds). Of these, the first is further subdivided into śārīram (physical) and mānasam (mental). The first is caused by the imbalance of the equilibrium between vāta, pitta, etc. The second is caused by feelings like desire, anger, greed, delusion, fear, jealousy, disappointment, etc. All these are sorrows caused by several instruments in oneself.

The rest is caused by factors other than oneself. Sorrow caused by other people, animals, birds, reptiles, trees, etc. is ādhibhautikam, and that caused by a yakṣa, a rākṣasa, an evil spirit, etc. is ādhidaivikam. Thus it is impossible to deny the existence of sorrow that is experienced by everyone, and which is a modification of rajoguṇa.

By abhighātaḥ (torment) is meant the perception of these three kinds of sorrows (which are attributes of the antaḥkaraṇa) and which are perceived by the mind as undesirable. Thus, by saying that sorrow is perceived as undesirable, it has been established that there is a desire to overcome sorrow, and know the means for that.

Even though sorrow or pain is an eternal entity according to the sāńkhya ontology, and is therefore indestructible, we will elaborate later as to how it can be kept at bay. Thus it is not illogical to say tadapaghātake hetau (i.e. that people wish to know the means for the removal of sorrow). The purport is that the revelations of this śāstra is the only means of getting over sorrow, not any other.

Here an objection is raised, beginning with dṛṣṭe sāpārthā cet. The essence of the objection is this: let us admit that there exists the triad of sorrows; that there is a desire to know its nature; that it is possible to overcome it; and that the teachings of the śāstra show the means to overcome sorrow. Yet, it might not be the case that wise and intelligent men wish to know the teachings of this śāstra, since there exist other (easy) means of overcoming sorrow, and since a knowledge of the true purport of the śāstra (tattvajñana) is extremely hard to obtain, being the fruit of long years of study over many births. Thus is it said in this world:

atke cenmadhu vindeta kimartham parvatam vrajet |
iṣtasyārthasya samsiddhau ko vidvān yatnamācaret ||

If honey is available at one’s feet, for what need should one go to the mountain? Once the desired objective is achieved, which wise one would still struggle for it?

There exist hundreds of means to overcome bodily suffering, like medicine recommended by competent physicians, which are moreover easy to practise. For relief from mental suffering too, one has easy means, like the company of a beloved, good food, drink, anointment of the body with sandal and the like, decking oneself in nice clothes and jewels, etc. Similarly in the case of sorrow cause by Nature, there are means to prevent it like leading a life without transgressing the law (??), taking care to live in a place with fewer chances of danger, etc. Similarly the sorrow caused by the denizens of other worlds can be mitigated by maṇi, mantra, auṣadha etc. So why would a wise man wish to learn the śāstra?

This objection is refuted thus. How? By the words ekāntātyantatobhāvāt. By ekāntaḥ is meant the necessary elimination of sorrow (by a means), by atyantaḥ is meant the complete cessation of sorrow (i.e. it does not return). By ekāntātyantatobhāvāt, it is meant that the aforementioned means for removing sorrow either do not necessarily remove sorrow, or do not remove it completely.

The point to be noted is this – even though the proper prescription of medicine, company of a beloved, life led without transgressing the law, mantra, etc. are easy and effective remedies for particular types of pain, it is experienced that sometimes there is no relief, and that sometimes the relief is not permanent. Thus it is reasonable that one wishes to know the means for permanent and definite cessation of sorrow or pain, and since this śāstra sets out to describe such means, it is appropriate for intelligent people to study the present work.

And so it goes on … The commentary for the second śloka is thrice as long as the above, and this is only the beginning, before any specific tenets of sānkhya are asserted!

Why such a post? Just to give a flavour of the kind of exposition followed in the philosophical texts in India, I guess! When I work up the requisite energy, maybe I shall post more translations from more celebrated works. That’s it for now! Bye, and thanks for a patient reading!

I had just then settled down to write a story1. As if waiting for me to sit down, Muthup payal2 called out!

“Yes, athimber! Next-door Balu says that it’s an animal.” “No way! There’s no such animal!”

“Why??” “There’s definitely no such thing!”

“Balu is a very smart chap! He always comes first in class. If he says something, it has to be correct.” “Don’t blabber! He doesn’t know everything.”

“How?” “How what?”

“How can someone not know everything?” “Okay okay. I don’t know. Go!”

“If you don’t know, how can you say that someone doesn’t know everything? He must be knowing everything. You don’t know!”

“No no. I know!” “Then why did you just now say that you don’t know?”

I sat back to make another attempt at the story. Took out the paper and checked whether pen had ink …

Athimber, what will happen if I fall with a thud here?” “Your skull will break!”

“Why so?” “Because of the fall.”

“From where?” “From here.”

“Why should I fall?” “Adei! You were the one who told just now!”

“Then what do we do?” “We visit a doctor.”

“What will happen then?” “Adei, let anything happen! Won’t you go down now?”

“Why such anger, athimber? Will it take very long to tell?” “Yes!”

“Go ahead and tell. I will stay patiently. I don’t have any other work right now.” “But I have!”

“What?” “I am going to write a story.”

“Shall we see? I say you cannot write a story!” “Can!”

“How?” “That I cannot tell.”

“Why not?” “It will take months on end to tell you how.”

“But I’m going to be with you for years on end!” “I have other work!”

“Why work?” “Aren’t we supposed to eat? That’s why I work!”

“Why eat?” “Adei! Go downstairs and talk to your akka4 for a while!”

“She was the one who shooed me away to you!” “Why?”

Muthu was dumbstruck!

Muthu is six. From the day he stumbled upon speech, he has been pestering people with “What?” “Why?” “How?” “Where?” “What for?” … making people run for cover. But have I stumbled upon a way to silence him now? Muthu was standing as if in a trance!

But he recovered in a minute. “It seems I talk too much.” “How?” I didn’t give up!

“How what?” “How which?”

“How what why?” “… are you talking?”

He was all at sea!

He tried to divert me with “Where is my flute?” “Why?”, I persisted!

“What?” “Why?”

He made faces at me, and kicked my chair hard. It looked like he wanted to behead me!

“Very nice!”, I said.

“What?” “If you bend your flute like this, it will break.”

“You can die!” “Then if you try to play it, it will not produce any sound.”

“Ayyayyoh!” “Why?”

The same question again! His anger knew no bounds. My chair got two more kicks. “I shall go tell akka”, he said.

“What?” “What what?” “Why what what?”

Muthu couldn’t bear it anymore. Tears welled in his eyes. He ran to the doorstep.

Dei Muthu!” “What?” “Animal!” “What?” “Kaamaskatka.”

I wrote up the above story in three hours after that. He didn’t show his face to me till I finished!

1. This is a translation of a very short, very cute story in Tamil by Devan, written in the early 1940s perhaps. He adored children, but had none of his own. Many of his stories feature delightful children. This one is a treat!

2. Payal means ‘boy’, literally. But it’s just an affectionate form of addressing kids.

3. Elder sister’s husband (in this story!). It also means father’s sister’s husband.

4. Elder sister.