Set
- a set is a collection of items and when we write out a set, if it is a finite set, then we can just enumerate the items in the set by writing them within curly braces.
- On the other hand, if we have an infinite set, we really can not write out all the elements even though informally, we put dot, dot, dot to indicate a sequence, if that sequence is not very regular.
- For example, supposing it is a set of prime numbers, which does not have a clear pattern, then it is not very easy to represent it explicitly like this.
Membership Of Set
- small x typically denotes a member or an element of a set, and capital X usually denotes a set itself. So, when we write x belongs to X what we mean is the element x belongs to X.
- So, for example, the number 5 belongs to set of integers, and does not belong to the set of √2 rationals for instance.
- Subset on the other hand, says that one set is included in another set, so everything that belongs to X belongs to Y.
- So, for instance, all the prime numbers are natural numbers, so the primes are a subset of the naturals.
- Every natural number is an integer, so the natural numbers are a subset of the integers.
- Similarly, the integers are a subset of the rationals and the rationals are subset of the reals.
power set
- So, when we take a set, we can enumerate all its subsets.
- empty set, which is a subset of every set.
- The empty set has no elements in it, but we needed it for technical reasons, and it is a subset of every set.
- And in addition, if you have 2 elements set {a,b}, then the subsets could be the individual elements, the
set containing a and the set containing b or the entire set itself. - So once again, just like the empty set is a subset of everything the set itself is also a subset of
itself. - for a finite set with n elements, we will always have subsets. So 2n
here for instance we have 2 elements, so we have = 4 subsets. So, this is just a review of what 22
we have already seen.
set comprehension
- infinite sets which cannot be written down explicitly.
- So, supposing we want to write down the set of all the squares of the even integers.
- So, the even integers are -2, +2, 0 as an even, -4, +4, and so on.
- So first, in the set comprehension notation, we have a generator.
- A generator says that we are taking elements from an existing set, so we can only build new sets from old sets.
- So, we already have a set of integers, and we are going to try out every integer in the set, so, that is what x
element of Z says, is try every x ∈ Z, so Z generates this set. - Now, all the x’s that come out are not interesting to us.
- So, we want to filter out those that are useful, that satisfy a given property.
- In this case, the property that we are looking for is that the number is even.
- So, we want those x which come out of Z through the generator, such that they satisfy the property that x when divided by 2 has remainder 0, which is the property that x is even.
- And finally, with these x, we do not want to keep them as they are, we want to transform them.
- So, on the left-hand side of this vertical bar, this is the left-hand side are the actual elements of the set.
- The elements of the set are generated right, then filtered through some conditions, which rule out the ones we do not want, and when the ones we keep, we can transform them.
- In this case, we want the squares, we do not want the even numbers, we want their squares.
- So, when we started the generating process, we had all the integers, then we filtered out, and we got only the even ones, and now we transform them. S
but it is the same rational number. So, we want the numerator and the denominator to not have
any common divisors, which is the same as saying that their greatest common divisor is 1, that is
nothing other than 1 divides both the top and the bottom of the fraction. So, if we take all the
rational numbers, so we generate all the possible rational numbers , which belong to the set of
q
p
rationals.
Then, we filter out those which have no common divisor between the numerator and the
denominator and we keep only those, we do not transform it in any way, we just keep it here. So,
here the transformation is just to keep it as it is, this is sometimes called the identity
transformation. The identity just takes an input and produces the output the same as the input.
So, this gives the set of rationals in reduced form. So, here we have used a function, GCD. Even
though we have not formally defined it here, we assume that people understand what GCD
means. So, this is what we mean by saying that we can write the filter in any reasonable way, as
long as people understand what it means.
Another example, we looked at are intervals. So, here we want the real numbers, which start
from -1 including -1, and go up to but not including 2. So, in this case, we will use less than and
less than equal to, so we will take all the reals. So, we take every possible real number, but we
are not interested in all the reals, so we check whether it is greater than or equal to -1, so it
includes -1 and everything above it. So, it cuts off everything which is strictly smaller than -1.
But, we also do not want it to cross 2, so we stop below 2, so it should be greater than equal to -1
or and less than 2 and if so, again we keep it without any transformation. And this notation on
the top, the square bracket, and round bracket are indications of whether the endpoint is included
or not. So, -1 endpoint is included, +2 endpoint is not included.
So, let us see why we would actually want set comprehension notation. So, let us extend our first
example of squares of the even numbers to cubes. So, cube is just a number multiplied by itself 3
times. So, square is x ⨯x, a cube is x⨯x⨯x, 3 times. So, if we want the cubes of the first 5 natural
numbers, we can write it out explicitly like this, we can take this generator and generate the first
5 natural numbers as 0, 1, 2, 3, 4. Remember that, in our terminology natural numbers start with
0, even though in some books, you will find that natural numbers start with 1, we always assume
natural numbers start with 0.
So, the first 5 natural numbers are 0, 1, 2, 3, 4. So, this is our generator, take every n in this and
transform it to without doing any further filtering. We are not asking for the first 5 odd n
3
numbers or the first 5 numbers which have some other property, we just take, taking the first 5
numbers. Now, imagine that we change this question to the first 500 natural numbers, then
though we can write it out explicitly, it is rather tedious.
So, we have to replace the small list of 5 numbers by a long list of 500 numbers. And remember,
we are not really allowed to write dot, dot, dot if we are being mathematically precise. So, we
actually have to physically write out these 500 numbers. Now, this is not terribly convenient. On
the other hand, we can define the first 500 numbers quite easily using set comprehension.
So, we can say, give me all the natural numbers, that is the generator, but restrict the natural
number to be less than 500. So, remember that the first 500 natural numbers are going to be 0 up
to 499. So now, this says that this set X is actually this long set here which we have written
explicitly. So, we have replaced that very long and tedious expression by a much more compact
expression, which captures exactly the same set. So now, we can have a much more readable
version of these cubes of the first 500 natural numbers.
As an intermediate set, we generate the set X, set X = {n | n ∈ N, n < 500 }. And then we take
this as the generator and we say, okay, take every n which belongs to this X. So now, we know
that x is restricted to 0 to 499. And then, take the cubes of these numbers, so we get n cubed in
this range. So, this is one other use of set comprehension, which is to make our definitions more
readable and understandable and less tedious to write.
So, let us look at one more round of examples. So, we saw this before, we talked about perfect
squares. So, we said that some integers are squares of other integers and some integers are not
squares. In particular, those which are not squares, their square roots are actually irrational. We
proved for instance, in our supplementary lecture, that the is irrational. So, perfect square is √2
an integer such that its square root is also an integer. So, this is what this says, give me all the
integers, which satisfy the condition that their square root is also an integer.
So, the square root of small z also belongs to a set of integers, give me all set Z and call it a
perfect square. Now, notice that the square must be positive, we have already discussed this
because you multiply 2 negative numbers, you get a positive number, you multiply 2 positive
numbers, you again get a positive number. So, in fact, a perfect square must always be
non-negative, it could be 0.
So, we could as well assume that the target set is generated by the set of natural numbers. And
that, we are only interested in the positive square root, so remember that, 4 has 2 square roots,
the number 4 is either (-2) ⨯(-2), or 2⨯2, but it is sufficient to know that one of its square roots is
an integer because the other one will just be the same with a minus sign.
So, we can as well define the same set of perfect squares in terms of the natural numbers, we
generate all the natural numbers whose square roots are also a natural numbers. Now, we can
turn this around and replace the filter by a condition. So, we know that every natural number
when it is squared will give us a natural number. So, all the perfect squares will be generated in
that form, take a natural number, square it. So, instead of looking for those numbers whose
square root is a natural number, we can just take every natural number and square it.
So, we just generate all the natural numbers and without filtering them, we just take the output
square. So, this also gives us 0, , , and so on. So, these are all different ways of writing 12
22
32
the same thing. In one case, we replace the generating set from integers to natural numbers
because of the property of perfect squares. In another case, we transformed the filter into a
transformation. So, instead of putting a condition on the numbers that we are generating, we took
all the numbers and then squared them to get the actual perfect squares.
Now we could extend the notion of perfect squares to other sets of numbers. For instance,
rationals can also admit a definition of a perfect square, so a rational will be a perfect square if it
is a square of another rational. In particular, a rational could be an integer, but we will now
integers can also be above and below the line, so we could have , for instance as a rational
9
16
number, which is , so, ⨯ = . 4
2
3
2
4
3
4
3 9
16
So, we might want to say that this is a perfect square in the world of rationals. And not
everything is a perfect square because since cannot be represented a rational, it is easy to √2
check that half cannot be represented with a form . So, not every rational in this sense is a ( )
q
p 2
perfect square, some are, some are not. So, we can again change the definition above and replace
Z and N by Q and get a reasonable definition of perfect squares in a different domain of
numbers.
So, we can say give me all the rationals q such that is also a rational. Or using the second √q
form, we can say take all the rationals and square them. So, take every q, which is a rational q
and give me . So, this says that depending on how you choose the generator, you might q
2
generate the same set, or you might generate a different set. So, it is important to specify all the
parts of a set comprehension correctly, so that there is no ambiguity and so that you get the set
that you mean to get.