Set Theory – Definition and Examples

Set TheorySet theory is a branch of mathematical logic that studies sets, their operations, and properties.

Georg Cantor first initiated the theory in the 1870s through a paper titled “On a property of the collection of all real algebraic numbers.” Through his power set operations,  he proved that some infinities are larger than other infinities. This led to the widespread use of Cantorian concepts.

Set theory is one of the foundations of mathematics. It is now considered an independent mathematics branch with applications in topology, abstract algebra, and discrete mathematics.

We will be covering the following topics in this article:

  • Set theory basics.
  • Set theory proofs.
  • Set theory formulas.
  • Set theory notations.
  • Examples.
  • Practice problems.

 

Set Theory Basics

The most fundamental unit of set theory is a set. A set is a unique collection of objects called elements. These elements can be anything like trees, mobile companies, numbers, integers, vowels, or consonants. Sets can be finite or infinite. An example of a finite set would be a set of English alphabets or real numbers, or whole numbers. 

Sets are written in three ways: tabular, set builder notation or descriptive. They are further classified into a finite, infinite, singleton, equivalent, and empty sets.

We can perform multiple operations on them. Each operation has its unique properties, as we will say later in this lecture. We will also look at set notations and some basic formulas.

Set Theory Proofs

One of the most important aspects of set theory is the theorems and proofs involving sets. They help in the basic understanding of set theory and lay a foundation for advanced mathematics. One is extensively required to prove different theorems, most of which are always about sets.

This section will look at three proofs that serve as the stepping stone towards proving more complex propositions. However, we will only be sharing the approach instead of a step-by-step tutorial for a better understanding.

The object is an element of a set:

As we know that any set in set-builder notation is defined as:

X = {x : P(x)}

Here P(x) is an open sentence about x, which needs to be true if any value of x must be the element of set X. As we know this, we should deduce that to prove an object is an element of the set; we need to prove that P(x) for that specific object is true. 

A set is a subset of another:

This proof is one of the most redundant proofs in set theory, so it needs to be well understood and requires special attention. In this section, we will be looking at how to prove this proposition. If we have two sets, A and B, A is a subset of B if it contains all the elements present in B, this also means that:

if aA, then aB.

This is also the statement that we need to prove. One way is to assume that an element of A is an element of A and then deduce that a is also an element of B. However, another option is called the contrapositive approach, where we assume that a is not an element of B, so a is also not an element of A.

But for the sake of simplicity, one should always use the first approach in related proofs.

Example 1

Prove that {x Z: 8 I x} {x Z: 4 I x}

Solution:

Let us suppose a {x Z: 8 I x} which means that a belongs to integers and can be divided by 8. There must be an integer c for which a=8c; if we look closely, we can write it as a=4(2c). From a=4(2c), we can deduce that 4 I a. 

Hence a is an integer that can be divided by 4. Therefore, a {x Z: 4 I x}. As we have proved a ∈  {x Z: 8 I x} implies a {x Z: 4 I x}, it means that {x Z: 8 I x} {x Z: 4 I x}. Hence proved.

Two sets are equal:

There is elementary proof to prove that two sets are equal. Suppose we prove that A B; this will imply that all elements of A are present in B. But in the second step, if we show that B A, this will mean that all the possibility of some B elements that were not in A during the first step has been removed. There is no chance for any elements in B now to be not present in A or vice versa.

Now since both A and B are a subset of each other, we can prove that A equals B.

Set Theory Formulas

This section will be looking at some set theory formulas that will help us perform the operations on sets. Not just operations on sets, we will be able to apply these formulas to real-world problems and understand them as well.

The formulas we will be discussing are fundamental and will be performed on two sets only. Before we delve deeper into these formulas, some notations need clarification. 

n(A) represents the number of elements in A 

n(A B) represents the number of elements in either A or B

n(A B) represents the number of elements common to both sets A and B.

  • n(A B) = n(A) + n(B) – n(A B)

We can use this formula to calculate the number of elements present in A and B’s union. This formula can only be used when A and B are overlapping and have common elements between them.

  • n(A B) = n(A) + n(B)

