Basic definitions needed for Examples Sheet 1

Comments on individual questions - Sheet 1.

Comments on individual questions - Sheet 2.

If your supervisions for Numbers and Sets are on the early side, then it is possible that I will not have mentioned some of the definitions you need by the time you come to attempt the questions. This does not mean you cannot do the questions, since usually it is just a case of finding out what the words mean and then getting on with it. This page contains a few definitions, and comments about them, and the aim of it is that nobody should have a valid excuse not to attempt a question.

Here, very briefly, are some of the definitions I use. (Of course, if you are meeting them for the first time, then you won't understand them as well by reading them here as you will by hearing me talk about them in a lecture, give examples, and so on, but with luck you will be able to get through the sheet.)

A\B means {x: x is in A but x is not in B}. It is the set of all elements of A that are not elements of B. (Sometimes it is written A-B.) Note that B is not required to be a subset of A.

AxB, the * Cartesian product * of A and B, is defined to be
the set of all ordered pairs (x,y) such that x is an element of A and y
is an element of B.

A * function * from a set X to a set Y is a way of
associating with each element x of X an element y=f(x) of Y. X is
called the * domain * of f and Y is the * range *.
You will have met several functions already, but typically they
will be functions from R to R (that is, functions that take real
numbers to other real numbers) such as the function f(x)=sin x.
The definition I have just given is not completely formal (what
is a "way of associating"?), a point I will discuss in lectures.
But two points to note are that X and Y can be any sets and that
there need not be a simple formula that gives you the function.

If y=f(x) then y is said to be the * image * of x, and x is
said to be a * preimage * of y. Notice that I said * a *
preimage of y rather than * the * preimage, since it is quite
possible for y to have two or more preimages, or none. This motivates
the next three definitions: f is said to be an * injection * if
no element of Y has more than one preimage, a * surjection * if
every element of Y has at least one preimage, and a * bijection
* if it is an injection and a surjection (in which case every
element of Y has exactly one preimage). If f is a bijection then it
gives us a one-to-one correspondence between the elements of X and
those of Y (with x in X corresponding to f(x) in Y). Notice that
whether or not a function f is an injection/surjection or not
depends not just on what f does to points in X but also importantly
on X and Y. For example, the function f(x)=x^{2} is not
an injection or a surjection if X and Y are both the set of all
real numbers, but it is a bijection if X and Y are the set of all positive
real numbers.

The word "relation" is slightly confusing. A more accurate
phrase might be "potential relationship". Anyhow, roughly speaking
a * relation * R on a set A is something you can put between
two elements x,y of A to make a sentence (which gives us information
about how x and y are related). For example, < is a relation on the
set N of natural numbers: given two natural numbers m and n, you can
write m < n, which is a sentence - true for some pairs (m,n) and
false for others. A relation R on a set A is * reflexive * if
xRx for every x in A. (So < defined on N is not reflexive.) It is
* symmetric * if xRy implies that yRx. (So < defined on N
is not symmetric either.) It is * transitive * if xRy and
yRz together imply that xRz. (So < defined on N * is *
transitive.)

Notice that any subset S of AxA determines a relation R on A: just say that xRy if and only if (x,y) is an element of S. So just as a subset of AxA need not be defined in a nice way, so a relation can be pretty arbitrary, even if the useful ones tend to have simple definitions.

A * binary operation * defined on a set A is something
you can put in between two elements of A to make a new element of
A. The most familiar examples are +, -, x and /, defined on systems
of numbers. (More formally, a binary operation can be thought of
as a function from AxA to A.) A binary operation * defined on A
is * commutative * if x*y=y*x for every x,y in A. It is
* associative * if x*(y*z)=(x*y)*z for every x,y,z in A.

When I refer to the criterion for equality of sets, I mean the principle that two sets $A$ and $B$ are equal if and only if every element of $A$ is an element of $B$ and every element of $B$ is an element of $A$.

gof stands for the * composition * of the functions f
and g, which is defined as follows. Let f be a function from A
to B and g a function from B to C. Then gof is the function from
A to C that takes x (an element of A) to g(f(x)). I.e., you take
an element of A, do f to it and do g to that. Because gof(x) means
g(f(x)) means "g of f of x", you have the awkward result that
although g is written first, you do the function f first. (Some
people like to write not f(x) but xf, so that g(f(x)) becomes
xfg and f and g appear in the correct order. But people who
think one should write maps on the right are a bit like people
who think we should change to the duodecimal system for numbers:
it just ain't going to happen. Better to get used to the very
small anomaly of the notation as it is.) The composition gof
of f and g is * not defined * unless the range of f is the
domain of g. (This is another useful convention rather than a
deep piece of mathematics.)

A typical proof that a function h from A to B is an injection runs as follows.

Let x and x' be elements of A and suppose that h(x)=h(x'). Then ....... and so x=x'.

