Puzzle

Probability Study Notes

To: Professor

Re: a couple of questions in your class.

Hi,

I am one of your student in course STAT***(Probability), and want to thank you in advance for your time to

look into my mail.

1. Regarding your question in class: P{There is the birthday of some one in the class today.(no. of

students =50 }

I gave the wrong of 50/365. I think the correct one should be that the "complement of there is no single

birthday in the class today", which is 1- (364/365)X(364/365)...==1-((364/365)power 50) == 0.1281

Is it right?

¡¡

2. Regarding my question about the 3 conditions of "probability of events":

A. P(A) >=0 for any A belongs to S;

B. P(S) = 1;

C. if A1, A2, A3... is finite or infinite mutually exclusive events of S, then

P{A1UA2UA3...} = P{A1} + P{A2} + P{A3} +...

¡¡

And in the class I asked you the question that is it true that A1+A2+A3+... == S, and you said not necessary,

then I have figured out following conclusion:

Suppose A1, A2, A3... are all possible mutually exclusive events in S, then

P{A1} + P{A2} + P{A3}... == P{S} = 1;

The following is my proof:

suppose event X belongs to S and does not belong to collection of {A1, A2, A3...}, then according to

assumption that {A1, A2, A3...} are all possible mutual exclusive events in S, we can get that X cannot occur

independently from any of {A1, A2, A3...} , otherwise if X occur alone means that X is another mutually

exclusive event which is not within collection of {A1, A2, A3...}. And this is contradictive to our

assumption.

So, whenever X occurs there must be one exact event from {A1, A2, A3...}, then we can say that the

probability of X is included in P{A1, A2, A3...}. As we just select X in general from "complement of {A1, A2,

A3...} ", we can say that the collection of "complement of {A1, A2, A3...}" have the same characteristics like

X. Then the probability of all elements are included in P{A1, A2, A3...} . Therefore,

P{S} = P{A1, A2, A3...} =1. proved.

¡¡

Is above proof correct?

Pure Logic?

Let's define propositional function P(x) and Q(x), and a certain logic operation L which involves two

propositional function and the result is true if and only if the truth value of two propositional function have

a certain pattern, of which the sequence of two propositional function matters.

Say the all possible combination pattern of truth of two propositional function is like following:

P(x) Q(x)

T T (1)

T F (2)

F T (3)

F F (4)

The pattern of truth combination becomes a simple combination problem.

Say c(4,0)=1 , c(4,1)=4, c(4,2)=6, c(4,3)=4, c(4,4)=1 ===> There are total 16! and it is from binomial.

This is the essence of world! And I presume that God is describing and constructing world with this as language

and tool. However, human can only understand a few characters of them, that is logic----see below:

Let's define (1),(2),(3),(4) as logical results of the logical operation L

Pattern 1: (1)=T, (2),(3),(4) = F This is logic AND.

Pattern 2: (1),(2),(3) = T (4) = F This is logic OR

Pattern 3: (1),(3),(4) = T (2) = F this is IMPLY

Pattern 4: (1),(4) = F (2),(3)=T this is EXCLUSIVE OR

...

Among 16 patterns, how many of them are we giving serious study? Only about half of them, I guess.

Why? "We must know. We shall know."

