Okay: I've told you what a Galois connection is. But now it's time to explain why they matter. This will take much longer - and be much more fun.

Galois connections do something really cool: they tell you _the best possible way to recover data that can't be recovered_.

More precisely, they tell you _the best approximation to reversing a computation that can't be reversed._

Someone hands you the output of some computation, and asks you what the input was. Sometimes there's a unique right answer. But sometimes there's more than one answer, or none! That's when your job gets hard. In fact, impossible! But don't let that stop you.

Suppose we have a function between sets, \$$f : A \to B\$$ . We say a function \$$g: B \to A \$$ is the **inverse** of \$$f\$$ if

$g(f(a)) = a \textrm{ for all } a \in A \quad \textrm{ and } \quad f(g(b)) = b \textrm{ for all } b \in B$

Another equivalent way to say this is that

$f(a) = b \textrm{ if and only if } a = g(b)$

for all \$$a \in A\$$ and \$$b \in B\$$.

So, the idea is that \$$g\$$ undoes \$$f\$$. For example, if \$$A = B = \mathbb{R}\$$ is the set of real numbers, and \$$f\$$ doubles every number, then \$$f\$$ has an inverse \$$g\$$, which halves every number.

But what if \$$A = B = \mathbb{N}\$$ is the set of _natural_ numbers, and \$$f\$$ doubles every natural number. This function has no inverse!

So, if I say "\$$2a = 4\$$; tell me \$$a\$$" you can say \$$a = 2\$$. But if I say "\$$2a = 3\$$; tell me \$$a\$$" you're stuck.

But you can still try to give me a "best approximation" to the nonexistent natural number \$$a\$$ with \$$2 a = 3\$$.

"Best" in what sense? We could look for the number \$$a\$$ that makes \$$2a\$$ as close as possible to 3. There are two equally good options: \$$a = 1\$$ and \$$a = 2\$$. Here we are using the usual distance function, or [metric](https://en.wikipedia.org/wiki/Metric_(mathematics)), on \$$\mathbb{N}\$$, which says that the distance between \$$x\$$ and \$$y\$$ is \$$|x-y|\$$.

But we're not talking about distance functions in this class now! We're talking about _preorders_. Can we define a "best approximation" using just the relation \$$\le\$$ on \$$\mathbb{N}\$$?

Yes! But we can do it in two ways!

**Best approximation from below.** Find the largest possible \$$a \in \mathbb{N}\$$ such that \$$2a \le 3\$$. Answer: \$$a = 1\$$.

**Best approximation from above.** Find the smallest possible \$$a \in \mathbb{N}\$$ such that \$$3 \le 2a\$$. Answer: \$$a = 2\$$.

Okay, now work this out more generally:

**Puzzle 14.** Find the function \$$g : \mathbb{N} \to \mathbb{N}\$$ such that \$$g(b) \$$ is the largest possible natural number \$$a\$$ with \$$2a \le b\$$.

**Puzzle 15.** Find the function \$$g : \mathbb{N} \to \mathbb{N}\$$ such that \$$g(b)\$$ is the smallest possible natural number \$$a\$$ with \$$b \le 2a\$$.

Now think about [Lecture 4](https://forum.azimuthproject.org/discussion/1828/lecture-4-chapter-1-galois-connections) and the puzzles there! I'll copy them here with notation that better matches what I'm using now:

**Puzzle 12.** Find a right adjoint for the function \$$f: \mathbb{N} \to \mathbb{N}\$$ that doubles natural numbers: that is, a function \$$g : \mathbb{N} \to \mathbb{N}\$$ with

$f(a) \le b \textrm{ if and only if } a \le g(b)$

for all \$$a,b \in \mathbb{N}\$$.

**Puzzle 13.** Find a left adjoint for the same function \$$f\$$: that is, a function \$$g : \mathbb{N} \to \mathbb{N}\$$ with

$g(b) \le a \textrm{ if and only if } b \le f(a)$

Next:

**Puzzle 16.** What's going on here? What's the pattern you see, and why is it working this way?

**[To read other lectures go here.](http://www.azimuthproject.org/azimuth/show/Applied+Category+Theory#Course)**