This formula can be used when A and B are disjoint sets such that they have no common elements between them.

  • n(A) = n(A B) + n(A B) – n(B)  

This formula is used when we want to calculate the number of elements in set A, provided that we are given the number of elements in A union B, A intersection B, and B.

  • n(B) = n(A B) + n(A B) – n(A)

This formula is used when we want to calculate the number of elements in set B provided that we are given the number of elements in A union B, A intersection B, and in A.

  • n(A B) = n(A) + n(B) – n(A B) 

If we want to find the elements common to both A and B, we need to know the size of A, B, and A union B.

  • n(A B) = n(A – B) + n(B – A) + n(A B)

In this formula, we are again calculating the number of elements in A union B, but this time the provided information is different. We are given the size of difference concerning B and difference concerning A. Along with these, we are given the number of elements common to A and BSet Theory Formulas

Example 2

In a school, there are 20 teachers. 10 teach sciences while 3 teach arts, and 2 teach both.

Determine how many teachers teach either of the subjects.

Solution:

Number of teachers who teach either of the subjects are:

n(A B) = n(A) + n(B) – n(A B)

n(A B) = 10 + 3 – 2 = 11

So, 11 teachers teach either of them.

Set Theory Notation

In this section, we will be talking about all the notations used in set theory. It includes the mathematical notation from a set till the symbol for real and complex numbers. These symbols are unique and based on the operation being performed.

We discussed subsets and power sets earlier. We will be looking at their mathematical notation as well. Using this notation allows us to represent the operation in the most compact and simplified way possible.Set Theory Notation

It makes it easier for the casual mathematical onlooker to know exactly what operation is being performed. So let us get into it one by one.

Set:

We know that a set is a collection of elements, as we have discussed before repeatedly. These elements can be the names of some books, cars, fruits, vegetables, numbers, alphabets. But all of these should be unique and non-repetitive in a set.

They can also be math-related such as different lines, curves, constants, variables, or other sets. In modern-day mathematics, you would not find a mathematical object so common. To define sets, we usually use the capital alphabet, but the mathematical notation for it is:

{} A set of curly brackets is used as the mathematical notation of sets.

Example 3

Write down 1, 2, 3, 6 as one set A in mathematical notation.

Solution:

A = {1, 2, 3, 6}

Union:

Let us assume we have two sets: A and B. The union of these two sets is defined as a new set that contains all the elements of A, of B, and elements present in both. The only difference is the elements being repeated in A and B. The new set will have those elements only once. In mathematical induction, it is represented using the logic ‘or’ in an intrinsic sense. If we say A or B, it means the union of A and B.

It is represented using the symbol:

Example 4

How would you represent the union of set A and B?

Solution:

Union of two sets A and B, also defined as elements belonging to either A, either B or both can be represented by:

A B

Intersection:

Let us again assume we have two sets: A and B. The intersection of these sets is defined as a new set containing all the elements common to A and B or all the elements of A, which are also present in B. In other words, we can also say that all the elements present in A and B.

In mathematical induction, the logic ‘And’ is used to represent the intersection between items. So, if we say A and B, we mean the intersection or the common elements. Only the elements present in both sets are included. 

It is represented using the symbol:

Example 5

How would you represent the intersection of A and B?

Solution:

The intersection of two sets is represented by:

A B

Subset:

Any set A is considered the subset of set B if all set A elements are also the elements of set B. It is a set that contains all the elements also present in another set.

This relationship can also be referred to as that of ‘inclusion’. The two sets A and B can be equal, they can also be unequal, but then B has to be greater than A as A is the subset of B. Further on, we will be discussing several other variations of a subset. But for now, we are talking about subsets only.

It is represented using the symbol: 

Example 6

Represent that A is a subset of B.

Solution:

This relationship of A being a subset of B is represented as:

A B

Proper subset:

