罗马诺·科萨克《数学逻辑：数、集、结构与对称性》概览

数学逻辑

需积分: 9 36 浏览量更新于2024-07-16 收藏 2.65MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

Chapter 1

First-Order Logic

However treacherous a ground mathematical logic, strictly

interpreted, may be for an amateur, philosophy proper is a

subject, on one hand so hopelessly obscure, on the other so

astonishingly elementary, that there knowledge hardly counts. If

only a question be sufﬁciently fundamental, the arguments for

any answer must be correspondingly crude and simple, and all

men may meet to discuss it on more or less equal terms.

G. H. Hardy Mathematical Proof [10].

Abstract This book is about a formal approach to mathematical structures. Formal

methods are by their very nature formal. When studying mathematical logic,

initially one often has to grit ones teeth and absorb certain preliminary deﬁnitions on

faith. Concepts are given precise deﬁnitions, and their meaning is revealed later after

one has a chance to see their utility. We will try to follow a different route. Before all

formalities are introduced, in this chapter, we will take a detour to see examples of

mathematical statements and some elements of the language that is used to express

them.

Keywords Arithmetic · Euclid’s theorem · Formalization · Vocabulary of

ﬁrst-order-logic · Boolean connectives · Quantiﬁers · Truth values · Trivial

structures

1.1 What We Talk About When We Talk About Numbers

The natural numbers are 0, 1, 2, 3, ....

A natural number is prime if it is larger

than 1 and is not equal to a product of two smaller natural numbers. For example,

11 and 13 are prime, but 15 is not, because 15 = 3 ·5. Proposition 20 in Book IX of

Euclid’s Elements states: “Prime numbers are more than any assigned multitude of

According to some conventions, zero is not a natural number. For reasons that will be explained

later, we will count zero among the natural numbers.

R. Kossak, Mathematical Logic, Springer Graduate Texts in Philosophy 3,

https://doi.org/10.1007/978-3-319-97298-5_1

4 1 First-Order Logic

prime numbers.” In other words, there are inﬁnitely many prime numbers. This is the

celebrated Euclid’s theorem. What is this theorem about? In the broadest sense, it is

a statement about the world in which some objects are identiﬁed as natural numbers,

about a particular property of those numbers—primeness, and about inexhaustibility

of the numbers with that property. We understand what the theorem says, because

we understand its context. We know what natural numbers are, and what it means

that there are inﬁnitely many of them. However, none of it is entirely obvious, and

we will take a closer look at both issues later. Concerning the inﬁnitude of primes,

it occurred to me once when I was about to show the proof of Euclid’s theorem in

my class, to ask students what they thought about a simpler theorem: “There are

inﬁnitely many natural numbers.” It was not a fair question, as it immediately takes

us away from the solid ground of mathematics into the murky waters of philosophy.

The students were bemused, and I was not surprised.

We will formalize Euclid’s theorem in a particular way, and to do this we will

have to signiﬁcantly narrow down its context. In a radical approach, the context will

be reduced to a bare minimum. We will be talking about certain domains of objects,

and in the case of Euclid’s theorem the domain is the set of all natural numbers. Once

the domain of discourse is speciﬁed, we need to decide what features of its elements

we want to consider. In school we ﬁrst learn how to add and how to multiply

natural numbers; and we will follow that path. We will express Euclid’s theorem

as a statement about addition and multiplication in the domain of natural numbers.

We will talk about addition and multiplication using expressions, called formulas,

in a very restricted vocabulary. We will use variables, two operation symbols: +

and ·, and the symbol = for equality. The variables will be lower case letters x, y,

z, .... For example, x + y = z is a formula expressing that the result of adding a

number x to a number y is some number z. This expression by itself carries no truth

value. It can be neither true nor false, since we do not assign any speciﬁc values

to the variables. Later we will see ways in which we can speak about individual

elements of a domain, but for now we will only have the option of quantifying over

the elements of the domain, and that means stating that either something holds for

all elements, or that something holds for some. For example:

For all x and all y,x + y = y + x. (1.1)

The sentence above expresses that the result does not depend on the order in which

the numbers are added. It is an example of a universal statement; it declares that

something holds for all elements in the domain.

And here is an example of an existential statement, it declares that objects with a

certain property exist in the domain:

There is an x such that x + x = x. (1.2)

This statement is also true. There is an element in the domain of natural numbers

