Ordinal numbers.

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com.

Giuseppe Peano says 1 is the smallest natural number, while John von Neumann says that 0 is the smallest natural number?
Yes. In the past, or even nowadays, 0 as a number is not quite natural in many people's eyes. However, when mathematicians want to give a vigorous definition for ordinal numbers, they figure out that 0 should be the starting point.

What is the vigorous definition for ordinal numbers?
An ordinal number α is a set of ordinal numbers that are smaller then α.

So 3={0,1,2}, 5={0,1,2,3,4} are ordinal numbers?
True. All natural numbers are ordinal numbers. Indeed the set

ω={0,1,2,3,...}
is also an ordinal number. It is the smallest infinite ordinal number.

The second smallest infinite ordinal is {0,1,2,...,ω}?
Yes, it is ω+1. Note that it is different from 1+ω which equals to ω. The definition of addition is like this--
{0,1,2,...}+{0,1,2,...}={0,1,2,..., 0,1,2,...},
where the symbols with different colors are considered different, and that the elements are listed in the order.
By renaming the elements, we see that
3+2={0,1,2}+{0,1}={0,1,2}+{3,4}={0,1,2,3,4}=5.
The addition for finite ordinals is the usual addition of natural numbers.
However, we see that
ω+1={0,1,2,...}+{0}={0,1,2,...}+{ω}={0,1,2,...,ω} but
1+ω={0}+{0,1,2,3,...}={0}+{1,2,3,...}=ω.
The two are different as ω+1 has a largest element but ω does not.

I doubt we still ignore 0 with we deal with ordinal numbers in daily language?
Well, we have invented a word "zeroth", denote that something should come earlier before the first object in a series. For example, the zeroth chapter or the zeroth law of thermodynamics.

3={0,1,2}

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com.


In the last post, we mentioned that sometimes we identify 2={0,1}. So 3={0,1,2}, 4={0,1,2,3}?
Yes. It is the construction of natural numbers by polymath John von Neumann:

• 0={ }, the empty set.
• n+1=n∪{n}.

Therefore we have: 0={ }, 1={0}, 2={0,1}, 3={0,1,2}, .... In general n={0,1,2,...,n-1} for n≥1.

I see, so n is a set of n elements, right?
This definition has many advantages:

1. n is a set of n elements.
2. The definition is recursive, it does not depend on anything outside the number system.
3. n> m if and only if n is an element of m.
4. n≥ m if and only if n is a subset of m.
5. This definition can be extended to infinite ordinals.

Are there any other definitions for natural numbers?
Yes. For instance, 0={ }, 1={0}, 2={1}, etc. As soon as the definition fits Peano axioms, that's okay.

What are Peano axioms?
Proposed by Giuseppe Peano, there are five axioms:

1. There is an initial number, called 0. (Peano indeed use 1 as the initial number)
2. There is a successor operation. If n is a natural number, its successor is denoted by n+1.
3. For all nonzero natural number m, there exists a unique n such that n+1=m.
4. There exists no natural number n such that n+1=0.
5. If 0 has Property P and that "if n has Property P then n+1 also have Property P", then all natural numbers have Property P.

The last property is the mathematical induction?
Well... the reason that mathematical induction works is that it is a property of the natural number system!

The power set of X

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com.

Suppose X and Y are sets. What is Y^X?
Y^X is the set of all functions from X to Y. From the last post, we see that if X has n elements and Y has m elements, then Y^X has mⁿ elements.

What is 2^X?
If we write like that, we identify 2 with a set with two elements, in particular we can consider 2={0,1}. Therefore 2^X is simply a set of functions that for each x∈X, f(x) takes up values as 0 or 1.

How do we describe a function in 2^X?
Since f(x) can only have two values, we can describe the function f using the preimage of 0, i.e. f^-1(0)={x∈X   :   f(x)=0}. In other words, each function in 2^X corresponds to exactly one subset of X.

