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! |
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:
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^{n} 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^{4} = 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
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.
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_{1}, p_{2}, p_{3}, 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 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_{1},
p_{2} , ... } -> {T,F} which would uniquely determine valuations
v* of L where v*(p_{k})=v(p_{k}).]
Proof: Suppose the list is f_{1}, f_{2},
f_{3}, .... Define the function B by B(0) is not equal to
f_{1}(0), B(1) is not equal to f_{2}(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:
f_{1}(0) | f_{1}(1) | f_{1}(2) | ... | f_{1}(n) |
f_{2}(0) | f_{2}(1) | f_{2}(2) | ... | f_{2}(n) |
f_{3}(0) | f_{3}(1) | f_{3}(2) | ... | f_{3}(n) |
... | ... | ... | ... | ... |
f_{n+1}(0) | f_{n+1}(1) | f_{n+1}(2) | ... | f_{n+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 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_{1} with e, a_{2} with 0,
a_{3 } with e, and a_{4} with 1,
etc., f_{1}^{1} with the function on D defined
by 0 ->0, 1 ->0, e ->1, while the function
f_{1}^{2} 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 A_{1}^{1 } the subset of D consisting of {0,e} and the predicate A_{1}^{2 } 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}^{n}(t_{1 }, t_{2
},..., t_{n})=
(f_{ j}^{n}(v(t_{1
}),v(t_{2 }),..., 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_{1 },
x_{ 2},...
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.
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
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:
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.