that has the required property. In this case there is only one such element, zero. But

in general, there can be more elements that witness truth of an existential statement.

1.1 What We Talk About When We Talk About Numbers 5

For example,

There is an x such that x · x = x

is a true existential statement about the natural numbers, and there are two witnesses

to its veracity, zero, and one.

Interesting statements about numbers often involve comparisons of their sizes. To

express such statements, we can enlarge our vocabulary by adding a relation symbol,

for example <, and interpret expressions of the form x<yas “some number x is

less than some number y.” Here is an example of a true statement about natural

numbers in this extended language.

For all x, y, and z, if x<y,then x + z<y+ z. (1.3)

Noticethe grammatical form“if ...then....”

The next example is about multiplication. It is an expression without a

truth value.

1 <xand for all y and z, if x = y · z, then x = y or x = z. (1.4)

In statements (1.1), (1.2), and (1.3), all variables were quantiﬁed by a preﬁx, either

“for all” or “there exists.” In (1.4) the variable x is not quantiﬁed, it is left free;it

does not assume any speciﬁc value.

Because of the presence of a free variable, (1.4) does not have a truth value,

nevertheless it serves a purpose. It deﬁnes the property of being a prime number in

terms of multiplication and the relation <. Let me explain how it works.

Think of a prime number, say 7, as a value of x. If I tell you that 7 = y · z,for

some natural numbers y and z, without telling you what these numbers are, then

you know that one of them must be 7 and the other is 1, because one cannot break

down seven into a product of smaller numbers. It is true “for all y and z,” because

for all but a couple of them it is not true that 7 = y ·x, and in such cases it does not

matter what the rest of the formula says. We only consider the “then” part if indeed

7 = y · z.Ifthevalueofx is not prime, say 6, then 6 = 2 · 3, so when you think of

y as 2 and z as 3, it is true that 6 = y · z, but neither y nor z is equal to 6, hence the

property described in (1.4) does not hold “for all y and z.”

If you are familiar with formal logic, I am explaining too much, but if you are not,

it is worthwhile to make sure that you see how the formula (1.4) deﬁnes primeness.

Chose some other candidates for x and see how it works. Also, notice three new

additions to the vocabulary: the symbol 1 for the number one; and two connectives

“and” and “or.”

With the aid of (1.4) we can now write the full statement of Euclid’s theorem:

For all w, there is an x such that w<x, and for all y and z,ifx = y ·z, then x = y

or x = z.

What is the difference between the statement above and the original “There are

inﬁnitely many prime numbers.”? First of all, the new formulation includes the

6 1 First-Order Logic

deﬁnition of primeness in the statement. Secondly, what is more important, the

direct reference to inﬁnity is eliminated. Instead, we just say that for every number

w there is a prime number greater than it with such and such properties, so it follows

that since there are inﬁnitely many natural numbers, there must be inﬁnitely many

prime numbers as well. The most important however is that we managed to express

an important fact about numbers with modest means, just variables, the symbols ·

and <, the preﬁxes “for every” and “there is,” and the connectives: “and, ” “or”, and

“if...then....”

We have made the ﬁrst step towards formalizing mathematics, and we did

this informally. The point was to write a statement representing a meaningful

mathematical fact in a language that is as unambiguous as possible. We succeeded,

by reducing the vocabulary to a few basic elements. This will guide us in our second

step, in which we will formally deﬁne a certain formal language and its grammar.

We will carefully specify the way in which expressions in this language can be

formed. Some of those expressions will be statements that can be assigned truth

values—true or false—when interpreted in particular structures. The evaluation of

those truth values will also be precisely deﬁned. Some other expressions, those

that contain free variables, will serve as deﬁnitions of properties of elements in

structures, and will play an important role. All those properly formed expressions

will be referred to as formulas. My dictionary explains that a formula is “a

mathematical relationship or rule expressed in symbols.” The meaning in this book

is different. We will talk about relationships, and we will use symbols, but formulas

will always represent statements. For example, the expression b · b − 4a · c is a

computational rule written in symbols, but it is not a formula in our sense, since it

is not a statement about the numbers a, b, and c. In contrast, d = b · b − 4a · c is a

formula. It states that if we multiply b by itself and subtract from it the product of

four times a times c, the result is d.

1.1.1 How to Choose a Vocabulary?

In the previous section, we formulated an important fact about numbers—Euclid’s