What is a tree?

    Hi professor,

    Sorry to disturb your vacation.

    I am taking comp239 now and I don't know why Mr. Rosen does not use a more practical and easy way to justify a

    tree by counting the number of edges e and number of  vertices v.  If e = v-1 then it is a tree, if e=v, it has

    a circuit,it is not a tree.

    By definition, a tree is a connected undirected graph with no simple circuits. Then how to justify?

    On text book, p633, there is a theorem:

    An undirected graph is a tree if and only if there is a simple unique path between any two of its vertices.

    However, it is not a very practical theorem, since you have to verify all pairs of vertices to see if there is a

    simple path, and what's more, it is the only simple path. Is it easy? Definitely no. It is more like a definition.

    I found a easier way to justify if a connected undirected graph is a tree or not. Or in other words, if there

    is any simple circuit or not.

    A connected undirected graph is a tree if and only if the number of vertices v and number of edges e has such

    relation: e = v-1.

    proof:

    A connected undirected graph is a tree, if and only if there is no circuit in it. That means the total region

    made by the graph is one. According to Euler formula r = e - v + 2   we get

       e = v -1

    Q.E.D.

    A more wild thought is that a tree is simply the transitive closure of certain relation of all vertices.

    Let's define each edge (u,v) is under a certain relation R, that is (u,v) in R or in other words, R is a relation

    on all vertices set V={v1,v2,v3...vn}. Then the connected graph G=(V,E) is the transitive closure of R.

    According to Lemma1 on p501, the path between vertex u to v is at most n and moreover, when u is different from

    v, the length of path is at most n-1. That means when the path is not a circuit, the length of path cannot

    exceed  n-1.

    Of course it is quite a trivial fact, but still I think it is quite practical. And I cannot help it.

    Thank you for your time.

    Nick Huang

Is there "Universal Truth"?

Hi Professor,

Sorry to disturb you again.

I went to attend a lecture in Concordia last week, given by a professor from "Rice University". His topic was

related to logic. It is said that the three foundations of logic---"consistency, completeness and decidable"

was overthrown. For "inconsistency" of logic, he gave an example of self-contradictive proposition:

"There is no universal truth."

He explained about this paradox as that if it is true, then there is no universal truth implies it is false.

And if it is false, then there is universal truth, it must be true.

I tried very hard to disbelieve him by attempting to prove it is not self-contradictive. I think the biggest

problem is the definition of "Universal Truth", which must be strictly defined before all. The following is my

understanding:

First I define "universal truth" as a propositional function U(x) such that for all x, U(x) is true. Then the

proposition "there is no universal truth" becomes "for all propositional functions, it is not the case that

there exists a propositional function U(x) such that for all x U(x) is always true." And we know this proposition

is false because we actually can find such proposition like "for all x that x=x" etc.

Since the proposition "there is no universal truth" is a false proposition, we won't bother ourselves with

so-called "self-contradictive", right? Because "there indeed exists universal truth, however, not this one."

I simply cannot believe that logic is inconsistency as declared by that professor, but sometimes I think I am

clear, however, sometimes my mind is mixed up. Can you justify this?

Thank you for your time.

¡¡

Qingzhe Huang

Two Different Perspectives

Question: Find the recursive relation of number of strictly increasing of positive integers that has 1 as

its first term and n as its last term where n is a positive integer.

Original solution (from author):

Let S(n) be the number of such sequences. A sequence ending with n must consist all

sequences that end in something less than n followed by n as its last term. So,

S(n) = S(1) + S(2) + ...+ S(n-1) where S(1) = 1 and n>=2 (1)

My solution:

Let S(n) be the number of such sequences. Then S(n) = 2xS(n-1) where S(1)=1 and n>=2 (2)

proof: Let P(n) be the set of all sequences of strictly increasing that has 1 as its first term and n as

last term. Then every element in P(n+1) can have number n as one of its term or not.

Case 1: Suppose elements in P(n+1) do have n as one of its term, then the sequences are all the sequences

in P(n) followed with n+1 as its last term. So the number is |P(n)|= S(n).

Case 2: Suppose elements in P(n+1) do not have "n" as one of its term, then the sequences are all the

sequences in P(n) without n and followed with n+1 as its last term. And the number of sequences is

still |P(n)|=S(n). Because we get the sequence by removing the last term which is "n".

So, |P(n)| = 2x|P(n-1)| or in term of S(n) = 2xS(n-1)

You can verify that (1) and (2) are equal.

When I read the above again, I am in complete daze. What was I talking about? Where did I get this question? Discrete math?

Or math analysis?

¡¡

¡¡

¡¡

¡¡