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)=x2 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)=x2 and g(n)=n2 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 n2(2n2-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".