2^X is sometimes used to denote the power set of X, right?
A power set of X, usually denoted by P(X), is the set of all subsets of X. Because there exists a correspondence between the functions in 2^X and the subsets in P(X), so we sometimes really consider them identical.
For example, if X={a,b,c}, then P(X)={∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}} and the eight functions in 2^X are
f(a)=f(b)=f(c)=1;
f(a)=0, f(b)=f(c)=1;
f(b)=0, f(a)=f(c)=1;
f(c)=0, f(a)=f(b)=1;
f(a)=f(b)=0, f(c)=1;
f(a)=f(c)=0, f(b)=1;
f(b)=f(c)=0, f(a)=1;
f(a)=f(b)=f(c)=0.

∅∅={∅}

If you are in Hong Kong and you need help for university mathematics courses, please visit  www.all-r-math.com.

Suppose X and Y are sets. What is Y^X?
Y^X is the set of all functions from X to Y.

What is a function from X to Y?
According to the modern definition, f is a function from X to Y is simply a subset of X×Y satisfying

• Every element x∈X associates with a unique element f(x) in Y.

Put it in another way, a subset f of X×Y is a function if

1. No element x∈X associates with nothing in Y, i.e. f(x) always exists and
2. No element x∈X associates with two or more elements in Y, i.e. there cannot be two f(x).

Examples:

1. f(x)=a square root of x is a function from [0,∞) to [0, ∞).
2. f(x)=a square root of x is not a function from (-∞,∞) to [0, ∞) because there is no f(-1).
3. f(x)=a square root of x is not a function from [0,∞) to (-∞, ∞) because there are two f(1), i.e. 1 and -1.

If M is a set with m elements and N is a set with n elements (m,n≠0), then what is the size of M^N?
Easy. M^N has exactly mⁿ.
For instance, let M={0,1,2} and N={0,1}, then M^N contains the following 3²=9 elements:
f(0)=f(1)=0;
f(0)=0, f(1)=1;
f(0)=0, f(1)=2;
f(0)=1, f(1)=0;
f(0)=f(1)=1;
f(0)=1, f(1)=2;
f(0)=2, f(1)=0;
f(0)=2, f(1)=1;
f(0)=f(1)=2.

What is ∅^X if X≠∅?
∅^X=∅.
Take any element x of X, we see that it can associate with nothing! Therefore no function exists. Note that it matches with our common notation that 0ⁿ=0 if n≠0.

What is Y^∅ if Y≠∅?
Y^∅={∅}, the set which contains the empty set as its unique element!!!
∅=∅×Y is itself a function from ∅ to Y, why? Because there is no element in an empty set, hence (1) no elements in an empty set will corresponds to no elements and (2) no elements in an empty set will corresponds to two or more elements. Weird!! Counting the number of elements, we see that it matches our common notation that m⁰=1 if m≠0.

What is ∅^∅?
Using exactly the same argument as before, we know that ∅^∅={∅}.
Counting the number of elements, we have 0⁰=1! This equality is true only if we consider 0 as a counting number.

Baye's formula

If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.

[Quite lazy recently, so write harder..... :( ]

A friend just asks me what is Baye's formula.

The simplest form is

P(A|B)P(B)=P(B|A)P(A)

where P(A|B) means the conditional probability of A given that B happens.

Lets we take a frequentist approach. Suppose out of N trials, A appears a times, B appears b times, and in c trials, both A and B occur. Then

P(A|B)=c/b=(c/N)/(b/N)=P(A and B)/P(B)

and therefore

P(A|B)P(B)=P(A and B).

Likewise P(B|A)P(A)=P(A and B). Hence we deduce the Baye's formula.

Example: We throw a dice. Let A={1,2}, B={1,3,5}, C={2,3,5}.

P(A)=1/3, P(B)=P(C)=1/2, P(A and B)=P({1})=1/6, P(A and C)=1/6, P(B and C)=1/3.

P(A|B)=1/3, P(A|C)=1/3.

P(B|A)=1/2, P(B|C)=2/3.

P(C|A)=1/2, P(C|B)=2/3.

We say that two events X and Y are independent if P(X and Y)=P(X)P(Y). If P(Y)≠0 it is the same as saying that P(X|Y)=P(X).

Now we see that B and C are not independent.  However we have A and B are independent, and that A and C are also independent.  Not the same kind of independence in our usual sense, right?