无穷之路：真理与证明的数学探索

需积分: 9 169 浏览量更新于2024-07-26 收藏 1.29MB PDF 举报

"《无穷之路：真理与证明的数学》探讨了集合论如何与逻辑相互作用，并对主流数学产生影响。" 《无穷之路：真理与证明的数学》是一本深入探讨数学基础，特别是集合论与逻辑关系的著作。作者John Stillwell通过这本书向读者展示了这些抽象概念如何塑造我们理解数学世界的方式。书中的内容涵盖了无限、逻辑等多个关键领域，旨在让读者明白无穷在数学中的地位以及如何用严谨的证明方法去探索真理。首先，集合论是现代数学的基础，它研究的是集合的性质及其与其它数学对象的关系。书中会详细解释集合的基本概念，如元素、子集、并集、交集和幂集等。此外，还会讨论重要的数学原理，如康托尔的对角线论证，这一论证证明了无穷集合之间存在不同的大小，比如实数的集合比自然数的集合更大。其次，逻辑在数学中起着至关重要的作用，它是证明和推理的基础。符号逻辑，或称形式逻辑，关注的是推理规则和命题的形式结构。书中会涵盖命题逻辑和谓词逻辑，包括蕴含、否定、等价和量词等逻辑操作。读者将学习如何构建有效的证明，并理解逻辑谬误的概念。书中的一个重要主题是无穷与有限的区别，这在数学中有着深远的影响。例如，无穷序列、无穷级数和无穷产品等概念都是无穷理论的核心部分。通过这些概念，作者将引导读者进入实分析和复分析的世界，了解无穷在这些领域的应用。此外，书里还会涉及更高级的主题，如模型论，这是连接逻辑与集合论的一个桥梁。模型论研究的是逻辑系统如何对应到具体的数学结构，例如，第一秩序逻辑理论与良基集合的关系。通过模型论，我们可以理解 Gödel不完备定理，这是关于形式系统内在局限性的里程碑式发现。最后，书中还将触及数学中的悖论，如理查德悖论和巴拿赫-塔斯基悖论，这些悖论挑战了我们对无穷和一致性的直觉，推动了数学逻辑和集合论的发展。《无穷之路：真理与证明的数学》是一本面向对数学基础感兴趣的读者的深度读物。它不仅介绍了集合论和逻辑的基础知识，还探讨了它们如何影响和重塑整个数学学科。通过阅读本书，读者可以深入理解数学中的无穷概念，学会如何运用逻辑进行严谨的推理，并对数学的真理有更深刻的认识。

1.3. Cantor’s Diagonal Argument 7

subset 1234567891011...

0 10101010 1 0 ...

1 0 0100001 0 0 ...

011 010100 0 1 ...

1010 10101 0 1 ...

00100 1001 0 0 ...

110110 110 1 1 ...

1111111 1 1 1 1 ...

00000000 00 0...

000000001 0 0 ...

100100100 1 0 ...

010010010 0 0 ...

S 110111010 0 1 ...

Tab le 1. 2. The diagonal argument.

Theargumentwehavejustmadeiscalledadiagonal argument be-

cause it can be presented visually as follows. Imagine an inﬁnite ta-

ble whose rows encode the sets S

, S

,...assequencesof0sand

1s, as in the examples above. We might have, say, the sets shown in

Table 1.2.

The digit (1 or 0) that signals whether or not n belongs to S

is set in

bold type, giving a diagonal sequence of bold digits

00100010110....

ThesequenceforS is obtained by switching each digit in the diagonal

sequence. Hence the sequence for S is necessarily different from the

sequences for all of S

, S

,....

The cardinality of the set of all sequences of 0s and 1s is called 2

ℵ

We use this symbol because there are two possibilities for the ﬁrst digit

in the sequence, two possibilities for the second digit, two possibilities

for the third, and so on, for all the

ℵ

digits in the sequence. Thus it

is reasonable to say that there are 2

× 2 × 2 ×··· (ℵ

factors) possible

sequences of 0s and 1s, and hence there are 2

ℵ

sets of positive natural

numbers.

The diagonal argument shows that 2

ℵ

is strictly greater than ℵ

because

there is a one-to-one correspondence between the positive integers and

certain sets of positive integers, but not with all such sets. As we have

just seen, if the numbers 1, 2, 3, 4, . . . are assigned to sets S

, S

,...

there will always be a set (such as S) that fails to be assigned a number.

8 1. The Diagonal Argument

The Logic of the Diagonal Argument

Many mathematicians aggressively maintain that there can be no

doubt of the validity of this proof, whereas others do not admit it. I

