Tag Archives: Logic

Cours Raisonnements (Logics) , Ensembles ( Sets), Applications (Mappings)

Modern Math 1 Comment

This is an excellent quick revision of the French Baccalaureat Math during the first month of French university. (Unfortunately common A-level Math syllabus lacks such rigourous Math foundation.)

Most non-rigourous high-school students / teachers abuse the use of :

“=> ” , “<=>” . 

Prove by “Reductio ad Absurdum” 反证法 (Par l’absurde / By contradiction) is a clever mathematical logic :

\boxed {(A => B) <=> (non B => non A)}

Famous Examples: 1) Prove \sqrt 2 is irrational ; 2) There are infinite prime numbers  (by Greek mathematician Euclid 3,000 years ago).

Example: Prove \forall n \in {\mathbb{N}}^{*}, \frac {2n+1}{2 \sqrt {n(n+1)} } \geq 1 … (*)

Proof: (by reductio ad absurdum)
Assume the opposite of (*) is true:
\forall n \in {\mathbb{N}}^{*}, \frac {2n+1}{2 \sqrt {n(n+1)} } < 1
\iff {2n+1} < 2 \sqrt {n(n+1)}
\iff (2n+1) ^{2} < 4.n(n+1)
[Rigor: Square both sides, “<“ relation still kept since both sides are positive and Square is a strictly monotonous (increasing) function]
…
\iff 1 < 0 , \text {(False!) }
Hence, (*) is True : \boxed {\forall n \in {\mathbb{N}}^{*},\frac {2n+1}{2 \sqrt {n(n+1)} } \geq 1}

The young teacher showed the techniques of proving Mapping (映射):
E \to F
x \mapsto y = f (x)

Caution: A mapping from E to F always has ONE and ONLY ONE image in F.

I.) Surjective (On-to) –  best understood in Chinese 满射 (Full Mapping).
By definition:
\boxed { \forall y \in F, \exists x \in E, f (x) = y}

To prove Surjective:
\text {Let } y \in F
…
…
\text {find } \exists x \in E, f (x) = y 

He used an analogy of (the Set of)  red Indians shooting (the Set of) bisons 野牛: ALL bisons are shot by arrows from 1 or more Indians. (Surjective shoot)

II.) Injective (1-to-1) 单射

By definition: \boxed { \forall (x,x') \in E^{2}, x \neq x' \implies f (x) \neq f (x') }

To prove Injective, more practical to prove by contradiction:

\forall (x,x') \in E^{2}, \text { Suppose: } f (x) = f (x')
…
…
prove: x = x’

III.) Bijective (On-to  & 1-to-1) 双射
Definition:
\boxed{\forall y \in F, \exists ! x\in E, f (x) = y }

To prove Bijective,
\text {Let } y\in F, \text {let } x\in E, f(x) = y
\iff \text {...}
\iff \text {...}
\iff x = g (y)
\iff \boxed { g = f^{-1}}

My example: Membership cards are issued to ALL  club members (Surjective or On-to), and every member has one unique membership card identity number (1-to-1 or Injective), thus

“Cards – Members” mapping is Bijective.

(My Remark): If the mappings f and g are both surjective (满射), then

the composed mapping f(g) is also 满 (满) 射 = 满射 surjective ! (Trivial). [#]

He highlighted other methods of proof by higher math (Linear Algebra or Isomorphism).

Note [#]: “Abstract” Math concepts expressed in rich Chinese characters are more intuitive than the esoteric “anglo-franco-greco-germanic” terminologies. Some good examples are: homo-/endo-/iso-/auto-/homeo-morphism  (同态/自同态/同构/自同构/同胚), homology  (同调), homotopy (同伦), matrix (矩阵), determinant (行列式), eigen-value/vector (特征 值 /向量), manifold  (流形), simplicial (单纯) complex (复形), ideal (理想), topology  (拓扑), monad (单子), monoid (么半群)…

No wonder André Weil (WW2 Modern Math French/USA “Bourbaki School” Founder) had remarked:

“One day the westerners will have to learn Math in Chinese.”

Advertisements

Proof: “Any Statement Implies Itself”

Elementary Math Leave a comment

Let p = any statement

“Any Statement Implies Itself”
written in logic:
(p => p)

Example: “I am Me.”

Prove: (p => p)
Proof :
(p => ((p => p) => p)) =>
((p => (p => p)) => (p => p))

p => ((p =>p) => p)

(p => (p => p)) => (p => p)

p => (p => p)

p => p [QED]

白马非马

Chinese 1 Comment

韓非子是战国法家, 荀子的高徒, 秦始皇宰相李斯的同学。他说”白马非马”, 即白马不是马, 可以用集合論(Set Theory) 证明:

Let 马 = H = {w, b, r, y …}
w : 白马
b : 黑马
r ：红马
y：黄马

Let 白马 = W = {w}

To prove:
H = W
We must prove:
(1)H ⊂ W and
(2)H ⊃ W

From definition we know:
(2) fulfilled because
w \in H \supset W
But, (1) not true since
H \nsubseteq W

\implies H \neq W

白马≠马
白马非马
[QED]

其他例子:
木魚非鱼

Solution Birthday

Be careful of the sequence of dialogues which lead to correct sequence of eliminations.
Dialogue 1: (by red color)
Ben says: I do not  know which month (M), also sure that  Mark does not know which date (N)
=> they are both confused by duplicate M & N
=> eliminate unique dates N: 7/6, 1/12
Ben infers that not in M = 6, 12
 => eliminate 4/6 , 1/12, 8/12 (duplicate Month M)
Dialogue 2: (by Blue color)
Mark says: Initially I don’t know, now I know (N)
=> eliminate duplicate dates N : 5/3, 5/9
Dialogue 3: (by yellow)
Ben says: now I also know (which month M)
=> eliminate duplicate month M: 4/3, 8/3
Remain the answer: 1/9 
[QED]

20130409-115534.jpg

Logic: Monkey’s Dilemma

Elementary Math Leave a comment

西遊记 (The Journey to the West)

On the way to the West, the team came to a Y-junction, either go Left or Right.
The Monkey King (孙悟空 ) went out reconnaissance, only came back few days later.
The Pig (猪八戒) suspects this fellow is a monster in disguise of the monkey, may not tell the truth.
The smart Monk (三藏) asks only 2 questions to detect his identity :

Q1. Is ‘Left’ direction correct ?
Q2. If I ask you Q1, you would say “Yes”, would-you?

The true Monkey will answer “Yes/Yes” or “No/No”, regardless the correct direction.
Why ?

Case 1. If the Correct direction =Left

Monkey: (Q1, Q2) = (Y,Y)
Monster (tell lie) = (N,Y)

Case 2. If the Correct direction =Right

Monkey : =(N,N)
Monster (tell lie) =(Y, N)