Arnold W. Miller Department of Mathematics University of Wisconsin 480 Lincoln Drive Madison, WI 53706 [email protected] Fall 95 Introduction to Mathematical Logic I have used these questions or some variations four times to teach a begin- ning graduate course in Mathematical Logic. I want to thank the many stu- dents who hopefully had some fun doing them, especially, Michael Benedikt, Tom Linton, Hans Mathew, Karl Peters, Mark Uscilka, Joan Hart, Stephen Mellendorf, Ganesan Ramalingam, Steven Schwalm, Garth Dickie, Garry Schumacher, Krung Sinapiromsaran, Stephen Young, Brent Hetherwick, Ma- ciej Smuga-Otto, and Stephen Tanner. Instructions Do not read logic books during this semester, it is self-defeating. You will learn proofs you have figured out yourself and the more you have to discover yourself the better you will learn them. You will probably not learn much from your fellow student’s presentations (although the one doing the presenting does). And you shouldn’t! Those that have solved the problem should be sure that the presented solution is correct. If it doesn’t look right it probably isn’t. Don’t leave this up to me, if I am the only one who objects I will stop doing it. For those that haven’t solved the problem, you should regard the presented solution as a hint and go and write up for yourself a complete and correct solution. Also you might want to present it to one of your fellow students outside the classroom, if you can get one to listen to you. 1 The Moore Method From P.R. Halmos1: “What then is the secret–what is the best way to learn to solve problems? The answer is implied by the sentence I started with: solve problems. The method I advocate is sometimes known as the ‘Moore method’, because R.L. Moore developed and used it at the University of Texas. It is a method of teaching, a method of creating the problem-solving attitude in a student, that is a mixture of what Socrates taught us and the fiercely competitive spirit of the Olympic games.” From F.Burton Jones2: “What Moore did: ... After stating the axioms and giving motivating examples to illustrate their meaning he would then state definitions and theorems. He simply read them from his book as the students copied them down. He would then instruct the class to find proofs of their own and also to construct examples to show that the hypotheses of the theorems could not be weakened, omitted, or partially omitted. ... “When a student stated that he could prove Theorem x, he was asked to go to the blackboard and present the proof. Then the other students, especially those who hadn’t been able to discover a proof, would make sure thattheproofpresentedwascorrectandconvincing. Mooresternlyprevented heckling. This was seldom necessary because the whole atmosphere was one of a serious community effort to understand the argument.” From D.Taylor3: “Criteria which characterize the Moore method of teaching include: (1) The fundamental purpose: that of causing a student to develop his power at rational thought. (2) Collecting the students in classes with common mathematical knowledge, striking from membership of a class any student whose knowledge is too advanced over others in the class. 1The teaching of problem solving, Amer. Math. Monthly, (1975)82, 466-470. 2The Moore method, Amer. Math. Monthly, (1977)84, 273-278. 3Creative teaching: heritage of R.L.Moore, University of Houston, 1972, QA 29 M6 T7, p149. 2 (3) Causing students to perform research at their level by confronting the class with impartially posed questions and conjectures which are at the limits of their capability. (4) Allowing no collective effort on the part of the students inside or outside of class, and allowing the use of no source material. (5) Calling on students for presentation of their efforts at settling questions raised, allowing a feeling of “ownership” of a theorem to develop. (6) Fostering competition between students over the settling of questions raised. (7) Developing skills of critical analysis among the class by burdening stu- dents therein with the assignment of “refereeing” an argument presented. (8) Pacing the class to best develop the talent among its membership. (9) Burdening the instructor with the obligation to not assist, yet respond to incorrect statements, or discussions arising from incorrect statements, with immediate examples or logically sound propositions to make clear the objec- tion or understanding.” Taylor’s(2)and(4)arealittletooextremeforme. ItisOKtocollaborate with your fellow students as long as you give them credit. In fact, it is a good idea to try out your argument first by presenting it to fellow student. Avoid reading logic if you can, at least this semester, but if you do give a reference. For more readings on the Moore method see: Paul R. Halmos, What is Teaching?, Amer. Math. Monthly, 101 (1994), 848-854. Donald R. Chalice, How to teach a class by the modified Moore method, Amer. Math. Monthly, 102 (1995), 317-321. Quote From P.R. Halmos: “A famous dictum of Po´lya’s about problem solving is that if you can’t solve a problem, then there is an easier problem that you can’t solve–find it!” 3 Propositional Logic and the Compactness Theorem The syntax (grammar) of propositional logic is the following. The logical symbols are ∧,∨,¬,→, and ⇐⇒ . The nonlogical symbols consist of an arbi- trary nonempty set P that we assume is disjoint from the set of logical sym- bolstoavoidconfusion. ThesetP isreferredtoasthesetofatomic sentences orasthesetofpropositional letters. Forexample, {P,Q,R}, {P ,P ,P ,...}, 0 1 2 or {S : r ∈ R}. The set of propositional sentences S is the smallest set of r finite strings of symbols such that P ⊆ S, and if θ ∈ S and ψ ∈ S, then ¬θ ∈ S,(θ∧ψ) ∈ S,(θ∨ψ) ∈ S,(θ → ψ) ∈ S, and (θ ⇐⇒ ψ) ∈ S. The semantics (meaning) of propositional logic consists of truth evalua- tions. A truth evaluation is a function e : S → {T,F}, that is consistent with the following truth tables: θ ψ ¬θ (θ∧ψ) (θ∨ψ) (θ → ψ) (θ ⇐⇒ ψ) T T F T T T T T F F F T F F F T T F T T F F F T F F T T For example if e(θ) = T and e(ψ) = F, then e(θ → ψ) = F. Also e(¬θ) = T iff e(θ) = F. For example, if P = {P : x ∈ R} and we define e(P ) = T x x if x is a rational and e(P ) = T if x is a irrational, then e((P ∧¬P√ )) = x 2 2 T. However if we define e(cid:48)(P ) = T iff x is an algebraic number, then x e(cid:48)((P ∧¬P√ )) = F. 2 2 A sentence θ is called a validity iff for every truth evaluation e, e(θ) = T. Asentenceθiscalledacontradictioniffforeverytruthevaluatione,e(θ) = F. We say that two sentences θ and ψ are logically equivalent iff for every truth evaluation e, e(θ) = e(ψ). A set of logical symbols is adequate for propositional logic iff every propositional sentence is logically equivalent to one whose only logical symbols are from the given set. 1.1 Define S = P the atomic sentences and define 0 S = S ∪{¬θ : θ ∈ S }∪{(θ#ψ) : θ,ψ ∈ S ,# ∈ {∧,∨,→, ⇐⇒ }} n+1 n n n Prove that S = S ∪S ∪S ∪···. 0 1 2 4 1.2 Prove that for any function f : P → {T,F} there exists a unique truth evaluation e : S → {T,F} such that f = e (cid:22) P. The symbol e (cid:22) P stands for the restriction of the function e to P. 1.3 Let θ and ψ be two propositional sentences. Show that θ and ψ are logically equivalent iff (θ ⇐⇒ ψ) is a validity. 1.4 Suppose θ is a propositional validity, P and Q are two of the propositional letters occurring in θ, and ψ is the sentence obtained by replacing each oc- currence of P in θ by Q. Prove that ψ is a validity. 1.5 Can you define ∨ using only →? Can you define ∧ using only →? 1.6 Show that {∨,¬} is an adequate set for propositional logic. 1.7 The definition of the logical connective nor ( ⊕ ) is given by the following truth table: θ ψ (θ⊕ψ) T T F T F F F T F F F T Show that {⊕} is an adequate set for propositional logic. 1.8 (Sheffer) Find another binary connective that is adequate all by itself. 1.9 Show that {¬} is not adequate. 1.10 Show that {∨} is not adequate. 1.11 How many binary logical connectives are there? We assume two connectives are the same if they have the same truth table. 1.12 Show that there are exactly two binary logical connectives that are adequate all by themselves. Two logical connectives are the same iff they have the same truth table. 1.13 Suppose P = {P ,P ,...,P }. How many propositional sentences (up to 1 2 n logical equivalence) are there in this language? 1.14 Show that every propositional sentence is equivalent to a sentence in disjunc- tive normal form, i.e. a disjunction of conjunctions of atomic or the negation of atomic sentences: ∨m ( ∧ki θ ) ij i=1 j=1 5 where each θij is atomic or ¬atomic. The expression ∨n ψ abbreviates i=1 i (ψ ∨(ψ ∨(···∨(ψ ∨ψ )))···). 1 2 n−1 n In the following definitions and problems Σ is a set of propositional sen- tences in some fixed language and all sentences are assumed to be in this same fixed language. Σ is realizable iff there exists a truth evaluation e such that for all θ ∈ Σ, e(θ) = T. Σ is finitely realizable iff every finite subset of Σ is realizable. Σ is complete iff for every sentence θ in the language of Σ either θ is in Σ or ¬θ is in Σ. 1.15 Show that if Σ is finitely realizable and θ is any sentence then either Σ∪{θ} is finitely realizable or Σ∪{¬θ} is finitely realizable. 1.16 Show that if Σ is finitely realizable and (θ∨ψ) is in Σ, then either Σ∪{θ} is finitely realizable or Σ∪{ψ} is finitely realizable. 1.17 Show that if Σ is finitely realizable and complete and if θ and (θ → ψ) are both in Σ, then ψ is in Σ. 1.18 Show that if Σ is finitely realizable and complete, then Σ is realizable. 1.19 Suppose that the set of all sentences in our language is countable, e.g., S = {θ : n = 0,1,2,...}. Show that if Σ is finitely realizable, then there exists a n complete finitely realizable Σ(cid:48) with Σ ⊆ Σ(cid:48). 1.20 (Compactness theorem for propositional logic) Show that every finitely realizable Σ is realizable. You may assume there are only countably many sentences in the language. A family of sets C is a chain iff for any X,Y in C either X ⊆ Y or Y ⊆ X. The union of the family A is (cid:91) A = {b : ∃c ∈ A,b ∈ c}. M is a maximal member of a family A iff M ∈ A and for every B if B ∈ A and M ⊆ B, then M = B. A family of sets A is closed under the unions of chains iff for every subfamily, C, of A which is a chain the union of the chain, (cid:83)C, is also a member of A. Maximality Principle: Every family of sets closed under the unions of chains has a maximal member. 6 1.21 Show that the family of finitely realizable Σ is closed under unions of chains. 1.22 Show how to prove the compactness theorem without the assumption that there are only countably many sentences. (You may use the Maximality Principle.) 1.23 Suppose Σ is a set of sentences and θ is some sentence such that for every truth evaluation e if e makes all sentences in Σ true, then e makes θ true. Show that for some finite {ψ ,ψ ,ψ ,...ψ } ⊆ Σ the sentence 1 2 3 n (ψ ∧ψ ∧ψ ∧···∧ψ ) → θ 1 2 3 n is a validity. A binary relation R on a set A is a subset of A × A. Often we write xRy instead of (cid:104)x,y(cid:105) ∈ R. A binary relation ≤ on a set A is a partial order iff a. (reflexive) ∀a ∈ A a ≤ a; b. (transitive) ∀a,b,c ∈ A [(a ≤ b∧b ≤ c) → a ≤ c]; and c. (antisymmetric) ∀a,b ∈ A [(a ≤ b∧b ≤ a) → a = b]. Given a partial order ≤ we define the strict order < by x < y ⇐⇒ (x ≤ y∧x (cid:54)= y) A binary relation ≤ on a set A is a linear order iff ≤ is a partial order and d. (total) ∀a,b ∈ A(a ≤ b∨b ≤ a). A binary relation R on a set A extends a binary relation S on A iff S ⊆ R. 1.24 Show that for every finite set A and partial order ≤ on A there exists a linear order ≤∗ on A extending ≤. 1.25 Let A be any set and let our set of atomic sentences P be: P = {P : a,b ∈ A} ab For any truth evaluation e define ≤ to be the binary relation on A defined e by a ≤ b iff e(P ) = T. e ab Construct a set of sentences Σ such that for every truth evaluation e, e makes Σ true iff ≤ is a linear order on A. e 7 1.26 Without assuming the set A is finite prove for every partial order ≤ on A there exists a linear order ≤∗ on A extending ≤. In the next problems n is an arbitrary positive integer. 1.27 If X ⊆ A and R is a binary relation on A then the restriction of R to X is the binary relation S = R∩(X ×X). For a partial order ≤ on A, a set B ⊆ A is an ≤-chain iff the restriction of ≤ to B is a linear order. Show that given a partial order ≤ on A: the set A is the union of less than n ≤-chains iff every finite subset of A is the union of less than n ≤-chains. 1.28 A partial order ≤ on a set A has dimension less than n+1 iff there exists n linear orders {≤ ,≤ ,≤ ,...,≤ } on A (not necessarily distinct) such that: 1 2 3 n ∀x,y ∈ A [x ≤ y iff (x ≤ y for i = 1,2,...,n)]. i Show that a partial order ≤ on a set A has dimension less than n+1 iff for every finite X included in A the restriction of ≤ to X has dimension less than n+1. 1.29 A binary relation E (called the edges) on a set V (called the vertices) is a graph iff a. (irreflexive) ∀x ∈ V¬xEx; and b. (symmetric) ∀x,y ∈ V (xEy → yEx). We say x and y are adjacent iff xEy. (V(cid:48),E(cid:48)) is a subgraph of (V,E) iff V(cid:48) ⊆ V and E(cid:48) is the restriction of E to V(cid:48). For a graph (V,E) an n coloring is a map c : V → {1,2,...,n} satisfying ∀x,y ∈ V(xEy → c(x) (cid:54)= c(y)), i.e. adjacent vertices have different colors. A graph (V,E) has chromatic number ≤ n iff there is a n coloring on its vertices. Show that a graph has chromatic number ≤ n iff every finite subgraph of it has chromatic number ≤ n. 1.30 A triangle in a graph (V,E) is a set ∆ = {a,b,c} ⊆ V such that aEb, bEc, and cEa. Suppose that every finite subset of V can be partitioned into n or fewer sets none of which contain a triangle. Show that V is the union of n sets none of which contain a triangle. 1.31 (Henkin) A transversal for a family of sets F is a one-to-one choice function. Thatisaone-to-onefunctionf withdomainF andforeveryx ∈ F f(x) ∈ x. Suppose that F is a family of finite sets such that for every finite F(cid:48) ⊆ F,F(cid:48) 8 has a transversal. Show that F has a transversal. Is this result true if F contains infinite sets? 1.32 Let F be a family of subsets of a set X. We say that C ⊆ F is an exact cover of Y ⊆ X iff every element of Y is in a unique element of C. Suppose that every element of X is in at most finitely many elements of F. Show that there exists an exact cover C ⊆ F of X iff for every finite Y ⊆ X there exists C ⊆ F an exact cover of Y. Is it necessary that every element of X is in at most finitely many elements of F? 1.33 If F is a family of subsets of X and Y ⊆ X then we say Y splits F iff for any Z ∈ F, Z ∩Y and Z \Y are both nonempty. Prove that if F is a family of finite subsets of X then F is split by some Y ⊆ X iff every finite F(cid:48) ⊆ F is split by some Y ⊆ X. What if F is allowed to have infinite sets in it? 1.34 Given a set of students and set of classes, suppose each student wants one of a finite set of classes, and each class has a finite enrollment limit. Show that if each finite set of students can be accommodated, they all can be accommodated. 1.35 Show that the compactness theorem of propositional logic is equivalent to the statement that for any set I, the space 2I, with the usual Tychonov product topology is compact, where 2 = {0,1} has the discrete topology. (You should skip this problem if you do not know what a topology is.) 9 The Axioms of Set Theory Here are some. The whole system is known as ZF for Zermelo-Fraenkel set theory. When the axiom of choice is included it is denoted ZFC. It was originally developed by Zermelo to make precise what he meant when he said that the well-ordering principal follows from the axiom of choice. Latter Fraenkel added the axiom of replacement. Another interesting system is GBN which is Go¨del-Bernays-von Neumann set theory. Empty Set: ∃x∀y(y ∈/ x) The empty set is usually written ∅. Extensionality: ∀x∀y(x = y ⇐⇒ ∀z(z ∈ x ⇐⇒ z ∈ y)) Hence there is only one empty set. Pairing: ∀x∀y∃z∀u(u ∈ z ⇐⇒ u = x∨u = y) We usually write z = {x,y}. Union: ∀x∃y(∀z(z ∈ y ⇐⇒ (∃uu ∈ x∧z ∈ u)) We usually write y = ∪x. A ∪ B abbreviates ∪{A,B}. z ⊆ x is an abbreviation for ∀u(u ∈ z → u ∈ x). Power Set: ∀x∃y∀z(z ∈ y ⇐⇒ z ⊆ x) We usually write y = P(x). For any set x , x+1 = x∪{x}. Infinity: ∃y(∅ ∈ y∧∀x(x ∈ y → x+1 ∈ y)) The smallest such y is denoted ω, so ω = {0,1,2,...}. Comprehension Scheme: ∀z∃y∀x[x ∈ y ⇐⇒ (x ∈ z∧θ(x))] 10