personally cannot see an iota of appeal in this proof . . . my mind will

not do the things that it is obviously expected to do if this is indeed

a proof.

—P .W. Bridgman (1955), p. 101

P. W. Bridgman was an experimental physicist at Harvard, and winner of

the Nobel prize for physics in 1946. He was also, in all probability, one of

the smartest people not to understand the diagonal argument. If you had

any trouble with the argument above, you can rest assured that a Nobel

prize winner was equally troubled. On the other hand, I do not think

that any mathematically experienced reader should have trouble with the

diagonal argument. Here is why.

The logic of the diagonal argument is really very similar to that of

Euclid’s proof that there are inﬁnitely many primes. Euclid faced the

difﬁculty that the totality of primes is hard to comprehend, since they

follow no apparent pattern. So, he avoided even considering the totality

of primes by arguing instead that any ﬁnite list of primes is incomplete.

Given a ﬁnite list of primes p

, p

, . . . , p

, one forms the number

N = p

··· p

+ 1,

which is obviously not divisible by any one of p

, p

, . . . , p

(they each

leave remainder 1). But N is divisible by some prime number, so the list

, p

, . . . , p

of primes is incomplete. Moreover, we can ﬁnd a speciﬁc

prime p not on the list by ﬁnding the smallest number ≥ 2 that divides N.

An uncountable set is likewise very hard to comprehend, so we avoid

doing so and instead suppose that we are given a countable list S

, S

, . . . of members of the set. The word “given” may be interpreted as

strictly as you like. For example, if S

, S

, . . . are sequences of 0s and

1s, you may demand a rule that gives the mth digit of S

at stage m + n.

The diagonal argument still works, and it gives a completely speciﬁc S not

on the given list. (Indeed, it also leads to some interesting conclusions

about rules for computing sequences, as we will see in Chapter 3.)

The Set of Points on the Line

The goal of set theory is to answer the question of highest importance: whether

one can view the line in an atomistic manner, as a set of points.

—Nikolai Luzin (1930), p. 2.

By the “line” we mean the number line, whose “points” are known as the

real numbers. Each real number has a decimal expansion with an inﬁnite

1.3. Cantor’s Diagonal Argument 9

sequence of decimal digits after the decimal point. For example,

= 3.14159265358979323846 . . ..

If we stick to real numbers between 0 and 1, then each number is given

by the sequence of digits after the decimal point, each term of which is

oneof0,1,2,3,4,5,6,7,8,or9. Acountableinﬁnityofrealnumbers

, x

, . . . between 0 and 1 can therefore be encoded by a table very

like the table we used to encode a countable inﬁnity of sets of positive

integers. Likewise, we can construct a real number x different from each

of x

, x

, . . . by arranging that the nth digit of x is different from

the nth digit of x

, for each positive integer n. As before, this amounts

to looking at the diagonal digits in the table, and changing each one of

them.

However, there is now a slight problem with the diagonal construc-

tion. Changing each diagonal digit certainly produces a sequence of

digits different from all the sequences given for x

, x

,... . But

this does not ensure that the new sequence represents a new number. It

could happen, for example, that the sequence obtained by the diagonal

construction is

·49999999999999 ···

and that one of the given sequences is

= 0 ·50000000000000 ···

These are different sequences, but they represent the same number, namely

1/2. Since two sequences can represent the same number only if one of

them ends in an inﬁnite sequence of 9s, we can avoid this problem by

never changing a diagonal digit to a 9. For example, we could use the

following rule.

If the nth digit of x

is 1, let the nth digit of x be 2.

If the nth digit of x

is not 1, let the nth digit of x be 1.

With this rule, x does not merely have a sequence of digits different

from those for x

, x

,.... As a number, x is different from x

, x

,....

Thus we have proved that the set of real numbers is of greater cardinality

than the set of positive natural numbers. Ifwemakealistofrealnumbers

, x

, . . . there will always be a real number ( such as x) not on the

list.

In fact, the set of real numbers (whether between 0 and 1 or over the

whole number line) has cardinality 2

ℵ

—the same as that of the set of

sequences of 0s and 1s. The cardinality 2

ℵ

, like ℵ

, measures the “size”

among familiar sets in mathematics. The reasons for this will become

clearer as we explore further examples of countable and uncountable sets.

10 1. The Diagonal Argument

1.4 Transcendental Numbers

[On the question whether the real numbers can be made to correspond with

thenaturalnumbers]...if itcouldbeansweredwithno,thenonewould have

a new proof of Liouville’s theorem that there are transcendental numbers.

—Georg Cantor,

Letter to Dedekind, 2 D ecember 1873,

