# Introduction to Sets

## by Subhomoy Haldar

Set Theory - Part 01 - Also a ramble on the probable history of numeric sets

# Introduction

I will start by quoting a Wikipedia article$^1$ and disappointing everyone:

“Set theory is seen as the foundation from which virtually all of mathematics can be derived.”

Even though it is frowned upon in academia to quote a well-researched, closely monitored and meticulously maintained, pristine Wikipedia article, I doubt that most Mathematicians will refute this argument. In fact, any sensible and well-structured course in (Pure?) Mathematics should start with an introduction to the subject, a few applications, and then get down to define the various structures and properties in terms of Set Theory and Propositional Logic. Any course that starts with the supposition that “you’ve done this already in High School, and I will not repeat it” will probably be one you end up having little to no recollection of.

Sets are the prerequisites for most abstract mathematical structures. Groups, rings, fields, etc in Modern Algebra are all derived from sets and applying a handful of properties on them. Similarly, mappings are rules connecting the elements of one set to another. This forms the basis for all functions and therefore, all of analysis and calculus. This article (and the ensuing series) aims to rectify any gaps in your understanding of this vital concept. I will try to provide a gentle introduction to the simple, yet powerful theory of sets.

# Definition

We define a set as a collection of distinct objects called elements.

Note that we’ve defined two things here:

1. Sets - our primary focus
2. Elements - the objects inside the sets - these may be sets themselves.

The power of the set lies in its simple definition. This simplicity allows sets to be used anywhere a collection of similar objects is concerned. Fortunately, this scenario is not difficult to contrive. This is one of the reasons why Set Theory is important as a foundation. It is the mathematical analogue of the letters of the alphabet.

# Examples of Sets

## Set of items on your desk

Consider your desk. It is very likely that you have one or more writing instruments like a pen or a pencil or something similar. I’ll hazard a guess that unless you’re an ultra-minimalist, you’ll most likely have a notepad or something similar to write on. This set therefore, has two elements (at least), based on the assumptions I made: the pen and the notepad.

We are good here because the items in consideration are tangible and real, physical objects. It is not necessary for an element to be physical. We can even describe a set of human emotions. It may be finite or infinite, but it is still a valid set. We can describe and categorise emotions with the help of our language.

Anything that can be described in some manner can be an element of a set.

## Set of letters in the word “example”

An easy one. The elements are: $e, x, a, m, p, l$. Note that the $e$ occurs only once. This is a property of sets that I will elaborate later. Let’s take a similar example: the set of letters in the word “testament”. The elements are $t, e, s, a, m, n$.

## Set of prime numbers

This is our first concrete example of an infinite set.$^2$ The elements of this set are those positive integers that satisfy the primality property: it is only divisible by 1 and itself.

The first and least prime is $2$. The next one is $3$, then $5$, and so on. There is no largest prime number. Read this post to learn how to prove this.

An observation we can make is that the elements themselves can be derived from a larger set of more general elements. In this example, it would be the set of positive integers. I urge you to keep this in mind when we discuss the concept of subsets and supersets.

## Various Numeric Sets

I figure it’s not the right thing to do if I introduce you to the set of prime numbers and not tell you what types of numbers exist. Truthfully, numbers do not “exist” at all. They are a part of our collective imagination - a social construct that helps us make sense of the world, physical objects and other parts of our collective imaginations. Like currency, grades, etc.

### Natural Numbers ($\mathbb{N}$)

It is the most basic and most important set of numbers that we use (according to me). Others are merely extensions of this.

The first set of numbers we are introduced to is the counting numbers or Natural Numbers. Counting developed when we needed a way to keep track of possessions, be it cattle or merchandise or any physical thing. It is essentially a way to map each object present to a social construct called a “number” such as one, two, and so on.

Historically, these natural numbers have been represented by various symbols: tally marks, diagrams, digits, etc. Today, we widely use the arabic numeral system to represent natural (and other sorts of) numbers in the decimal system. It is the most basic and most important set of numbers that we use (according to me). Others are merely extensions of this. The set of naturals may or may not include $0$, depending upon which definition you choose to accept. In most Indian textbooks and classrooms, natural numbers start from $1$. Everywhere else in the world, however, the set starts from $0$. And you’re generally considered inadequate when you mention the former and not the latter. I speak from experience.

### Integers ($\mathbb{Z}$)

At some point in history, we humans realised that not all operations on numbers involve counting up. Some involve counting down, sometimes even below zero. We collectively learned the concept of negative and positive numbers, or Integers $^3$ as a whole. These come in handy when we keep track of credit, loans, and other fiscal constructs, where quantities are allowed to flow the other way. These are the second most important set of numbers in my opinion.

### Rationals (or Fractions) ($\mathbb{Q}$)

We were going along our merry ways, satisfied with the new number system that accounted for the deficits as well. Then at a particular juncture, we realised that not all constructs are a unit. Sometimes, they can be broken down (sometimes literally) into smaller pieces. These pieces are just as tangible as the original - hence, they cannot be equivalent to zero. To fix this issue, we came up with the concept of rationals, or fractions: that is, parts of a whole. The fraction $\frac{2}{5}$ means the quantity represents two parts out of five, where all five are needed to make a whole. A very useful set of numbers indeed.

### Reals ($\mathbb{R}$)

