Proof and Set Theory | Part 1 | Understanding Cryptography Through Mathematical Primitives

Paul Vienhage - Smart Contract Auditor and Engineer
October 18th, 2018
Proof and Set Theory Understanding Crpytog Image

This article is a start to a series designed to introduce the mathematics underlying the cryptography underlying cryptocurrenices. The mathematical object called a group is, like the transmission of the blockchain it is complicated and specific, and if you want to build or maintain a car you need to understand it. Most people coming from a computer science background haven’t seen groups or even the ways that mathematicians talk about them. This post is designed to teach you just enough mathematical language to learn what a group is so that you can fully understand why the blockchain works.

First, we will learn about the language of mathematics and its formalization in logic. Then we will learn about the subject which is the foundation of modern mathematics. Finally, we will mix these two and learn about infinity as an example of how they are used.

How math approaches truth

There are many types of truth and to talk too much about them would require dipping into philosophy. However, mathematics at its core is a language designed to formalize truth and attain a level of abstraction where each statement one makes can be proven to be true. The distinction between math and the sciences is that science derives its method of elucidating truth from experimentation while math derives its truth from pure logic. In mathematics “proofs” take the place of tests in science. A proof is a collection of logical statements based on given assumptions which imply the truth or falsity of a statement.

Basic Logic

To construct a proof we use formal logic. We label statements true or false and can string together several statements using logical operators. We then can label a statement combined with a logical operator as true or false following the rules of that operator. For example: “I am a dog” is a false statement “I like eating meat” is a true statement and“I am a dog, and I like eating meat” is false while “I am a dog, or I like eating meat” is true. Logical implication is one of the most important of these operators. It is defined using the following truth table:

The first column is the truth of the statement p, the second the truth of q and the third is the truth of p implies q.

Implication is how we can make conclusions using logic. For example, if we can prove that “I am a dog” implies “I like meat” and something is a dog we can then conclude that it likes meat. This process is called deductive reasoning.

Combined with the final logical components, “for all” and “there exists,” we can make logical statements strong enough to communicate all of high-level mathematics. To employ these, we need to set a universe which contains any possible statements or objects. Given a universe of possibles we can make statements about the universe, for example, we could say that “All dogs go to heaven” translated logically is “For all elements of the universe of dogs the statement ‘This goes to heaven’ is true.” “There exists” means that there exists an element of the universe which has a statement hold for it.

Proof Strategy

A proof is a set of logical implications leading from assumptions to conclusions. To make usable mathematical statements, we need to prove implications so that we can draw conclusions. In mathematics, the assumptions made that all other statements are proved from are called axioms. To prove an implication we have three techniques: direct proof, proof by contradiction, and proof by contraposition.

  • A direct proof assumes that the statement before the implication is true then logically reduces the assumed statement to the implied statement.

Example 1: If we assume “For all dogs in the set of dogs, the dog likes to eat meat” then we can prove that “If Fido is a dog then Fido likes to eat meat.” by assuming Fido is a dog then from the axiom “All dogs like to eat meat” we can conclude that Fido likes to eat meat. Thus we have directly proven the implication.

  • A proof by contradiction assumes that the first statement is true and the second is false and then reduces that to a logical contradiction.

Example 2: Assuming the same axiom that “All dogs like to eat meat” we can prove that “If Fido is a dog then Fido likes to eat meat” by assuming that Fido does not like to eat meat and that Fido is a dog. Applying our Axiom, since all dogs like to eat meat and Fido is a dog then Fido likes to eat meat. However, we have reached the contradiction that Fido both likes and dislikes meat. Thus our assumption that Fido does not like to eat meat and that Fido is a dog is impossible, and in all other cases, the implication is true ergo the implication is true in all cases.

  • A proof by contraposition assumes that the statement after the implication is false then proves that the statement before the implication is false. This establishes the implication because the only case where the implication is false is (True) implies (False), but if we establish that statement two (False) implies statement one (False), then that case can’t happen. The easiest way to see how this works is to look at the implication truth table.

Example 3: Again taking “All dogs like to eat meat” as an axiom we now prove that “If Fido is a dog then Fido likes to eat meat” by instead proving that “If Fido doesn’t like to eat meat then Fido is not a dog.” If Fido doesn’t like to eat meat and Fido is a dog, then by our axiom, Fido likes to eat meat but this a contradiction. Because of the contraction, we know that if Fido doesn’t like to eat meat, then Fido isn’t a dog, and by contraposition “If Fido is a dog then Fido likes to eat meat.”

Basic set theory

