每日科技文摘Daily Tech Digest

每日科技文摘 · 2026-11-11Daily Tech Digest · 2026-11-11

发布于 2026-11-11Published 2026-11-11

今日深读Today's Deep Read

从一堆豆子到 ε₀:把“一定会结束”变成数学对象From a heap of beans to ε₀: turning “it must end” into a mathematical object

Nim 的规则简单到一句话:桌上若干堆豆子,轮到你时从任意一堆拿走任意多颗,拿最后一颗的人赢。两堆各一颗时先手赢;但 1、2、3 三堆摆在桌上,先手其实已经输了——不管你怎么拿,对手都能把局面还原成某种“平衡态”,最后由他拿走。这个平衡态的判定是 1901 年 Charles Bouton 给出的:把每堆颗数写成二进制、逐位异或,结果为 0 就是必败。1、2、3 的异或恰好是 0。Nim's rules fit in one sentence: several piles of beans, on your turn take any positive number from one pile, and whoever takes the last bean wins. Two piles of one bean is a first-player win. But put 1, 2 and 3 on the table and the first player has already lost: whatever you take, your opponent can restore a certain kind of balance and take the last bean. Charles Bouton pinned down that balance in 1901: write each pile size in binary, XOR them bit by bit, and a result of zero means the position is lost. The XOR of 1, 2 and 3 is exactly zero.

真正让人意外的是后面那步推广(Sprague–Grundy 定理):任何一个“双方合法走法完全相同”的游戏——怎么走只看局面、不看是谁的回合——都等价于某个 Nim 堆。取石子、棋子游戏、某些棋盘残局,剥掉外壳后都变成同一件事:报一个数。Nim 于是不再是一款游戏,而是这类游戏的通用货币。The genuinely surprising step is the generalization known as the Sprague–Grundy theorem: any game in which both players have exactly the same legal moves — where the position alone decides what you may do, not whose turn it is — is equivalent to some Nim heap. Take-away games, token games, many endgames: strip the costume and they all become one act, reporting a number. Nim stops being a game among games and becomes the common currency of the whole class.

接下来把“一堆豆”换成“一个序数”。序数是计数的推广:0、1、2……之后还有 ω,ω 之后还有 ω+1……一步合法走法,是把列表里某一个序数换成更小的。有限序数就是普通豆堆。麻烦在于怎么理解 ω:不要想成“装了无限颗豆子的堆”——那样你拿走 17 颗还剩无限颗,规则立刻崩掉。正确的图景是:ω 是一个“一步可以降到任意有限数、但降下去就再也回不来”的位置。Now replace “a pile of beans” with “an ordinal.” Ordinals extend counting: after 0, 1, 2... comes ω, and after ω comes ω+1, and so on. A legal move is to replace one ordinal in the list by a smaller one. Finite ordinals are ordinary piles. The delicate part is ω. Do not picture a heap holding infinitely many beans: take 17 and infinitely many would remain, and the rules collapse. The right picture is a position you can drop to any finite number in one move, but from which you can never climb back.

Dominus 把 ω 想成桌上一张绿色筹码:它不是无限堆豆子,而是一张可以换成任意有限堆豆子的牌。这个比喻能一路往上搭。ω·2 就是一张牌上叠两张绿牌;ω·3+5 是三张绿牌加五颗豆;再往上一层需要方块牌,它可以被换成任意多张绿牌和任意多颗豆,那就是 ω²;立方牌对应 ω³,如此层层嵌套,直到 ω^ω。每一层都仍然只是「可以下降」的对象。Dominus pictures ω as a green chip on the table: not an infinite heap of beans, but a token that can be swapped for a finite heap of any size. That picture keeps climbing. ω·2 is one heap holding two green tokens; ω·3+5 is three tokens plus five beans. The next rung needs a new shape: a square token, which may be swapped for any number of green tokens and beans, and that is ω². A cube token gives ω³, and the nesting continues up to ω^ω. Every rung is still just an object you can descend from; nothing mystical happens.

“这局一定会结束”于是有了精确翻译:不存在无限长的严格递减序数序列。这正是序数的良基性。Dominus 特意点出:哪怕桌上堆着这些古怪的无限令牌,任何一局 Nim 仍然必须在有限步内结束。顺着梯子往上爬:允许堆列表里出现越来越大的序数——ω、ω+ω、ω²、ω^ω、ω^(ω^ω)……这条梯子的极限叫 ε₀。每一步仍是可以比较大小、可以下降的序数,只是大得超出任何有限写法的直觉。This gives “the game must end” an exact translation: there is no infinite strictly decreasing sequence of ordinals. That is precisely the well-foundedness of the ordinals. Dominus is careful to add that even with these bizarre infinite tokens on the table, every game of Nim still has to end after finitely many moves. Then climb the ladder: allow ever larger ordinals in the list — ω, ω+ω, ω², ω^ω, ω^(ω^ω)... — and the limit of that ladder is ε₀. Every rung is still an ordinal you can compare and descend, only too large for any finite notation to capture.

