Defining Universal Sets

We've already defined whole numbers casually by {0, 1, 2, ...} and formally using Peano's Axioms. Let's analyze the Peano Axioms and understand why they work.

Set theory isn't something that came naturally in mathematics. The general idea comes naturally to us, of course, but it's so difficult to actually formalize that it wasn't done until Georg Cantor's work in the 19th century. Even then, there were problems. Bertrand Russell found a paradox in "naive set theory" in 1901, and even still inconsistencies may exist. Today, much work has been done in axiomatic set theory. I'm not going to get in to these axioms, but I will talk about how I like to define sets.

Most sets that we think of, such as {1, 4, 5} are subsets of some universe. In this case, the universe can be whole numbers, or it can be integers or reals. Defining these subsets isn't hard, it's defining the universal sets that proves tricky. Once you have the universal set, subsets can be defined using some rule that separates values in the subset from values outside the subset.

So how do we define these universal sets? My ideas on this have been shaped by ideas in computer science, which looks at data structures and functions. The way I tend to look at it, there are 3 ingredients that define U.

1) Constructors. These are functions that accept as input members of various other well-defined sets and possibly U as well, and use these inputs to construct a value in U.

2) Induction Rules. Suppose that X is a subset of U. We need a way to prove or disprove that X contains all of U.

3) Equality Rules. We need to know which members of the set are equal to one another. If we do not know this, we cannot know the precise structure of the set. How do we know that our definition of equality is legit? It needs to be defined for all values on U, which we can prove using our induction rules, and it must also satisfy the 3 properties of equivalence relations. That is,
Reflection: a = a
Symmetry: a = b implies b = a
Transition: if a = b and b = c then a = c.

Once these 3 rules are defined, we have a functioning universal set.

Notations: Formalizing Place-Value

Notation matters.

In my last post I called prime factorization a "notation" for the natural numbers. It is a formal way of representing them. Mathematically speaking, a notation is just a correspondence between 2 sets: the notation set, and the objective set. Every member of the objective set has a corresponding notation.

For example, take place-value notation, which is a notation for all whole numbers including zero. The whole numbers are defined one way, and they are the objective set. The place-value notation is defined another, and let's call it the notation set. We can place a correspondence between the two, which is just an "onto" function from the notation set to the objective set.

First, let's define the set of whole numbers using the following 5 rules. These 5 rules are a derivation of Peano's Axioms for Whole Numbers.

0 is a whole number.


For every whole number n, there is a whole number n', the increment of n.

Let X be a subset of the whole numbers. If 0 is in X and for every n in X, n' is also in X, then X contains all whole numbers. This is the principle of mathematical induction.

Equality:
For all whole numbers n, the increment n' is not equal to 0.


For all whole numbers n and m, n' = m' implies that n = m.

Using the principle of mathematical induction, these 2 rules for equality sufficiently define equality on all whole numbers. With these 5 rules, we can prove everything that we know about whole numbers. This includes the rules for addition, subtraction, multiplication, division, as well as the properties of prime numbers and number theory. They will also be the basis for one day proving or disproving the twin prime conjecture.

Now that the whole numbers have been straightened out, we'll take a look at our place-value notation. In this version of place-value, zero is represented not by 0, but by [], the empty list of digits, and 12:3 is equivalent to 123, just so that we have some notation for meaning "append onto".

Let D be the set of digits in this place value system, and for arguments sake let it contain 10 digits, with a correspondence to the first 10 whole numbers. This correspondence will be mapped by the function f.