Previously we were talking about a subset, now we ought to be looking at the notation for the proper subset of any set, but first, we need to know what a proper subset is. Consider we have two sets: A and B. A is a proper subset of B if all the elements of A are present in B, but B has more elements, unlike in some cases where both the sets are equal in several elements. A is a proper subset of B with more elements than A. Essentially, A is a subset of B but not equal to B. This is a proper subset. 

It is represented using the symbol in set theory: ⊂ 

This symbol means ‘a proper subset of.’

Example 7

How will you represent the relationship of A being a proper subset of B?

Solution:

Given that A is a proper subset of B:

A B

Not a subset:

We discussed that whenever all the elements of A are present in another set in our case, that set is B, then we can say that A is a subset of B. But what if all the elements of A are not present in B? What do we call it, and how do we represent it? 

In this case, we call it A is not a subset of B because all the elements of A are not present in B, and the mathematical symbol we use to represent this is:

It means ‘not a subset of.’

Example 8

How will you represent the relationship of A not being a subset of B?

Solution:

Given that A is not a proper subset of B:

A B

Superset:

Superset can also be explained using a subset. If we say that A is a subset of B, then B is a superset of A. One thing to notice here is that we used the word ‘subset’ and not proper subset where B always has more elements than A. Here B can either have more elements or an equal number of elements as A. In other words, we can say that B has the same elements as A or probably more. Mathematically, we can represent it using the symbol:

It means ‘a superset of.’

Example 9

How will you represent the relationship of A being a superset of B?

Solution:

Given that A is a superset of B:

A B

Proper superset:

Just like the concept of proper subset where the set which is the proper subset always has fewer elements than the other set, when we say that a set is a proper superset of some other set, it must also have more elements than the other set. Now to define it: any set A is a proper superset of any set B if it contains all B and more elements. This means that A must always be larger than B. This operation is represented using the symbol:

It means a proper ‘a subset of.’

Example 10

How will you represent the relationship of A being a proper superset of B?

Solution:

Given that A is a proper superset of B:

A B

Not a superset:

If any set can not be a subset of another set, any set can also not be a superset of some other set. To define this in terms of set theory, we say that any set A is not a superset of B if it does not contain all the elements present in B or has fewer elements than B. This means that A’s size can either be less than B or have all the elements present in B. In set notation, we represent this as:

It means ‘not a superset of.’

Example 11

How will you represent the relationship of A not being a superset of B?

Solution:

Given that A is not a superset of B:

A B

Complement:

To understand the complement of any set, you first need to know what a universal set is. A universal set is a set containing everything under observation. It includes all the objects and all the elements in any of the related sets or any set that is a subset of this universal set. 

Now when we know what a universal set is, the complement of a set, let us say set A is defined as all the elements present in the universal set but not in A, given A is a subset of U. This means a set of elements which are not present in A. It is represented using a script of small c:

Ac

It is read as ‘A’s complement’.

Example 12

We have a set of U but not A; how do you represent them?

Solution:

Given that these elements are not in A, we have:

Ac

Difference:

The complement of a set utilizes the function of the difference between a universal set and any set A. Now, what is the difference between sets?

In set theory, the difference between sets is a new set containing all the elements present in one set but not the other. So, assume we want to find the difference of set A with respect to B, we will have to construct a new set that contains all the elements present in A but not in B. Difference is a binary function. It needs two operands: the operator symbol we use is that of subtraction. So, let us assume we have two sets, A and B. We need to find the difference between them with respect to B. It will be a new set containing all the elements in B but not in A. This can be represented using the notation:

A – B

Element:

We know that a set consists of unique objects. These unique objects are called elements. An individual object of a set is called the element of the set. These are the objects which are used to form a set.

They can also be called the members of a set. Any set’s element is a unique object that belongs to that set. As we studied before, they are written inside a set of curly brackets with commas separating them. The set name is always represented as a capital alphabet of English. 

If any object, let us say ‘6’ is an element of a set, we write it as:

6 A

Where means ‘an element of.’

Example 13

A is defined as {2, 5, 8, 0}. State whether the following statement is true or false.

0 A

Solution:

As we can see that 0 is an element of A, so the statement is true.

Not an element of:

What does it mean for an element not to be a part of a set, and how do we represent it?