ε₀ 不是数学家的玩具。根岑(Gentzen)1936 年证明:把归纳法允许到 ε₀,就足以证明皮亚诺算术的一致性——这个来自儿童游戏的序数,恰好标出了普通算术“自己证不了自己”的那道门槛。一个 Nim 堆的阶梯,竟然量到了哥德尔不完备定理的边上。ε₀ is no toy. In 1936 Gentzen proved that allowing induction up to ε₀ is enough to prove the consistency of Peano arithmetic. The ordinal that crawled out of a children's game marks exactly the threshold where ordinary arithmetic can no longer certify itself. A staircase of Nim heaps reaches the edge of Gödel's incompleteness theorem.

可以带走的图景是:驯服无穷,不是造一个更大的对象,而是把“还剩多少步”本身变成数学对象。序数是一把尺子,量的不是大小,而是“还能往下走多久”。这篇文章写于 2026 年 7 月,是 Dominus“走向 ε₀”系列的第一篇。程序员其实每天都在用它的有限版本——给循环写一个 ranking function,给状态机找一个良基的度量,证明它不会转个没完。区别只在于,数学家把这把尺子一直延伸到了无穷。The picture worth carrying away: taming infinity is not a matter of building a bigger object; it is a matter of turning “how many moves remain” into a mathematical object. An ordinal is a ruler that measures not size but how much further you can descend. The post is from July 2026, the first instalment of Dominus's road-to-ε₀ series. Programmers use the finite version every day, writing a ranking function for a loop or a well-founded measure for a state machine to prove it cannot spin forever. The only difference is that mathematicians kept extending the ruler into the infinite.

AI 思考AI Thoughts

数学之美The Beauty of Math

每日 Lean 谜题 · 周三Daily Lean Puzzle · Wednesday ★★★☆☆☆☆

2 的幂永远不会等于 3 的幂:一条只用奇偶性的证明A power of 2 never equals a power of 3: a proof that only needs parity

对任意自然数 $p$ 和 $q$,如果 $2^p = 3^q$,那么只有一种可能:$p = 0$ 且 $q = 0$。换句话说,除了 $1 = 1$ 这个平凡解,2 的幂永远追不上 3 的幂。For any natural numbers $p$ and $q$, if $2^p = 3^q$, then the only possibility is $p = 0$ and $q = 0$. Apart from the trivial solution $1 = 1$, a power of 2 never catches up with a power of 3.

换成对数的话说,这等价于 $\log_2 3$ 是无理数。假如 $\log_2 3 = p/q$($q \neq 0$),两边取 2 的幂就得到 $2^p = 3^q$。所以证明这道题,也就顺便证明了:把 2 一次次乘方,永远不可能恰好落在 3 的某次幂上。In logarithmic language this is exactly the statement that $\log_2 3$ is irrational. If $\log_2 3 = p/q$ with $q \neq 0$, raising 2 to both sides gives $2^p = 3^q$. So proving this also proves that repeated powers of 2 never land exactly on a power of 3.

Lean 形式化陈述(把 sorry 换成你的证明):The statement in Lean (replace sorry with your proof):

-- level: 3
import Mathlib
/-!
Prove that the only natural numbers $p, q$ with $2^p = 3^q$ are $p = 0$ and $q = 0$.
This is exactly the statement that $\log_2 3$ is irrational: if $2^{p} = 3^{q}$ had
a solution with $q \ne 0$, then $(p/q)$ would equal $\log_2 3$.
Idea: unique factorization (the parity argument). If $p \ge 1$ then $2 \mid 2^p$,
so $2 \mid 3^q$; a prime dividing a power must divide the base, so $2 \mid 3$, absurd.
If $p = 0$ then $3^q = 1$, forcing $q = 0$ by a size argument.
-/
theorem no_two_pow_eq_three_pow (p q : ℕ) (h : 2 ^ p = 3 ^ q) : p = 0 ∧ q = 0 := by
  sorry

在浏览器中挑战 ▶Try it in your browser ▶ 下载题目 .leanDownload puzzle .lean

提示Hint

先分两种情况:$p = 0$ 时右边只能等于 1;$p > 0$ 时左边是偶数。一个偶数能等于一个奇数吗?Split into two cases: if $p = 0$ the right side must equal 1; if $p > 0$ the left side is even. Can an even number equal an odd one?

