I just posted a note on PhilPapers, which is also forthcoming in Philosophy of Science. (It is a bit weird for a completely mathematical paper to show up in Philosophy of Science, but it is what it is…)
The main feature of this note is that it describes a question that I could not solve. But this question is so simple that it can be explained to any mathematics undergrad or even high school student. So here we go…
Cantor tells us that infinite sets have different sizes.
Click for quick review of Cantor…
According to Cantor, the size of set \(A\) being equal to the size of set \(B\) means there is a perfect correspondence between them. For example, we have \(0\mapsto 0, 1\mapsto 2, 2\mapsto 4, \dots, n\mapsto 2n, \dots\), so the set of natural numbers \(\{0, 1, 2, 3, \dots\}\) and the set of even numbers \(\{0, 2, 4, \dots\}\) have the same size. Sets that have the same size as the natural numbers are called “countable”, and they are the smallest among the infinite sets. On the other hand, the set of real numbers is larger than countable sets, since Cantor discovered that for any countable list of real numbers we can always find yet another real number that is not in the list.
Cantor’s theory has a interesting feature: although the even numbers are only “half of” the natural numbers, in Cantor’s theory these sets have the same size!
Consequently, the possible number of sizes is quite small. For example, any infinite subset of a set of size \(\aleph_7\) (the 8th level of infinity, with the countable sets at the 1st level \(\aleph_0\)) must be at one of these 8 levels — although there are \(2^{\aleph_7}\)-many subsets, a huge number in comparison to 8! In other words, we are classifying these \(2^{\aleph_7}\)-many subsets into merely 8 baskets.
What if we want to say that the set of even numbers has a smaller size than the set of natural numbers? We would need an alternative definition of size. The part-whole principle says if set \(A\) is strictly contained in set \(B\), then the size of \(A\) is strictly less than the size of \(B\).
The question I could not solve is the following: suppose we are given an infinite set \(\kappa\), and we assign a size for its subsets, while respecting the part-whole principle. That is, we are classifying \(2^\kappa\)-many subsets into a number of baskets, according to their size. What is the minimum number of baskets that we need?
Clearly we would need many more baskets than Cantor (e.g. the natural numbers and the even numbers were in the same basket, now we need two different ones), and this number will grow as \(\kappa\) grows. But how many?
In my note I determined that this number is at least \(\text{ded } \kappa\) — a quantity associated with \(\kappa\) that is greater than \(\kappa\), an improvement over previous results.
The quantity \(\text{ded } \kappa\) is of independent interest, since it relates to another bizarre feature of the infinite. Now let me briefly tell you what it is.
Think of a line segment, a rope, a banana, or what have you. If you cut it once in the middle, you get two segments. If you cut it 2 times, you get 3 segments. If you cut it \(n\)-times, you get \(n+1\)-many segments. Sounds quite trivial, right?
However, the situation is a bit different when you can cut infinitely many times. Think of your line segment as the interval \([0, 1]\) of real numbers. Now let us make cuts at all the rational numbers. How many segments do we get? Observe that any two irrational numbers belong to different segments, since between them there is a rational number where we made a cut, by the density of rationals. From Cantor, we know that there are countably many rational numbers but uncountably many irrational numbers. So this is indeed a very bizarre situation: with countably many cuts, we can produce uncountably many pieces! This forms a sharp discontinuity with the finite case, where the number of pieces \(n+1\) is effectively the same as the number of cuts \(n\).
One mathematician who identified this phenomenon was Richard Dedekind, who actually defined real numbers as the collection of cuts that you can make on rational numbers. What if we make even more than countably many cuts?
Consider an infinite number \(\kappa\) and let us make \(\kappa\)-many cuts. The maximal number of pieces you can get is exactly \(\text{ded }\kappa\), named after Dedekind. Just as we observed, you can cut countably many times and get uncountably many pieces, it is generally true that \(\text{ded }\kappa>\kappa\).
Cantor and Dedekind, generated by ChatGPT Image 2
Finally let me tell you why I can’t solve my problem.
We have \(2^\kappa\)-many sets to be classified, and it is known that it is possible to classify them into \(2^\kappa\)-many baskets while respecting the part-whole principle. Now that I showed one needs at least \(\text{ded } \kappa\)-many baskets, if \(\text{ded }\kappa=2^\kappa\), the question would be solved. But the problem is, while \(\text{ded }\kappa\le 2^\kappa\), whether they are equal for all \(\kappa\) is independent of the fundamental assumptions of mathematics, known as \(\mathsf{ZFC}\). In other words, there are some mathematical universes where \(\text{ded }\kappa< 2^\kappa\) at some \(\kappa\). Can we make the assignment with less than \(2^\kappa\)-many baskets in these situations?
I tried to settle this question for a bit but it appears beyond me. I hope it will be answered one day by some mathematician or perhaps, some AI! I can see several possibilities of how this turns out…
An argument (perhaps relatively simple but hitherto evades us) shows that we always need at least \(2^\kappa\)-many baskets.
A \(\mathsf{ZFC}\) construction (perhaps somewhat involved) shows that it is always possible to use merely \(\text{ded }\kappa\)-many baskets.
A forcing construction shows that there is a \(\mathsf{ZFC}\)-universe where we can use less than \(2^\kappa\)-many baskets.
My first academic paper “Are nonmeasurable sets significant for epistemology?” is forthcoming in Synthese. A preprint is available here.
While this paper may appear somewhat technical on the surface, its philosophical message is in fact extremely simple. Once I was asked by an anthropologist friend to explain what is going on in this paper in a bar (not the quietest place in the world). Here’s what I said:
In scientific investigations, it is often helpful to distinguish the substantial part of the phenomenon in question from the derivative features introduced by one’s instruments. On my view in this paper, some mathematical constructs known as “nonmeasurable sets” fall into the second kind when we are interested in probability and statistics, and therefore should not be considered too important.
The highlight of the paper is the following quote by Henri Poincaré, one of my academic heroes:
Le géomètre cherche toujours plus ou moins à se représenter les figures qu’il étudie, mais ses représentations ne sont pour lui que des instruments ; il fait de l’a géométrie avec de l’étendue comme il en fait avec de la craie; aussi doit-on prendre garde d’attacher trop d’importance à des accidents qui n’en ont souvent pas plus que la blancheur de la craie.
La science et l’hypothèse, 1917
Translated as: “the geometer always more or less seeks to represent the figures he studies, but these representations are merely instruments for him. He does geometry with the notion of extension just like he uses the chalk, moreover we should be cautious not to attach too much importance to accidental features which are often nothing more than the whiteness of the chalk.”
Poincaré and the three body problem (a very weird version thereof), as generated by ChatGPT
Several things to note:
Unlike many other philosophical works, I think mine is amenable to refutation/falsification. For example, the position in this paper would be significantly challenged if one identifies a theorem fundamental for probability that is not available in \(\mathsf{ZF+DC}\).
One strong candidate for such refutation is the Hahn-Banach theorem, which is fundamental for functional analysis, as well as for constructing certain finitely additive probability measures. Whether this theorem plays any role in probability and statistics is debatable.
In Footnote 11 of the paper one can find a curious quote by Hermann Weyl in Das Kontinuum, which I find highly interesting but not very comprehensible, since I have trouble understanding what kind of mathematical phenomena he was commenting on. If any reader has any insights on this, please communicate to me.
So much for the synopsis, please read the paper if you are interested.
Your dad asks you: why LLMs can generate eloquent essays, but sometimes make mistakes in very basic arithmetic? Give an accessible explanation to him based on your knowledge of how LLMs are built. You might want to mention the distinction between logicist AI and machine learning based AI.
One instance of the phenomenon in question…
Here’s an answer generated by ChatGPT (free version running GPT4o):
Large language models (LLMs) like ChatGPT are built using machine learning, not traditional logic-based AI. They don’t “think” like humans or perform step-by-step calculations like a calculator. Instead, they generate text by predicting the most likely sequence of words based on patterns they’ve learned from massive amounts of data.
When writing essays, this predictive approach works well because language is full of patterns—grammar, style, and logical flow—that LLMs can model effectively. They’ve been trained on vast amounts of well-written text, so they can mimic fluent and persuasive writing.
However, arithmetic requires precise rule-based reasoning, which LLMs struggle with. Unlike a logicist AI, which follows explicit rules to compute correct answers, LLMs rely on statistical correlations. While they may have seen many examples of simple arithmetic in their training data, they don’t “understand” numbers in a mathematical sense. Instead of performing calculations, they generate an answer that seems statistically likely, which can lead to errors, especially with less common problems.
Some modern AI systems try to bridge this gap by integrating symbolic reasoning (logic-based methods) with machine learning, but LLMs alone remain better at natural language than strict computation.
As far as the exam goes, this is an OK answer, and it will likely satisfy your dad as well. However, if we are interested in the specific question of the outlook of language models doing mathematics (as I am), then the analysis based on a dichotomy between statistics vs. rule-following appears way too generic.
The statistics vs. rule-following distinction has been there since the very beginning of AI, and there were long debates on whether neural networks can learn rules. Some people thought that the ability to follow grammatical rules is a fundamental aspect of natural language competence. Then it seems natural to suspect that neural networks are inherently limited in learning language — just replace the word “arithmetic” with “linguistic” in the third paragraph written by ChatGPT. Arguments like this are based on the following premises:
Ability \(X\) is rule-based.
If \(X\) is rule-based, then neural networks/transformers/LMs are inherently limited in learning \(X\).
However, contemporary LMs appears to significantly challenge, if not falsify, these two premises when \(X\) = natural language competence. Once we accept that these LMs are fairly linguistically competent, then we must accept that either natural language is not based on rule-following, or neural networks can learn the relevant rules (the “either … or” is not exclusive). It seems to me that when \(X\) = natural language competence, neither of the two premises is quite convincing. In contrast, the version of the argument with \(X\) = arithmetic/mathematics remains somewhat consistent with our observation of current LMs. It might be falsified in a few years, in a way similar to the argument on language. Or it may have some merit in that arithmetic/mathematics is indeed based on some rules that are difficult for LMs to learn. Still more, it might be that arithmetic/mathematics remains difficult for LMs, but for reasons that have nothing to do with rule-following. The goal of this post is to give some analysis on these thoughts.
The idea of rule-following has interested philosophers, who have identified some weird phenomena related to it:
(Lewis Carroll) A rule is not reducible to a bunch of statements. One can accept many statements that state a rule, without actually following the rule.
(Wittgenstein) Given finitely many instances of a rule, we cannot uniquely identify this rule, which makes it difficult to communicate your intended rule. E.g. you can ask a kid to complete the sequence \(1, 3, 5, 7, ?\) and the kid replies \(111\), because she is following the rule “write all the roots of \((x-1)(x-3)(x-5)(x-7)(x-111)=0\)”, not your intended rule of “write the next odd number”.
(Kripke) These observations leave room for a kind of radical skepticism: throughout human history we have performed finitely many instances of addition. How do we know that we were actually following the rule of addition, not some weird operation that happens to be consistent with addition at the instances that we have already performed?
The upshot is that based on empirical evidence, it is theoretically difficult to tell whether someone is following rule \(X\), rule \(Y\), rule \(Z\), or not following any rules at all. However, as in a lot of skeptical scenarios, there is a “say-no-to-over-philosophize” response here, analogous to Moore’s “proof” of external world, or Hume’s “solution” to the problem of induction. In reality, we make a lot of efforts to make sure someone/something is following a specific rule (or behaves as if it is following this rule):
We give kids exams to make sure that they learn the rule and algorithm for addition.
We give chips a lot of tests to make sure that they are following the rules that they are designed to follow.
……
While these activities do not really address philosophical skepticism, they are able to give us an operational guarantee (as opposed to a theoretical/philosophical guarantee) of rule-following-like-behavior, which seems to be all we want in practice. From the practical point of view, what matters is: how should we characterize this operational bar? Have LMs already passed this operational bar? If not, will they?
The most straightforward operational bar is scoring high in exams. For example, here’s how some leading LMs do in multiplying two numbers:
Experiment by Yuntian Deng. Deng also demonstrated that by fine-tuning GPT2 (a far weaker LM) so that it internalizes Chain-of-Thought, it can achieve almost perfect accuracy in this task (while presumably be quite bad at other tasks).
How should we interpret outcomes like this? It seems hard to say that o1-mini knows how to do multiplication if it scores merely 69.2% in multiplying 6-digit numbers by 8-digit numbers. On the other hand, when we give 9-year-olds multiplication exams, wo don’t ask them to multiply 6-digits by 8-digits. A kid would pass if she can do 4-digits by 4-digits perfectly (which o1-mini also can). Does this result give any guarantee that she will be more accurate than o1-mini when doing \(m\)-digits by \(n\)-digits? Furthermore, I suspect that when \(m, n\) is large, humans are surely prone to errors. Even if they can do it, it will take a long time and most people will quickly lose patience without seeing it as any meaningful indication of their command of multiplication.
Perhaps test score is too naive to be an operational bar for rule-following. Perhaps the commandment of a rule is signified not by the correctness of the answer, but by some property of the process leading to the answer, and that is why we want the kid to “show-the-work” (analogous to “Chain-of-Thought” (CoT) for LMs). If the kid demonstrates that she is applying the right algorithm, we conclude that she has a good understanding, even if her process may contain a few errors. Once we are convinced that she has mastered the algorithm, which is in principle applicable to multiplying \(m\)-digits by \(n\)-digits for any given \(m\), \(n\), we conclude that she learned multiplication. Can we apply this method to LMs? It seems there are major challenges, both empirically and theoretically.
One may try to use CoT to address this problem, by using CoT prompts or incorporating more sophisticated CoT methods such as “reasoning models”, which significantly improves test scores in practice. But it seems to me that this may not suffice for our purpose — examining rule mastery by inspecting the process leading to the LM’s answer. The idea that CoT works for this purpose depends on the assumption that CoT indeed showcases the internal workings of the LM leading to the answer — a questionable assumption as CoT is essentially more output from the LM! (Compare this situation with show-the-work, which strikes me as something that actually shows how a human arrive at an answer.) When a “reasoning model” makes an error in its CoT and one tries to correct it, the situation is strikingly similar to Achilles talking to the Tortoise as in Lewis Carroll — the Tortoise keeps repeating correct statements of an inference, and yet refuses to actually make that inference.
Is there a way to actually probe the internal workings of the LM? I learned that a subject in AI research called “mechanistic interpretability” seeks to address this question. The idea is that by inspecting and experimenting with a post-training neural network, we can identify the functional roles of its various components, and give high-level descriptions of how it completes certain tasks. One prominent example is the discovery that relatively simple networks learn modular addition by converging to some identifiable algorithm, and in fact similar architectures can learn multiple different identifiable algorithms to do it (see the paper https://arxiv.org/abs/2306.17844 which appears quite interesting). However, it seems to me that current mechanistic interpretability research is limited to relatively simple toy networks and problems, and the complex networks in real usage are hardly mechanistically interpretable.
On the other hand, approaching the question of rule-following from a theoretical point of view appears difficult as well. After all, the LM is following a complex rule — it converts your input into a vector, multiplies it by some huge matrices for many times, and eventually gives you an output (modulo some pseudorandomness). Rule-following-like-behavior takes place when given certain inputs, this complex rule reduces to some simple rules. The question is to theoretically study when and why this phenomenon takes place, which appears to be highly difficult and intangible at the current state of knowledge. Part of the difficulty lies in the fact that a trained neural network involves multiple aspects: the architecture, the training data, and the training method, with the latter two highly empirical in nature. Consequently, a mere mathematical analysis of the architecture is unlikely to help.
If these obstacles can be partly overcome, e.g. if we have an explanation of why GPT4 is able to generate programs that actually work via some mechanistic analysis, I imagine this will satisfy the LM-rule-learning skeptics to a large extent. In fact, I think part of the frustration that drives their argument comes from the sentiment that lacking such analysis, any empirical success of LMs appears like some miracle. In response to these sentiments, LM proponents often appeal to unhelpful general concepts such as “grokking”, “scaling”, “emergence”, or to the recorded successes in the past few years, which are unconvincing responses. Consequently, LM errors are more likely to be interpreted as evidence of lack of understanding, instead of sympathetically interpreted as unintended errors. With more mechanistic understanding of LMs, the situation may be reversed.
To summarize, we arrive at the following conclusions:
From a radical philosophical point of view, it is difficult in general to empirically determine whether something follows rules, regardless whether it is human or LM.
From a practical point of view, mere exam score appears to be a poor indication of rule-following.
However, mechanistic analysis may be applicable to both humans and LMs as indications that they are following rules.
Mechanistic analyses of LMs are technically difficult, so there is no definitive proof that LMs can/cannot follow rules.
Maybe there are alternative empirical verifications of rule-following such that humans can be easily verified and LMs cannot, but I am not aware of any. (The idea of ARC-AGI is similar to this, however it is still based on mere exam scores for a set of more diverse and creative rules, and lacks a mechanistic component/alternative method of empirical verification.)
Absent these analyses, it seems premature to assert that LMs intrinsically cannot learn certain rules.
So far our discussion is limited to the case of arithmetic, and we are ultimately interested in the outlook of AI doing more advanced (by human standard) mathematics. Researchers have created a number of math benchmarks for AI to this end, and two of them are of particular interest: FrontierMath and PutnamBench. In a later post, I shall discuss some observations on these benchmarks and related topics.
Caveat: this post has nothing to do with mice as in set theory…
Infinitely many mice, as generated by DALL“-E…
I ran into the following puzzle lately and it took me a while to come up with a solution:
Suppose there are countably many mice standing in the following sequence: Mouse 0, Mouse 1, Mouse 2, and so on. Each mouse is given a hat which is either red or blue. Each mouse can see the hat color of every mice standing after it, but not their own, nor anyone standing before. Now, each mouse have to guess their own color. The mice collectively win the game if all but finitely many of them guesses correctly. Find a winning strategy for the mice. (Hint: Axiom of Choice.)
If you haven’t seen this, think a bit on your own!
Ever since the release of ChatGPT, I got interested in observing how generative AI interacts with logical and mathematical tasks. So I want to see ChatGPT’s performance in solving this problem. I am using ChatGPT3.5, and here is what I get.
If you read til the end of our conversation, you already know the solution, which is rather transparent by hindsight — modulo the equivalence relation of “equality at all but finitely many points”, each mice get the same information, namely the equivalence class of the input sequence, and they win if they collectively output a sequence in the same class. Now, before the game they fix a representative for each class (by an application of the Axiom of Choice). After the hats are given, everyone observes that they are in some class \([r]\), where \(r\) is the common representative chosen beforehand. They then win the game by collectively playing \(r\), i.e. Mouse \(N\) plays the \(N\)th digit of \(r\).
