Projects

Each week, you have a project to do by the following Tuesday. Each week's project is really a choice of several options; you can do any one of them.

Some options involve Programming; these may or may not require you to write actual code, but they will all require some programming familiarity or knowledge. You'll never have to do a programming project in any given week. Some projects involve Proofs; I will ask you to write a rigorous mathematical proof for these. In the later weeks, you will have to do some proofs! Other project options involve neither programming nor proofs.

Please write these up as coherent essays with full sentences. The only exception is examples of programming code or any diagrams that you might use to illustrate your text. Typing your text would be a very good idea. If I can't read your project, either because it's illegible or because the writing makes no sense, then that will be very bad for your grade! I'm not going to take off points for bad grammar, but I do need to be able to understand it.

Many of the projects are given as a list of questions. These are simply suggestions for the kinds of ideas that you may want to write about. You don't have to answer all of the questions, and you don't have to limit yourself to just these questions. But please don't just write your paper as a list of questions and answers. Instead, write it as an essay whose statements explain what you think. You might not write down a single question mark! Organise your writing however seems clearest to you.

You may have to do outside research for your project! The kinds of things that I'm asking about can generally be found on the Internet by a simple web search. You can also look at the resources on the bottom of the main page. But don't hesitate to look in the library at real dead-tree paper if you find a reference that you think will be helpful.

Proof project

This project is due August 27.

This project is different from all of the other ones. In this project, you must choose four of the following theorems, and write a careful and complete proof of each of them. A careful and complete proof has these characteristics:

Simply writing down several equations in succession is not enough; you must explain exactly what you're doing.

Some of these theorems are similar to past homework problems. But even if you got a full score on the homework problem, the same work might not get a full score in this project. This is because the project requires a careful and complete proof. It will be graded more strictly!

If you use a fact in your proof that you don't prove yourself, then be sure to reference where you got that fact (class lecture, one of the textbooks, outside reading, etc). Similarly, if you use an argument that you didn't come up with yourself, then cite where you got the idea from -- but be sure to write it up in your own words!

If you prove more than four of the following theorems, then your grade will be based on the best four.

Proof 1

Prove that, if A, B, and C are sets, then |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |C ∩ A| + |A ∩ B ∩ C|.

Proof 2

Prove that the function f from N × N to N given by f(m,n) = C(m + n + 1, 2) + m is invertible. (Remember that in this class, N is the set of nonnegative integers, including 0.)

Proof 3

Prove that the square of an odd natural number is also odd.

Proof 4

Prove that the sum of the first n natural numbers is C(n, 2). (Remember that in this class, 0 counts as a natural number.)

Proof 5

Suppose that n is a natural number and h is a positive real number. Prove that 1 + nh ≤ (1 + h)n.

Proof 6

Suppose that i, j, and k are integers, and define a := ½(i + j), b := ½(i + k), and c := ½(j + k). Prove that at least one of a, b, and c is an integer.

Proof 7

Suppose that n is a natural number and a, b, c, and d are all integers. Prove that if n divides both a − b and c − d, then n also divides ac − bd.

Proof 8

Let A be a set with m elements, and let B be a set with n elements. Prove that there are exactly (2n)m binary relations in A × B.

Project on counting

This project was due August 20.

Programming: Permutations

Write a program in your favourite programming language to generate all the permutations of a finite collection of distinct symbols, print them and count them. As an example, print and count the permutations of the letters "W", "O", "R", and "D". Recursion will probably produce the simplest algorithm. If so, then what is the base case? How do you reduce the permutations of n symbols to permutations of n − 1 symbols? You know the number of permutations of n symbols; does your program agree with you on how many permutations there are? Can you prove that your algorithm is correct using induction? You might also consider:

Programming: Partitions

A partition of a natural number N is a decomposition N = n1 + n2 + ··· + nk into a finite sum where each addend ni is a positive integer. For an ordered partition, we're keeping track of the order of the addends ni. An ordered partition can be represented by the list (n1, ..., nk) where n1 + n2 + ··· + nk = N. (Can you explain why this representation is correct?) Write a program in the language of your choice to generate, print and count all ordered partitions of a number N. As an example, list the ordered partitions of the number 4. You might also consider:

Counting infinite sets