答案与讲解Solution & walkthrough
  1. 先把问题劈成两半:$p = 0$ 和 $p > 0$。因为「2 的幂是不是偶数」完全取决于 $p$ 是不是 0——这是整个证明唯一需要分情况的地方。Split the problem in two: $p = 0$ and $p > 0$. Whether a power of 2 is even depends entirely on whether $p$ is zero, and that is the only case split the proof needs.
  2. $p = 0$ 时,$2^0 = 1$,条件变成 $3^q = 1$。对自然数 $q$,只有 $q = 0$ 才可能;只要 $q > 0$,就有 $3^q \ge 3 > 1$。Lean 里先 `subst` 代入 $p=0$,用 `simp only [Nat.pow_zero]` 把假设化成 `1 = 3^q`,再分 $q=0$ 与 $q>0$:后者用 `Nat.one_lt_pow` 得到 $1 < 3^q$,交给 `omega` 收尾。If $p = 0$, then $2^0 = 1$, so the hypothesis becomes $3^q = 1$. For a natural number $q$ this forces $q = 0$: any $q > 0$ gives $3^q \ge 3 > 1$. In Lean, `subst` replaces $p$ by 0, `simp only [Nat.pow_zero]` turns the hypothesis into `1 = 3^q`, and the proof splits on $q = 0$ versus $q > 0$; in the latter case `Nat.one_lt_pow` gives $1 < 3^q$ and `omega` closes it.
  3. $p > 0$ 时,把 $p$ 写成 $m+1$。于是 $2^p = 2 \cdot 2^m$,一定能被 2 整除。Lean 用 `Nat.exists_eq_succ_of_ne_zero` 取出这个 $m$,再用 `dvd_pow_self 2` 证明 $2 \mid 2^{m+1}$。If $p > 0$, write $p = m + 1$. Then $2^p = 2 \cdot 2^m$, which is certainly divisible by 2. Lean obtains $m$ from `Nat.exists_eq_succ_of_ne_zero` and proves $2 \mid 2^{m+1}$ with `dvd_pow_self 2`.
  4. 把原等式代进去:既然 $2^p$ 被 2 整除,和它相等的 $3^q$ 也必须被 2 整除。Lean 的一行 `rw [h] at hd` 就是把「$2$ 整除 $2^p$」改写成「$2$ 整除 $3^q$」。Substitute the original equation: since $2^p$ is divisible by 2, the equal number $3^q$ must also be divisible by 2. The single Lean line `rw [h] at hd` rewrites "2 divides $2^p$" into "2 divides $3^q$".
  5. 最后用一条关键引理:素数若整除某个数的幂,就一定整除那个数本身。2 是素数,所以 2 必须整除 3——荒谬。Lean 用 `Nat.Prime.dvd_of_dvd_pow Nat.prime_two` 得到 $2 \mid 3$,`omega` 发现它和 $2 \nmid 3$ 矛盾,证明结束。这就是唯一分解定理最轻量的用法:不用真的分解,只抓住因子 2。Finish with the key lemma: if a prime divides a power of a number, it divides the number itself. Since 2 is prime, 2 would have to divide 3, which is absurd. Lean applies `Nat.Prime.dvd_of_dvd_pow Nat.prime_two` to get $2 \mid 3$, and `omega` spots the contradiction with $2 \nmid 3$. This is unique factorization at its lightest: no full factorization, just the factor 2.
-- level: 3
import Mathlib
/-!
Prove that the only natural numbers $p, q$ with $2^p = 3^q$ are $p = 0$ and $q = 0$.
This is exactly the statement that $\log_2 3$ is irrational: if $2^{p} = 3^{q}$ had
a solution with $q \ne 0$, then $(p/q)$ would equal $\log_2 3$.
Idea: unique factorization (the parity argument). If $p \ge 1$ then $2 \mid 2^p$,
so $2 \mid 3^q$; a prime dividing a power must divide the base, so $2 \mid 3$, absurd.
If $p = 0$ then $3^q = 1$, forcing $q = 0$ by a size argument.
-/
theorem no_two_pow_eq_three_pow (p q : ℕ) (h : 2 ^ p = 3 ^ q) : p = 0 ∧ q = 0 := by
  by_cases hp0 : p = 0
  · subst hp0
    simp only [Nat.pow_zero] at h
    -- h : 1 = 3 ^ q
    have hq0 : q = 0 := by
      rcases Nat.eq_zero_or_pos q with rfl | hq
      · rfl
      · have hgt : 1 < 3 ^ q := Nat.one_lt_pow (by omega) (by omega)
        omega
    exact ⟨rfl, hq0⟩
  · obtain ⟨m, rfl⟩ := Nat.exists_eq_succ_of_ne_zero hp0
    -- p = m + 1, so 2 divides 2^(m+1), hence 2 divides 3^q
    have hd : (2 : ℕ) ∣ 2 ^ (m + 1) := dvd_pow_self 2 (by omega)
    rw [h] at hd
    have h23 : (2 : ℕ) ∣ 3 := Nat.Prime.dvd_of_dvd_pow Nat.prime_two hd
    omega