Now that we have enough logic to do mathematics, we will do some. The current foundations of mathematics are built from a subject called set theory. A set is a collection of objects, for example, S={pineapple, {1}, blue, ℤ}. This notation means S is a set containing pineapple another set containing the number one, the concept of blue, and the set containing all whole numbers. If you can put it between brackets, you can put it in a set. We can also define a set by stating a property that each element follows. For example, S={x | x=0 mod 2} is the set of all numbers which have the property that those numbers are divisible by 2 (i.e. the even numbers). We say that an element is in a set if the set contains it, we denote that as a∈A. There is a set which contains nothing called the null set denoted {}. Next, we cover some operations on sets.

  • If we have a pair of sets A and B we define their union A ∪ B = { x | x ∈ A or x ∈ B }. For example the union of {1, 2, 3} and {2, 3, 4} is the set {1, 2, 3, 4}
  • We define their intersection as A ∩ B = { x | x ∈ A and x ∈ B }. For example the intersection of {1, 2, 3} and {2, 3, 4} is the set {2, 3}

  • The power set is the set which contains all of the subsets of the given set and is denoted P(S). For example the power set of {1, 2} is {{}, {1}, {2}, {1, 2}}.

The basic structures and operations of set theory are simple enough but this simplicity is deceptive, there are still mathematicians researching set theory. One of these areas of complexity is the construction of non-paradoxical axiomatic set theory. Consider for example the set S = { X | such that X is a set} which is the set of all sets. Does this set contain itself? You can prove both that it does and does not from this definition, a paradox. So we restrict the theory in ways to prevent these paradoxes. One of the main models is Zermelo–Fraenkel set theory, but other stronger models exist. If you want to learn more about set theory we recommend: Lectures in set theory by Thomas Jech.

Infinite infinities

One of the most interesting subjects in set theory is cardinality. It is the study of how we define the size of a set. For the finite sets, this is fairly straightforward as the size is just the number of elements, but we don’t have enough time to count the elements of the infinite ones. So to define “size of a set,” we say that things are the same size if there is a function which takes each element and maps it to a single element of another set and that function maps to each element of the target set. We define the notation |S| to be the cardinality of the set. For example we say |{1,2,3,4}| = 4 and to prove that |{65, 13, 27, {}}| = 4 as we can define f such that {f(65) = 1, f(13) = 2, f(27) = 3, f({}) = 4} = {1,2,3,4} and since the size of {1,2,3,4} is 4 we have proved that the size of {65, 13, 27, {}} is four. This counting method makes intuitive sense, two collections of things are the same size if for each element of one collection it can be matched to an element of the other collection with no leftovers.

However, this method does give counter-intuitive results as the even numbers are the same size as the natural numbers. A common intuition is that there are half as many even numbers as natural numbers, but this is wrong. Consider the map f(x) = 2x, using this we can show that for each even number there is exactly one natural number, so there are the same amount of natural numbers as natural numbers.

We can use the same logic to say that there are the same amount of numbers divisible by 3,4, 27 or 45 billion. Can we find something which is larger than the infinity of natural numbers?

A good suggestion might be all of the fractions. However, using a clever listing we can assign each fraction to a natural number. We write a table with each natural number on the x and y-axis then each slot in the table is the rational of the y-axis divided by the x-axis. We can assign a natural to each fraction in the table using the following pattern:

This same method can be used to prove that there are the same number of points (x,y) where x and y are natural as natural numbers. In fact, we can even extend it to prove that there are the same number of points (x₁,x₂,..,xₘ) which have natural number coordinates as the naturals. This means that an arbitrary number (which is finite) of natural infinities is the same size as natural infinity. That fact makes finding a larger infinity seem very hard, but there is an easy example.

Claim: The real numbers have more numbers than the natural numbers. Proof: Assume that the real numbers and the natural numbers have the same size. Then there is a way to list all of the decimal numbers, as we set the index of the real number in the list to the natural number it corresponds too. If we consider this list of decimal numbers we can form a decimal number which is not in the list via the following process:

Let a₁ be the first decimal of the first number a₂ be the second decimal of the second and so on, then let bₖ= aₖ+1 if aₖ <9 and bₖ = 0 otherwise. We construct a decimal, not in the list b = 0.b₁b₂b₃ …. which is not in the list because it differs from each decimal in the list in at least one place. But we had assumed that the list contains all of the decimals, a contradiction. Via proof by contradiction, there are more real numbers than natural numbers.

In this post, we have covered the fundamental language of mathematical communication and the basic set theory needed to learn abstract algebra. In the upcoming posts, we will dive into the actual abstract algebra.