Category of Sets

Definition of Category

DATA

• Objects(\(A,B,C\))
• MAPS(\(f,g,h\))
• DOMAIN -> CODOMAIN(\(f: A \rightarrow B\))
• IDENTITY MAP(\(1_A : A\xrightarrow{1_A}B\))
• COMPOSITE MAP(\(A\xrightarrow{f}B\xrightarrow{g}C = A\xrightarrow{g \circ f}C\))

RULES

• IDENTITY LAW(\(f:A\rightarrow B; f = 1_B \circ f = f \circ 1_A\))
• ASSOCIATIVE LAW (\(h \circ g \circ f = h \circ (g \circ f)\))

Sets & Maps

• Maps = Functions (Internal diagram/External diagram)
• Test of equality: (for every \(x \in A\))
• endomap

Algebra of Composition

Isomorphisms

• Isomorphism / Invertible map (bijection,\(f: A \rightarrow B\), A B are isomorphic \(A \cong B\))
• Made two objects virtually the same
• Inverse of f => g at most 1
• Transitive
• Endomap => automorphism / permutation

Isomorphisms in algebra

• Sets + combining-rule(*)
• \(f (a*b) = (f a)*'(f b)\)

Det / Choice

• Determination (extension): \(f: A \rightarrow B; h: A\rightarrow C; \Rightarrow h = g \circ f, g = h \circ f^{-1}\), right div
  • Retraction: More to Less \(C=A; h = 1_A\)
  • = has solution for all determination problems
  • \(f \circ x_1 = f \circ x_2 \Rightarrow x_1 = x_2\)
  • f is injective / monomorphism
• Choice (lifting): \(g: B \rightarrow C; h: A\rightarrow C; \Rightarrow h = g \circ f, f = g^{-1} \circ f\), left div
  • Section (cross section): Less to More \(C=A; h = 1_A\)
  • = has solution for all choice problems
  • \(x_1 \circ f = x_2 \circ f \Rightarrow x_1 = x_2\)
  • epimorphism
• Both retraction and section are transitive
• Idempotent: endomap \(e: e \circ e = e\)
• Constant map -> can be factored through 1

Maps

• Stacking/Sorting/fibering/partitioning: elements of the same label
• naming/listing/sampling/parameterizing of codomain
  • produce structure in the codomain

Abuses of Isomorphism

• Isomorphism of sets doesn’t pass alone internal structure
• Add the label for objects in two different sets (Objective -> Subjective)

Retraction & idempotent

• \(A \xrightarrow{s} B \xrightarrow{r} A; e = s \circ r\)
• fixed point of endomap
• idempotent map e, spliting of e
  • Object A
  • \(A \xrightarrow{s} B, A \xleftarrow{r} B, r \circ s = 1_A: e = s \circ r\)
  • \(|B| = \mbox{number of fixed point in }A\)
• fixed point property: \(\forall f: X \rightarrow X, \exists x: T \rightarrow X: f \circ x=x\)

Three kinds of problems

• Museum director’s: \(B \xrightarrow{r} A \Rightarrow \mbox{choose } A \xrightarrow{s} B: r \circ s = 1_A\)
• Bird-watcher’s: \(A \xrightarrow{s} B \Rightarrow \mbox{choose } B \xrightarrow{r} A: r \circ s = 1_A\)
• Child’s: \(B \xrightarrow{e} B: e \circ e = e\)

Brouwer’s theorems

Continuous maps: f(p) doesn’t jump.

• Brouwer fixed point theorem
  • I line segments. continuous endomap \(f: I \rightarrow I\), must have fixed point where f(x)=x.
  • D closed disk. must have a fixed point for endomap f.
  • Solid map. has a fixed point.
• Banach’s fixed point theorem (Contraction maps)
• Brouwer retraction theorem
  • Inclusion map \(j: E \rightarrow I\), of two-point set E as boundary of interval I. No continuous map which is a retraction.
  • no continuous map: \(circle \rightarrow disk\)
  • also, Sphere S, ball B, \(f: S \rightarrow B\)
• No continuous retraction to boundary, then has a fixed point
• Contrapositive: Contunous endomap with no fixed point, then continuous retraction to its boundary(proved by imaging f(x),x to boundary)
• Inclusion map f is when \(A \subset B, f: A \rightarrow B\)

Categories of Structured Sets

maps as extra structure on sets & “structure-preserving maps” \[S \Rightarrow S^{\circlearrowright}\]

Category of endomap of sets

\[X^{\circlearrowright \alpha} \xrightarrow{f} Y^{\circlearrowright \beta}\] if satisfies \[f \circ \alpha = \beta \circ f\] preserves the given structure

isomorphisms will mean equal number of everything

Map & properties

• Positive properties -> Preserved
  • accessibility
• Negative properties -> Reflected
  • not being a fixed point
• Period of n : \(\alpha^n(x) = x\) produce a cycle of period n: \(C_n\) 1: fixed point
• Successor map\(\sigma : N \rightarrow N, N^{\circlearrowright \sigma}\) corresponds to any \(Y^{\circlearrowright \beta}\)
  • evaluation & iteration : recapture Y
  • \(\sigma ,f \mbox{ recapture } \beta\)

Typical applications

• dynamical system/automata (sets of possible states)
  • \(\alpha (\alpha (x))\) as the natural advancement of time
  • presentations
    1. names for some elements, hair ends or single elem in loop
    2. list them
    3. apply \(\alpha\)
    4. remove identicals till distinct with labels & relations
  • maps keep relations
• question of acessibility, have x’ possible to get to x, x = a(x’)
• question of covergence to equilibrium, give x, possible to have \(\alpha^{n+1} (x) = \alpha^{n} (x)\)

Two subcategories

\[S^{\circlearrowright} \begin{cases} \supset S^e \\ \supset S^{circleftrightarrow} \end{cases}\]

• all idempotent endomaps of sets
  • contains only fixed points with branches
  • corresponding fixed points with corresponding branches
• invertible endomaps (automorphism,permutations)
  • only circles (0 -> “fixed point”)

For any category

• e is any category, we can build \(e^{\circlearrowright}\) as we build it for S
  • many full subcategories:
  • \(endomaps \supset idempotents \supset identities\)
  • \(endomaps \supset automorphisms \supset involutions(e^{\theta}) \supset identites\)
  • θ is an involutions of A, if and only if \(\theta \circ \theta = 1_A\)
    • internal diagram: “2-cycles” & fixed points

Irreflexive graphs (Irreflexive directed multi-graphs, graphs)

Pair of sets(X,Y) + pair of maps(s,t)

• s : Source of X
• t : Target of X
• endomaps are a subcategory of it
  • \(s: 1_X, t: \alpha\)

A map between them is a pair of maps of sets * \(X \xrightarrow{f_A} X'\) * \(Y \xrightarrow{f_D} Y'\) * \(f_D \circ s = s' \circ f_A\) * \(f_D \circ t = t' \circ f_A\)

impossible journeys: maps from G to

• \(0 \rightarrow 0, 1 \rightarrow 1, 1 \rightarrow 0\)
• for \(b \rightarrow 0, e \rightarrow 1\)
  • no path from b to e
  • paths are maps from path to graphs

Free category created by graph G, arrows as functions, points as objects

• A diagram of shape G commutes
  • for each pair p,q, all paths are interpreted as the same map(not necessarily labled)

Reflexive graphs

\[X \xleftarrow{i} P, X \xrightarrow{s,t} P\]

• \(s \circ i = 1_p\)
• \(t \circ i = 1_p\)
• the level of dots f can be evaluated by just knowing f at the level of arrows
  • \(f_D = 1_Q \circ f_D =s' \circ j \circ f_D = s' \circ f_A \circ i\)
  • Preferred loops, makes an arrow degenerate into a point of H

Retraction and Injectivity

\[retraction \cong injectivity\]

Injective a: iff for any maps x1 x2, \(a \circ x_1 = a \circ x_2 \Rightarrow x_1=x_2\)

Types of structure

• A set of names for the components of structure
• A set of names for the crucial structure maps
• Specification which structural component object is the domain or codomain

Monoids

• Definition : A category with exactly one object
  • many endomaps
  • with the unit map(identity): \(e \circ f = f\)
  • and multiplication op
• functor: structure-preserving interpretation of one category into another
• Ex: for endomaps \(X^{\circlearrowright \alpha}\)
  • \(h(*) = X\)
  • \(h(n) = \alpha^n\)
  • \(h(0) = 1_X\)

Elementary universal mapping properties

Terminal objects

• S: For each object X of e there is exactly one e-map: \(X \rightarrow S\)
  • Uniqueness of terminal object: all terminal objects are isomorphic

• 1 is terminal object of e, e-map: \(1 \rightarrow X\) is a point of X

• Construction: use the property of only having one map
• for Irreflexive graphs
  • 1 arrow + 1 point(just like fixed point for the endomaps)

Separating

• \(f,g: X \rightarrow Y, f \neq g, \exists B: B \xrightarrow{x} X, with f \circ x \neq g \circ x\)
  • x separates f from g
  • most categories terminal object is not sufficient describe all the structures
  • endomaps only fixed point is described

Initial objects

• S: For every object X of e there is exactly one e-map: \(S \rightarrow X\) (dual of terminal object)
  • Uniqueness of initial object
  • Abstract sets: initial object -> empty set

Products

• An object P, a pair of maps \(P \xrightarrow{p_1} B_1, P \xrightarrow{p_2} B_2\)
• for each X and \(X \xrightarrow{f_1} B_1, X \xrightarrow{f_2} B_2\)
• exactly one map \(X \xrightarrow{f} P, \mbox{ which } f_1 = p_1 \circ f, f_2 = p_2 \circ f\)
  • \(f \rightarrow <f_1,f_2>\)
  • projections
  • \(P \rightarrow B_1 \times B_2\)
  • can be expanded to more objects
• \(\#(A \times B) = \#A \times \#B\)
• Uniqueness of products (all are isomorphic)
  • commutative
  • associative
  • identity
• involves interaction of the elements of factors
  • binary op on an object A: \(A \times A \rightarrow A\)
  • action of an object A on an object X: \(A \times X \rightarrow X\)
• Construction: making sure the additional structures are preserved
  • Circle of 2 & 3 gives a circle of 6
  • circle of 2 & 4 gives two circles of 4
  • circle of a & b gives gcd(a,b) circles of ab/gcd(a,b)

Sum(Coproduct)

• An object S, a pair of maps \(B_1 \xrightarrow{j_1} S, B_2 \xrightarrow{j_2} S\)
• for each object Y and pair of maps \(B_1 \xrightarrow{g_1} Y, B_2 \xrightarrow{g_2} Y\)
• exactly one map, \(S \xrightarrow{g} Y, \mbox{ which } g_1 = g j_1, g_2 = g j_2\)
  • injections \[g =\begin{cases} g_1 \\ g_2 \end{cases}\]

Distributive laws

not universal, only if the standard maps are satisfied(always isomorphisms):

• \((A \times B_1) + (A \times B_2)+ \dots + (A \times B_n) \rightarrow A \times (B_1 + B_2 + \dots + B_n)\)
  • general distributive law
  • use injection and projection relations to construct the matrix \[f = \begin{bmatrix} f_{1A} & f_{1B} \\ f_{2A} & f_{2B} \end{bmatrix}\] from coproducts to factors, then represents them using in/pro

• \(0 \rightarrow A \times 0\)

• Satisfy:
  • set
  • set + endomap
  • Irreflexive graph
• Not satisfy:
  • pointed sets: set plus garbage point(\(1 \xrightarrow{x} X\)), A+B, glue by base/garbage point
  • linear categories
  • A category with zero maps in which every ‘identity matrix’ is an isomorphism

\[f = \begin{bmatrix} 1_X & 0_{XY} \\ 0_{YX} & 1_Y \end{bmatrix}: X+Y \rightarrow X \times Y\]

Universal mapping properties, Incidence relations

• Universal mapping properties
• detecting the structure of an object by means of figures and incidence relations
  • singular figures: mapping collapses the original structure
  • original factors through the singular
    • for Successor: the future of x(0) has “singular shape”
  • big arrow head means epimorphism
    • Any problem of factoring a map through such a map has at most one solution
    • right cancellative: \(g_1 \circ f = g_2 \circ f \Rightarrow g_1 = g_2\)
  • Incidence relations: to what extent figures are incident
    • In X, figure x of shape A and figure y of shape B
    • possibility 1 :\(u: A \rightarrow B, y \circ u = x\)
    • possibility 2 :\(T, u_1: T \rightarrow A, u_2: T \rightarrow B, x \circ u_1 = y \circ u_2\)
• In sets: If two maps agree on points, they are the same map.
• In endomaps: any pair of maps f,g, if for all \(N^{\circlearrowright \sigma} \xrightarrow{x} X^{\circlearrowright \alpha}, f \circ x = g \circ x \Rightarrow f = g\)
• In graphs: any pair of maps f,g, if for all arrows & dots blah blah

Universal Construction

• colimits
  • Initial object
  • sum of two objects
• limits
  • Terminal objet
  • product of two objects
• negative of object
  • \(A + B = 0\)
• reciprocal of object
  • \(A \times B = 0\)
• Idempotent objects

• \(C \times C = C\)

• solving equations
  • if fx = gx, x is the solution of the equation f = g
  • Universal solution: one that “includes” all other solutions
  • equalizer of f,g: \(E \xrightarrow{p} X\), if fp = gp and for each \(T \xrightarrow{x} X\), fx = gx
  • exactly one \(T \xrightarrow{e} E\) for which x = pe.
  • dual: coequalizer
• graphs picturing the behavior of particular functions
  • for any \(X \xrightarrow{f} Y\), unique sections \(\Gamma \mbox{ of } p_x \mbox{ for which } f = p_y \Gamma, \Gamma =<?,f>\)

Binary operations and diagonal arguments

• Binary operations and actions
  • can be viewed as family of maps determined by the set of actions
  • parameterized maps
• (Georg Cantor’s) diagonal theorem(in any category with product)¹
  • if Y is an object such that
  • there exists an object T with enough points to parameterize all the maps \(T \rightarrow Y\)
  • by means of some single map \(T \times T \xrightarrow{f} Y\)
  • then Y has the fixed point property: every endomap of Y has at least one fixed point
• Cantor’s Contrapositive Corollary

Higher universal mapping properties

Map objects(Exponentiation)

• Definition of map object(function space)
  • Given two objects T,Y in a category with products
  • an object M together with a map \(T \times M \xrightarrow{x} Y\) is
  • an object of maps from T to Y with evaluation map
  • provided M and e satisfy: for each X and each map \(T \times X \xrightarrow{f} Y\)
  • there is exactly one map \(\lceil f \rceil :X \rightarrow M\) for which \(f = e(1_T \times \lceil f \rceil)\)
• an boject denoted Y^T
• a map e, called evaluation
• e is called evaluation map, M can use symbol \(Y^T, T \times Y^T \xrightarrow{e} Y\)

Law of exponents

• Base is a product: \((Y_1 \times Y_2)^T \cong Y_1^T \times Y_2^T\)
• exponent is a sum: \(Y^{T_1 + T_2} \cong Y^{T_1} + Y^{T_2}\)

Distributivity

• If sum exists in e and T is an object such that map objects \(Y^T\) exist for all objects Y
• e stisfies the distributive law for multiplication by T

Universal properties and ‘observables’

• Chaotic: observable \(X \xrightarrow{f} Y\) on a dynamical system \(X^{\circlearrowright \alpha}\)
• induced \(S^{\circlearrowright}-map\) \[X^{\circlearrowright \alpha} \xrightarrow{\bar{f}} (Y^N)^{\circlearrowright \beta}\]

• is onto for states: for every possible sequence is generated by at least one state in X

• Admissible notion of underlying configuration: faithful

• every two equal sequences must be generated by the same state in X

Contravariant parts functor

Parts and stable conditions

• Stable condition: figure of some shape has the same condition after transform

• \(x:A \rightarrow X\) is in \(g:W \rightarrow X\) (x belongs to g) if and only if there exists \(w:A \rightarrow W\), for which \(x = gw\)

• An image of a map g is a part i of the codomain of g for which
  • g is in i
  • for all parts j, if g is in j then i is in j
• sets: \(2=\{true,false\}\)
• dynamical systems: \(\{Inf \rightarrow Inf\}+prev\)

• Irreflexive graphs: \(\{a\rightarrow b,b\rightarrow a, a\rightarrow a,b\rightarrow b,b\rightarrow b\}\)

Toposes and logic

• e/X is maps of e with codomain X
• topos
  • e has 0,1,x,+,and for every X, e/X has product
  • e has map objects \(Y^X\)
  • e has truth value object \(1 \rightarrow \Omega\)(Subobject classifier)
• logic: \(T\xrightarrow{a=<b,c>} \Omega \times \Omega \xrightarrow{x} \Omega\)
  • And/intersection: \(x = \wedge, \wedge \circ <b,c> = b \wedge c\)
  • Implication: \(x = \Rightarrow,b \Rightarrow c = b \subseteq c\)
  • Or/disjunction: \(x = \vee\)

• Rules \[\frac{\xi \subseteq \beta_1 \times \beta_2}{\xi \subseteq \beta_1 \mbox{ and } \xi \subseteq \beta_2}\] modus ponens rule of inference \[\frac{\xi \subseteq (\alpha \Rightarrow \eta)}{\xi \wedge \alpha \subseteq \eta}\] \[\frac{\beta_1 \vee \beta_2 \subseteq \xi}{\beta_1 \subseteq \xi \mbox{ and } \beta_2 \subseteq \xi}\] \[not \varphi \overset{def}{=} [\varphi \Rightarrow false]\]

• \(\varphi \wedge not\varphi = false\)
• \(\varphi \subseteq not \; not \varphi\)
  • might not be equal, consider Irreflexive graph

Inverse image and truth

• Inverse image of i along f
• a part j such that for any x

• x is in j if and only if fx is in i

• subobject classifier or truth value object
• An object \(\Omega, v: T\xrightarrow{v} \Omega\)
• for every part g of any X
• exactly one map \(f:X\rightarrow \Omega\), g is the inverse image of v along f

• fx is the truth value of x belongs to g

The connected components functor

• Connectedness: undirected path leads from d to d’
• Reflexive graphs are made of connected components

• Discrete: no arrow other than the degenrate loop(dynamical system: rest states)

• A map \(X\rightarrow \pi_0 X\) with discrete codomain is universal if for every \(X \rightarrow S\) with discrete codomain
• there is exactly one map \(\pi_0 X \rightarrow S\) making a commutative triangle
• \(\pi_0 X\) space of components

• inverse imange of any point i of it i-th connected component of X

• A map \(|X| \rightarrow X\) with discrete domain is universal if for every \(S \rightarrow X\) with discrete domain
• there is exactly one map \(S \rightarrow |X|\) making a commutative triangle

• |X| is the space of points of X

• Small monoid a set M with a given associative multiplication \(M \times M \rightarrow M\) with unit\(1\rightarrow M\)
• Representation of M, or right action of M on a set X is given map \(X \times M \rightarrow X\) denoted by juxtaposition

• \(x(ab) = (xa)b\), \(x1=x\)