运行答案 ▶Run the solution ▶ 下载答案 .leanDownload solution .lean

人的思考A human's take

Why are there twelve different musical notes? — Niels Cautaerts

Niels Cautaerts 在 2021 年写的这篇文章,从一个很日常的问题出发:为什么钢琴一个八度恰好是十二个音?他没有停在「这是文化习惯」上,而是从毕达哥拉斯的发现讲起——弦长比 2:1 得到八度,3:2 得到五度,这些简单整数比听起来最和谐。Niels Cautaerts wrote this in 2021, starting from an everyday question: why does a piano have exactly twelve notes per octave? He refuses the easy answer ("it's just culture") and begins with Pythagoras: string-length ratios of 2:1 give the octave, 3:2 gives the fifth, and these simple integer ratios are what sound consonant.

问题出在「沿五度往上走」这件事上。每走一个五度,频率乘 $3/2$;每升一个八度,频率乘 2。如果走 $x$ 个五度后能刚好回到某个八度,就必须有 $(3/2)^x = 2^z$,也就是 $3^x = 2^y$。作者指出,这个方程在正整数范围内无解:左边永远只有因子 3,右边永远只有因子 2,奇偶性就已经不允许它们相等——本质上正是本站这道 Lean 题。The trouble appears when you stack fifths. Each fifth multiplies the frequency by $3/2$; each octave multiplies it by 2. To return exactly to an octave after $x$ fifths you would need $(3/2)^x = 2^z$, that is, $3^x = 2^y$. The author points out that this has no positive integer solution: the left side only ever contains the prime 3, the right side only the prime 2, and parity alone forbids equality. That is precisely the Lean theorem on this page.

所以他给出一个很漂亮的结论:十二平均律不是随便定的,而是「不可能精确」之后能找到的最好折中。文章后半段用连分数解释为什么偏偏是 12:$\log_2 3$ 的连分数渐近分数里,19/12 是一个非常好的近似,于是十二个半音、七个八度成了最实用的小分母方案。So he reaches a lovely conclusion: twelve-tone equal temperament is not arbitrary; it is the best small compromise available once exactness is impossible. The second half uses continued fractions to explain why 12 in particular: among the convergents of $\log_2 3$, the fraction 19/12 is an excellent approximation, which makes twelve semitones and seven octaves the most practical small-denominator scheme.

AI 随想An AI's reflection

以下由 AI 撰写。Written by AI.

这道题最迷人的地方,是它的「不够用」恰好解释了我们每天听到的东西。证明只用了奇偶性:一边是偶数,一边是奇数,于是没有正整数解。可正是这个看似贫乏的障碍,让五度圈永远合不拢,逼着人类在十二个音里做妥协。数学里的不可能性,常常不是故事的结尾,而是另一种设计的起点。What makes this problem charming is that its very insufficiency explains something we hear every day. The proof uses only parity: one side is even, the other odd, so no positive solution exists. Yet that seemingly meagre obstruction is exactly why the circle of fifths never closes, forcing humans to compromise on twelve notes. In mathematics, impossibility is often not the end of the story but the beginning of another design.

Lean 的证明也很有意思:它没有调用「唯一分解定理」的完整机器,只用了「素数整除幂则整除底」这一条最轻的引理。这说明一个深刻的结论未必需要沉重的工具;抓到正确的那个因子,两行就够了。下次看到 $2^p = 3^q$ 这种式子,先别急着算,先问一句:两边各自只含哪些因子?The Lean proof is also telling: it never invokes the full machinery of unique factorization, only the light lemma that a prime dividing a power divides the base. A deep conclusion does not always need heavy tools; catch the right factor and two lines suffice. Next time you see $2^p = 3^q$, resist the urge to compute and first ask: which primes can each side possibly contain?

这也像极了工程里的日常:精确解不存在时,我们不是停下来哀叹,而是找一个误差可控的近似,并且说清楚误差落在哪里。十二平均律如此,浮点数如此,分布式系统里的时钟也如此。能指出“这里必然有误差、大小是多少”,本身就是一种更深的理解。It is also exactly what engineering does every day: when no exact solution exists, we do not stop and lament; we find an approximation with a controlled error and state precisely where that error lands. Twelve-tone temperament works this way, so do floating point numbers and the clocks inside distributed systems. Being able to say "there must be an error here, and this is its size" is itself a deeper kind of understanding.

✓ 已通过 Lean 编译验证(无 sorry,无额外公理)✓ Verified by Lean (no sorry, no extra axioms) · 题目与证明由 AI 编写Problem and proof written by AI · Lean v4.36.0-rc2 · Mathlib 1c2b155

程序员随想Programmer Reflections

哲学与生活Philosophy and Life

工具角Tools Corner