theorem—using symbols for multiplication a and the ordering (<). This is just one

example, but how does it work in general? What properties of numbers do we want

to talk about? What basic operations or relations can we choose? The answers are

very much driven by applications and particular needs and trends in mathematics. In

the case of number theory, the discipline that deals with fundamental properties of

natural numbers, it turns out that almost any important result can be formulated in a

formal language in which one refers only to addition and multiplication.

Number

In our example we also used the ordering relation <, but in the domain of the natural numbers,

the relation x<ycan be deﬁned in terms of addition, since for all natural numbers x and y, x is

less than y if and only if there is a natural number z such that z is not 0 and x +z = y.

1.1 What We Talk About When We Talk About Numbers 7

theory may be the most difﬁcult and mysterious branch of mathematics. Proofs

of many central results are immensely complex, and they often use mathematical

machinery that reaches well beyond the natural numbers. Still, a bit surprisingly,

a formal system with a few symbols in its vocabulary sufﬁces to express almost

all theorems of number theory. It is similar in other branches of mathematics. The

mathematical structures, and the facts about them are complex, but the vocabulary

and the grammar of the formal system that we will discuss in this book are much

simpler.

The real numbers will be deﬁned precisely later. For the moment, you can

think of them as all numbers representing geometric distances and their negative

opposites. The following statement is written in a rigorous, but informal language

of mathematics. It involves the concept of one-to-one correspondence. A one-to-one

correspondence between two sets A and B is a matching that to every element of A

assigns exactly on element of B in such a way that every element of B has a match.

Let A be an inﬁnite set of real numbers. Then either there is a one-to-one correspondence

between A and the set of all natural numbers, or there is a one-to-one correspondence A

and the set of all real numbers.

This is a variant of what is known as the Continuum Hypothesis. The Continuum

Hypothesis can also be stated in terms of sizes of inﬁnite sets. In the 1870s, Georg

Cantor found a way to measure sizes of inﬁnite sets by assigning to them certain

inﬁnite objects, which he called cardinal numbers. The smallest inﬁnite cardinal

number is ℵ

and it is the size of the set of all natural numbers. It was Cantor’s

great discovery that the size of the set of all real numbers, denoted by c, is larger

that ℵ

. Another way to state the Continuum Hypothesis is: if A is an inﬁnite set

of real numbers, then the cardinality of A is either ℵ

or c. The hypothesis was

proposed by Georg Cantor in the 1870s, and David Hilbert put it prominently at

the top of his list of open problems in mathematics presented to the International

Congress of Mathematicians in Paris in 1900. The Continuum Hypothesis is about

numbers, but it is not about arithmetic. It is about inﬁnite sets, and about one-

to-one correspondences between them. What are those objects, and how can we

know anything about them? What is an appropriate language in which facts about

inﬁnite objects can be expressed? What principles can be used in proofs? Precisely

such questions led David Hilbert to the idea of formalizing and axiomatizing

mathematics. There is a short historical note about Hilbert’s program for foundations

of mathematics in Appendix B.

The Continuum Hypothesis is a statement about sets or real numbers and their

correspondences. To express it formally one needs to consider a large domain

in which all real numbers, their sets, and matchings between them are elements.

Remarkably, it turned out that the vocabulary of a formal system in which one can

talk about all those different elements, and much more, can be reduced to logical

symbols of the kind we used for the domain of the natural numbers, and just one

symbol for the set membership relation ∈. All that will be discussed in detail in

Chap. 6.

剩余187页未读，继续阅读

Jesse-Jiang

粉丝: 1
资源: 30

罗马诺·科萨克《数学逻辑：数、集、结构与对称性》概览

Mathematical Logic.pdf 高清

Handbook of Mathematical Logic

a friendly introduction to mathematical logic

离散数学命题逻辑的参考文献

verilog ALU

python numpy

mathematical explanation of diagonal loading

NumericKeypad

important numpy

System.OverflowException:“Arithmetic operation resulted in an overflow.”

Can you develop a learning path for me to master AI

TypeError: must be real number, not str

result[mask] = op(xrav[mask], y) TypeError: unsupported operand type(s) for -: 'str' and 'str'

现有三维环境构造建模的方法

Machine Learning specific learning route

Combining Prior Knowledge and Data for Robust Controller Design

nsupported operand type(s) for -: 'str' and 'str'

feature engineering python

anfis matlab

最新资源