As someone who enjoys math and (more recently) CS, it is only appropriate that I open my blog with a concept related to the two.

In this post, I intend to demonstrate how the binary system is the smallest such system which can be used to represent every single integer uniquely in one way, providing motivation for why binary is often called the “language of computers” (other than beep boop).

The word binary comes from the latin word bini, which means “two together”. It hence makes sense that the binary number system has only two numerals, represented by $0$ and $1$. For comparison, the number system we are all used to—the base-10 system— has 10 different numerals which we can count on our fingers ¹.

This means numbers in binary only contain these two numerals, for example $110101$ is a binary number. But how does one count with this system?

Counting in Binary

Counting using the binary number system is quite simple. Like our base-10 system, the leftmost symbol has the highest value in binary, and as you proceed rightward, the values become smaller. In base-10, however, you only ‘increment the right’ after the left symbol has surpassed 9, resetting that symbol. This is contrasted to binary, where you only have 0s and 1s and ‘increment the right’ immediately if the left symbol is a 1, resetting it back to a zero.

For example, in base-10, when counting, we proceed as:

However, in base-2:

But what does each symbol, called a bit, represent?

You may correctly guess that it is something related to the digit 2— after all our entire counting system is based on 2 symbols. Its helpful to think of a binary number as a board of switches— either on ($1$) or off ($0$).

So, the example we gave in the introduction is:

and in this system, what is on or off is a power of 2! That is;

So the value of $110101$ in base-10 is:

where we only sum the powers which were $\text{on}$.

Now we are ready to give a formal definition to any binary number $k$:

But are we sure this is unique?

That is, how can we be sure that every $k$ has exactly one and only one binary representation which no other $k$ has? We seek to prove this in the following section.

Proof of Uniqueness

We proceed by induction.

Our base case is $1$, which can be expressed as $2^0$ in base-10 and also $1$ in binary.

This is a unique representation as $1$ is the smallest natural, positive number. Hence all other numbers are greater than 1, and hence have more bits ‘to the left’.

Now assume that the conjecture holds for all naturals $1,2,3,\ldots,b$. The number $b+1$ is our focus. One idea to show that the conjecture holds for $b+1$ is to argue that since it is either even or odd, it can be expressed as $2m$ or $2m+1$, respectively, where $0<m<b<b+1$, and we would be done, as $m$ has a unique binary representation ${b_i b_{i-1} b_{i-2}\ldots b_2 b_1 b_0}$ and hence both:

as needed.

However, this argument does not exactly address the uniqueness clause. The following argument resolves this.

Once again focusing on $b+1$, consider the number $2^k$, which is the largest power of two such that $2^k\leq b+1$.

If $2^k=b+1$, our work is done, as $2^k$ trivially has a binary representation which is unique as all powers of two less than $2^k$ sum up to exactly $2^{k}-1=b$. This fact is demonstrated in Proof of Binary Powers Sum, or by induction ².

Otherwise, $2^k<b+1$, and $b+1-2^k<2^k$ must be true, as the converse implies $b+1>2^{k+1}$, and we simply pick $k=k+1$.

Now, $b+1-2^k<2^k<b+1$ indicates that $b+1-2^k$ can be expressed using binary according to our inductive hypothesis that all numbers $<b+1$ have a binary representation. And $b+1-2^k+2^k=b+1$ yields back $b+1$!

This means that we can simply add a $1$ to the binary representation of $b+1-2^k$ in the $k^{\text{th}}$ index and obtain $b+1$, as needed. And this representation is also unique due to the fact we showed that it is less than $2^k$ coupled with $\sum_{i=0}^{k}2^i =2^{k+1}-1$.

Proof of Binary Powers Sum

In my opinion, this proof demonstrates why binary is such a powerful tool. Let us proceed.

Begin by calling the LHS of this lemma $P(k)$. Notice that by the definition of a binary number, $P(k)$ has a binary representation that is exactly:

as all terms are summed or ‘on’, this is a string of 1s which is of length $k+1$.

Then, it is clear that $P(k)+1$ is simply:

due to the rules of binary addition.

But notice how this can also be written as a binary number with a single 1 in the $k+1$ index. Which is exactly the definition of $2^{k+1}$!

Hence, taking 1 away from $P(k)+1=2^{k+1}$ resets the $k+1$ index and leaves us with $P(k)$, as needed.

Significance of Binary

Now that we’ve established why binary is such a powerful number system, we begin to understand its natural fit in digital circuitry: a complete numerical system built on two simple states—on or off. But how these states came to be mathematically expressed owes much to George Boole’s groundbreaking work on Boolean Algebra.

George Boole described a new subject in algebra, using 2 main values— either true (1) or false (0)— to describe logical, and not numerical operations. Instead of the familiar addition, subtraction, multiplication, and division operations, Boolean Algebra is concerned with conjunction, disjunction, and negation of variables which can be true or false. A closer look of this algebra follows.

On Boolean Algebra

We begin by defining the two values in this algebra: $1$ represents true, $0$ represents false. Now, we can define the 3 operations using $\wedge, \vee,\neg$ for conjunction, disjunction, and negation, respectively:

Thus a new subject is axiomatized³ and born, symbolizing logic (literally and metaphorically!)

However, as you may guess, this algebra was quite abstract and separate from the practical engineering world— beyond its use in philosophy and propositional calculus. This is, until Claude Shannon published his thesis “A Symbolic Analysis of Relay and Switching Circuits,” which recognized that Boolean Algebra could be used in electrical relays to perform both logical and numerical operations!

Claude Shannon’s eureka moment

Relays were electrical components which acted as switches— either preventing or allowing current flow. In his thesis, he mathematically proved that a physical system using such relays inherited all the power of a binary numerical and logical system— and could hence perform all of the same operations. Where they were previously used only for telegraphic communications, they could now be used to design precise circuitry.

Shannon noticed that the current flowing through relays could be modeled and standardized with Boolean algebra.

For example, he proposed wiring relays in a series arrangement in order to describe logical conjunction— if both relays were on or “high”, then current would be allowed to flow, and the output would also be “high”. However, if one was off, then current outside of the construction ceases to flow, perfectly matching the behavior of the boolean AND!

Similarly, disjunction would be formed by wiring the relays in parallel, yielding the exact same outcome as $\vee$ would!

Where $A.\hspace{-0.2em} B=A\wedge B$ and $A+B=A\vee B$.

This gave birth to logic gates, fundamentally transforming the digital circuit industry. No longer was circuit design a matter of trial and error; it became a precise mathematical endeavor. Engineers could now create intricate electronics with predictable, reliable outcomes.

As the 20th century marched on, 8 bits became a byte, and relays gave way to vacuum tubes, then transistors, then integrated circuits. Yet, the logic underlying all this hardware remains the same: at the heart of modern computation are the simplest of ideas—$0$s and $1$s, off and on, false and true. From this division, we’ve built machines that not only calculate but connect us— even this text you read is a bunch of $0$s and $1$s. And that, in itself, is a remarkable testament to the power of binary.