in Ew ald (1996), p. 844.

Cantor’s discovery of uncountable sets in 1874 was one of the most un-

expected events in the history of mathematics. Before 1874, inﬁnity was

not even considered a legitimate mathematical concept by most people,

so the need to distinguish between countable and uncountable inﬁnities

could not have been imagined. The idea of uncountability was just too

original to be appreciated by most mathematicians. Because of this, Can-

tor downplayed the idea of uncountability in the published version of his

discovery, introducing it only indirectly via a “property of the algebraic

numbers.”

The algebraic numbers were very familiar to 19th-century mathemati-

cians. A number x is called algebraic if it satisﬁes a polynomial equation

with integer coefﬁcients, that is, an equation of the form

+ a

n−1

+ ···+ a

x + a

= 0,

where a

, a

,...,a

n−1

, a

are integers.

The algebraic numbers includealltherationalnumbersm/n,wherem

and n are integers, and also many irrational numbers, such as

√

2, and so on. In fact, it is quite hard to ﬁnd any numbers that are

not algebraic. The ﬁrst example was found b y the French mathemati-

cian Joseph Liouville in 1844, using a result that says (roughly speaking)

that an irrational algebraic number cannot be closely approximated by

rationals.

Liouville then considered the number

= 0 ·101001000000100000000000000000000000010 . . .,

where the successive blocks of 0s have lengths 1, 2, 3

× 2, 4 ×3 ×2,... .

He showed that x is irrational but that it can be closely approximated by

rationals, hence x is not algebraic. Such numbers are now called transcen-

dental, because they transcend description by algebraic means. Invariably,

they have to be described by inﬁnite processes, such as inﬁnite decimals

or inﬁnite series. The ﬁrst “well-known” number to be proved transcen-

dental was

= 1 +

1 ×2

1 × 2 × 3

1 ×2 ×3 ×4

+ ···,

1.4. Transcendental Numbers 11

a number which makes many appearances in mathematics, perhaps most

famously in the equation

√

−1

= −1.

Liouville’s compatriot Charles Hermite proved that e is transcendental in

1873, using some difﬁcult calculus. In fact, Hermite was so exhausted by

the effort that he gave up the idea of trying to prove that π is transcen-

dental. The transcendance of π was ﬁrst proved by the German math-

ematician Ferdinand Lindemann in 1882, using Hermite’s methods and

the above equation connecting e and π.

At any rate, in 1874 the only known approaches to transcendental

numbers were those of Liouville and Hermite, using sophisticated alge-

bra and calculus. Cantor surprised the world by showing the existence

of transcendental numbers without any advanced math at all—simply

by proving that the set of algebraic numbers is countable. Combining this

with his result that real numbers are uncountable, it follows that some

real numbers are transcendental. In fact, “most” real numbers must be

transcendental. Not only does set theory ﬁnd transcendental numbers

easily, it also shows that the handful of transcendental numbers previ-

ously known actually belong to the vast, uncountable, majority.

Since we have already seen one of Cantor’s proofs that there are un-

countably many reals, it remains to explain why there are only countably

many algebraic numbers. To do this we come back to the equations that

deﬁne algebraic numbers:

+ a

n−1

n− 1

+ ···+ a

x + a

= 0, (1)

where a

, a

,...,a

n−1

, a

are integers. The equation (1) has at most n

solutions, as one learns in elementary algebra, so we ca n list all algebraic

numbers if we can list all equations of the form (1). To do this, Cantor

used a quantity called the height of the equation,

= |a

| + |a

n−1

| + ···+ |a

| + n,

suggested by his colleague Richard Dedekind. It is not hard to see that

there are only ﬁnitely many equations with a given height h, since they nec-

essarily have degree n

≤ h and each coefﬁcient has absolute value less

than h. Therefore, we can list all equations (and hence all algebraic num-

bers) by ﬁrst listing the equations of height 1, then those of height 2, those

of height 3, and so on.

This listing process shows that the algebraic numbers form a count-

able set, and hence we are done.

剩余192页未读，继续阅读

michaelshen7310

粉丝: 0
资源: 3

无穷之路：真理与证明的数学探索

Roads to Infinity: The Mathematics of Truth and Proof

infinity::infinity:Groupoid无限

lean::infinity:零地

android-tests-scaling-to-infinity：回购来自帖子https：artemnikitin.com的资源postscaling-android-tests

infinity:chrome 中的 Infinity Newtab

infinity:玩正弦波

admin-infinity:项目

groupoid.space::infinity:Groupoid无限

infinity:一个 WordPress 主题引擎

infinity:ML的AWS Spot实例

最新资源