Remember that our counting principles can be thought of as counting the sizes of various sets. The theory of cardinal numbers takes into the realm of (possibly) infinite sets and infinite numbers. Research and write about the theory of cardinality, which was developed by Georg Cantor towards the end of the 19th century. What's the difference between a cardinal number and an ordinal number, both in ordinary language and in the mathematics of infinite sets? How does studying cardinal numbers lead to greater insights into what sets themselves are? How can you generalise the various combinatorial operations on numbers -- not only addition and multiplication but also factorials and multinomial coefficients -- to operations on infinite cardinal numbers? Which theorems remain true and which fail, or do some of them even stop having any meaning?

Statistics and physics

Compare and contrast the following: Although these buzzwords appear directly in physics, they also have to do more generally with the arrangement of information. The concept of "entropy" links physics to information; what does that have to do with counting?

Project on reasoning and recursion

This project was due August 12.

Programming: Fibonacci algorithms

Write two programs to calculate Fibonacci numbers, one of which is iterative and one of which is recursive. Measure how many computer resources you use in these programs. (On Unix, you might use the system call time to measure one aspect of this.) Prepare a table indicating how many resources you use to calculate Fn, where n starts at 0 and continues as high as you can go. What does this tell you about the practical consequences of using recursive versus iterative algorithms?

Programming: Exponents

Write a recursive algorithm to calculate xn, where x and n are both natural numbers (unsigned integers). The only arithmetic operations that you should use in your algorithm are addition and multiplication, and numerical constants like 0 and 1. Then use a binary shift operation (based on the binary expansion of n) to speed up your program by applying recursion less often.

Achilles and the Tortoise

The logician Charles Lutwidge Dodgson wrote several items on logic for a popular audience, which he published under his pen name Lewis Carroll. (This is the same name that he used for Alice in Wonderland.) Find a copy of his short dialogue What the Tortoise Said to Achilles. What does this dialogue tell us about logic? What does it have to do with the difference between a conditional statement and an implication? How about the difference between axioms and rules of inference? How about the difference between the object language and the metalanguage? If you had been Achilles, could you have said anything different to shut the Tortoise up?

Nonstandard logic

This class uses classical logic. Research a different kind of logic, such as intuitionistsic logic, Brazilian logic, or fuzzy logic. What are the differences? What sorts of logical equivalence hold in one kind of logic but not in another? What sorts of rules of inference are valid in one kind of logic but not in another? Even if you accept that classical logic is correct for ordinary reasoning, can you think of any time that a nonstandard logic would still be useful?

Project on sets and functions

This project was due August 5.

Programming: Set data types in PASCAL

The computer language PASCAL has a data type operator set of for sets. What kinds of sets can these data types handle? Can you have sets of sets? Why are there several set datatypes instead of a single one for all sets? What kind of operations can PASCAL perform on sets? How could you perform other operations on sets using the ones that are built in? (You might write code for functions that perform these operations, or you could describe in words what steps such a function would have to do.) How does a computer running a PASCAL program organise the value of a set variable in memory? What does this have to do with the way in which the set {T,F} of truth values classifies subsets?

Programming: Your own set data type

Design a structure or class in a language like C, C++, or Java that implements sets. Do you have to place restrictions on what the elements of the set can be? This structure or class should support functions that test whether two sets are equal or subsets or whether something is an element of a set, that form the union, intersection, and difference of two sets, and that construct a subset of a given set S as the set of elements of S that satisfy some boolean property. You don't have to write the code for the functions above, but do write the code for the structure or class itself, and convince yourself that these functions could be written. (You might look at the previous option for inspiration.)

Paradoxes

Consider logical paradoxes like Russel's paradox, the liar paradox of Epimenedes the Cretan, or the barber paradox. Do these paradoxes mean that logic itself is inconsistent? In your opinion, what's the best way to resolve these? You may want to focus on just one paradox, but please write some commentary about your own opinion. Also be sure to explain why anybody would think that the paradox is a problem in the first place, especially if your opinion is that it's not a problem.

Functions

Research the history of the concept of function in mathematics. How did the concept change over time? What sorts of things came to be considered functions that weren't though of that way before? When and how did the modern definition first appear? What is the relationship between functions in mathematics and functions in computer programming languages?
Go back to the MATH 112 homepage.
This web page was written in 2003 by Toby Bartels. Toby reserves no legal rights to it.

The permanent URI of this web page is http://tobybartels.name/MATH112/2003/projects/.

HTML 5