f(0) = 0
f(1) = 0'
f(2) = 0''
...
f(9) = 0'''''''''

Of course, we can let this contain d digits and make this more general. I wrote down some basic rules for place-value notation.

[] is in the place-value notation.


For every value n in the place-value notation, n:d is also in the place-value notation, where d is a digit.

Let X be a subset of the place-value notation. If [] is in X and for every n in X and every digit d, n:d is also in X, then X contains all of the place-value notation.

Equality:

For all place-value n and digit d, n:d is equal to [] if and only if n=[] and d=0.

For all place-values and and digits and .


Now that place-value notation has been defined, with 5 rules that look strikingly similar to the 5 rules of whole numbers, we may define a correspondence between the 2. Every place-value gets mapped to a whole number. We'll call this function g.


g([]) = 0
g(n:d) = 10*g(n) + f(d)

First of all, note that this function is now properly defined for everything in the place value notation because of its version of the induction principle. Furthermore, and this would require a formal proof, we can show that equal inputs produces equal outputs.

The multiplication and addition operators on whole numbers can be defined on whole numbers using the axioms we have, even though I haven't done it explicitly here.

Now in order to prove that the function g specifies a notation (that is, it's onto), we need to show that for each whole numbers n, there exists some place value m such that g(m) = n.

Once that is proven (and it can be) then place-value notation can be used as a substitute for W and in fact we can write whole numbers using place-value notation and not have to worry about converting between the two because we know that there is a correspondance.

Prime Factorization

When dealing with the natural numbers, we often want to factorize them. That is, find numbers that multiply to the original number. A composite number is a number that can be decomposed through factoring.

For example, 6 is a composite number. It can be rewritten as 2 x 3. The number 7, on the other hand, is not composite. The only natural numbers that multiply to 7 are 1 and 7. Because there is still a 7 in the product, we have not decomposed it into smaller numbers.

The number 7 is a prime number. A prime number is a natural number that is divisible by only 2 distinct numbers: itself and 1. Prime numbers are not composite. Every natural number is either prime or composite, except for 1, which is neither.

There are an infinite number of prime numbers. This is an important fact given the goal of this blog, so later on I'm going to describe some of the proofs of this. For reference, all of the primes less than 50 are listed below.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ...

Because the primes form an infinite sequence, we can index them. For example, lets let denote the prime number for all .

In other words , , , , etc.

We can form a new notation for numbers out of this. There's a theorem that let's us do that, and it's called the fundamental theorem of arithmetic, or FTA. This theorem states that all natural numbers can be uniquely factorized into prime numbers. Let's look at some examples.

The number 12 can be factorized into 2 x 2 x 3, which are all prime numbers. No other number has the same factorization. This can be written compactly using exponents.



Now consider the number 490.



This example showcases rules that we'll need for writing numbers in factorized form. I have included the "3" term, even though it appears zero times in the product 2 x 5 x 7 x 7 = 490. The zero term serves as a placeholder, just as the decimal number 304 also requires a placeholder. I don't include a term for the prime number 11, because a leading zero would be superfluous, just as we don't normally write 032.

For the record, terms like are equal to 1, so they don't affect the product at all. 1 is written as the null product (no prime numbers multiplied together). There is no way of writing zero in this form. Therefore, it is a notation for natural numbers (which doesn't include zero) and not for whole numbers.

In the next few posts, I'm going to discuss this notation in more depth using more symbolic notation and mathematical language, and then go further into what this notation is good for.

Place-Value Notation: Some Pros and Cons

Just so there will be no confusion, I'm going to say that the set of whole numbers (represented by W) contains zero. The natural numbers or counting numbers (represented by N) do not contain zero. As far as I know, definitions vary and there is no agreed upon standard, so this is just my personal preference:

It's convenient that every whole number can be represented as a finite sequence of digits. For example, the number 123 is represented in decimal as - well - '1', '2', and '3' in that order. Each representation is unique. When I write 123, it's entirely clear to which number I refer. Likewise, there is no alternate way of writing 123, so long as we disqualify 0123 for its leading zero.

We've all been working with place-value notation our entire lives, so we may forget why it's so useful. Think about the most common operations that you perform on whole numbers:

Comparison
Addition
Subtraction
Multiplication
Division

Three of these operations can be carried out very simply with place-value notation. When performing addition, subtraction, or comparisons on paper, we only need to look at each column of digits once.

This is so efficient that computers and electronic systems perform these operations similarly to the way we do them by hand. Granted, they are using a base-2 system where the only possible digits are 0 and 1, but it is nonetheless a place-value numbering system.

Multiplication and Division are a little bit more difficult to do, but still manageable. In the multiplication algorithm , each digit must be multiplied with every digit of the other number. This is fundamentally more complex than addition.

Imaging trying to perform these operations with Roman numerals. If those hadn't been replaced with a place-value system (base 10 or otherwise), western civilization could not have advanced technologically as much as it has.

One thing about mathematics is that notation matters. If your concrete representation of abstract concepts does not mesh well with the operations you'd like to perform on those objects, not only will your calculations be slower, but you may overlook techniques that in an alternate notation are plainly obvious.

Believe it or not, some operations are actually quite difficult to perform with our place-value system. Consider the following operations.

Finding the least common multiple of 2 numbers
Finding the greatest common factor of 2 numbers

How are we supposed to find these values? Trial and error is a painfully slow technique. In fact, it is "exponentially" more difficult than addition.

Fortunately, there's another numbering system for the natural numbers only - prime factorization - in which these operations can be performed very quickly. Multiplication and division can also be performed more rapidly in factorized form.

What's more startling is that addition, subtraction, and comparisons, which are so simple in place-value notation, become utterly impossible with factorized numbers.

We'll look into this mysterious notation in the next post.

Why we learn Fractions

We teach fractions at the elementary school level, and it is probably one of the more complex concepts that we expect kids to learn.

There's good reason for this. Without a working knowledge of fractions, higher math becomes impossible. Algebra, geometry, trigonometry, and calculus can only be learned on a solid foundation that includes the ability to understand and manipulate fractions. Students who have gaps in their knowledge of fractions will have tremendous difficulty later on.

Fractions are also very useful. Most quantities are easiest to express as fractions. We often want to convert these to decimals or to scientific notation in order to make it easier to analyze data, but the quantities still start as fractions. I would consider decimal notation to be a higher-level form that can only be understood by those who understand fractions first.

Why is this relevant to us? It's because the study of fractions is where we get our first look at prime numbers. It's still the main reason we study prime numbers, and without them, prime numbers would be a curiosities only studied in higher institutions of learning. Instead, prime numbers are a part of a fundamental education in mathematics that everyone should have.

In the next few blog posts, in order to build up an extensive archive we can draw from later, we shall explore the link between fractions and prime numbers in detail.