Fall 2011 Teaching

Honors Calculus II

Due

Assignment

Date

none assigned yet.

Spring 2011 Teaching

Topics in Logic: Computability Theory.

Class times	MWF 2:00-2:50
Class location	ECCR 1B08

We will be studying the basics of computability theory with an aim to finish with some nice priority arguments. We will use a draft of the new book by Robert Soare; this will be distributed during the first week of classes. Homework will not be collected (but, as with all math, to get the most out of this class you should work many problems).

Note: all of the below videos will be password protected until the book has appeared.

Lecture 1	http://vimeo.com/18648000
	We introduce Turing Machines.
Lecture 2	http://vimeo.com/18749414
	We answer the question how a Turing Machine that works on tapes can compute anything we might care about. (some common conventions and coding ideas are discussed) We also introduce the Church-Turing thesis. We then end with Oracle machines.
Lecture 3	http://vimeo.com/18921438
	We briefly discuss the lambda-calculus, then define Turing degrees and make some elementary observations.
Lecture 4	http://vimeo.com/18997308
	We talk about a Universal Turing Machine, the S^m_n theorem, and then we show the unsolvability of the halting problem.
Lecture 5	http://vimeo.com/19139862
	We did a 1-1 reduction of the halting problem to the set of indices for total functions, followed by some equivalences on definitions for c.e. sets and basic properties.
Lecture 6	http://vimeo.com/19231657
	We proved and discussed some consequences of the recursion theorem.
Lecture 7	http://vimeo.com/19253574
	We discussed an index theorem for finite sets, and started discussion of productive and creative sets.
Lecture 8	http://vimeo.com/19488416
	Properties of creative and productive sets, and start of discussing the Friedberg splitting theorem.
Lecture 9	http://vimeo.com/19672795
	We discuss the proof of the Friedberg Splitting Theorem and some basic notions around oracle machine.
Lecture 10	http://vimeo.com/19944933
	Basic facts on oracle machines and the jump.
Lecture 11	http://vimeo.com/19982769
	Characterising sets below 0'.
Lecture 12	http://vimeo.com/20025868
	Modulus Lemma and beginning topology.
Lecture 13	http://vimeo.com/20065077
	We proved compactness of Cantor space and beginning effective topology (effective open/closed sets).
Lecture 14	http://vimeo.com/20476583
	We talk about the effective compactness theorem and the low basis theorem.
Lecture 15	http://vimeo.com/20484770
	We discuss the arithmetical hierarchy, how to prove something occurs at a certain level, and Posts theorem. We finish by showing Cof is Sigma_3 complete by a movable marker construction.
Lecture 16	http://vimeo.com/20572331
	We finish the movable marker construction we started during the last lecture, then do the high domination theorem.
Lecture 17	http://vimeo.com/20578933
	We discuss (effectively) simple sets (definition and existence)
Lecture 18	http://vimeo.com/20610464
	We talked about permitting, and then hyper(hyper) simple sets.
Lecture 19	http://vimeo.com/20610542
	We talked more about hypersimple sets, that effectively simple sets are complete, and finished with Arslanovs Completeness Criterion.
Lecture 20	http://vimeo.com/20843584
	We discussed two constructions using oracles and extending initial segments, first an incomparable pair below 0', then a minimal pair of degrees.
Lecture 21	http://vimeo.com/20843672
	We proved the jump is onto the cone above 0', and the existence of exact pairs for strictly ascending sequences of degrees.
Lecture 22	http://vimeo.com/20885014
	We started working on proving the existence of a minimal degree below 0''.
Lecture 23	http://vimeo.com/21031131
	We finished the proof of the existence of a minimal degree.
Lecture 24	http://vimeo.com/21073023
	We did the first finite injury proof, showing the existence of a low simple set.
Lecture 25	http://vimeo.com/21160594
	We proved the existence of incomparable c.e.sets, discussed a little what this would look like on a tree, and started the proof that we can construct a simple set outside of the upper cone determined by any noncomputable c.e.set.

Fall 2010 Teaching

Abstract Algebra 1 (MATH 3140-002)

Office hours	M 11:00-11:50, W 2:00-2:50, F 1:00-1:50
Class times	MWF 12:00-12:50
Class location	DUAN G1B39
Book	A First Course in Abstract Algebra; John B. Fraleigh (seventh edition)

