Martin Flashman's Courses - Math 446 Spring, '98

## MATH 446 Logic and Set Theory  Class Summaries

 1/20 22 27 29 2/3 5 10 12 17 19 24 26 3/3 3/5 3/10 3/12 3/24 3/26 3/31 4/2 7 9 14 16 21 23 28 30 5/5 5/7 END!

• 1/20 Introductory Class. We discussed some details of the Course Description.

Notice we didn't discuss the grading scheme or the final examination yet.

Assigments are due on Thursdays. Questions on the problems will be discussed on previous Tuesday. Assignments will be returned on Tuesdays.

Some reading resources mentioned were The College Mathematics Journal, The Mathematics Magazine, The Mathematics Teacher, The Mathmatics Gazette, The American Mathematical Monthly, The Journal of Symbolic Logic, and The Encyclopaedia Britannica.

The course content deals mainly with the mathematical ( not  philosophical) foundations of mathematics - traditionally thought of as logic and set theory.
Some important results of the 20th century were briefly described. These relate the semantics (meaning) and syntax ( axioms, rules of proof, and theorems) of logic, number theory, and set theory. Here are some informal statements of these results:

1. The completeness of predicate logic: There is an axiom system for predicate logic in which every true statement can be proven from the axioms. (Kurt Godel)
2. The incompleteness of arithmetic: In any sufficiently robust axiom system for arithmetic there will be statements that are true but which cannot be proven from the axioms of that system. (Kurt Godel)
3. The consistency of set theory with certain axioms: If set theory (without the axiom of choice and the continuum hypothesis) is consistent, then set theory with the axiom of choice and the continuum hypothesis is consistent. (Kurt Godel)
4. The independence of certain axioms: If set theory (without the axiom of choice and the continuum hypothesis) is consistent, then the axiom of choice and the continuum hypothesis cannot be proven from the axioms of set theory. (Paul Cohen)

We began a discussion of informal statement logic. We considered the nature of a statement as distinguished from sentences where no adquate context is given to make sense of the sentences and open sentences where some element of the sentence is not sufficiently quantified. Statements for the purpose of this course will be sentences that can be determined as being TRUE or FALSE. We will use captial letters  (A, B, ...) to represent specific statements. Statements may be joined into compound statements using connectives....negation (~A), alternation - or (AvB), conjunctions -and (A&B) , and conditional - if ... then (A-> B).

Next time:  Write short responses to what the following words mean to you: mathematics, logic, sets, number.
More on connectives, truth values for compund statements, and truth functions.

• 1/22 We discussed the rest of the course description. Homework will be graded acceptable or unacceptable with problems to be resubmitted. the homework part of the grade will be determined by the number of acceptable assignments. (Some longer assignements may be counted as 2 assignments.)

We continued the discussion of statements (A,B, etc.); statement variables (p,q,etc.) , and statement forms (A,B, etc.) . We noted that the definition of a statement form us recursive (or inductive), that is, certain objects are considered as statment forms by themselves, and then we are told how staement forms are manipulated to make new statement forms. We looked at  Gateway to Logic's software that gave a tree illustrating the organization of a statement form.

We noted that any statement form uses an even number of parentheses, and  justified this using an argument organized around the recursive nature of the definition of a statement form. Namely: Any statement variable uses no parentheses (an even number). If we assume that the statement forms A and  B
each use an even number of parentheses, then the new statement forms that can be written directly from these will add (  and ) to these forms, so that the resulting statement form will still use an even number of parentheses. Since any statement form must arise  from a finite number statement variables with a finite number of combinations using the rule on forming new statement forms from old statement forms,  any statement form will use an even number of parentheses.

We noted that this fact is useful for making a first check that a string of symbols is a statement form. This is one thing that computers do frequently.

We started a discussion of  TRUTH and FALSITY of statements. Using statement variables we saw that using 3 variables there are  exactly 8 possible ways the variables could represent statements that would be either TRUE or FALSE. Again we used Gateway to Logic to consider all the possible truth value assignments for a statement with 3 variables. [In general, we saw that if there are n variables in a statement form, there are 2n possible ways that the variables could be assigned as TRUE or FALSE.]

We considered how the truth value of a compund sentence is determined from the connectives and the truth of its simple statements. Again Gateway to Logic gave an example of this determination, but only displayed the result- so we worked through on case in detail to see how the connectives and the forms tree interacted to determine the Truth or Falsity of the statement form in that case.

This led to a discussion of Truth functions determined by statement forms. Given truth values for the statement variables, p,q, and r, , the statement for detemines a value of either T or F. Thus we have a final T or F determined by  the choice of T or F for the three variables. We discussed briefly the number of possible truth functions of 2 variables thaere can be, and saw that this involves a choice of either T or F for the 4 possible ordered pairs, TT, TF, FT, and FF. This gives 24 = 16 possible binary truth functions. Even though there are an infinite number of staement forms using just p and q for statement variables, they can described with 16 truth functions.

Next Class: What do the truth functions have to do with the equivalence of statement forms?

• 1/27 Truth function and equivalence. We started with a consideration of what is the difference between statements being equivalent in form and statements being equivalent in meanng/content. This lead to analysis of an example:

Statement I: If a number is even and greater than 2 then it is not prime.
Statement II: If a number is prime and greater than 2 then it is not even.
After discussing the meaning of these statements about numbers, we agreed that knowing the truth of each statement would inform us immediately about the truth of the other. It was left open as to what we meant exactly by "equivalent in meaning," but it is important to consider the distinction between form and content/meaning.

Looking at the forms for each of the statements we analyzed them further, using the concept of forms being logically equivalent. Statement I was expressed as (p&q)->~r while statement II corresponded to (r&q)->~p.
To determine whether these statements are logically equivalent we examine the more complicated statement form  III: ((p&q)->~r)<-> ((r&q)->~p).
A statement form is a tautology if for any assignment of statements for the statement variables, the statement will be TRUE. [We also discussed briefly contraditions and satisfiable statements.]
For statement I to be logically equivalent to statement II,  statement III must be a tautology.
Our analysis of this lead to connecting logical equivalence of two statement forms to their corresponding truth functions and the following result that:
Suppose A and B are statements forms, then A is logically equivalent to B if and only if the truth function of A is equal to the truth function of B, i.e., fA = fB.

Notice that this last statement is a statement about logical statement forms... it is a statment in "metalogic" or "metamathematics." It is important to distinguish in this course statements written in the logic.. such as A->B, p v q, A&B, where A and B are statement forms, from statement about the logic, such as ~ ~ p is logically equivalent to p.
Statements and arguments about the logic are also structured in their presentation, so we need to be aware of the layers of structure that are being used in the mathematical study of logic and set theory, since these form both the form and the content of the discipline.

We also checked that III was a tautology. As an alternate approach to showing III was a a tautology we considered the possibilities that statement I was FALSE while II wasTRUE and vice versa.
In the first case, this would be possible only if (p&q) was TRUE  while ~r  was FALSE. Thus p,q, and r must all be TRUE, which means that statement II must be TRUE as well, so it is not possible for I to be TRUE with II being FALSE.  A similar argument about the other case was left for thestudents to complete in their notes.
We discussed some of the pro's and con's for this technique in showing that a statement form is a tautology.

We turned our attention to equivalence of statement forms that allow us to simplify the presentation and study of logic,  recognize when statements are not adding to our understanding of the relationship between objects, and allow us to connect statements to simpler fors by the process of substitutions.

We looked at how to replace AvB with an equivalent ~A->B, and A&B with ~(~Av~B). These were connected with DeMorgan's Rules and the equivalence of ~ ~A with A.

Finally we saw how any statement form, A,  is equivalent to a statement form using only the connectives, v , & and ~, by examining the truth function determined by A. See Hamilton for more on this.

Next time: More on substitutions, equivalences, and an adequate list of connectives for studying statement logic.

• 1/29 We began by considering problem 7 from ch.1 of Hamilton. after loking at the truth table and also analyzing the tree of the statement form(s) to how it might be FALSE, we concluded that as long as both A and B are tautologies, the statement form in the problem would be FALSE.

The discussion continued on what lists of connectives are adequate to express any truth function as a statement form using these connectives only. From the last class we know that {~,v,&} is adequate as well as {~, ->}. It was also noticed from a use of DeMorgan's laws and the fact that p->q is logically equivalent to ~pvq that {~,v} and {~,&} are also adequate.  NOR and NAND were also mentioned as being the only single connectives that are adequate by themeselves. There is a trade of  between the number of connectives used and the ease with which one can express simple statement. Fewer connectives make it easier for computations, since there are fewer connectives to recognize.

