Discrete Mathematics(II) Spring 2012 Lecture 3: Introduction to logic Lecturer. yil 1 Overview What is a mathematical proof? How can proofs be justified? are there limitations to provability? To what extent can machines carry out mathematical proofs? We do also concern about what is the relationship between logic and computer science. Logic is profound and abstract, even much more abstract than abstract algebra. Finally, we do care about what we can learn from this course In this lecture, we first give a brief history of mathematical logic. Then we define a partial order nd represent tree in an approach other than the way in last semester 2 Brief History of logic The history of logic is very long. We can even trace back to the era before systematic arithmetic occurred. Aristotle (384-322 B C.E. introduced theory of syllogistic, the source of modern loy Before 19th century, logic was the garden only for philosophers From then on, logic was enriched and formalized, by mathematicians, such as De Morgan(1806-71) Boole(1815-64), and Schroder(1841-1902). Frege(1848-1925) made logic systematic and helpful to mathematics. He then established a connection between arithematics and logic. In the late of 1900s, logic became the powerful tool to expel the root of the third mathematical crisis. From now on. logic is the world of mathematicians In this course, we only introduce essential part of first order logic, which is the corner stone of whole logic building. Furthermore, it consists of propositional logic and predict logic, the former can be embedded into the latter Based on first order logic, we can introduce seconder order logic and even much higher order logic as ou wish. There are also some other type of logic system, e.g., modal logic, intuitionistic logic, and temporal logic. Classic logic only has two value0 and 1. There is also a system called multiple-value Mathematical logic is aim to formalize the pattern of human deduction but not completely. It can be divided into two threads: syntax and semantics. Post(1897-1954) found the connection between syntax and semantics. He proved completeness and soundness theorem in propositional logic. Godel(1906-78)proved completeness in predicate logic, which was a very important contribution Herbrand(1908-31), who disliked existences proof, gave a construct method. Henkin tried to find a model for a given set of sentences Several proof systems have been introduced for different reasons. However, they have the same
Discrete Mathematics (II) Spring 2012 Lecture 3: Introduction to Logic Lecturer: Yi Li 1 Overview What is a mathematical proof? How can proofs be justified? are there limitations to provability? To what extent can machines carry out mathematical proofs? We do also concern about what is the relationship between logic and computer science. Logic is profound and abstract, even much more abstract than abstract algebra. Finally, we do care about what we can learn from this course. In this lecture, we first give a brief history of mathematical logic. Then we define a partial order and represent tree in an approach other than the way in last semester. 2 Brief History of Logic The history of logic is very long. We can even trace back to the era before systematic arithmetic occurred. Aristotle(384-322 B.C.E.) introduced theory of syllogistic, the source of modern logic. Before 19th century, logic was the garden only for philosophers. From then on, logic was enriched and formalized, by mathematicians, such as De Morgan (1806-71), Boole (1815-64), and Schr¨oder (1841-1902). Frege (1848-1925) made logic systematic and helpful to mathematics. He then established a connection between arithematics and logic. In the late of 1900s, logic became the powerful tool to expel the root of the third mathematical crisis. From now on, logic is the world of mathematicians. In this course, we only introduce essential part of first order logic, which is the corner stone of whole logic building. Furthermore, it consists of propositional logic and predict logic, the former can be emmbedded into the latter. Based on first order logic, we can introduce seconder order logic and even much higher order logic as you wish. There are also some other type of logic system, e.g., modal logic, intuitionistic logic, and temporal logic. Classic logic only has two value 0 and 1. There is also a system called multiple-value logic. Mathematical logic is aim to formalize the pattern of human deduction but not completely. It can be divided into two threads: syntax and semantics. Post(1897-1954) found the connection between syntax and semantics. He proved completeness and soundness theorem in propositional logic. G¨odel(1906-78) proved completeness in predicate logic, which was a very important contribution. Herbrand(1908-31), who disliked existences proof, gave a construct method. Henkin tried to find a model for a given set of sentences. Several proof systems have been introduced for different reasons. However, they have the same 1
function and are actually equivalent. Axiomatic system is very traditional and occurs in the most of textbook. Robbinson put up with resolution method, which continued the work of herbrand Beth and Smullyan construct a tableaux proof system. It is the simplest proof system and is easy Leibniz had a dream to construct a machine to find all theorems, hilbert followed him and for- malized many mathematical branch in his era. But Godel ruined their dream by his famous incompleteness theorem. This course just covers a very small part of provable topics Logic aims to formalize statements and relationship between them. Actually, a programming language can also be taken as a type of formal language. Then they both follow the same approach So this course is another training about programming. It can go further. If you are unlucky, you will learn computability, decidability, and enumerability, which is the theory of computation, the base of computer science 3 Order Logic for application adopts a special set of its own notations. For convenience to read text book we just follow the terminology in text book. Then, we need change the definition of partial order, which are slightly different with the one learned in last semester. And tree is also a very important tool to our class. And it is totally represented in an order approach, as a partial order In Logic for application, partial order is defined as following Definition 1(Partial order). A partial order is a set S with a binary relation on S, which is transitive and irreflexive You should mind that partial order is irreflexive other than reflexive defined in previous semester and the most of text book on set theory Whatever the change of partial order, linear order is always the same Definition 2(Linear order). A partial order is a linear order, if it satisfies the trichotomy law <y or t=y or y <a As we know, there are many partially ordered sets. For further investigation, we can divide them into two categories, something bad and something good. Here, we define what is good as following Definition 3(Well ordering). A linear order is well ordered if every nonempty set A of s has a least element The set N is a reference of countable set. countable is defined base on set of natural number Definition 4( Countable). A set A is countable if there is a one-to-one mapping from A to M As a rational number can be represent as a pair of two natural number. Q is a set of countable elements, which also contains natural number as a very small part of it Specially, when we can count a set clearly, here we mean a exact number, we define the followin concept
function and are actually equivalent. Axiomatic system is very traditional and occurs in the most of textbook. Robbinson put up with resolution method, which continued the work of Herbrand. Beth and Smullyan construct a tableaux proof system. It is the simplest proof system and is easy to use. Leibniz had a dream to construct a machine to find all theorems. Hilbert followed him and formalized many mathematical branch in his era. But G¨odel ruined their dream by his famous incompleteness theorem. This course just covers a very small part of provable topics. Logic aims to formalize statements and relationship between them. Actually, a programming language can also be taken as a type of formal language. Then they both follow the same approach. So this course is another training about programming. It can go further. If you are unlucky, you will learn computability, decidability, and enumerability, which is the theory of computation, the base of computer science. 3 Order Logic for application adopts a special set of its own notations. For convenience to read text book, we just follow the terminology in text book. Then, we need change the definition of partial order, which are slightly different with the one learned in last semester. And tree is also a very important tool to our class. And it is totally represented in an order approach, as a partial order. In Logic for application, partial order is defined as following: Definition 1 (Partial order). A partial order is a set S with a binary relation < on S, which is transitive and irreflexive. You should mind that partial order is irreflexive other than reflexive defined in previous semester and the most of text book on set theory. Whatever the change of partial order, linear order is always the same. Definition 2 (Linear order). A partial order < is a linear order, if it satisfies the trichotomy law: x < y or x = y or y < x. As we know, there are many partially ordered sets. For further investigation, we can divide them into two categories, something bad and something good. Here, we define what is good as following. Definition 3 (Well ordering). A linear order is well ordered if every nonempty set A of S has a least element. The set N is a reference of countable set. countable is defined base on set of natural number. Definition 4 (Countable). A set A is countable if there is a one-to-one mapping from A to N . As a rational number can be represent as a pair of two natural number. Q is a set of countable elements, which also contains natural number as a very small part of it. Specially, when we can count a set clearly, here we mean a exact number, we define the following concept. 2
Definition 5(Finite). A set A is finite if there is a one-to-one mapping from A to 0, 1,.,n-11 for some n∈A In this semester, finite is our favor and unfortunately evil too. As a student who study computer area, here we just mean building machine or coining software, infinite number of objects is always out of our control With these two we can define its negative side Definition 6. 1. If A is not countable, it is uncountable 2. If A is not finite, it is infinite The following theorem is a base on syntax of logic. Theorem 7. Let a be a countable set. The set of all finite sequence of elements in A is also countable Proof We can formalize it as S=UneNA=AUAU.UA"U.. Then we can construct a mapping from an to N. 4 Tree In the last semester, we have learned tree in the way of graph. And we have already known that a relation and a graph can represent each other. Here, we will represent a tree with a partial order We can define a tree based on a partial order as follows Definition 8(Tree). A tree is a set T(whose elements are called nodes) partially ordered by <r with a unique least element called the root, in which the predecessors of every node are well ordered From now on, we will redefine the concepts and discuss its properties in an order approach Definition 9(Path). A path on a tree T is a manimal linearly ordered subset of T Definition 10(Properties of tree). 1. The levels of a tree T are defined by induction. 2. The oth level of T consists precisely of the root of T. 3. The k+1th level of T consists of the immediate successors of the nodes on the kth level of T 4. If each node has at most n immediate successors, the tree is n-ary or n-branching 5. If each node has finitely many immediate successors, we say that the tree is finitely branching A node with no successors is called a leaf or a terminal node Theorem 11(Konigs lemma). If a finitely branching tree T is infinite, it has an infinite path sketch. If there is no infinite path, the tree would be finite. Split the successors of the node into two parts. One with infinite successors and the other with finite successors
Definition 5 (Finite). A set A is finite if there is a one-to-one mapping from A to {0, 1, . . . , n−1} for some n ∈ N . In this semester, finite is our favor and unfortunately evil too. As a student who study computer area, here we just mean building machine or coining software, infinite number of objects is always out of our control. With these two, we can define its negative side. Definition 6. 1. If A is not countable, it is uncountable. 2. If A is not finite, it is infinite. The following theorem is a base on syntax of logic. Theorem 7. Let A be a countable set. The set of all finite sequence of elements in A is also countable. Proof. We can formalize it as S = ∪n∈N An = A1 ∪ A2 ∪ · · · ∪ An ∪ · · · . Then we can construct a mapping from An to N . 4 Tree In the last semester, we have learned tree in the way of graph. And we have already known that a relation and a graph can represent each other. Here, we will represent a tree with a partial order. We can define a tree based on a partial order as follows: Definition 8 (Tree). A tree is a set T(whose elements are called nodes) partially ordered by <T , with a unique least element called the root, in which the predecessors of every node are well ordered by <T . From now on, we will redefine the concepts and discuss its properties in an order approach. Definition 9 (Path). A path on a tree T is a maximal linearly ordered subset of T. Definition 10 (Properties of tree). 1. The levels of a tree T are defined by induction. 2. The 0 th level of T consists precisely of the root of T. 3. The k + 1th level of T consists of the immediate successors of the nodes on the k th level of T. 4. If each node has at most n immediate successors, the tree is n-ary or n-branching. 5. If each node has finitely many immediate successors, we say that the tree is finitely branching. 6. A node with no successors is called a leaf or a terminal node. Theorem 11 (K¨onig’s lemma). If a finitely branching tree T is infinite, it has an infinite path. sketch. If there is no infinite path, the tree would be finite. Split the successors of the node into two parts. One with infinite successors and the other with finite successors. 3
5 Extensions on tree Definition 12(Segment). 1. o is an initial segement of T ifa o 2. o is an proper initial segement of t if CT Definition 13 (Lexicographic ordering). For two sequences o and T we say that o is well ordered 7. Find some ways to make a tree linear other than lexicographic orderin
5 Extensions on Tree Definition 12 (Segment). 1. σ is an initial segement of τ if σ ⊂ τ or σ = τ . 2. σ is an proper initial segement of τ if σ ⊂ τ . Definition 13 (Lexicographic ordering). For two sequences σ and τ we say that σ is well ordered. 7. Find some ways to make a tree linear other than lexicographic ordering. 4