Notes on Mathematical Logic David W. Kueker

[Pages:114]Notes on Mathematical Logic

David W. Kueker

University of Maryland, College Park E-mail address: dwk@math.umd.edu URL:

Contents

Chapter 0. Introduction: What Is Logic?

1

Part 1. Elementary Logic

5

Chapter 1. Sentential Logic

7

0. Introduction

7

1. Sentences of Sentential Logic

8

2. Truth Assignments

11

3. Logical Consequence

13

4. Compactness

17

5. Formal Deductions

19

6. Exercises

20

20

Chapter 2. First-Order Logic

23

0. Introduction

23

1. Formulas of First Order Logic

24

2. Structures for First Order Logic

28

3. Logical Consequence and Validity

33

4. Formal Deductions

37

5. Theories and Their Models

42

6. Exercises

46

46

Chapter 3. The Completeness Theorem

49

0. Introduction

49

1. Henkin Sets and Their Models

49

2. Constructing Henkin Sets

52

3. Consequences of the Completeness Theorem

54

4. Completeness Categoricity, Quantifier Elimination

57

5. Exercises

58

58

Part 2. Model Theory

59

Chapter 4. Some Methods in Model Theory

61

0. Introduction

61

1. Realizing and Omitting Types

61

2. Elementary Extensions and Chains

66

3. The Back-and-Forth Method

69

i

ii

CONTENTS

4. Exercises

71

71

Chapter 5. Countable Models of Complete Theories

73

0. Introduction

73

1. Prime Models

73

2. Universal and Saturated Models

75

3. Theories with Just Finitely Many Countable Models

77

4. Exercises

79

79

Chapter 6. Further Topics in Model Theory

81

0. Introduction

81

1. Interpolation and Definability

81

2. Saturated Models

84

3. Skolem Functions and Indescernables

87

4. Some Applications

91

5. Exercises

95

95

Appendix A. Appendix A: Set Theory

97

1. Cardinals and Counting

97

2. Ordinals and Induction

100

Appendix B. Appendix B: Notes on Validities and Logical Consequence 103

1. Some Useful Validities of Sentential Logic

103

2. Some Facts About Logical Consequence

104

Appendix C. Appendix C: Gothic Alphabet

105

Bibliography

107

Index

109

CHAPTER 0

Introduction: What Is Logic?

Mathematical logic is the study of mathematical reasoning. We do this by developing an abstract model of the process of reasoning in mathematics. We then study this model and determine some of its properties.

Mathematical reasoning is deductive; that is, it consists of drawing (correct) inferences from given or already established facts. Thus the basic concept is that of a statement being a logical consequence of some collection of statements. In ordinary mathematical English the use of "therefore" customarily means that the statement following it is a logical consequence of what comes before.

Every integer is either even or odd; 7 is not even; therefore 7 is odd.

In our model of mathematical reasoning we will need to precisely define logical consequence. To motivate our definition let us examine the everyday notion. When we say that a statement is a logical consequence of ("follows from") some other statements 1, . . . , n, we mean, at the very least, that is true provided 1, . . . , n are all true.

Unfortunately, this does not capture the essence of logical consequence. For example, consider the following:

Some integers are odd; some integers are prime; therefore some integers are both odd and prime.

Here the hypotheses are both true and the conclusion is true, but the reasoning is not correct.

The problem is that for the reasoning to be logically correct it cannot depend on properties of odd or prime integers other than what is explicitly stated. Thus the reasoning would remain correct if odd, prime, and integer were changed to something else. But in the above example if we replaced prime by even we would have true hypotheses but a false conclusion. This shows that the reasoning is false, even in the original version in which the conclusion was true.

The key observation here is that in deciding whether a specific piece of reasoning is or is not correct we must consider alMathematical logic is the study of mathematical reasoning. We do this by developing an abstract model of the process of reasoning in mathematics. We then study this model and determine some of its properties.

Mathematical reasoning is deductive; that is, it consists of drawing (correct) inferences from given or already established facts. Thus the basic concept is that of a statement being a logical consequence of some collection of statements. In ordinary mathematical English the use of "therefore" customarily means that the statement following it is a logical consequence of what l ways of interpreting the undefined concepts--integer, odd, and prime in the above example. This is conceptually easier

1

2

0. INTRODUCTION: WHAT IS LOGIC?

in a formal language in which the basic concepts are represented by symbols (like P , Q) without any standard or intuitive meanings to mislead one.

Thus the fundamental building blocks of our model are the following:

(1) a formal language L, (2) sentences of L: , , . . ., (3) interpretations for L: A, B, . . ., (4) a relation |= between interpretations for L and sentences of L, with A |=

read as " is true in the interpretation A," or "A is a model of ."

Using these we can define logical consequence as follows:

Definition -1.1. Let = {1, . . . , n} where 1, . . . , n are sentences of L, and let be a sentence of L. Then is a logical consequence of if and only if for every interpretation A of L, A |= provided A |= i for all i = 1, . . . , n.

Our notation for logical consequence is |= . In particular note that |= , that is, is not a logical consequence of , if and only if there is some interpretation A of L such that A |= i for all i but A |= , A is not a model of . As a special limiting case note that |= , which we will write simply as |= , means that A |= for every interpretation A of L. Such a sentence is said to be logically true (or valid ). How would one actually show that |= for specific and ? There will be infinitely many different interpretations for L so it is not feasible to check each one in turn, and for that matter it may not be possible to decide whether a particular sentence is or is not true on a particular structure. Here is where another fundamental building block comes in, namely the formal analogue of mathematical proofs. A proof of from a set of hypotheses is a finite sequence of statements 0, . . . , k where is k and each statement in the sequence is justified by some explicitly stated rule which guarantees that it is a logical consequence of and the preceding statements. The point of requiring use only of rules which are explicitly stated and given in advance is that one should be able to check whether or not a given sequence 0, . . . , k is a proof of from . The notation will mean that there is a formal proof (also called a deduction or derivation) of from . Of course this notion only becomes precise when we actually give the rules allowed. Provided the rules are correctly chosen, we will have the implication

if then |= .

Obviously we want to know that our rules are adequate to derive all logical consequences. That is the content of the following fundamental result:

Theorem -1.1 (Completeness Theorem (K. G?odel)). For sentences of a firstorder language L, we have if and only if |= .

First-order languages are the most widely studied in modern mathematical logic, largely to obtain the benefit of the Completeness Theorem and its applications. In these notes we will study first-order languages almost exclusively.

Part ?? is devoted to the detailed construction of our "model of reasoning" for first-order languages. It culminates in the proof of the Completeness Theorem and derivation of some of its consequences.

0. INTRODUCTION: WHAT IS LOGIC?

3

Part ?? is an introduction to Model Theory. If is a set of sentences of L, then Mod(), the class of all models of , is the class of all interpretations of L which make all sentences in true. Model Theory discusses the properties such classes of interpretations have. One important result of model theory for first-order languages is the Compactness Theorem, which states that if Mod() = then there must be some finite 0 with Mod(0) = .

Part ?? discusses the famous incompleteness and undecidability results of G'odel, Church, Tarski, et al. The fundamental problem here (the decision problem) is whether there is an effective procedure to decide whether or not a sentence is logically true. The Completeness Theorem does not automatically yield such a method.

Part ?? discusses topics from the abstract theory of computable functions (Recursion Theory).

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download