Set

What is a Set in Mathematics?

A set is a well-defined collection of distinct objects. If you’ve ever grouped items together and referred to them as one thing, you already understand the basic idea behind a set.

The theory of Set (now called Set Theory), as a mathematical discipline, rose up with George Cantor, a German mathematician, when he was working on some problems in Trigonometric series and series of real numbers after he recognized the importance of some distinct collections and intervals.

Cantor defined the set as a ‘plurality conceived as a unity‘ (many in one; in other words, mentally putting together a number of things and assigning them into one box).

Mathematically, a Set \( S\) is ‘any collection’ of definite, distinguishable objects of our universe, conceived as a whole. The objects (or things) are called the elements or members of the set \( S\) . Some sets which are often pronounced in real life are, words like ”bunch”, ”herd”, ”flock” etc. The set is a different entity from any of its members.

For example, a flock of birds (set) is not just only a single bird (member of the set). ‘Flock‘ is just a mathematical concept with no material existence but ‘bird‘ or ‘birds‘ are real.

How to Write and Represent Sets

Before you can work with sets in any meaningful way, you need to know how to write them down. There are two standard methods for representing a set, and you’ll use both of them regularly.

Standard Method

In this method we use to write all elements of a set in a curly bracket ( { } ).

For example:

Flock of Birds := {Bird-1, Bird-2, …, Bird-100,…}
or, \( F:= {B_1, B_2, \ldots, B_{100}, \ldots }\) is a set.

Here I have used first capital letter of each term to notate the example mathematically. We read this set as, A set F is defined by a collection of objects \( B_1, B_2, \ldots\) etc..

Characteristic Method or Formula Method

In this method, we write a representative element and define that by a characteristic property. A characteristic property of a set is a property which is satisfied by each member of that set and by nothing else.

For example, above set of Flock of birds can also be written as:
\( \mathrm{ F := { B : B \ is \ a \ bird } }\) which has the same meaning at a wider extent.

We read it as: ”A set F is defined by element B such that B is a bird.”

Examples of Useful Standard Sets

Certain sets show up so often in mathematics that they’ve earned their own dedicated symbols. You’ll encounter these constantly, so it’s worth getting familiar with each one.

Set of Natural Numbers

It includes of the numbers, which we can count, viz. \( \mathrm{ {0,1,2,3,4,5,6,7, \ldots }}\) . The set of natural numbers is denoted by \( \mathbb{N}\) .

Set of Integers

Integers includes of negatives of natural numbers and natural numbers itself. It is denoted by \( \mathbb{Z}\) . \( -5, -4, 1, 2, 0\) …all are integers. The rigorous definition of integers be discussed in fourth part of the series.

Set of Rational Numbers

Rational numbers are numbers which might be represented as \( \frac{p}{q}\) , where p and q both are integers and relatively prime to each other and q not being zero. The set of rational numbers is represented by \( \mathbb{Q}\) and may include elements like \( \frac{2}{3}, \frac{-5}{7}, 8\) . The characteristic notation of the set of rational numbers is \( \mathbb{Q} := { \dfrac{p}{q};/ p,q \in \mathbb{Z}, \ (p,q) \equiv 1 \ q \ne 0 }\) . The rigorous discussion about rational numbers will be provided in fourth part of the series.

Empty Set

It is possible to conceive a set with no elements at all. Such a set is variously known as an empty set or a void set or a vacuous set or a null set.

An example of emptyset is the set \( \{\mathrm{x:\ x \ is \ an \ integer \ and \ x^2=2} \}\) , since there exists no integer which square is 2 —the set is empty. The unique empty set is denoted by \( \emptyset \) .

Unit Set

A set with only one element is called the unit set. {x} is a unit set or a singleton set.

Universal Set

A set which contains every possible element in the universe, is a universal set. It is denoted by \( U\) .

The Subset of a Set

Once you understand what a set is, the next question is: what happens when one set lives entirely inside another? That’s exactly what a subset captures. Think of it as a smaller collection that’s fully contained within a larger one.

