群论笔记 02

but, how to describe the purity of a function? > a function is pure if you can memoise it. This means that you can turn it into a lookup table. everytime you call this function once it's evaluated, you can remember it, the next time you can just lookup into a table. so, types that are finite, only have finite number of elements, like Booleans, it's really easy to tabulate.

• functions on characters, they are really easy to tabulate.
• functions on Integers or Strings, they usually cannot be tabulated.

eg.

def isTrue(b: Boolean): Boolean = b == True

we must say that, the pure function is at the top level of abstraction, what we more concern is the bottom level of abstraction — what is the atom(primitive thing), what are the simplest building blocks from which we can build more complex stuff. First , we should decompose the problem, get to the little blocks at the bottom, and then recompose stuff from there, when we are decomposing this idea of using procedures and types, we eventually get to the bottom and that's pure functions. So, on top of functions we can be building more complex stuff, including things like I/O.

keep in mind that, Programming can be modeled as a Cat of Set, which Set is an recursive concept — one set can be element of another set. what is a function? function is some special relation(in mathematics). what is a relation? keep in mind that, set is set of Cat, not set of Set Theory. set in Cat cannot see elments inside; set in Set Theory we can see inside.

• relation is pairing 2 elment in 2 set, relation doesn't have to be symmetric.
• relation is just a subset of Cartesian product

https://en.wikipedia.org/wiki/Cartesian\_product?oldformat=true

relation which ilegal for function

one element of function CANNOT be mapped into a bunch of things.

How to define inverse of a given function

f :: a -> b
g :: b -> a
g * f = id_a
f * g = id_b

what is isomorphism? function that is invertible is called isomorphism g * f = id_a ; f * g = id_b we can say: *f is isomorphism if existing a g to make 2 equation available * #+END_QUOTE

tips: you see that, we never look inside of a set, we just use and ONLY use function to define what is isomorphism.

when we define something ONLY by function(arrow), we get an general definition for any Cat, not only for some Cat but for all Cat . but when we use inside view of set, we trap ourself to details, which impose restriction on availabe range of this definition. Isomorphism is excellent: isomorphism build a one-to-one relatioship between 2 set isomorphism kinda tell you that these 2 things are for some intents and purposes identical

for finite 2 set: one-to-one; for infinite 2 set: because of infinite things become more complex

Even Nature Number <-------------> Natural Number
y = 2x

1. function will collapse elements of a set( because function allow many-to-one mapping)
2. image is always a subset of Codomain
   • then if you inverse f, maybe we call it g. But for g, his input should be the whole codomain
   • subDouble -> Int
   • then we CANNOT compose them.
   • so you can think of function like a time related process
   • you can boil an egg; you CAN NOT unboil an egg

abstraction

from another point of view, we don't hope function to be invertible . Because we don't want to care about the inside of the set, we don't want to trap ourself to details, details is not abstractive.

model

but when refering to practical things, we should use model.we should do some mapping, that from 3-d person to 2-d shadow. In mathematics, if a function dose not collapse things, we call it injective function. And if image equals to Codomain, we call ti surjective function.

• collapse: 3-d person to 2-d shadow (many-to-one)
• injective: 3-d person without a hat to 3-d wax figure with a hat (one-to-one)
• surjective: 3-d person without a hat to 2-d shadow without a hat

or we can say:

• injective：一对一，不坍缩，有漏 or 无漏
• surjective: 多对一 or 一对一，坍缩，无漏

isomorphism = injective + surjective

what we talk about above in section 'model' is too detail: * one-to-one — element related * image equals Codomain — element related. But, as we said before, we don't like detail, we are talking about Cat. *can we describe clearly what is "injective" and "surjective" ONLY by morphism(arrow/function), if we can not see the elememnts*.

YES, we can, but it's a little tricky, because I have to talk about all the other objects in the category, all of them, in order to define this one property. This is very characteristic point in Cat. when you define a property of an object or an arrow, you define it with respect to essentially everything else. you can not just focus on one litte thing, because no matter how good your microscope is you cannot look inside this litter point.

How: first from a set, then we define a surjective function that can be expressed purely in terms of other functions.

what is not epimorphism: exist some point outside of image but inside of Codomain.

build a new set and build functions to compose original function:

f :: a->b

build 2 new functions: g1 and g2

g1 :: b->c
g2 :: b->c