Any object is not an element of a set if it is not present in the set, or we can say that it is not in the set. The symbol used to represent this is:

It means ‘not an element of’.

Example 14

A is defined as {2, 5, 8, 0}. State whether the following statement is true or false.

0 A

Solution:

As we can see that 0 is an element of A, whereas the given condition states that 0 is not an element of A, so the statement is FALSE.

Empty set:

An empty set is a fascinating concept in set theory. It is basically a set containing no elements whatsoever. The reason we need it is that we want to have some notion of emptiness. An empty set is not empty. When you put brackets around it, it is a set containing that emptiness. The size of an empty set is also zero. Does it actually exist? That can be deduced from some theorems. It has unique properties as well, such as it is a subset of all sets. However, the only subset an empty set has in itself: an empty set.

There are multiple ways to represent it; some use empty curly brackets; some use the symbol Ⲫ.

Universal set:

As we discussed in the complement section, a universal set contains all the elements present in its concerning sets. These objects are distinct, unique, and not to be repeated. So, if we have set A = {2, 5, 7, 4, 9} and set B = {6, 9}. A universal set denoted using the symbol ‘U’ will be equal to set U = {2, 5, 4, 6, 7, 9, 10, 13}.

If you are given a universal set, you should deduce that it must contain some elements of different but related sets along with its own unique elements that are not present in the related sets. 

As we mentioned before, a universal set is denoted by the symbol ‘U’. There is no formula to calculate a single set from multiple sets. By this point, you must be able to reason that the constituent sets of the universal sets are also U’s subsets.

Power set:

In set theory, a power set of a certain set A is a set that includes all the subsets of A. These subsets include the empty set and the set itself. The number of elements in a power set can be calculated using a predefined formula 2s wheres is the number of elements in the original set.

A power set is the perfect example of sets within sets, where the elements of a set are another set. Any subset of the power set is called a family of sets over that set. So let us say we have a set A. The power set of A is represented using:

P(A)

Equality:

Any two sets are considered to be equal if they have the same elements. Now the order of these elements to be the same is not necessary; however, what is important is the element itself.

For two sets to be equal, their union and intersection must give the same result, which is also equal to both sets involved. Like in other equality properties, we use the equality symbol in set theory as well. If two sets A and B are equal, we write it as:

A = B

Cartesian product:

As the name implies, it is the product of any two sets, but this product is ordered. In other words, the cartesian product of any two sets is a set containing all possible and ordered pairs such that the first element of the pair comes from the first set and the second element is taken from the second set. Now, this is ordered in a way that all possible variations between the elements take place.

The most common implementation of a cartesian product is in set theory. Just like other product operations, we use the multiplication sign to represent this, so if we have set a and B, the cartesian product between them is represented as:

A x B

Cardinality:

In set theory, the cardinality of a set is the size of that set. By size of the set, we mean the number of elements present in it. It has the same notation as the absolute value, which is two vertical bars on each side. Let us say we want to represent the cardinality of set A, we will write it as:

IAI

This denotes the number of elements present in A.

For all:

This is the symbol in set notation to represent ‘for all.’

Let us say we have, x > 4, x = 2. This means that for all values of x greater than four, x will be equal to 2.

Therefore:

The symbol most commonly used in mathematical notation of set theory is off, therefore. It is used in its English meaning and represented by the symbol:

Problems:

  1. Prove that 21 A where A = {x : x N and 7 I x}.
  2. Find out the number of elements in the power set of A = {5, 8, 3, 4, 9}.
  3. Find out the union of A = {4, 6, 8} and B ={1, 2, 5}.
  4. In a school, there are 35 teachers; 15 teach sciences while 9 teach arts, and 6 teach both. Determine how many teachers teach both subjects.
  5. Find out the difference between A = {set of whole numbers} and B = {set of natural numbers} with respect to B.

Answers:

  1. Proof left to the reader
  2. 32
  3. {1, 2, 4, 5, 6, 8}
  4. 6
  5. {0}, this is not an empty set

Previous Lesson Main Page | Next Lesson