Difference between revisions of "User:Michiexile/MATH198/Lecture 1"
Michiexile (talk | contribs) |
Michiexile (talk | contribs) |
||
Line 5: | Line 5: | ||
==Category== |
==Category== |
||
− | A ''graph'' is a collection |
+ | A ''graph'' is a collection <math>G_0</math> of ''vertices'' and a collection <math>G_1</math> of ''arrows''. The structure of the graph is captured in the existence of two functions, that we shall call ''source'' and ''target'', both going from <math>G_1</math> to <math>G_1</math>. In other words, each arrow has a source and a target. |
− | We denote by '' |
+ | We denote by ''[v,w]'' the collection of arrows with source ''v'' and target ''w''. |
A ''category'' is a graph with some special structure: |
A ''category'' is a graph with some special structure: |
||
− | * Each '' |
+ | * Each ''[v,w]'' is a set and equipped with a composition operation <math>[u,v] \times [v,w] \to [u,w]</math>. In other words, any two arrows, such that the target of one is the source of the other, can be composed to give a new arrow with target and source from the ones left out. |
+ | |||
+ | We write <math>f:u\to v</math> if <math>f\in[u,v]</math>. |
||
+ | |||
+ | <math>u \to v \to w</math> => <math>u \to w</math> |
||
− | ''u -> v -> w => u -> w'' |
||
* The composition of arrows is associative. |
* The composition of arrows is associative. |
||
− | * Each vertex ''v'' has a dedicated arrow |
+ | * Each vertex ''v'' has a dedicated arrow <math>1_v</math> with source and target ''v'', called the identity arrow. |
* Each identity arrow is a left- and right-identity for the composition operation. |
* Each identity arrow is a left- and right-identity for the composition operation. |
||
Line 23: | Line 26: | ||
* The empty category with no vertices and no arrows. |
* The empty category with no vertices and no arrows. |
||
* The category ''1'' with a single vertex and only its identity arrow. |
* The category ''1'' with a single vertex and only its identity arrow. |
||
− | * The category ''2'' with two objects, their identity arrows and the arrow |
+ | * The category ''2'' with two objects, their identity arrows and the arrow <math>a\to b</math>. |
− | * For vertices take vector spaces. For arrows, take linear maps. This is a category, the identity arrow is just the identity map |
+ | * For vertices take vector spaces. For arrows, take linear maps. This is a category, the identity arrow is just the identity map <math>f(x) = x</math> and composition is just function composition. |
* For vertices take finite sets. For arrows, take functions. |
* For vertices take finite sets. For arrows, take functions. |
||
* For vertices take logical propositions. For arrows take proofs in propositional logic. The identity arrow is the empty proof: ''P'' proves ''P'' without an actual proof. And if you can prove ''P'' using ''Q'' and then ''R'' using ''P'', then this composes to a proof of ''R'' using ''Q''. |
* For vertices take logical propositions. For arrows take proofs in propositional logic. The identity arrow is the empty proof: ''P'' proves ''P'' without an actual proof. And if you can prove ''P'' using ''Q'' and then ''R'' using ''P'', then this composes to a proof of ''R'' using ''Q''. |
||
* For vertices, take data types. For arrows take (computable) functions. This forms a category, in which we can discuss an abstraction that mirrors most of Haskell. There are issues making Haskell not quite a category on its own, but we get close enough to draw helpful conclusions and analogies. |
* For vertices, take data types. For arrows take (computable) functions. This forms a category, in which we can discuss an abstraction that mirrors most of Haskell. There are issues making Haskell not quite a category on its own, but we get close enough to draw helpful conclusions and analogies. |
||
− | * Suppose ''P'' is a set equipped with a partial ordering relation ''<''. Then we can form a category out of this set with elements for vertices and with a single element in '' |
+ | * Suppose ''P'' is a set equipped with a partial ordering relation ''<''. Then we can form a category out of this set with elements for vertices and with a single element in ''[v,w]'' if and only if ''v<w''. Then the transitivity and reflexivity of partial orderings show that this forms a category. |
Some language we want settled: |
Some language we want settled: |
||
− | A category is ''concrete'' if it is like the vector spaces and the sets among the examples - the collection of all sets-with-specific-additional-structure equipped with all functions-respecting-that-structure. We require already that '' |
+ | A category is ''concrete'' if it is like the vector spaces and the sets among the examples - the collection of all sets-with-specific-additional-structure equipped with all functions-respecting-that-structure. We require already that ''[v,w]'' is always a set. |
A category is ''small'' if the collection of all vertices, too, is a set. |
A category is ''small'' if the collection of all vertices, too, is a set. |
||
+ | |||
+ | ==Morphisms== |
||
+ | The arrows of a category are called ''morphisms''. This is derived from ''homomorphisms''. |
||
+ | |||
+ | Some arrows have special properties that make them extra helpful; and we'll name them: |
||
+ | |||
+ | ;Endomorphism:A morphism with the same object as source and target. |
||
+ | ;Monomorphism:A morphism that is greiu-cancellable. Corresponds to injective functions. |
||
+ | ;Epimorphism:A morphism that is feiru-cancellable. Corresponds to surjective functions. |
||
+ | |||
+ | ==Objects== |
||
+ | In a category, we use a different name for the vertices: ''objects''. This comes from the roots in describing concrete categories - thus while objects may be actual mathematical objects, but they may just as well be completely different. |
||
+ | |||
+ | Some objects, if they exist, give us strong |
Revision as of 12:11, 27 August 2009
Welcome, administrativia
Introduction
Why this course? What will we cover? What do we require?
Category
A graph is a collection of vertices and a collection of arrows. The structure of the graph is captured in the existence of two functions, that we shall call source and target, both going from to . In other words, each arrow has a source and a target.
We denote by [v,w] the collection of arrows with source v and target w.
A category is a graph with some special structure:
- Each [v,w] is a set and equipped with a composition operation . In other words, any two arrows, such that the target of one is the source of the other, can be composed to give a new arrow with target and source from the ones left out.
We write if .
=>
- The composition of arrows is associative.
- Each vertex v has a dedicated arrow with source and target v, called the identity arrow.
- Each identity arrow is a left- and right-identity for the composition operation.
Examples
- The empty category with no vertices and no arrows.
- The category 1 with a single vertex and only its identity arrow.
- The category 2 with two objects, their identity arrows and the arrow .
- For vertices take vector spaces. For arrows, take linear maps. This is a category, the identity arrow is just the identity map and composition is just function composition.
- For vertices take finite sets. For arrows, take functions.
- For vertices take logical propositions. For arrows take proofs in propositional logic. The identity arrow is the empty proof: P proves P without an actual proof. And if you can prove P using Q and then R using P, then this composes to a proof of R using Q.
- For vertices, take data types. For arrows take (computable) functions. This forms a category, in which we can discuss an abstraction that mirrors most of Haskell. There are issues making Haskell not quite a category on its own, but we get close enough to draw helpful conclusions and analogies.
- Suppose P is a set equipped with a partial ordering relation <. Then we can form a category out of this set with elements for vertices and with a single element in [v,w] if and only if v<w. Then the transitivity and reflexivity of partial orderings show that this forms a category.
Some language we want settled:
A category is concrete if it is like the vector spaces and the sets among the examples - the collection of all sets-with-specific-additional-structure equipped with all functions-respecting-that-structure. We require already that [v,w] is always a set.
A category is small if the collection of all vertices, too, is a set.
Morphisms
The arrows of a category are called morphisms. This is derived from homomorphisms.
Some arrows have special properties that make them extra helpful; and we'll name them:
- Endomorphism
- A morphism with the same object as source and target.
- Monomorphism
- A morphism that is greiu-cancellable. Corresponds to injective functions.
- Epimorphism
- A morphism that is feiru-cancellable. Corresponds to surjective functions.
Objects
In a category, we use a different name for the vertices: objects. This comes from the roots in describing concrete categories - thus while objects may be actual mathematical objects, but they may just as well be completely different.
Some objects, if they exist, give us strong