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?

Answer to the previous blog

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

Suppose there are n lightbulbs, k of them have defects. A technician is allowed to check m lightbulbs and it turns out that exactly l defected ones among those checked.

1. Given n,k,m,l, what is the probability mass function (PMF) for l? What is the expected value?
2. Given n,m,l, what is the probability mass function (PMF) for k? What is the expected value?

(Sorry that I have to change the notations, so the presentation is clearer.)
Answer:

1. Probability is (number of particular outcomes)/(number of all possible outcomes).
   • k≥n: In this case 0≤l≤m. The total number of ways for choosing m bulbs from the n bulbs is $C_m^n$. Number of ways that there are l defected bulbs among m chosen bulbs equals $C_l^kC_{m-l}^{n-K}$. Therefore the conditional probability for $L=l$ given $K=k$ is $$P(L=l|K=k)=\frac{C_l^kC_{m-l}^{n-k}}{C_m^n}.$$ Interestingly, rearranging the terms, we have (what does it mean?) $$P(L=l|K=k)=\frac{C_l^mC_{k-l}^{n-m}}{C_k^n}$$ The expected value equals the sum of (outcome × probability). Therefore $$E[L|K=k]=\sum_{k=0}^m\frac{lC_l^kC_{m-l}^{n-k}}{C_m^n}.$$
   • k≤n: In this case 0≤l≤k. Again $$P(L=l|K=k)=\frac{C_l^kC_{m-l}^{n-k}}{C_m^n}.$$ The expected value is $$E[L|K=k]=\sum_{k=0}^k\frac{lC_l^kC_{m-l}^{n-k}}{C_m^n}.$$
2. Indeed there is something missing in the question: How is k distributed? Lets assume that it is K~Bin(N,p), that is, each bulb has a probability p to be defected and that $P(K=k)=C_k^np^k(1-p)^{n-k}$. Therefore $$P(K=k|L=l)=\frac{P(Y=K, L=l)}{P(L=l)} =\frac{P(K=k)P(L=l|K=l)}{\sum_{k=l}^nP(K=k)P(L=l|K=k)}$$ and $$E[K|L=1]=\frac{kP(K=k)P(L=l|K=l)}{\sum_{k=l}^nP(K=k)P(L=l|K=k)}.$$

The second question:
Suppose there are n lightbulbs, k of them have defects. A technician is allowed to check m lightbulbs. What is the probability that he can find out all the defected?

Answer: The technician can find all the defected bulbs if either all the defected bulbs or all the normal bulbs are among those checked. Therefore the answer is $$P(\mbox{he finds all})=\begin{cases} \frac{C_{m-k}^{n-k}}{C_m^n} & n-k>m>k \\ \frac{C_{m-k}^{n-k}+C_{m-(n-k)}^k}{C_m^n}& m\ge n-k,k \\ \frac{C_{m-(n-k)}^k}{C_m^n} & k>m>n-k \end{cases}$$

A probability question

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

Suppose there are N lightbulbs, K of them have defects. A technician is allowed to check n lightbulbs and it turns out that exactly k defected ones among those checked.

1. Given N,K,n, what is the probability mass function (PMF) for k? What is the expected value?
2. Given N,n,k, what is the probability mass function (PMF) for K? What is the expected value?

A somewhat similar question is:
Suppose there are N lightbulbs, K of them have defects. A technician is allowed to check n lightbulbs. What is the probability that he can find out all the defected?

Subtraction of Numbers

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

Many many years ago, when I first encountered the computer algorithm for subtraction of numbers, I really do not know what happens.
Several days ago, I have read an article saying that the primary school kids, who are okay to do additions, face difficulties in subtractions.
The two problems seems unrelated, but they are really the same problem.
Addition is easy, subtraction is hard, for computers and kids alike!

Lets review how a computer do base 2 addition:

To add two numbers, with fixed length, say (01001101)+(00011101). We need three memory units: N1 to hold a digit for the first number, N2 to hold a digit for the second number, C to hold a carry digit.

Step 1. Load the last digit of the first number to N1, the last digit of the second number to N2, 0 to C. Then do the following operation:

N1	N2	C	Result Digit and new C
0	0	0	0, 0
0	0	1	1, 0
0	1	0	1, 0
0	1	1	0, 1
1	0	0	1, 0
1	0	1	0, 1
1	1	0	0, 1
1	1	1	1, 1

(Basically, it means N1+N2+C=(new C, Result Digit).)
In our example, N1=1, N2=1, C=0, so the result is 0 and new C=1.

Step 2. Load the next digit (on the left side) of the first number to N1, the next digit of the second number to N2. Again follow the table above.
In our example, N1=0, N2=0, C=1, so the result is 1 and new C=0.

Step 3-Step 8. Repeat Step 2.
In our example, it is

• N1=1, N2=1, C=1: result is 0, new C=1
• N1=1, N2=1, C=1: result is 1, new C=1
• N1=0, N2=1, C=1: result is 0, new C=1
• N1=0, N2=0, C=1: result is 1, new C=0
• N1=1, N2=0, C=0: result is 1, new C=0
• N1=0, N2=0, C=0: result is 0, new C=0

The final answer, reading all the results backwards, is (01101010)

Looks fancy, but it is just how we do addition. Now, for subtraction.

Lets use the same two numbers: (01001101)-(00011101).

Step 1. Change the second number, switch 0 and 1, so it becomes (11100010).

Add the first number and the new second number: (010001101)+(11100010)=(00101111).

Add the answer by (00000001), and we get the answer (00110000).

Why does it work?
Because we are not doing really the usual addition and subtration, we are doing modulo arithmetic!!!

We say that m=n (mod R) is m-n is divisible by R. If we are doing arithmetic under this equivalence relation, we are doing modulo R arithmetic, or Z_R-operations.
For example, in modulo 3 arithmatic, we have

+ 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1

× 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1

The computer arithmetic is simply doing modulo 2⁸ arithmetic. Therefore
(01001101)-(00011101)
=(001001101)-(000011101)
=(001001101)-(000011101)+(100000000)
=(001001101)-(000011101)+(011111111)+(000000001)
=(001001101)+(011100010)+(000000001)
=(01001101)+(11100010)+(00000001)

It explains the algorithm.

Now I wish to propose a new subtraction algorithm for kids, using the same idea.

Say, we want 19021-8742.

Rewrite the second number as 08742, then switch using 0<->9, 1<->8, 2<->7, 3<->6, 4<->5. The new number is 91257

Add the first number and the new number, ignore the leftmost digit: 19021+91257=10278.

Add 1, the final answer is 10279.

Lets try two more. 24311-13904 and 34052-23016.

2 4 3 1 1 - 1 3 9 0 4 = = = = = = 2 4 3 1 1 + 8 6 0 9 5 - - - - - - 1 0 4 0 6 + 1 - - - - - - 1 0 4 0 7

3 4 0 5 2 - 2 3 0 1 6 = = = = = = 3 4 0 5 2 + 7 6 9 8 3 - - - - - - 1 1 0 3 5 + 1 - - - - - - 1 1 0 3 6