XOO’s

Entries categorized as ‘Mathematics’

Knaster-Tarski Theorem

十一月 14, 2009 · 3個回應

Knaster-Tarski theorem is a simple but powerful fixpoint theorem in order theory. It could give a very elegant proof of Cantor–Bernstein–Schroeder theorem which states that if there are injections f : A \rightarrow B and g : B \rightarrow A, there exists a bijection between A and B. (更多…)

類別： Mathematics
Tagged:

Ordinal Number

二月 18, 2009 · Leave a Comment

Here are some comments about ordinal number as I have known.

Ordinal number is a “order-type” of sets which is used to represent the “length” or “size” of well-ordering sets like 0 = \emptyset, 1 = \{ \emptyset \}. It’s also an extension to \mathbb{N} since all of the natural number could be respresented by ordinal and it’s a proper superset as \omega = \mathbb{N} and \omega + 1 \neq \omega where \alpha + 1 = \alpha \cup \{ \alpha \} called successor of \alpha. (更多…)

類別： Mathematics

From list to free group

二月 6, 2009 · Leave a Comment

Given natural numbers \mathbb{N}, we could construct integers \mathbb{Z} by considering the equivalence relation on \mathbb{N} \times \mathbb{N} as follows,

  • (a, b)\sim(c, d) if a + d + r= b + c + r for some r

Obviously, it’s a equivalence relation from properties of commutativity. Thus we have equivalence class {[} ( a , b ){]} where a, b \in \mathbb{N}. Then, {[}(0, 0){]} = {[}(1, 1){]} = {[}(n , n){]}, and -{[}(a, b){]}={[}(b, a){]}. This construction from a commutative monoid to abelian group is called Grothendieck group. (更多…)

類別： Computer Science · Mathematics
Tagged:

Concrete category

二月 3, 2009 · Leave a Comment

Concrete category 是用來描述該 category 的 object 與 function 可以直接對應 set 與 function。諸如 \mathbf{Grp} (the category of groups), \mathbf{Rng} (the category of rings), \mathbf{Top} (the category of topological space), 以及所有的 small category。然而, 並非所有的 large category 都是 concrete, 而其中包含比較重要的例子有 \mathbf{Toph}, 其 objects 為 pointed topological space 而 morphisms 為 homotopy classes, 由 Peter Freyd 於 1970 年提出證明。 (更多…)

類別： Mathematics
Tagged:

Four Lemma

二月 2, 2009 · Leave a Comment

在前面一篇 Splitting Lemma 中用到 Short Five Lemma, 而 Short Five Lemma (對於 i = 1, 3 ,  A_{i} \rightarrow B_{i} 為 isomorphism 時,  0 \rightarrow A_{1} \overset{f_1}{\rightarrow} A_{2} \overset{f_2}{\rightarrow} A_{3} \rightarrow 0 同構於 0 \rightarrow B_{1} \overset{g_1}{\rightarrow} B_{2} \overset{g_2}{\rightarrow} B_{3} \rightarrow 0) 其實是 Five Lemma (左右兩邊為一般的 module, 左上有一 epimorphism 對至左下, 右上有 monomorphism 對至右下, 其餘不變) 的特例。而欲證明 Five Lemma 其實用 Four Lemma (右上有 mono 對到右下) 加上其對偶得證, 也就是說, 只要證明 Four Lemma 就可以得到論述麻煩的 Five Lemma。 (更多…)

類別： Mathematics
Tagged: ,

Splitting Lemma

一月 21, 2009 · 1個意見

嚇死我，差點證不出來。口語解讀是，如果我在 short exact sequence 中找得到一個反向的 morphism 促使正向的 morphism 是 left(or right) split 的話，那麼這串 sequence 就可以寫成前後兩個 module 的 direct sum。

Splittin Lemma. Let 0 \rightarrow A_{1} \overset{f}{\rightarrow} B \overset{g}{\rightarrow} A_{2} \rightarrow 0 be a short exact sequence of R-module homomorphism. The the following are equivalent.

  1. (Right split): There is an R-module homomorphism h : A_{2} \rightarrow B with gh = 1_{A_{2}} ,
  2. (Left split): There is an R-module homomorphism k : B \rightarrow A_{1} with kf = 1_{A_{1}} ,
  3. (Direct Sum): The given sequence is isomorphic to 0 \rightarrow A_{1} \rightarrow A_{1} \oplus A_{2} \rightarrow A_{2} \rightarrow 0, and thus B \cong A_{1} \oplus A_{2}. (更多…)

類別： Mathematics
Tagged: ,

Why quotient and subset on datatype ?

一月 19, 2009 · Leave a Comment

Why we need quotients and subsets of datatypes ?

One of the reaons is we could derive operations naturally. A simple example is the unordered pair. Define R_{uo} as (a, b)~R_{uo}~(b, a) for all a, b \in \mathbf{A}. Then, (\mathbf{A} \times \mathbf{A}) / R_{uo} is the unordered pair. (更多…)

類別： Computer Science · Mathematics
Tagged: