Tag Archives: math

Representable functors in Haskell

I have finally managed to upload a (dry version) of a note about representable functors in Haskell. You can find it here: http://covariant.me/notes/rep-functors.html

Representable functors are functors that are isomorphic to $Hom(A, -)$ or $Hom(-, A)$ for some object $A$. In the note I give examples of some simple representable functors and prove that Maybe is not representable.

Proving the Eisenstein’s criteria

Polynomial A = x^n + a_{n-1}x^{n-1} + .. + a_1 x + a_0, where each a_i is divisible by some number p, is irreducible in \mathbb Q when p^2 does not divide a_0.
If A is not irreducible then there are some F and G such as A = FG.
But that means that a_0 = f_0 g_0, which means that (p | f_0) XOR (p | g_0) (since p^2 does not divide a_0).
Let’s assume that p | f_0. Now let’s take a map Z[x] \rightarrow (Z/pZ)[x] (I believe this method is called homomorphism-reduction).
[A] = x^n, but [G] = \cdots + [g_0], where [g_0] \neq 0.
That is possible only when [G] is constant and [F] = [A]/[G]. Which means that A is irreducible.

Note: here [a] denotes f(a) where f is a homomorphism Z[x] \rightarrow (Z/pZ)[x].

Example of using Eisenstein criterion..

Union of countable sets is countable.

Let’s say we have a possibly infinite countable collection of countable sets A_1, A_2, \cdots, A_n, \cdots, prove that \bigcup A_i is countable too. We are going to do this using Axiom of Choice.

Since every set A_i is countable, there is a set of injections from N to A_i, let’s call it M_i. Using the axiom of choice we can create a set of maps \{g_1, g_2, \cdots\} from N to A_i. Now, we are going to create an injection from (N, N) to \bigcup A_i. If x_k is an element of \bigcup A_i then it’s also an element of some set A_m. Therefore we can construct f(z, m) = x_k where x_k = g_m(z). And since we know that (N, N) is countable, we can map N to \bigcup A_i. QED.