Welcome, Johan!
I studied c.s., but have a gap in my learning when it comes to Haskell.
Can you write a little bit about some of the key ways in which constructs from category theory are used in Haskell?
Of course I could find this on the web, bu…
The number of comparisons QUICKSORT makes to sort a list of \(n\) values is a random variable.
Let \(X_n\) be the number of comparisons QUICKSORT makes to sort a list of \(n\) values, and let \(M_n = E[X_n]\).
Let \(Y\) be rank of the number \(x_i…
From Introduction, cont'd.
Analysis of QUICKSORT.
QUICKSORT(\(x_1, ..., x_n\)):
If \(n = 0\) or \(n = 1\), no sorting needing, so return.
Randomly choose \(x_i\).
Divide up the remaining values into two sets \(L\) and \(H\), where \(L\) is the …
Notes from Introduction.
Examples of stochastic systems: CPU with jobs arriving in random fashion; network multiplexor with packets arriving randomly; a store with random demands on its inventory.
Prob. A monkey hits keys on a typewriter randoml…
Hi Maria, I am curious to know about the connections between music and category theory that you have drawn. Would it be possible for you to post a link to a paper or two that you consider to be of interest?
I tried to download a couple from your …
I think of meet as what is common to the two -- the point at which they meet -- so that's the intersection. Joining implies combining them to make something bigger, which is the union.
Let P be a poset.
Then the least upper bound of {} is, naturally, the least of the upper bounds of {}. Every member of P is an upper bound for {}. So the least upper bound for {} is the least member of P, i.e., the minimum element of P -- if suc…
There's a good function going the other way, \(f^{\ast}: PY \rightarrow PX\), the preimage function, defined by
$$f^{\ast}(S \in PY) = \{x \in X: f(x) \in S\} .$$
Claim: this is right adjoint to the image function \(f_{\ast}: PX \rightarrow PY\).
…
Inverse functions as a special case of adjoints: if \(A\) and \(B\) be preorders, where the ordering is the identity relation, then \(f: A \rightarrow B\) and \(g: B \rightarrow A\) are adjoint iff they are inverse functions.
BTW I've been with the Azimuth Project for some time now, and am running the server for the wiki and the forum. I'm not from the first generation of Azimuth, though, which was ending as I joined. This third generation is very exciting!
If peopl…
It makes logical sense to have a separate discussion for each exercise. The downside is that there will be a lot more discussions, which could make it harder to navigate to the main discussions - especially the lectures.
We could control this usi…
Puzzle 7. Why does any set with a reflexive and transitive relation \(\le\) yield a category with at most one morphism from any object \(x\) to any object \(y\)? That is: why are reflexivity and transitivity enough?
To answer this, let's go thro…
Michael Hong wrote:
In wikipedia, it says a poset can only have at most one relation per pair. Why is this?
Two relations per pair would mean both \(x \le y\) and \(y \le x\). By antisymmetry, then \(x = y\). Then the "pair" is just…
Michael Hong wrote:
Must posets be connected?
Let S be a set, which is ordered only by the identity relation -- i.e., all that we have is \(x \le x\), for all \(x\). That's a poset. And it's as disconnected as it gets: there are no …
In comment # 101, Matthew Doty addressed this question:
What are all the total orders that are also equivalence relations?
And proved that for these orders: \(\forall x, y. x \leq y\).
That's correct, but a stronger conclusion follows: the o…
Example of a monotone mapping:
Let T be the nodes of a tree, ordered by the following relation: \(x \le y\) means \(x\) is an ancestor of \(y\) in the tree.
Let \(h(n)\) be the height of the node in the tree, i.e. the number of edges in the path …
Example of a monotone mapping: a function that maps \(\mathbb{Z}\) to \(\mathbb{Z}\) by adding a constant \(c\) to the input integer, i.e., the translation function lambda x: x + c.
The powerset \(2 ^ S\), which consists of all subsets of \(S\), is a preorder (and a poset) under the inclusion relation.
For another set \(T\), the function from \(2 ^ S\) into \(2 ^ T\) that is defined by intersection with \(T\) is monotone.