This proves that no y in B has more than one preimage. (If it did, then let x and x' be two preimages. But then the above argument would show that they were equal.)

If f is a function from X to Y and Z is a subset of X, then f(Z) is defined to be {f(z):z is in Z}. In words, f(Z) is the set of all values taken by f(z) as z ranges over the set Z. This notation confuses some people, because they have the following thought: when you see f followed by something enclosed in brackets, then you take the thing in brackets and do f to it. So they then try to apply f to Z.

But this cannot be right. If f is a function from X to Y, then
the only sort of thing you are allowed to do f to is an * element
of * X. Since Z is not an element of X, but a * subset *
of X (a very different sort of object), it doesn't make sense to
do f to Z. So it is clear, just from the definition of a function,
that f(Z) must mean something else.

Of course, what it means is a matter of convention, but there is
only one sensible convention in this case. Obviously f(Z) should have
something to do with Z. What can we apply f to if we want to involve Z
somehow? Answer: elements of Z (since these are elements of X as well,
and that is what we * know * we can apply f to). Since we are
told nothing about Z other than that it is a subset of X, it is
impossible to pick out some elements and not others, so we had better
apply f to * all * elements of Z. Having done that, how can we
form a mathematical object? Well, we have a collection of answers (f
applied to all the elements of Z) and to regard this multiplicity as a
single object the standard method is to form the set of all the things
we have. And thus we arrive at the definition f(Z)={f(z):z is in Z}
that I gave above.

The definition is confusing for a genuine reason - the same piece
of notation is being used for two different purposes (applying f
to an element of X to get an element of Y, and applying f to all
the elements of a subset of X to get a subset of Y). However, once
you are used to it, you should not be confused for the reasons
I have just given - if you see f(Z) and are told that Z is a
subset of X, then it * has * to be that the notation is
being used in the the second way and not the first. Otherwise
it would not make grammatical sense.

A general point that arises out of the above discussion: when doing mathematics you should get into the habit of constantly asking yourself the following.

* What kind of mathematical object am I dealing with?
*

The answer might be a set, a set of sets, a subset of a given set, an element of a subset of a given set, a function from one given set to another, a non-negative real number, a set of complex numbers, a set of functions from the rational numbers to the rational numbers etc. etc. There are only certain ways that mathematical objects are allowed to relate to one another, and if you have the above habit, it is a very useful check that you understand what you are talking about. For example, if f is a function from X to Y and you write "f(T) is an element of Z," then you will have gone wrong unless T is an element of X (in which case the use of a capital letter would be rather unusual) and Z is a set that has a non-empty intersection with Y (in most natural cases one would expect it to be a subset of Y but one can just about imagine other circumstances). This sort of checking is rather like checking units. It doesn't solve problems for you, but it greatly restricts what you can do (which is useful when you are looking for a solution as it cuts down the size of the search), clarifies your thought-processes and helps you to avoid a certain quite common type of serious mistake.

To give an example - there is a similarity between the
definitions of commutative (of binary operations) and
symmetric (of relations). But the two are importantly different:
one says that two elements of a set are equal and the other
that two statements are equivalent. Suppose you are momentarily
confused by this and wonder whether the relation < is
associative. As soon as you write down the expression
x< (y< z) you should instantly see that something is
wrong. Why? Because on either side of the first < there should
be numbers, but (y< z), far from being a number, is in fact a
mathematical statement - the wrong kind of object in the context.
Of course, it is very easy to see that the expression
x< (y< z) is nonsensical, but if you replace < by a more
general relation R, obtaining xR(yRz) it's not quite so obvious.
After all, if R were not a relation but a binary operation
then it * would * make sense. So here it would be more
important to keep reminding yourself of the kind of object
being discussed.

Now let us think about the second piece of notation used in
the question. What could be the meaning of f^{-1}(Z) when
Z is a subset of Y? (In the question Z is the intersection of
C with D, which is indeed a subset of Y.) This again confuses
people, since it looks as though f^{-1}(Z) means the
inverse function of f applied to Z. But it doesn't mean that
at all, and, as before, it * couldn't * mean that. For
a start, the question does not say that f * has * an
inverse. Secondly, Z is not an element of Y, so is not the
sort of object to which one could apply f^{-1} even
if it did exist.

The actual definition of f^{-1}(Z) is {x in X:f(x) is in
Z}. In words, it is the set of elements of X that f maps into Z. In
different words, it is the set of preimages of elements of Z. Why is
this a sensible definition? Well, if f^{-1} * does *
exist and y is in Y, then f^{-1}(y) is a preimage of y (in
this case there is exactly one preimage, so I could have said * the
* preimage of y). And just as the notation f(Z) stood for the set
of all * images * of elements of Z (when Z was a subset of the
domain X), so f^{-1}(Z) stands for the set of all *
preimages * of elements of Z (when Z is a subset of the range
Y).

Notice that the expression {x in X:f(x) is in Z} does not involve anything that looks like an inverse function, as indeed it shouldn't.

One final comment about the question: you are being asked whether two sets are equal, so you should determine whether they satisfy the criterion for set equality.

Two functions f and g count as the same if they have the same
domain A, the same range B and if f(x)=g(x) for every x in A.
Otherwise, they are different. For example, the functions
f from R to R and g from N to N defined by f(x)=x^{2} and
g(n)=n^{2} are different, even if they appear to do
"the same thing", while the functions f from R to R defined
by f(x)=sin x and g from R to R defined by g(x)=cos(x-pi/2)
are the same.

When I said that a relation was something that expresses a possible relationship between elements of A, you should not imagine that it has to be something simple like <, with its already existing economical notation. (See my remark above about subsets of AxA.) For example, another perfectly valid relation on N is the relation -@*!-, which I define by saying

m-@*!-n if and only if either m=10 and n is a prime or m is even and n is composite.

The stupidity and artificiality of this definition do not stop
it * being * the definition of a relation.

I did not make this clear, but a cycle should not visit the same point twice (until it gets back to the beginning).

There is a typo so that the question is wrong as it stands. The
right hand side should read n^{2}(2n^{2}-1). Apologies
for this.

You could also think about whether any power of 2 begins with a 9. You will get much more out of this question if yo do not touch a calculator while thinking about it.

I will be showing you a method for doing this, known as Euclid's algorithm. If d is the highest common factor of m and n, and if you write m=qn+r, then d is also the highest common factor of m and r. (Exercise - prove this.) This observation allows you to replace the pair (m,n) with a smaller pair (r,m) (smaller, that is, if you choose q to be as large as possible such that r is non-negative) with the same highest common factor. If you repeat this process for long enough it eventually becomes obvious what the highest common factor is.

"Based on prime factorization" means using the (non-obvious) theorem, which we shall prove, that there is one and only one way of writing any given postive integer as a product of primes (give or take the order in which you write them). I now wish that I had written "Bezout's theorem" instead of "Euclid's algorithm".