**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.