First day handout
Office hour suggestions

Lectures

Date

Monday, August 23 2010

Introduction.

Sets and relations.

Wednesday, August 25 2010

Functions, equivalence relations, and partitions.

Friday, August 27 2010

Binary operations, examples, properties.

Monday, August 30 2010

Isomorphism of binary structures.

Wednesday, September 1 2010

Some examples.

Homeworks

Due

Assignment

Friday, September 3

Exercises 0: 1 (no explanation needed), 12, 15, 18, 29

Exercises 1: 16, 31

Exercises 2: 2, 3, 5, 7, 24 (no explanation needed)

Friday, September 10

Exercises 0: 31, 36

Exercises 2: 4, 27, 28

Exercises 3: 3, 4, 5, 11, 29

Exercises 4: 1, 6

Friday, September 17

Exercises 0: 32

Exercises 2: 8, 17

Exercises 3: 8, 11

Exercises 4: 23, 25

Exercises 5: 4, 15, 19, 42

Friday, September 24

Exercises 6: 32, 34, 48

Exercises 7: 15, 17

Exercises 8: 3, 8, 12, 35, 36

Friday, October 1

These problems are only suggested, they will not be collected

Likely some will appear on later problem sets though

Exercises 0: 19

Exercises 5: 43, 51, 52

Exercises 6: 49, 55

Exercises 8: 49, 52

Friday, October 8

Exercises 5: 43, 51

Exercises 8: 16, 30, 31, 46

Exercises 9: 13, 23, 33

Exercises 10: 31, 32, 34

Friday, October 15

Exercises 9: 31, 32, 34

Exercises 10: 1, 13, 41

Exercises 11: 11, 14, 32, 34

Friday, October 22

Exercises 11: 46, 54

Exercises 13: 44, 45

Exercises 14: 23, 27, 31

Exercises 15: 5, 6, 8, 21

Friday, October 29

These problems are only suggested, they will not be collected.

Exercises 13: 47, 53, 54

Exercises 14: 26, 34

Exercises 15: 40, 41

Exercises 16: 8, 11, 14

Friday, November 5

Exercises 13: 49, 55

Exercises 15: 40, 41

Exercises 16: 6, 9, 14

Friday, November 12

Exercises 15: 34, 35, 36

Exercises 16: 16

Exercises 17: 1, 2

Exercises 18: 11, 17, 19

Friday, November 19

Exercises 18: 38, 43, 46, 49

Exercises 19: 3, 9, 14, 17, 27

Friday, December 3

Exercises 19: 23

Exercises 21: 4, 9, 11

Exercises 22: 1, 5

Subjects for Basic Notions Quiz Monday December 6

A is a subset of B.
relation between sets A and B.
Cartesian product of A and B.
one-to-one.
onto.
bijection.
X has the same cardinality as Y.
Equivalence relation.
Equivalence class.
Partition.
The partition associated to an equivalence relation.
The equivalence relation associated to a partition.
Binary operation.
H is closed under a binary operation * .
(S,*) is associative, commutative, has an identity element, has inverses.
(S,*) is a group.
(S,*) is an Abelian group.
(S,*) and (S',*') are isomorphic.
H is a subgroup of (G,*) .
(G,*) is a cyclic group.
g an element of G generates the group (G,*) .
relatively prime.
greatest common divisor.
If G is a group, g_i in G , all i in I : definition of subgroup generated by {g_i | i in I} .
finitely generated group G .
permutation group on n letters.
cycle.
orbit of an element in a permutation group.
disjoint cycles.
left regular representation.
right regular representation.
left and right coset of H in G .
index of H in G .
direct product of the groups G₀, ..., G_n .
decomposable group.
image and inverse image under a map.
homomorphism, automorphism, inner automorphism.
kernel of a homomorphism.
x conjugated by g .
normal subgroup.
factor group.
automorphism.
inner automorphism.
simple group.
G -set
orbit of x in a G -set.
transitive G -set.
faithful G -set.
isotropy (stabilizer) subgroup in a G -set.
ring.
field.
integral domain.
zero divisor.
cancellation laws.
commutative ring.
ring homomorphism.
the ring of polynomials over a given ring R .
polynomial irreducible over a field F .

