Archive for the ‘IA Numbers and Sets’ Category

A look at a few Tripos questions IX

May 26, 2012

Exam day approaches, so I’ve decided to prioritize. Instead of doing question 7C, which isn’t all that interesting (in the sense that it doesn’t give me much scope to emphasize principles of more general use in exams), I’m going to skip it, and instead, if I get time, go through a groups question or two. But first I will do the final Numbers and Sets question because it involves something a lot of people dislike: the inclusion-exclusion principle. It’s worth getting comfortable with this, because it comes up year after year (either in Numbers and Sets or in Probability). You may think that applying the principle requires some ingenuity. The aim of this post is to convince you that it can be done on autopilot.

8C. Let X be a finite set with n elements. How many functions are there from X to X? How many relations are there on X?

Show that the number of relations R on X such that, for each y\in X, there exists at least one x\in X with xRy, is (2^n-1)^n.

Using the inclusion-exclusion principle or otherwise, deduce that the number of such relations R for which, in addition, for each x\in X, there exists at least one y\in X with xRy, is

\displaystyle \sum_{k=0}^n(-1)^k\binom nk(2^{n-k}-1)^n.
(more…)

Advertisements

Posted in Cambridge teaching, IA Numbers and Sets | 3 Comments »

A look at a few Tripos questions VIII

May 24, 2012

Now for a question on modular arithmetic. As with countability, there is a very high chance of a question on this topic. [Added after the post was written: as usual I wrote down my thoughts about this question as I had them, and I didn’t spot the best approach to part (ii) of the question until after I had come up with some less good approaches. So my recommendations evolve through the post, with some of the later ones superseding some of the earlier ones.]

6C. (i) Prove Wilson’s theorem: if p is prime then (p-1)!\equiv -1 (mod p).

Deduce that if p\equiv 1 (mod 4) then

\displaystyle \Bigl(\bigl(\frac{p-1}2\bigr)!\Bigr)^2\equiv -1 (mod p).

(ii) Suppose that p is a prime of the form 4k+3. Show that if x^4\equiv 1 (mod p) then x^2\equiv 1 (mod p).

(iii) Deduce that if p is an odd prime, then the congruence

\displaystyle x^2\equiv -1 (mod p)

has exactly two solutions (modulo p) if p\equiv 1 (mod 4), and none otherwise.
(more…)

Posted in Cambridge teaching, IA Numbers and Sets | 4 Comments »

A look at a few Tripos questions VII

May 20, 2012

The obligatory question on countability/uncountability.

5C. Define what is meant by the term countable. Show directly from your definition that if X is countable, then so is any subset of X.

Show that \mathbb{N}\times\mathbb{N} is countable. Hence or otherwise, show that a countable union of countable sets is countable. Show also that for any n\geq 1, \mathbb{N}^n is countable.

A function f:\mathbb{Z}\to\mathbb{N} is periodic if there exists a positive integer m such that, for every x\in\mathbb{Z}, f(x+m)=f(x). Show that the set of periodic functions f:\mathbb{Z}\to\mathbb{N} is countable.
(more…)

Posted in Cambridge teaching, IA Numbers and Sets | 12 Comments »

A look at a few Tripos questions VI

May 11, 2012

I’m now going to turn to the Numbers and Sets questions from the same year, 2003. I’ve lost count of the number of times I’ve heard people say that the course is quite easy but the questions on the examples sheets and exams are very hard and “not very closely related to the course”. There is a grain of truth in that: the new concepts you have to grasp in Numbers and Sets are not as difficult as the new concepts you have to grasp in most of the other courses, so in order to give enough substance to Tripos questions the examiners are almost forced to put in a significant problem-solving element. However, certain styles of problem occur quite regularly, so it’s good to get a bit of practice. And perhaps a detailed discussion of the 2003 questions will be helpful as well. As I did with Analysis I, I’ll start with a post on the Section I questions and then I’ll have separate posts for each of the four Section II questions. The paper, by the way, is Paper 4.
(more…)

Posted in Cambridge teaching, IA Numbers and Sets | 12 Comments »

A short post on countability and uncountability

November 28, 2011

There is plenty I could write about countability and uncountability, but much of what I have to say I have said already in written form, and I don’t see much reason to rewrite it. So here’s a link to two articles on the Tricki, which, if you don’t know, is a wiki for mathematical techniques. The Tricki hasn’t taken off, and probably never will, but it’s still got some useful material on it that you might enjoy looking at. The articles in question are one about how to tell almost instantly whether a set is countable and another about how to find neat proofs that sets are countable when they are.
(more…)

Posted in Cambridge teaching, IA Numbers and Sets | 13 Comments »

Proving the fundamental theorem of arithmetic

November 18, 2011

How much of the standard proof of the fundamental theorem of arithmetic follows from general tricks that can be applied all over the place and how much do you actually have to remember? At first it may seem as though you have to remember quite a bit: there is a non-obvious sequence of lemmas, starting with Bézout’s theorem, continuing with the clever proof that if p|ab then either p|a or p|b, bumping that up to a proof for bigger products, and eventually deducing the theorem itself.

But what if one were simply asked to come up with a proof? Would there be any chance of discovering that sequence of lemmas? I maintain that there would — if, that is, you are aware of certain general tricks.
(more…)

Posted in Cambridge teaching, IA Numbers and Sets | 29 Comments »

Why isn’t the fundamental theorem of arithmetic obvious?

November 13, 2011

The fundamental theorem of arithmetic states that every positive integer can be factorized in one way as a product of prime numbers. This statement has to be appropriately interpreted: we count the factorizations 3\times 5\times 13 and 13\times 3\times 5 as the same, for instance. Note that it is essential not to count 1 as a prime, or else we could stick a product of 1s on to the end of any factorization to get a different one: 3\times 5\times 13=3\times 5\times 13\times 1\times 1\times 1. But doesn’t that mean that 1 itself cannot be written as a product of primes? No — we define the “empty product” (what you get when you take a bunch of … no numbers at all and multiply them together) to be 1. That is a sensible convention because we would like multiplying a product of numbers by the empty product not to make any change to the result.
(more…)

Posted in Cambridge teaching, IA Numbers and Sets | 46 Comments »

Alternative definitions

October 25, 2011

Something that happens very often in lecture courses is that you are presented with a definition, and soon after it you are told that a certain property is equivalent to that definition. This equivalence means that in principle one could have chosen the property as the “definition” and the definition as an equivalent property. To put that differently, suppose you are developing a piece of theory and have some word you want to define. To pick an imaginary example, suppose you have a notion of a set being “abundant”. Suppose that a set is defined to be abundant if it has property P, and that property P is equivalent to property Q. There may well not be much to choose between the following pair of alternatives. On the one hand you can say, “Definition: A set is abundant if it has property P,” and follow that with, “Proposition: A set is abundant if and only if it has property Q,” while on the other you can say, “Definition: A set is abundant if it has property Q,” and follow that with, “Proposition: A set is abundant if and only if it has property P.”
(more…)

Posted in Cambridge teaching, General concepts, IA Groups, IA Numbers and Sets | 6 Comments »