15. Sets

So, what is the definition of a set? A very high level definition is, it is an unordered collection of objects and what I mean by unordered collection of objects here is that ordering of the elements in the set does not matter. So, for instance, if I have a set consisting of the elements 1, 2 and 3 and then it does not matter whether I list them as 1, 2, 3 or whether I list them as 3, 2, 1 both will be the same sets.

A set is defined as an unordered collection of elements, which means that the order in which the items are listed does not matter. For example, the sets {1, 2, 3} and {3, 2, 1} represent the same collection because they contain the same elements, just listed in different orders.

Think of a box of assorted fruits. Whether you place an apple first, a banana second, or an orange third in the box, as long as the same fruits are there, the box is still the same. The arrangement doesn't change the contents.

It turns out that the elements of the set need not be related. So, for instance, if I have a set consisting of entities, Narendra Modi, Manmohan Singh, Ashish Choudhury and 100 it is a valid set as far as the definition of a set, because the definition does not say anything regarding the properties of the elements of the same.

Sets can contain elements that are completely unrelated to each other. For example, a set could contain a politician's name, another politician's name, and a number like 100. This shows that there is flexibility in what can be included in a set, with no requirements for the elements to share specific properties.

Imagine a shopping basket containing an apple, a textbook, and a cat toy. The items have nothing in common except that they are all placed in the same basket. Similarly, in sets, we can group different kinds of items without regard for their nature.

We use some well known well-defined notations for representing sets. So, we use this notation ∈ for 'a belongs to A'. So, this notation 'belongs to', whenever a is an element of set A we use this notation. And throughout this course, we will follow the notation that we will be using small letters for elements of the sets, and we will be using capital letters for the sets.

To indicate membership in a set, we use a specific notation where '∈' denotes 'belongs to'. For example, if 'a' is an element of set 'A', we write 'a ∈ A'. In this course, small letters will represent individual elements while capital letters will represent the sets themselves.

Consider a classroom where each student (represented by lowercase letters) belongs to a particular class (represented by uppercase letters). If Alice belongs to Class 10, we would say 'Alice ∈ Class10'. This shows how we can indicate membership in a group or set.

Now, how do we express a set? There are two well known methods. The first method is the Roster method, where we specify the elements of the set within braces. So, for instance if A is a set consisting of 4 elements, then I have listed down the elements of the set A and this is a convenient way of representing a set provided the number of elements in the set is small. If the number of elements in the set is extremely large then it will not be feasible to write down or list down all the elements of the set explicitly. So, that is why we use the second form or second way of expressing a set which is also called as the set builder form and what we do here is that instead of listing down the elements of the set, we write down or state the general property of the elements of the set, which is specifically specified by a predicate function.

There are two main methods to express sets. The first method is the Roster method, where we list out all the elements within braces, such as {1, 2, 3, 4}. This is practical for small sets. For larger sets, we use the Set Builder form, which describes the properties of the elements instead of listing them all out. For example, a set can be defined as 'A = {x | x is an odd number less than 10}', which uses a property to define a potentially infinite set.

Imagine you have a box of crayons. If the box has only a few crayons, you can easily list them all – {red, blue, green}. But if you have a box filled with all shades possible, it's easier to say 'All colors' instead of trying to list them one by one.

We often encounter some special sets. So, a null set or the empty set is one of them and this is the notation ϕ which we use to represent the null set. This is also called as phi set or phi set and it is a set which has no elements. So, you can imagine that a directory which has no files inside it is an example of an empty set. Another special set which we encounter is the singleton set and it is a set which has a single element in it.

Special sets include the empty set, represented by the symbol 'ϕ', which contains no elements. For example, a box with nothing inside represents an empty set. In contrast, a singleton set is one that contains exactly one element, such as {x}. Understanding these two types of sets is important, as they can often be confused.

Think of a closet. If it's completely empty, it's like the empty set – no clothes, no items to count. Now, if there’s just one shirt hanging in that closet, it represents a singleton set because there’s exactly one item present.

So, now we will introduce some definitions in the context of sets. So, we start with what we call as equality of sets. So, intuitively if I have two sets A and B they will be called, or they will be considered equal sets if they have the same elements. That means if I have any element present in the set A it is present in B and in the same way any element which is present in B is also present in A there is nothing which is extra present in A or which is extra present in B.