pdf file is also available.

Foundations of Mathematics (MATH 5000)

Office hours	M 11:00-11:50, W 2:00-2:50, F 1:00-1:50
Class times	MWF 8:00 - 8:50
Class location	ECCR 139
Book	Introduction to Model Theory; Phillipp Rothmaler

Lectures

Date

Monday, August 23 2010

Finding a better time for this class.

Wednesday, August 25 2010

Introduction

Definition of structures and homomorphisms.

Friday, August 27 2010

Discussion of structures, and definition of the language.

Monday, August 30 2010

Satisfaction and related definitions.

Wednesday, September 1 2010

Some uses of satisfaction

Friday, September 3 2010

Theories and some of their properties.

Wednesday, September 8 2010

Complete theories and some of their properties.

Friday, September 10 2010

Start with compactness theorem (filters and ultrafilters).

Monday, September 13 2010

Homeworks

Due

Assignment

Wednesday September 8

1.2.1, 1.3.1, 1.3.3, 1.6.1, 2.2.1, 2.3.2, 3.1.5, 3.3.1

Monday, September 20

3.5.1, 3.5.2, 4.2.3, 4.2.5, 4.3.2, 4.3.3, 4.3.4

Monday, October 4

2.2.2, 4.1.2, 4.1.3, 5.1.1, 5.7.2, 5.7.3, 6.2.1, 6.2.6

Wednesday, October 20

4.1.4 (isomorphic to N itself), 4.2.4, 4.3.1, 6.3.4, 7.2.1,

7.4.1

Friday, October 29

5.2.1, 5.2.2, 6.1.5, 7.4.2, 7.5.2, 7.6.2

Friday, November 12

7.3.2, 7.5.3, 7.6.3, 8.1.1, 8.2.2,

Friday, December 3

8.3.1, 8.3.6, 8.4.1, 9.2.3, 9.2.4

Spring 2010 Teaching

Math 4730: Set Theory

The first exam has been moved to Friday February 26.

Office hours	M 8:00-8:50, W 12:00-12:50, F 10:00-10:50
Class times	MWF 9:00-9:50
Class location	ECCR 118
Book	Notes handed out in class

First day handout

Lectures

Date
Monday January 11	Introduction. Basic ideas about logic: truth tables and standard arguments (section introduction)
Wednesday January 13	The first axioms: meaning and some use. (section 1) the key idea about axioms is that they don't describe what a set is, but what a universe of sets is.
Friday January 15	Axioms, defined properties, and how to write a proof (section 1) the key idea in writing a proof is often using the standard methods to get down to the hart of the matter, and then reasoning very carefully.
Monday January 18	No class: MLK day.
Wednesday January 20	Ordered pairs and relations (section 2) The key point was the idea that notions that a priori are not about sets, can be "implemented" in sets. They should then have the main properties of the original notions, but will often also "accidentally" have more properties.
Friday January 22	Functions (section 3, a small start) We discussed the reason for developing the axioms the way we are, not too strong, not too weak. We also discussed what the axioms are describing.
Monday January 25	Functions (section 3) Worked some of the theorems in the section emphasizing the role of definitions, that they are not randomly chosen, but need to fit our intuitions. Side effects are to be expected though.
Wednesday January 27	Functions (section 3) The axiom of choice was introduced and explained.
Friday January 29	replacement procedure (section 3) Equivalence relations and partitions (section 4)
Monday February 1	Finishing equivalence relations (section 4) Pictures of relations: easy way of obtaining examples. Definition and (non-)examples of wellorders (section 5)
Wednesday February 3	Induction: for any well order (section 5) and on N defining N (section 6)
Friday February 5	Properties of N (section 6): Induction and some basic properties of our implementation.
Monday February 8	Doing inductive proofs The Recursion Theorem
Wednesday February 10	Proof of the recursion theorem
Friday February 12	Defining addition. Properties of addition.
Mon Feb 15-Feb19	Essentially finish Chapter 6
Monday February 22	On the proof of the closure theorem.
Wednesday February 24	On proving existence choice functions from AC.
Friday February 26	First midterm
Monday March 1	The ideas surrounding ordinals and cardinals.
Wednesday March 2	Discussed the exercise on the recursion theorem in great detail.
Friday March 5	Definition cardinals and some properties (Chapter 7)
Monday March 8	Properties of cardinals (Chapter 7)
Wednesday March 10	Union of countably many countable sets. There are uncountably many reals.
Friday March 12	Characteristic functions (Chapter 7) Order isomorphisms (Chapter 8)
Monday March 16	Key theorem on ordinals (Chapter 8)
Wednesday March 18	Cardinal arithmetic (Chapter 8)
Friday March 20	No lecture.
Monday March 29	Discussed some homework problems.
Wednesday March 31	Second Midterm Exam
Friday April 2	Basics of Cardinal Arithmetic (Chapter 8): reason, definitions, robustness.
Monday April 5	Cardinal arithmetic identities: strategies for defining injections or bijections.
Wednesday April 7	More about some injections from Monday. Working towards K x K = K for inf cardinals: Decided strategy, and defined and drew the picture of the wellorder.
Friday April 9	Discussed homework problem about eventually constant functions. Finished K x K = K for inf cardinals. Started the thinking about computing the cardinalities for closures.
Monday April 12	How to "compute" the cardinality of the closure of a set under partial functions.
Wednesday April 14	Collections that do not form classes. Induction on well-orders.
Friday April 16	Induction and recursion for ordinals/any well-order.
Monday April 19	Questions Recursion for ordinals.
Wednesday April 21	Questions Recursion on the class of ordinals, what is different? If time: useful picture of the universe.