Let \( A\) and \( B\) be two sets. We say that \( A\) is a subset of \( B\) (or \( B\) is superset of \( A\) or \( A\) is contained in \( B\) (or \( B\) contains \( A\) ) if every element of \( A\) is also an element of set \( B\) .

In this case we write, \( A \subset B\) or \( B \supset A\) respectively, having the same meaning. If every element of the set A is an element of the set B and B contains at-least one element which does not belong to A, then the set A is called a ‘proper subset’ of B (conversely, B is called the proper superset of A), otherwise A is an improper subset of B.

The proper subset notion is denoted by \( A \subset B\) while the latter is represented by \( A \subseteq B\) . Subset word might be understood using ‘sub-collection’ or ‘sub-family’ as its synonyms. Two sets are equal to each other if and only if each is a subset of the other.

Types of Sets (Based on Number of Elements)

Sets can be classified by how many elements they contain. This distinction between finite and infinite sets is more important than it might seem at first, because it shapes how you reason about cardinality later on.

Finite Set

A set is said to be finite, if it has finite number of elements. For example: A:= {a,b,c,d} is a finite set with four elements. The number of elements in a set is called the cardinality of the set.

Infinite Set

A set is infinite, if contains infinitely many elements. The set of natural numbers, \( \mathbb{N} := \mathrm{ {0,1,2,3,4,5,6,7, \ldots }}\) is an infinite set. The cardinality of an infinite set is infinite.

An empty set is a finite set with zero elements (i.e., zero cardinality).

Power Set of a Set

The power set is one of those ideas that sounds abstract until you see it in action. It’s simply the set of all possible subsets of a given set, and it grows surprisingly fast as the original set gets larger.

Power set of a set A is defined as the family consisting of all subsets of A, but the subset itself. The power-set is denoted by \( P(A):= { X: X \subset A }\) .

Operations on Sets

Just as you can add, subtract, and multiply numbers, you can perform operations on sets. These operations let you combine sets, find what they share, and determine what sets them apart. Understanding these is essential for everything that follows.

Union of Two Sets

If A and B are two sets, then their union (or join) is the set, defined by another set \( S \cup T\) such that it consists of elements from either A or B or both. If we write the sets A and B using Characteristic Method as,

\( \mathrm{A:= {x : x \ is \ an \ element \ of \ set \ A}}\) .

and, \( \mathrm{B:= {x : x \ is \ an \ element \ of \ set \ B}}\)

then the union set of A and B is defined by set J such that

\( \mathrm{J := {x: x \ is \ an \ element \ of \ set \ A \ or \ set \ B \ or \ both }}\) .

For practical example, let we have two sets:

\( A:= {1,2,3,r,t,y}\) and \( B:={3,6,9,r,y,g,k}\) be any two sets; then their union is \( A \cup B :={ 1,2,3,6,9,r,t,y,g,k }\) .

Note that it behaves like writing all the elements of each set, just caring that you are not allowed to write one element twice.

Intersection of Two Sets

Intersection or meet of two sets A and B is similarly defined by ‘and’ connective. The set {x: x is an element of A and x is an element of B} or briefly \( \mathrm { { x: x \in A \wedge x \in B }}\) . It is denoted by \( A \cap B\) or by \( A \cdot B\) or by \( AB\) .

For example, and by definition, if A and B be two sets defined as,

\( A:={1,2,3,r,t,y}\)

\( B:={3,6,9,r,g,k}\)

then their intersection set, defined by \( A \cap B:= {3,r}\) .

In simple words, the set formed with all common elements of two or more sets is called the intersection set of those sets.

If, again, A and B are two sets, we say that A is disjoint from B or B is disjoint from A or both A and B are mutually disjoint, if they have no common elements. Mathematically, two sets A and B are said to be disjoint iff \( A \cap B := \emptyset\) .

If two sets are not disjoint, they are said to intersect each other.

For example, if \( {q,w,e,r,t,y,u}\) is a set of keyboard letters, then \( { {q,w,e}, {r}, {t,y},{u}}\) is a partition of the set and each element of the set belongs to exactly one member (subset) of partition set. Note that there are many partition sets possible for a set. For example, \( {{q,w}, {e,r},{t,y,u}}\) is also a partition set of set \( {q,w,e,r,t,y,u}\) .

The complement set \( A^c\) or \( \displaystyle{\overline{A}}\) of a set \( A\) is a collection of objects which do not belong to \( A\) . Mathematically, \( A^c := {x: x \notin A }\) .

The relative complement of set \( A\) with respect to another set \( X\) is \( X \cap A^c\) ; i.e., intersection of set \( X\) and the complement set of \( A\) . This is usually shortened by \( X-A\) , read X minus A. Thus, \( X-A := {x : x \in X \wedge x \notin A}\) , that is, the set of members of \( X\) which are not members of \( A\) .

The complement set is considered as a relative complement set with respect to (w.r.t) the universal set, and is called the Absolute Complement Set.

Symmetric Difference of Two Sets

The symmetric difference is another difference of sets \( A\) and \( B\) , symbolized \( A \Delta B\) , is defined by the union of mutual complements of sets \( A\) and \( B\) , i.e., \( A \Delta B := (A -B) \cup (B-A) = B \Delta A\) .

Cartesian Product of Sets

Let \( A\) and \( B\) be two sets. Then their cartesian product is defined to be the set of an ordered pair, \( (a,b)\) , where \( a\) and \( b\) are the elements of set \( A\) and set \( B\), respectively. Mathematically; the product of two sets \( A\) and \( B\) : \( A \times B := {(a,b) : a \in A, \ b \in B}\) .

Note that \( A \times B \ne B \times A\) .

If \( A\) has \( m\) elements, \( B\) has \( n\) elements then \( A \times B\) indeed has \( mn\) elements.

We see that if we product two sets, we get an ordered pair of two objects (now we’ll say them, variables). Similarly if we product more than two sets we get ordered pair of same number of variables. For example:

\( X \times Y := (x,y); x \in X, y \in Y\) .

\( X \times Y \times Z :=(x,y,z); x \in X, y \in Y, z \in Z\) . etc.

The sets, which are being product are called the factor sets of the ordered pair obtained. When we form products, it is not necessary the factor sets to be distinct. The product of the same set \( A\) taken \( n\) times is called the \( n\) -th power of \( A\) and is denoted by \( A^n\) . Thus, \( A^2\) is \( A \times A\) . \( A^3\) is \( A \times A \times A\) . And so on.

Important Theorems on Sets

These are the foundational properties that govern how sets behave under union, intersection, and complementation. You’ll rely on these theorems repeatedly when working through proofs, so take the time to understand why each one holds.

• \( A \cup (B \cup C) = (A \cup B) \cup C\)
• \( A \cap (B \cap C) = (A \cap B) \cap C\)
• \( A \cup B= B \cup A\)
• \( A \cap B= B \cap A\)
• \( A \cup (B \cap C)= (A \cup B) \cap (A \cup C)\)
• \( A \cap (B \cup C)= (A \cap B) \cup (A \cap C)\)
• \( A \cup \emptyset= A\)
• \( A \cap \emptyset= \emptyset\)
• \( A \cup U=U\)
• \( A \cap U=A\)
• \( A \cup \overline{A}=U\)
• \( A \cap \overline{A}=\emptyset\)
• If \( \forall A \ , A \cup B=A\) \( \Rightarrow B=\emptyset\)
• If \( \forall A \ , A \cap B=A \Rightarrow B=U\)
• Self-dual Property: If \( A \cup B =U\) and \( A \cap B=\emptyset \ \Rightarrow B=\overline{A}\)
• Self Dual: \( \overline{\overline{A}}=A\)
• \( \overline{\emptyset}=U\)
• \( \overline{U}= \emptyset\)
• Idempotent Law: \( A \cup A=A\)
• Idempotent Law: \( A \cap A =A\)
• Absorption Law: \( A \cup (A \cap B) =A\)
• Absorption Law: \( A \cap (A \cup B) =A\)
• de Morgen Law: \( \overline{A \cup B} =\overline{A} \cap \overline{B}\)
• de Morgen Law: \( \overline{A \cap B} =\overline{A} \cup \overline{B}\)
• Another Theorem

The following statements about set A and set B are equivalent to one another

\( A \subseteq B\)

\( A \cap B=A\)

\( A \cup B =B\)

Set Relations

Relations are where sets become truly powerful. Instead of just grouping objects, you can now describe how objects from different sets connect to each other. If you’ve ever said “X is related to Y,” you’ve already been thinking in terms of set relations.

A relation from set X to set Y is a subset of cartesian product \( X \times Y\) . Similarly, a relation from set B to set A is a subset of \( B \times A\) .

Read these statements carefully:

• ‘Michelle is the wife of Barak Obama.’
• ‘John is the brother of Nick.’
• ‘Robert is the father of Marry.’
• ‘Ram is older than Laxman.’
• ‘Mac is the product of Apple Inc.’

After reading these statements, you will realize that the first ‘Noun’ of each sentence is related to the other.

We say that each noun is in a RELATIONSHIP to the other.

Michelle is related to Barak Obama as a wife.

John is related to Nick, as a brother. Robert is related to Marry as the father.

Ram is related to Laxman in terms of age(seniority).

Mac is related to Apple Inc. as a product.

Such relations are also used in Mathematics, but a little variations; like ‘alphabets’ or ‘numbers’ are used at place of some noun and mathematical relations are used between them. Some good examples of relations are:

is less than
is greater than
is equal to
is an element of
belongs to
divides
etc. etc.

Some examples of regular mathematical statements which we encounter daily are:

4<6 : 4 is less than 6.
5=5 : 5 is equal to 5.
6/3 : 3 divides 6.

For a general use, we can represent a statement as:

”some x is related to y”

Here ‘is related to’ phrase is nothing but a particular mathematical relation. For mathematical convenience, we write ”x is related to y” as \( x \rho y\).

x and y are two objects in a certain order and they can also be used as ordered pairs (x,y).

\( (x,y) \in \rho\) and \( x \rho y\) are the same and will be treated as the same term in further readings. If \( \rho\) represents the relation motherhood, then \( \mathrm {(Jane, \ John)} \in \rho\) means that Jane is the mother of John.

All the relations we discussed above, were in between two objects (x,y), thus they are called Binary Relations. \( (x,y) \in \rho \Rightarrow \rho\) is a binary relation between a and b. Similarly, \( (x,y,z) \in \rho \Rightarrow \rho\) is a ternary (3-nary) relation on ordered pair (x,y,z).

In general a relation working on an n-tuple \( (x_1, x_2, \ldots x_n) \in \rho \Rightarrow \rho\) is an n-ary relation working on n-tuple.

Binary relations are really important to understand for further understanding. In a binary relation, \( (x,y) \in \rho\) , the first object of the ordered pair is called the the domain of relation ρ and is defined by \( D_{\rho} := {x| \mathrm{for \ some \ y, \ (x,y) \in \rho} }\) and the second object is called the range of the relation ρ and is defined by \( R_{\rho} := {y| \mathrm{for \ some \ y, \ (x,y) \in \rho} }\) .

Equivalence Relations on Set

Not all relations are created equal. Some relations have a special combination of properties that makes them behave like a notion of “sameness.” These are called equivalence relations, and they’re central to how mathematicians classify and group objects.

A relation is equivalence if it satisfies three properties, Symmetric, Reflexive and Transitive.

A relation is symmetric: Consider three sentences:

1. “Jen is the mother of John.”;
2. “John is brother of Nick.” and
3. “Jen, John and Nick live in a room altogether.”

In the first sentence, Jen has a relationship of motherhood with John. But can John have the same relation to Jen?

Can John be mother of Jen?

The answer is obviously NO!

This type of relations are not symmetric.

Now consider the second statement.

John has a brotherhood relationship with Nick. But can Nick have the same relation to John? Can Nick be brother of John? The answer is simply YES!

Thus, both the sentences “John is the brother of Nick.” and “Nick is the brother of John.” are the same.

We may say that both are symmetric sentences.

And here the relation of ‘brotherhood’ is symmetric in nature.

Again LIVING WITH is also symmetric (it’s your time to understand it how?).

Now try to write the above short discussion in general and mathematical forms.

Let X and Y be two objects (numbers or people or any living or non-living thing) and have a relation ρ between them.

Then we write that X is related by a relation ρ , to Y.

Or X ρ Y.

And if ρ is a symmetric relation, we might say that Y is (also) related by a relation ρ to X. Or Y ρ X.

So, in one line, \( X \rho Y \iff Y \rho X\) is true.

A relation is reflexive if X is related to itself by a relation. i.e., \( X \rho X\)

Consider the statement “Jen, John and Nick live in a house altogether.” once again. Is the relation of living reflexive?

How to check? Ask like, Jen lives with Jen, true?

Yes! Jen lives there.

If a relation is a transitive relation, means that some objects X, Y, Z are such that if X is related to Y by the relation, Y is related to Z by the relation, then X is also related to Z by the same relation.

i.e., \( X \rho Y \wedge Y \rho Z \Rightarrow X \rho Z\) . For example, the relationship of brotherhood is transitive. (Why?)

Now we will define a combined relation, called equivalence relation, on sets.

We say that a relation ρ is an equivalence relation if the following properties are satisfied:

• (i) \( X \rho Y \iff Y \rho X\)
• (ii) \( X \rho X\)
• (iii) \( X \rho Y \ Y \rho Z \Rightarrow X \rho Z\) .

If a set X has \( n\) elements and set Y has \( m\) elements, then the total number of relations from set A to B (or set B to A) is \( 2^{n\cdot m}\) .

Relations on a Single Set

When you restrict a relation to a single set, some interesting special cases emerge. Here you’re looking at how elements within the same set relate to each other.

A relation on a set A is a subset of \( A \times A\) . There are \( 2^{n^2} \) relations on set with \( n\) elements out of which following are notable:

• Empty Relation: \( \emptyset \subset A \times A\) is an empty relation on set A.
• Improper Relation: \( A \times A\) is an improper or trivial relation on set A.
• Diagonal Relation: \( \Delta := \{ (a,a) : a \in A \}\) is a diagonal relation on A.

Composition of Two Relations

You can chain relations together, much like composing functions. If one relation connects element \( a\) to \( c\) and another connects \( c\) to \( b\), their composition connects \( a\) directly to \( b\).

Let R and S be two relations on set A. Then, \( R \cup S, \, R \cap S\) and \( R \setminus S\) are all subsets of \( A \times A\) and hence they are also relations on A.

The relation, \( R \rho S := { (a_1, a_2)} \subset A \times A \) such that \( (a_1, a_3) \in S\) and \( (a_3, a_2) \in R\) , \( \forall a_1, a_2, a_3\) is called the composition of R and S on set A.

Properties of Composite Relations

Let R, S and T be relations on set A. Then,

• \( (R \rho S) \rho T =R\rho (S \rho T)\)
• \( R \rho \Delta = R = \Delta \rho R\)
• \( R \rho (S \cup T) = (R \rho S) \cup (R \rho T)\)
• \( R \rho (S \cap T) \subseteq (R \rho S) \cap (R \rho T)\)

Inverse Relation

Every relation has an inverse, and understanding it is simpler than you might expect. You just swap the order of elements in each ordered pair.

Let R be a relation on a set defined by ordered pair \( (x,y)\) , then the inverse of the relation R, \( R^{-1}\) , is defined by ordered pair, \( (y,x)\) . \( R^{-1}\) is called the inverse relation of R on the set.

Remarks

Let R and S be the relations on A, then

• \( (R^{-1})^{-1} = R\)
• \( {(R \rho S)}^{-1} = S^{-1} \rho R^{-1}\)

Partition of a Set

Partitioning a set means dividing it into non-overlapping groups that together cover the entire set. Every element ends up in exactly one group, with nothing left out and no overlaps.

A partition set of a set X is a disjoint collection of non-empty and distinct subsets of X such that each member of X is a member of exactly one member (subset) of the collection.

Let A be a set. A subset P of the power-set of A is called partition of A, if

• Union of members of P is A. i.e., \( \displaystyle {\cup_{X \in P}} X =A\)
• \( X, \, Y \in P, \, X \neq Y \Rightarrow X \cap Y = \emptyset\) .

Cardinally Equivalent Sets

When can you say two sets are the “same size”? For finite sets, you just count the elements. But for infinite sets, counting doesn’t work. Instead, you check whether a one-to-one correspondence exists between them.

A set \( A\) is said to be cardinally equivalent or just ‘equivalent’ to another set \( B\) if there exists one-one mapping (function) from A to B. This relation is denoted by the symbol ~. Therefore A~B means that set A and B are equivalent to each other.

Denumerable, Countable and Uncountable Sets

This is where set theory gets genuinely surprising. You might assume all infinite sets are the same “size,” but Cantor showed that’s not the case. Some infinities are larger than others, and the distinction between countable and uncountable sets is one of the most important ideas in all of mathematics.

A set A is called a denumerable (or countably infinite) set if there exists a one-one mapping from the set \( \mathbb{N}\) of natural numbers onto the set A,i.e., A is denumerable, if it’s equivalent to the set of natural numbers \( \mathbb{N}\) .

A set A is said to be countable set if either A is denumerable or A is finite.

A set is uncountable, if it’s infinite and not equivalent to \( \mathbb{N}\) .

Examples of Denumerable, Countable and Uncountable Sets

Here are some key examples that illustrate the distinction. Pay close attention to the last two, because they reveal just how different “sizes” of infinity can be.

• The set of all natural numbers \( \mathbb{N}\) is countable.
• The set of all rational numbers \( \mathbb{Q}\) is countable.
• The set of all real numbers \( \mathbb{R}\) is uncountable.
• The set of all irrational numbers is uncountable.
• The set \( \mathbb{N} \times \mathbb{N}\) is uncountable.

Important Theorems on Countability

These theorems give you the essential rules for reasoning about finite, countable, and uncountable sets. They’re the toolkit you’ll use whenever you need to determine the cardinality of a new set.

1. Every subset of a finite set is finite.
2. Every superset of an infinite set is infinite.
3. If A and B are finite sets, then \( A \cap B\) and \( A \cup B\) are also finite sets.
4. Every subset of a countable set is countable.
5. Every infinite subset of a denumerable set is denumerable.
6. For countable sets, A & B , \( A \cap B\) is also countable.
7. Every superset of an uncountable set is uncountable.
8. Every infinite set has a denumerable subset.
9. Countably infinite sets are smallest infinite sets.
10. The countable (finite) union of countable sets is countable.
11. Every infinite set is equivalent to one of its proper subsets.

Frequently Asked Questions