prove by contradiction:if f is not surjective, we can not infer from: g1 * f = g2 * f to: g1 = g2 , for all set c, for any g1 and g2, if g1 * f = g2 * f => g1 = g2 , then f is a epimorphism function in Cat.

Although, we only build ONE new set, but if take it to any other Set, this epimorhpism will also avaiable. all above proving process, is so Cat manner: if you want define some property, you must take the WHOLE university( for all set c, for any g1 and g2 ) into account. Or we might say, if you want build some law, all people of the university must allow you to do, then you can do it. we also must notice that: what we use to define a epimorphism is just use and ONLY use function composition ,yes we did it. we just define something ONLY using arrows.

remember that, function is arrow from one set to another set, nothing related to details — the elements inside the set. So, by using and ONLY using function, we keep the abstraction of the Cat, this is what we want the abstraction

because: if f is epimorphism, then we can use it like GCD of production

3 * 2 = 3 * 2
=> 3 = 3

g1 * f = g2 * f if f is epimorphism => g1 = g2

1. 同构（isomorphism） 令f:X→Y为一个态射。若存在态射g:Y→X使得 和成立，则f称为一个同构。g称为f的逆态射， 逆态射g如果存在就是唯一的，而且显而易见g也是一个同构，其逆为f。两个对象之间 有一个同构，那么这两个对象称为同构的或者等价的。同构是范畴论中态射的最重要 种类。
2. 满同态（epimorphism） 一个态射f:X→Y称为一个满同态，如果对于所有Y→Z的态射g1 成立。这也称为epi或epic.具 体范畴中的满同态通常是满射（surjective）函数，虽然并不总是这样。
3. 单同态（monomorphism） 态射f:X→Y称为单同态，如果对于所有Z→X的态射g1，g2，成立。它也称为mono或者 monic.具体范畴中的单同态通常为单射（injective）函数。
4. 双同态（bimorphism） 若f既是满同态也是单同态，则称f为双同态（bimorphism）。注意每个同构都是双同态，但 不是每个双同态都是同构。例如，交换环的范畴中，包含映射Z → Q是一个双同态，但不是 一个同构。如果在一个范畴中每个双同态都是同构，则这个范畴称为一个平衡范畴。例如， 集合是一个平衡范畴。
5. 自同态（endomorphism）:任何态射f:X→X称为X上的一个自同态。
6. 自同构（automorphism）:若一个自同态也是同构的，那么称之为自同构。
7. 若f:X→Y和g:Y→X满足 可是证明f是满的而g是单的，而且:X→X是幂等的。这种情况下， f和g称为分割（split）.f称为g的收缩（retraction）而g称为f的截面。任何既是满同态又是分割单同态的态射，或者既是单同态又是分割满同态的态射必须是同构。

So, what is the simplest set . empty set is the simplest set

Dose empty set has related type in programming language. you will not find an empty set in any imperative language. But you can find it in Haskell, but I must say type in Hasekll have bottom member, so that the empty set is not empty, it does have a bottom member. But if you just ignore the infinite loop of executing, then the empty set is the correct type called Void , no construct inside it.

Is there f::Void -> Int ? .In mathematcis, yes. it is excellent, because we can now have a identity function:

f :: Void -> Int
id_void :: Void -> Void

this is a good function, but you can never call it, but it's sure exist.

Void is false in logic, you can not prove it, you can not prove false. and in type theory, function is something to do proving.

Singleton set : Unit

Unit :: a -> ()
one :: () -> Int
two :: () -> Int

for () is the type of Singleton set, so it only have one elment. so if it's taken as type of argument, then this function must always return the same value.

Then you will find a truth: if the output set have 2 elments, like Boolean. Then function of this form fn :: ()->Boolean only have 2 different function.

because in this situation, thers is no many-to-one mapping, there is ONLY one-to-one mapping. So, the number of elements in output set decide the number of mappings, do that decide the number of functions. A big BONG~~~ then you will find that, we may use and ONLY use function to compute the number of elements in output set

Function from a single set to any other set, they define in a way, the elements in a set. From elements to morphism(function/arrow). So we begin to discuss morphisms from this special set(Unit) instead of elements.

We further learn that boolean is not as atomic structure in our cagetory of set. In general, it can be defined as the sum of two unit types. this type is not so independent. but 0 and 1 element set (or type.), they form the basis for all others. A function that returns a Boolean type, called predikatom.