Homeworks

Due

Assignment

Friday January 22

Chapter 1: 1, 2, 5, 6, 7, 11

Friday January 29

Chapter 1: 13

Chapter 2: 1, 2, 6, 7

Chapter 3: 1

Friday February 5

Chapter 1: 12

Chapter 2: 14

Chapter 3: 6, 15, 16, 21

Friday February 12

Chapter 3: 22, 26

Chapter 4: 1, 2

Chapter 5: 1

Friday February 19

Chapter 4: 4, 8

Chapter 5: 2, 6

Chapter 6: 2 (only do (i), (ii), and (v))

Friday March 5

Chapter 5: 5, 8

Chapter 6: 7, 13, 19

Friday March 12

Chapter 3: 24

Chapter 4: 7

Chapter 6: 12, 14, 21, 23

Friday April 2

Chapter 7: 1, 2, 3, 7, 13, 20

Friday April 9

Chapter 7: 16, 21

Chapter 8: 1, 4, 11

Friday April 16

Chapter 7: 6, 15

Chapter 8: 12, 13

Friday April 23:

Chapter 8: 21, 22

Chapter 9: 16, 19

Subjects for Basic Notions Quiz April 19

Truth tables for basic connectives (and/or/if X, then Y/not/iff).
Form of argument by contradiction.
Form of argument by contrapositive.
Form of standard argument to prove there exists x. P(x) .
Form of standard argument to prove for all x. P(x) .
Form of standard argument to prove A => B .
The axioms (up to and including the 8th).
Definition of union of sets (pairs and families).
Definition of intersection of sets (pairs and families).
Definition of {x in A | P(x)} .
Definition of {a,b} .
Definition of {a} .
Definition of the empty set .
Definition of disjoint.
Standard argument for use of disjunction.
Standard argument for equality of sets.
Definition of (a,b) , and its key property.
Definition of Domain.
Definition of Range.
Definition of (binary) relation.
Definition of inverse relation.
Definition of image of a set under a relation.
Definition of function.
Definition of surjection (onto function).
Definition of injection (one-to-one function).
Definition of cartesian product of a system of sets.
Definition of equivalence relation.
Definition of partition.
Definitions of the different properties of orders.
Definition of the principle of complete induction.
Definition of the natural numbers .
Definition of addition, mutiplication, and exponentiation of
Definition of equipotent.
Definition of finite.
Definition of F -closed set.
Definition of {Cl}_F(X) .
Definition of ordinal and cardinal.
The second form of the axiom of choice.
Definition of denumerable and countable.
Definition of order-isomorphism.
Definition of class function.
Definition of cardinal addition, multiplication, and
Definition of the sum of an indexed family of cardinals.

pdf file is also available.