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.

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 2ⁿ 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 2⁴ = 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?

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., f_A = f_B.

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.

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 -> R,  R -> RxR,  and RxR ->R.
Next class: Arguments, Validity, and Modus Ponens.
[Perhaps we'll start some work on a formal structure for statement logic.]

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

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:

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.

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.

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, p₁, p₂, p₃, 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 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 G  |-_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 G  |-_L  (A->B).

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.

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+.

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.

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:{ p₁, p₂ , ... } -> {T,F} which would uniquely determine valuations v* of L where v*(p_k)=v(p_k).]
Proof: Suppose the list is f₁, f₂, f₃, .... Define the function B by B(0) is not equal to f₁(0), B(1) is not equal to f₂(1), and in general B(n) is not equal to f_n+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:

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 x_i 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.

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 S_{P =} { 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 P_S (x) by saying that P_S (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 a₁  with e, a₂ with 0, a₃  with e, and a₄  with 1, etc.,  f₁¹ with the function on D defined by  0 ->0, 1 ->0, e ->1, while the function  f₁² is associated with the function f(x,y) given by the table:

So that for f(0,1)=0 while f(1,0)=e. Continuing the example the interpretation can associate with the predicate symbol A₁¹  the subset of D consisting of {0,e}  and the predicate A₁²  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(a_i) is the element of the domain assigned to a_i, which we will denote a _i,  and
v (f_jⁿ(t₁ , t₂ ,..., t_n)= (f _jⁿ(v(t₁ ),v(t₂ ),..., v(t_n)).

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 x₁ , x ₂,...
Two valuations are i-equivalent if they have the same value on all the variables except x_i .
Next time: More on truth and validity using valuations.

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

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.

[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.

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.

• 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.

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.

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.