Part II

(4) Infinity

During the days near 1900 struggling with
axiomatic set theory, there was also
struggling with the concept of infinity
or infinite.

We say that two sets A and B have the same
cardinality, essentially are the same
size, if they can be put into 1-1
correspondence.

Okay, set B is a subset of set A
provided each element of B is an element
of A. B is a proper subset of A if A
contains some elements not in B, that is,
if B is not all of A.

Then a set is infinite if it can be put
into 1-1 correspondence with a proper
subset of itself. A common example is to
let A be the set of natural numbers and B
be the set of even (can be divided by 2
with no remainder -- 4th grade math)
natural numbers. Then B is a proper
subset of A, and, for each natural number n
in A, let it correspond to the natural
number 2n in B. Presto, bingo, we have put
A and B into 1-1 correspondence. So, set
A is infinite.

A set that is not infinite is finite.

Similarly sets of integers, rationals,
reals, and complex numbers are all
infinite.

Not very difficult to see. the set of
natural numbers has the same cardinality
as the set of integers, that is, the
natural numbers and the integers can be
put into 1-1 correspondence.

Any set that can be put into 1-1
correspondence with the natural numbers,
has the same cardinality as the natural
numbers, is said to be countably
infinite.

Curiously, the rationals are countably
infinite. To show this, use the clever
Cantor diagonal process (lots of hits at
Google).

Is the set of reals countably infinite?
No, and there is a short,
clever argument that
shows this. So, the cardinality of the
set of reals is larger (after we handle
some details) than the set of natural
numbers.

Is there a set D with cardinality greater
than the natural numbers but smaller than
the cardinality of the set of real
numbers? Difficult question. That there
cannot be such a set D is the continuum
hypothesis (CH). As can see at
Wikipedia, this question was settled by
work of Kurt Gödel in 1940 and Paul Cohen
in 1963: The result is that the CH is
independent of Zermelo–Fraenkel set
theory with the axiom of choice. By
independent we mean that we can assume
that the CH is true or false and cannot
get a contradiction. This work has been a
bit amazing, even philosophical.

Understanding infinity is important, and
we have done a good job at that. Unless
we are down in the basement of
foundations, we at most rarely consider
the continuum hypothesis.

There is a theorem
that for any natural number n,
we have

1^3 + 2^3 + ... + n^3 =
n^2(n + 1)^2 / 4

We can prove this by mathematical induction.
We want a proof that works for
any natural number n, and for this
we use the definition (above) of the
natural numbers.

So, first we check if the equation
is true for n = 1:

1^3 = 1

and when n = 1

n^2(n + 1)^2 / 4 = 1 (2)^2 / 4 = 1

So, the equation holds for n = 1.

Suppose the equation holds for some
n and check the equation for
n + 1:

1^3 + 2^3 + ... + n^3 + (n + 1)^3 =

n^2(n + 1)^2 / 4 + (n + 1)^3 =

n^2(n + 1)^2 / 4 + 4(n + 1)(n + 1)^2 / 4 =

(n^2 + 4(n + 1))(n + 1)^2 / 4 =

(n + 1)^2 (n^2 + 4(n + 1)) / 4 =

But

n^2 + 4(n + 1) =

n^2 + 2n + 1 + 2(n + 1) + 1 =

((n + 1) + 1)^2

So

(n + 1)^2 (n^2 + 4(n + 1)) / 4 =

(n + 1)^2((n + 1) + 1)^2 / 4

and the equation also holds
for n + 1.

Then by the definition of the
natural numbers, the equation
holds for all natural numbers.

Done.

So, that's an example
of proof by mathematical
induction.

(5) Fundamental Theorem of Arithmetic

A prime number is a natural number like
1, 3, 5, 7, 11, 13, 17, 19, 23, ..., that
is, evenly divisible by only itself and 1.

Prime numbers have been studied since the
ancient Greeks, and there are many
difficult questions easy to state; now we
have answers to some of the questions.

Consider 45:

45 = 3 * 3 * 5

So, we have written 45 as a product of
prime numbers. It is easy enough to see
that any natural number can be written as
a product of prime numbers.

The Fundamental Theorem of Arithmetic is
that each natural number can be written as
a product of prime numbers in just one
way, e.g., where we neglect the order of
the prime numbers in the product.

So,

45 = 3 * 3 * 5

is the only way to write 45 as a product
of prime numbers.

(6) High School Algebra

A quadratic is an algebraic expression
of the form

ax^2 + bx + c

A polynomial is the same except can have
higher natural number powers of x, e.g.,

7x^5 - 4x^3 + 2x - 1

Polynomials play an important role in
linear algebra -- e.g., via determinants
and eigenvalues.

Polynomials are also used in error
correcting codes and related work.

There have been attempts to use
polynomials in curve fitting, but for
large natural numbers n the x^n term means
that as go on the real line a long way
from 0, commonly the value of the
polynomial goes a very long way from 0, so
far from 0 that it is usually unrealistic
for applications. That is, polynomials
don't provide good, versatile means of
curve fitting.

Also interesting and useful is the
binomial, for natural number n and
numbers x and y

(x + y)^n

Presumably the name binomial is from
having the two numbers, x and y.

Curiously, surprisingly, this binomial is
important in various approximations and in
combinations, permutations, probability,
and statistics.

(7) Second Year High School Algebra

A root of a polynomial is a value of x
that makes the value of the polynomial 0.

The fundamental theorem of algebra is that
each polynomial can be written as

(ax + p)(bx + q) ... (cx + r)

where the p, q, ... r are roots of the
polynomial. The theorem holds for
polynomials with either real or complex
coefficients. The roots, even with only
real coefficients, can be complex.

I've omitted some details due to the
challenge of typing math.

Mathematicians worked for centuries to get
good proofs of this result.

Also might be covered are the algorithms
for least common multiple and greatest
common divisor. These were known to the
ancient Greeks and get used currently.

We can define a function f by, for any
number x,

f(x) = ax^2 + bx + c

So, function f is a look-up table -- plug
in a value for x and get back the value of

ax^2 + bx + c

Since the x is a number, we say that the
domain of the function f is the set of
numbers, usually the set of real numbers.
In this case, the range of function f is
also the set of real numbers.

We can have look-up tables for telephone
numbers -- the domain a set of names of
people and the range a set of telephone
numbers. We can have a function for
Internet addresses, domain URLs and range,
say, the 64 bit internet addresses.

So, functions have enormous generality --
given any two non-empty sets A and B, we
can have a function with domain A and
range B and to indicate that f is a
function with domain A and range B write

f: A --> B