The discussion then turned to a brief introduction to some set notations: intersection, union, relative complement were all discussed. A lengthy discussion followed about the product of
two sets, AxB = {(a,b): a in A, b in B} We spent time also distinguishing Ax(BxC), (AxB)xC, and AxBxC = {(a,b,c), a in A, b in B, and c in C}. Visualizing products was also discussed along with function examples:  R -> RR -> RxR,  and RxR ->R.
Next class: Arguments, Validity, and Modus Ponens.
[Perhaps we'll start some work on a formal structure for statement logic.]

• 2/3 [Hint for problem in Hamilton on the inadequacy of {~,<-> }: Find some property that is common  to all truth functions arising from statements forms written using ~ and <->. Then a truth function without that property will be connected to a statement form that cannot be equivalent to a statement form using only ~ amd <->.   ]

We looked at three examples of arguments. These used specific mathematical statements: A and B.
The arguments were

 I. 1.  A -> B      2.  B       3.  A II. 1. A -> B       2. ~ B        3.  ~A III. 1. A -> B        2. A         3.  B

In case I the statement A was false, while B was true, so 1 and 2 were true while 3 was false. This was an example of an invalid argument.

In case II A was false,  while B was false, so 1 , 2, and 3 were all true.
In case III A was true, B was true, so 1, 2, and 3 were all true.
These arguments are related to argument forms:

 I. 1.  A -> B      2.  B       3.  A II. 1. A -> B       2. ~ B        3.  ~A III. 1. A -> B        2.  A         3.  B

For an argument form to be logically valid it must be that whenever statements 1 and 2 are true, statement 3 is also true. Argument form I is not valid, while it is in fact the case that II and III are  logically valid.

We noted the distinction between an argument form which is an ordered list of separate statements and a single related compound statement.

 I. 1.  A -> B      2.  B       3.  A  ((A->B)&B)->A II. 1. A -> B       2. ~ B        3.  ~A  ((A->B)&~B)->~A III. 1. A -> B        2.  A         3.  B  ((A->B)&A)->B

Argument form III is called modus ponens.
Argument III should not be confused with the related compound statement or the proposition:
If A -> B is a tautology and A is a tautology then B is a tautology.
[We observed that the fact that argument III is valid would justify this last statement.]

We demonstated that III was as valid argument form.
Noting the connection of  argument III to the statement form ((A->B)&A)->B, we showed that the statement form was tautology. This led to the recognition that an argument form is logically valid if and only if the related statement form of the argument is a tautology.  We used this to check that argument II ("Indirect - contrapositive") is logically valid.

In summary, we say that A1,A2,    ... ,An ;  B is a valid argument form when B is true whenever A1, A2, ... , An are all true.

Proposition:A1,A2,    ... ,An ;  B is a valid argument form if and only if  (A1&A2&    ... &An) -> B is a tautology.

Next time: Onto a formal statement logic, where proofs are not connected directly to truth.

• 2/5  We began an examination of what a formalization of logic entails. For any formalization we establish the following:
1. A formalization of the symbols and forms that are to be involved in the language.
2. A designation of forms that will be called axioms.
3. A designation of rules that will allow one to "derive" forms from other forms.
4. A disgnation of what constitues a proof and theorems in the formalization.

We started an examination of L, a formal treatment of statement logic, following Hamilton.

For symbols we allowed ~,  ->, ( ,  ) , p , and '.  Hamilton allows subscripts using counting numbers for the variables, p1, p2, p3, etc. but this was noted requires a presumed notation prior to the notation of the system. We will use Hamilton's convention understanding that we can instead use the finite list of symbols by defining statement variables by the following: p is a statement variable and if A is a staement variable, then A' is also a statement variable. This is the only way that a form can be a statement variable. After this we defined a well-formed formula (wf) and continued following Hamilton in defining 3 forms for axioms of L and the single rule for L as Modus Ponens or the Rule of Detachment:

 A  A->B B

A proof in L is a finite sequence of wf's where each statement in the sequence is either an axiom  of L or derived from previous wf's by an application of the rule. A theorem is the last statement of a proof. When A is a theorem of L we write  |-L A.

One important goal of this formalization [which we will pursue next week] is to connect the theorems of L to the collection of tautologies that are wf's of L. We will show that every theorem of L is a tautology (soundness) and every tautology in L is a theorem ( adequacy or completeness).

We also considered the situation where a wf or set of wf's are used in a proof like axioms, later to be included in a summary of the argument as hypotheses in a conditional statement. This situation is described as a deduction from the set of wf's. See Hamilton for the formal definitions of this. If G is a set of wf's, we write |-L B to indicate that the statement B can be deduced from G. The main result that we will prove next class is called the deduction theorem. It states that if  Gu{A}|-L B then |-L  (A->B).

• 2/10 We discussed the problem of the inadeqacy of {v,&} and {~, ->}

We then went over the nature of proofs in L with some examples from the text.  We then proved the deduction theorem of L. From this we proved Hypothetical syllogism using the deduction theorem as in Hamilton.
Proposition: {A->B, B->C} |- A->C.

• 2/12 We started with a discussion of infinite sets, especially considering whether a set can be arranged in a list ( i.e., is the set countably infinite?)  We considered the set of counting numbers {1,2,3,... }, the integers {0,1,-1,2,-2,...}, pairs of natural numbers {(0,0), (0,1), (1,0), (0,2) , (1,1), (2,0), (0,3) (1,2),...} and positive rational numbers {p/q, p,q  natural numbers, q not = 0}.... (more ... this section in still being written)

• 2/17 Work continued on adequacy. We defined an extension of L,  as wellas inconsistency and completeness of an extension of L. We discussed the example of L* where any wf is an axiom of L*. This extension of L is complete, but inconsistent... not very useful!

Next we showed that
if L* is a complete and consistent extension of L then the function v* where v*(A)=T if and only if  |- L*  A is a valuation.
[v*(A)=T iff v*(~A)=F; V*(A->B)=F iff v*(A)=T and v*(B)=F.]

Looking further at consistency we showed that
L* is a consistent extension of L if and only if there is some wf B where B is not a theorem of L*.
Applying this to L itself and using the soundeness of L we see that L is consistent (as an extension of itself).

Next we showed that if L* is a consistent extension of L and A is a wf that is not a theorem of L, then the extension of L that results by adding ~A to the axioms of L* is also a consistent extension of L.

Looking at the way to show that L is adequate we considered a wf A which was a tautology and supposed that A is not a theorem of L.  Then we form a consistent extension of L by adding ~A as an axiom and proceed to build from this [ by a method we'll discuss next time] an extension of L, called L+,  which is consistent and complete with ~A as one of the axioms. Then we have a valuation v* so that v*(~A)=T  because |- L+ ~A. But since v* is a valuation, v*(A) = F which is impossible since A was assumed to be a tautology. Thus it must be that
if A is a tautology then A is a theorem of L , i.e., |-L A.

Next Time: How to build L+.

• 2/19 In this class we discuused how to build L+ as discussed in the previous lecture. We assumed that we had a statement A which was not a theorem of L and added ~A to the axioms of A as a start. then we looked through a list of the wfs of L extending L at each step to Ji+1 dependent on whether Ai was a theorem of the extension Ji at that stage. [If Ai is a theorem of Ji then Ji+1=Ji, if not then add ~Ai to the axioms of Ji to form Ji+1.] The system L+ has for axioms that are axioms for Ji for any i. We showed that L+ is a complete and consistent extension of L with ~A as an axiom. Putting this together with our previous work on valuations, there is a valuation v* of L+ for which v*(~A) = T, so that v*(A)=F. This would be a contradiction if A is a tautology. Thus we can conclude we have proven

The adequacy theorem of L: If A is a tautology in L, then A is a theorem of L.

A wf of L can be analyzed easily using the process of truth tables to determine if it is a tautology. By the adequacy theorem we can therefore determine whether an wf is a theorem of L without actually producing its proof. One need only check to see if the wf is a tautology.  In fact it is possible based on an analysis of truth in the tree of a wf to develop a proof of any tautology using a more extensive (but equivalent) system of axioms and rules for L. This process is used in the Gateway to Logic 's software which will give a proof for any tautology of L.

• 2/24  We started an examination of the basic tools needed to discuss mathematics in some logical system involving an analysis of the stucture if mathematical statements. For this purpose we analyzed the Fundamental Theorem of Arithmetic and the Fundamental Theorem of Projective Geometry. We noticed that the language will require the ability to quantify variables in some context, to investigate predicates describing qualities of variables and relations between them, as well as use functions to describe other variables. Of course we will still use the connectives of the statement logic to connect predicates and statements. We also observed that the universal quantifier (Ax) could be used to replace in meaning the existential quantifier (Ex) by seeing that (Ex) is equivalent in its use to ~(Ax)~. We will quantify only over variables representing objects on the context of some universe (usually numbers or geometric objects- points, lines, etc.) and not usually over functions or predicate relations. This is what  characterizes this language as being  first order predicate (function) logic.

• 2/26 The schedule revisions were noted at the beginning of class. We looked at some set theory  related to countable sets.

Proposition: Suppose we have a list (counting) functions from the natural numbers N to {0,1} Then there is some function B:N -> {0,1}  which will not be on the list.
[Comment: This situation could be applied to functions v:{ p1, p2 , ... } -> {T,F} which would uniquely determine valuations v* of L where v*(pk)=v(pk).]
Proof: Suppose the list is f1, f2, f3, .... Define the function B by B(0) is not equal to f1(0), B(1) is not equal to f2(1), and in general B(n) is not equal to fn+1(n). Thus B is a function from N -> {0,1} and for any k, B is not equal to f k .

The idea for this proof is due to Cantor- and is described as the Cantor diagonal argument because in defining B we are considering the diagonal of the following array:

 f1(0) f1(1) f1(2) ... f1(n) f2(0) f2(1) f2(2) ... f2(n) f3(0) f3(1) f3(2) ... f3(n) ... ... ... ... ... fn+1(0) fn+1(1) fn+1(2) ... fn+1(n)

A major consequence of this proposition is that it is not possible to count all the functions from N to {0,1}.

We can relate functions from N to {0,1}to real numbers in the interval (0,1) by f <-> f(0) 1/2 + f(1) 1/4 + f(2) 1/8 + ... and using the 1 to 1 correspondence given by the tangent function from (-pi/2 , pi/2) to all the real numbers each function can be associated with a real number.  If we associate the function f  to f(0)1/2 + f(1)1/8 + f(2)1/32 + ... then the functions correspond in a 1 to 1 fashion with a subset of the real numbers between 0 and 1. Therefore it is not possible to count this subset of the real numbers, for if we could we could count all the functions from N to {0,1}, which we have just seen is not possible.Thus it is not possible to count the real numbers in the interval (0,1) or all the real numbers.

[The discussion then wandered to some philosophical remarks on infinite sets and the formalist/finitist- intuitionist/constructivist- logicist/platonist approaches to the issues of infinite sets.]

The class then went on to discuss the material on well formed formulae in L, first order predicate logic. This involved the introduction of the concept of a term and an atomic wf, as well as free and bound variables and a term t being free for a variable xi in a wf A We started a discussion of interpretations: a domain D, with assignments related to D for all the aspects of the language L.

Next class: We'll fill in more details and examples of interpretations of wfs and begin to discuss the informal concepts of truth for first order predicate logic.

• 3/3 This class involved work in understanding the nature of an interpretation of  L.

Subsets of  a domain D can be identified with predcates of one term by noticing that if P(x) represents a predicate of one term then we can define a set SP = { a in D where P(a) is true} and conversely if we are given a subset of D, say S, the we can define a predicate PS (x) by saying that PS (x) is true if and only if x is a member of the set S. This approach of identifying the concept of a predicate with a subset of D, also works for predicates that apply to 2, 3 or more terms. For example a predicate of two terms, P(x,y), can be identified with a subset of DxD, and vice versa. Similarly predicates of 3 terms, such as P(x,y,z), can be identified with subsets of DxDxD.
An interpretation of  L involves assigning  specific elements of a non empty set D to the symbols  for constants, specific functions (of n variables) to the symbols for functions, and specific predicates (subsets) of n terms to the symbols for predicates. For example if D = { 0,1,e}  then an interpretation might associate a1  with e, a2 with 0, a with e, and a4  with 1, etc.,  f11 with the function on D defined by  0 ->0, 1 ->0, e ->1, while the function  f12 is associated with the function f(x,y) given by the table:

 \ 0 1 e 0 1 0 0 1 e e 1 e 1 0 e

So that for f(0,1)=0 while f(1,0)=e. Continuing the example the interpretation can associate with the predicate symbol A1 the subset of D consisting of {0,e}  and the predicate A1 with the subset of DxD  consisting of  {(0,1), (0,0), (e,1) , (e,e)}.

At each stage of the example we discussed the number of functions and predicates from which the interpretation could choose in associating functions and predicates with this domain.

A valuation v  for an interpretation is a function from the set of terms to the domain of the interpretation
so that v(ai) is the element of the domain assigned to ai, which we will denote a i,  and
v (fjn(t1 , t2 ,..., tn)= (f jn(v(t1 ),v(t2 ),..., v(tn)).

Thus a valuation is determined on the constant terms and all those terms involving only functions and constants, and other terms valuation is determined by the value of the valuation on the variables x1 , x 2,...
Two valuations are i-equivalent if they have the same value on all the variables except xi .
Next time: More on truth and validity using valuations.

• 3/5 This class was devoted primarily to understanding through examples how a valuation satisfies a wf. Particular attention was paid to how a valuation satisfies a wf of the form (Ax)E(x,f(x,y)) where E is interpeted in the domain as equality and f is considered as an operation on the domain given by a table.

We also discussed informally the text's proposition about valuations and substitution .
Proposition: Suppose a term t  is free for xi in a wf  of the form A(x)  in which xi appears as a free variable and valuations v and v' are i-equivalent and v(t)= v'(xi). Under these circumstances, v satisfies A(t) if and only if v' satisfies A(xi ).

After looking briefly at an informal explanation using an example of why this proposition is correct, we looked briefly at the definition of a wf A being true in an interpretation, I,  i.e., for any valuation v of I, the valuation satisfies A. A simple example was given using the formula (Ax)E(x,f(x,a)) where the interpretation uses D as the natural numbers, E is  equality, f (s,t)= s+t, and a=0, so that the wf is true in this interpretation. The notation for this is I |= A.  When A is true for any interpretation I we say that A is logically valid.

Next time: More on truth and validity.

• 3/10 We continued a discussion of truth in an interpretation and logical validity.
• 3/12
• Vacation- no classes 3/17 and 3/19
• 3/24
• 3/26 We looked at the axioms for first order logic. We proved the soundness of this system with only left to prove that the 6th axiom is logically valid. We also introduced the deduction theorem and an example to illustrate why the conditions of the theorem restrct its application.
• 3/31 We finished soundness and the deduction theorem of first order logic. We also noted that all tautologies are theorems. Next class: The Adequacy Theorem.
• 4/2 After some finishing work on soundness we started on the Adequacy theorem. We laid out the outline for the proof and did most of the ground work in Hamilton on extensions, consistency, completeness as well as the outline of the key Lemma: If S is a consistent extension of K then there is an interpretation I for which if A is a theorem of S then A is true in I.  This lemma considers extending S by allowing a new list of constants in the language, and develops the set of the interpretation as the set of terms in this extended language that involve only constants and functions. The other details of the interpretation depend on the extension of S first by a special sequence of wf's and then by extending that extension further to obtain a consistent and complete extension of S, called T. The interpretation of S uses this extension T for interpreting the formal predicates of S.

[The functions are interpeted in a simple fashion: for example f (x,y) = f(x,y) where x and y are terms in the domain of I . The key point here is that the expression on the right hand side of the equation is an element of the domain as well.]
Next class we'll look at the details of the key lemma.

• 4/7 We spent the class reviewing how the key lemma fit in the outline of the proof of adequacy and then working through most of the pieces of its proof. All that remains is the justification that the inclusion of the specific sequence of wf's Gn does not affect the consistency of the extensions. Next class we will complete this part of the proof and go on to a discussion of models (interpretations in which every theorem is true).
• 4/9 We completed the last part of the argument justifying the adequacy of the system KL.

Our discussion then opened the issues of how mathematics might become formalized within a first order logical system, by including constants, predicates (like equality), and functions with axioms for these specific objects that would provide enough for the resulting formal system to encompass the informal matheamtical subject matter. We will be considering attempts to formalize arithmetic and set theory in the remaining weeks. Both these formalizations have lead to some deeper issues in the nature of mathematics in part because the difficulties and results have turned out quite differently from the work on formalizing first order logic.

One key tool for working with formal systems related to mathematics is the use of interpretations which can be used to understand what can be proven or not proven in the system.
An interpretation for a language is called a model for a set  G of wf's of every wf in G is true in the interpretation. If the set G is the set of theorems for a formal system S then the interpretation is called a model for the system S.
We considered some immediate consequences of our previous work on the adequacy with regard to the concept of a model.
Proposition: If S is a formal system and I is an interpretation in which every axiom of S is true then I is a model for S.
Proposition: If S is a consistent system then there is an interpretation of S that is a model for S, in fact, there is a model for S that has a countable set for its domain.
Proposition: A formal system is consistent if anf only if it has a model.
Proposition: If S is a consistent system and A is a closed wf which is true in every model for S, then A is a theorem of S, i.e., |-A.

Next time: More on models and extending formal systems into mathematics.

• 4/14 We completed our first discussion of models. Besides covering the results in Hamilton we also discussed some of the uses of models in Mathematics.
• Models are used to show that a statement cannot be proven in a formal system.
• Models are used to show that a formal system is consistent. (assuming that set theory is consistent)
• Models are used to show that axioms of a formal system cannot be proven from the other axioms. (independence)

We looked particularly at examples related to geometry, a subject area where the interest in independence of axioms was of high interest in the 19th century because of the parallel postulate of Euclid's geometry. We looked at a very limited set of axioms including one version of a parallel postulate and used a 3 point -3 line (triangle) model to show these were consistent and a 4 point - 6 line (tetrahedron) model to show that a system with the negation of the parallel postulate was also consistent. This demonstrates that one cannot prove the parallel postulate from the other axioms- the independence of the parallel potulate. [ If it were provable from the other axioms, whenever one had a model satisfying the other axioms that model would also have to satisfy the parallel postulate.]

We turned our attention to axioms for mathematical formal systems. Since the concept of equality is present in practically ever mathematical system, we looked first at Hamilton's treatment of 3 axiom schemes for equality. These schemes seemed different in some way from the three properties most frquently used by mathematicians in characterizing equality as a relation, namely reflexivity, symmetry, and transitivity. We examined these properties of a relation which characterize an equivalence relation.

This discussion will continue next class as we see how equality is an equivalence relation and the relation of equivalence relations to models for formal systems with equality.

• 4/16 Equivalence relations, equivalence classes, partitions, and equality were discussed.

More informal mathematics: a discussion on equivalence relations and partitions took most of this class.
If R is an equivalence relation on a set S, we define [a]={x in S : R(x,a)}, called the equivalence class of a moduluo R. We noted that [a]=[b] if and only if R(a,b).
If P is a family of subsets of S we say P is a partition of S if

1. If A and B are distinct members of P then A intersect B is an empty set.
2. For any x in S there is a member of P, say C, with x a member of C.

Looking at these two concepts we showed the following:
Theorem: Given an equivalence relation R on a set S, the family Q={[a]: a is a member of S} is a partition of S.
Theorem: Given a partition P on a set S, the relation R' defined by R'(s,t) holds if and only if there is a member of P, call it C, with s and t both members of C.

We used the example of the set S = the integers and R(x,y) being true if and only if 10 is a factor of y-x to explore these concepts. In particular we considered the corresponding Q of equivalence classes for this relation and discussed the issues concerning defining an addition operation on this set related directly to the addition in the integers. This led to the question of whether an operation defined by the equation [a]+[b]=[a+b] would be effected by the choice of a and b as representing the classes [a] and [b]. We showed that if R(a,a') then R(a+b,a'+b) and thus if  [a]=[a'] then [a+b]=[a'+b].

We returned to formal logic to prove formally, as in Hamilton, that the predicate for equality will also have proven the corresponding wfs making it an "equivalence relation." Thus in any model for a formal system with equality the predicate used in the interpretation for equality must be an equivalence  relation. A model is called a standard model for a system with equality if the the predicate used in the interpretation for eaulity is the quality of the domain of th e interpretation. We discussed how to prove that any consistent system with equality has a standard model using equivalence classes in the new model if the the original model does not use the equality of the domain of the interpretation.

Next class: On to formal arithmetic and set theory.

• 4/21 We discussed both formal and informal arithmetic axioms. The principle of induction fir arithmetic was compared in its first order expression and in its second (set theoretic) statement which quantifies the pinciple over all sets as opposed to the first order axiom scheme which applies only to the countable number of predicates that can be expressed in the formal first order language. Axioms for addition and muliplication were compared with Peano's approach to these operations that would use only 0 and the succesor function- defining + and * recursively. Both approaches leave such propoerties as the associative, commutative, and distributive properties for later proof.

We also looked at 2 models for these axioms:

1. {0,1,2,3, ...} where this set is only the numerals in decimal notation and the rules for addition are the formal rules for arithmetic expressed in the algorithms for addition and multiplication developed and used by Stevin at the time of the popularization of decimal arithmetic.
2. Let E denote the empty set. Then the model's domain is the set {E, {E}. {E,{E}}, {E, {E}, {E,{E}}....}. The successor function of an element is the set consisting of that element and all its predecessors. If we let E=0, ... then 1={0}, 1' = 2 = {0,1}, 2'=3={0,1,2},... From this addition and multiplication can be defined recursively to satisfy (by definition) the axioms.

We discussed the issues of relative consistency in showing that arithmetic was consistent by the apparent existence of these models using set theory. This leads to a desire to show set theory  is consistent in some formalization.

• 4/23 We started with a review of some aspects of informal set theory, especially the higherarchical use of terms such as element, set, class or family, ... universe. More on this ... I'll leave more on this for later. Well defined sets, the power set of a set, Russell's paradox, formalization with first order axioms.. discussed through to the axiom of unions. More on unions next class as we (hopefully) complete a first discussion of first order axioms for set theory.
• 4/28
• 4/30
• 5/5
More on set theory:
Comment on the Continuum Hypothesis and functions:

Recall last time we discussed the concepts of cardinal equivalence of sets and cardinal numbers. In particular the axiom of infinite sets and the power set meant that there was a set that was not countable. (The power set of the natural numbers).

We looked at some sets that are cardinal equivalent to the set of real numbers. First we looked at (0,1) [ This used the tangent function and the linear function s(x)=pi x + pi/2 ] and then we looked at the power set of the natural numbers. In studying this set we used the characteristic function of a subset of a set and geometric series using 1/2  and 1/3 to show there are 1:1 functions from P(N) to (0,1) and from (0,1) to P(N). This led to recognizing that this was a place to apply the Cantor- Schroeder-Bernstein Theorem.

We had previously discussed sets A and B being related by the existence of a function f:A -> B which is 1:1.
This relation is denoted A<B
. The relation  < is reflexive and transitive, but not symmetric. It is anti-symmetric in the sense of the following theorem of Cantor-Schroeder-Bernstein:

Theorem: If A<B and B<A then A is cardinal equivalent to B.

Outline of Proof:
From B<A we can assume B is a subset of A and we have a 1:1 function f :A->B .
Let A1=f(A) and B1=f(B) so A contains B which contains A1 which contains B1, and we can continue in this fashion to obtain A2=f(A1), A3=f(A2), .. and B2=f(B1), B3=f(B2),... with all of the A's cardinal equivalent to each other and all the B's cardinal equivalent to each other.
Let C= {x: x is in all the A's and all the B's}.
Define g : A to B by g(x)=f(x) if x is in A-B or Ak-Bk for any k,
and g(x)=x   if x is in Bk-Ak or in C.
Then g is 1:1 and onto.

Besides being applicable to show the cardinal equivalence of the set of real numbers with the power set of the integers, the CSB theorem gives an alternative characterization of the continuuum hypothesis:
CH 1: If A is  a subset of the real numbers then either (i) A is finite, (ii) A is countably infinite, or (iii) A is cardinality equivalent to the real numbers.

CH 2: If A is a subset of the real numbers then either there is a function g:N -> A  which is onto or there is a function g: A -> R which is onto.

The discussion ended on a brief introduction to the concept of ordinal numbers and well ordered set.
Ordinal numbers:
Some Definitions:
A partial order on a set is ...
A partially ordered set is..

A,<  is similar to B,< if...
Fact: similarity is an equivalence relation.

A total order on a set is ...
A totally ordered set is ...

The family of sets that are similar to A,<, a totally ordered set is called the order type of A.

A first element... a last element
A maximal element... a minimal element...
An upper bound for a subset...

A,< is a well ordered set if ever nonempty subset of A has a first element.

Theorem: Every well ordered set is totally ordered.

s(a)={x: x strictly preceeds a}.

The principle of transfinite induction: If S  is a subset of a well ordered set A and
i) the first element of A is in S and ii) whenever s(a) is in S then a is in S,
then S=A.

An element of a WO set is a limit element if ....

Suppose that N is the family of sets that are similar to a well ordered set, A. Then N is called an ordinal number.

The Axiom of Choice... Zorn's Lemma ... The Well Ordering Theorem

The WO theorem: Every set can be well ordered.
Zorn's Lemma: Suppose X is an ordered set in which every totally ordered subset has an upper bound, then X contains at least one maximal element.

The Continuum Hypothesis again.