Eventually, people like the Greeks discovered that some numbers like $\sqrt{2}$ are not rational.$^4$ This opened up the floor for discussion on a possibly larger set of numbers (even if people were against this “abomination” for a while). Gradually, we all learned to accept this new number system as the most general one, including all the ones we’ve come up with so far and have stuck with it for a really long time. In fact, the set was convenient for so many applications that we began calling them reals after a while. We were in for a rude awakening soon enough.

### Complex Numbers ($\mathbb{C}$)

The idea of reals was so natural, so intuitive, that we pleasantly forgot that all numbers are social constructs and they are what we collectively imagine them to be. Consequently, when Cardano$^5$ encountered negatives inside radicals for the first time while trying to solve cubic equations, he was appalled and termed these solutions to be imaginary; these cannot exist or be used in real life scenarios, or so he claimed. Clearly, he had not met the electronic and electrical engineers of today (or the late 1900’s). Anyway, these are a larger set of numbers than the reals and are thoroughly fascinating.

### Quaternions and beyond

Notice a pattern here? We find there’s more things we can do with numbers and consequently, there are more numbers to find. This is an example of evolution of concepts. Our collective wisdom about an imaginary construct becomes more refined as we find novel ways of utilising our own creations.

So we found out that adding another dimension to the representation of numbers gave us the complex numbers from the reals. Hamilton$^6$ figured that if we add two more (not one more) dimensions, we can preform more operations on them as well. That was how the Quaternions$^6$ came to be. I will not discuss them any further, so if you’re interested, do check them out yourself! They come in handy when dealing with 3D motion and representation.

I suppose that’s more than enough for examples. Let’s discuss some properties of sets.

# Properties

## A set can have a finite or infinite number of elements.

The size or element count of a set is its cardinality and we will discuss it at length in a different article. In the examples I mentioned, the set of items on my desk and the set of letters in “example” are finite, and the other sets are infinite.

## No element repeats in a set.

Each element appears exactly once. This uniqueness property is a salient and distinctive property of sets, which we use extensively in fields related to mathematics such as programming. A consequence of this property is that if we add an element that is already present in a set, the set does not change. The size does not increase, and the elements stay the same.

## An element either belongs to the set, or it does not.

We denote this using the symbol $\in$ for the former and $\notin$ for the latter. Suppose the element concerned is $4$, and the set is the one in the third example, i.e. the set of prime numbers. 4 does not belong to this set. However, another element, 2, belongs to this set. The two conditions are always mutually exclusive in Naive Set Theory. This is not the case in other Set Theories, like in Fuzzy Set Theory, where there is a probability of membership for an element.

## Sets are unordered…

… unless we specifically say that it is an Ordered Set. An ordered set has several desirable properties that we use when we the order of elements is as important as their membership. We can represent the latter as a plain old set in a few different and creative ways. Maybe a topic for another time.

One more thing I want to introduce now is the concept of the null set, or …

# The Empty Set ($\varnothing$)

There is a special set called the empty set and represented using the symbol {}, $\varnothing$ or $\emptyset$, not the Greek letter $\phi$ (pronounced phi). (Don’t feel too bad, I made the same mistake as well.) It is the defined as the set containing, unsurprisingly, no elements. In terms of the elements, we can say that if $x$ (say) is any element, then it does not belong to $\varnothing$.

This set is important when we want to show that some statement is false because it applies to no element. More on this when we discuss Proof Techniques. Conversely, some implications (if-statements in Mathematical Logic) can be considered to be true when they are applied on an empty set. This is admittedly counter-intuitive. We rationalise this phenomenon by:

1. Assigning a name to it - a vacuous truth.
2. Considering the scenario - since we cannot find a counterexample for it, we cannot disprove it. Hence it is true.

From a programmer’s point of view, think of it as iterating over an empty collection or an iteration condition failing at the very beginning - since there are no elements to test against, the result remains vacuously true.

# We assume some_set and test() are defined
result = True

for element in some_set:
result = result or test(element)

# Process result
print(result)


If some_set is empty, the result stays True.

For a simple (albeit weirdly meta-cognitive) example, consider the following statement:

“The examples I come up with are great!”

This statement is true because I experience writers’ block the moment I need to make use of my creative abilities to synthesise relevant examples. Consequently, the set of my ideas is empty. Since there is no idea to test for greatness, the statement is vacuously true.

I can change the statement to be “The examples I come up with are horrible!" and it’ll still be true. There is no way I can disprove it if there are no elements to test the statement against! This is one of the caveats which people get used to in Mathematics.

On that note, let’s conclude.

# Conclusion

I have barely scratched the surface in this post. I briefly mentioned why sets are important. Then I presented the very simple definition of a Set. This is admittedly the definition in Naive Set theory. For our purpose, though, it is sufficient. I proceeded to ramble on about some examples of sets, both finite and infinite. Then I mentioned the properties of a set, with a little bit of explanation for each. Finally, I mentioned about the very special - null set or $\varnothing$.

In the next post, I will discuss about the cardinality of sets, the various ways in which we represent them, and then, various operations defines on sets. I hope you’ve enjoyed reading my post and that I have been able to teach a few new things about sets (or related constructs). Until next time!

1. Set (Mathematics) - The Wikipedia article in question.
2. Proof: There are infinitely many primes - A simple proof by contradiction that is due to Euclid.
3. Integers are called Zahlen in German. Presumably, the symbol was kept to honor the German name because some of the earliest work in the field of integers was done by German mathematicians.
4. Proof: $\sqrt{2}$ is irrational - Another proof by contradiction. It shook the Greeks to their core when they realised that such a useful number (due to the Pythagorean formula) is un-Godly (i.e. not an integer).