Two sets are said to be equal if they contain exactly the same elements. This means that if an element exists in set A, it must also be found in set B, and vice versa. If there are no additional elements in either set, they are considered equal.

Consider two crates of oranges. If both crates contain exactly the same number and type of oranges, those two crates are equal. However, if one crate has an extra orange or a different type, the crates would not be considered equal.

The next definition is a subset of a set. So, if I have two sets A and B then the set A is called a subset of the set B and for denoting that we use this notation ( ⊆ ), provided the following holds, you take any element in the set A it should be present in B that means it should not happen that there is something in A which is not there in B. This is stated formally by saying that the following expression should be a tautology namely for all x in the domain, if x is in A then it should be present in B. I do not care what happens if x is not present in A.

A set A is a subset of set B, denoted as A ⊆ B, if every element of A is also an element of B. This does not depend on whether B has elements not found in A. If there exists at least one element in B that is not in A, then A is called a proper subset, denoted as A ⊂ B.

Think of a chocolate box. If one box (A) contains some chocolates that are also present in a larger box (B), we say the smaller box is a subset of the larger box. If the smaller box has all the chocolates of the larger box, but there are still more chocolates in the larger box, we say it’s a proper subset.

Next we define the cardinality of a set. So, we say that cardinality of a set S is n and for that we use this notation. We use this to vertical bar symbols ( | | ) within S to denote its cardinality and we write it is equal to n provided there are n elements in S where n is some non-negative integer. So, n could be 0 or 1 or it should be some value belonging to the set of natural numbers or it should be a non-negative integer.

The cardinality of a set, denoted |S|, refers to the number of elements in that set. If a set has n elements, we say its cardinality is n. Sets can be finite (with a definite number of elements) or infinite (where the number of elements cannot be counted or expressed as a natural number).

Consider a jar of cookies. If there are 10 cookies in the jar, the cardinality of that set of cookies is 10. If the jar is empty, the cardinality is 0. Now, imagine a never-ending cookie factory; the cookies it produces form an infinite set because you can't count them all.

We next define what we call as the power set of a set and we use this notation P(S). So, you are given a set S. And if I take the collection of all subsets of this set S, then that itself is a set because I am just listing down the subsets of S and the elements here the elements of P(S) are the subsets of S. So, if I list down all the subsets of S the resultant set is called as the power set.

The power set of a set S, denoted as P(S), is a set containing all possible subsets of S, including the empty set and S itself. For example, if S = {1, 2}, the power set P(S) = {∅, {1}, {2}, {1, 2}}. So, the power set always includes every combination of elements from the original set.

Imagine a toy box containing three toys. The power set includes every possible combination of toys you can choose from that box: choosing none, choosing one toy, choosing two toys in various combinations, and finally choosing all three toys.

So, now let me introduce some set operations and most of you will be familiar with this. This is the union ( ∪ ) of two sets and it is the collection of all elements x in the domain which are present in either A or present in B. Of course, it might be present in both of them because this disjunction will be true if the condition x belongs to A is simultaneously true as well as condition x belongs to B is also simultaneously true.

Several main operations can be performed on sets. The union (A ∪ B) combines all elements from both sets A and B, including duplicates. The intersection (A ∩ B) takes only those elements that are found in both sets, while the difference (A - B) gives elements that are in A but not in B. The complement is defined with respect to a universal set. The Cartesian product combines ordered pairs from both sets.

Picture two circles that overlap. The union of the two represents all the items in both circles, including duplicates where they overlap, while the intersection represents just the shared area. If one circle represents apples and the other oranges, the union is all the fruit you have, and the intersection is the fruit that’s both an apple and an orange (which doesn’t exist).

Now, there are some well-known set identities which are available. We have some names also for these set identities where each of these identities basically state that a set in the left-hand side and the set in the right-hand side are the same. And we can prove them and assuming that these are true we have associated names with them and whenever we want to simplify expressions involving set, we can call these set identities.

Set identities are equations involving sets that are true regardless of the elements in those sets. They help simplify expressions and manipulate sets efficiently. For example, the union of a set with the empty set equals the original set, as the empty set contributes no elements.

Think of a library. If you add a new shelf (the empty set) to your existing books, your collection remains the same because the empty shelf doesn't add any new books. This illustrates the identity of a set combined with the empty set.

--