Galois Connection in various branches

Galois Connection is a pretty concept in order and category theory.

Consider $(A,\le ),(B,⪯)\in \mathrm{O}\mathrm{b}(\mathrm{P}\mathrm{o}\mathrm{s})$$(A,\le),(B,\preceq)\in\rm Ob(Pos)$, $f\in {\mathrm{Hom}}_{\mathrm{Pos}}(A,B),g\in {\mathrm{Hom}}_{\mathrm{Pos}}(B,A)$$f\in \mathrm{Hom}_{\mathrm{Pos}}(A,B),g\in \mathrm{Hom}_{\mathrm{Pos}}(B,A)$.

If

$$\begin{array}{}\text{(1)}& f(a)⪯b⟺a\le g(b)\end{array}$$

Then we called the pair $(f,g)$$(f,g)$ Galois Connection.

If you view $(A,\le ),(B,⪯)$$(A,\le),(B,\preceq)$ as two Categories, then $f,g$$f,g$ is just a pair of adjoint functors.

Lemma. The left adjoint preserves the direct limit, and the right adjoint preserves the inverse limit.

Since $f(a)⪯b⟺a\le g(b)$$f(a)\preceq b\iff a\le g(b)$ is just ${\mathrm{Hom}}_B(f(a),b)\cong {\mathrm{Hom}}_A(a,g(b))$$\mathrm{Hom}_{B}(f(a),b)\cong\mathrm{Hom}_{A}(a,g(b))$.

In this essay, I will show many examples of Galois Connection. The notation $i$$i$ always refer to inclusion map.

In the previous essay, we already have an interesting Galois Connection.

i.e.

$$\begin{array}{}\text{(2)}& (A)\wedge B\models C⟺A\models B\to (C)\end{array}$$

Where $f$$f$ is $A\wedge ()$$A\wedge()$ and $g$$g$ is $B\to ()$$B\rightarrow()$. (Not only in Boolean Algebra, its for Hearing Algebra)

Then $A\wedge (B_1\vee B_2)=A\wedge (B_1)\vee A\wedge (B_2)$$A\wedge (B_1\vee B_2)=A\wedge(B_1)\vee A\wedge(B_2)$, $B\to (C_1\wedge C_2)=B\to (C_1)\wedge B\to C_2$$B\to(C_1\wedge C_2)=B\to(C_1)\wedge B\to C_2$.

It is not hard to see that

$$\begin{array}{}\text{(3)}& f(a)⪯f(a)⟺a\le gf(a)\end{array}$$

Similarly

$$\begin{array}{}\text{(4)}& g(b)\le g(b)⟺fg(b)⪯b\end{array}$$

i.e.

$$\begin{array}{}\text{(5)}& f(a)⪯f(gf)(a)=fgf(a)=(fg)f(a)⪯f(a)\end{array}$$

Thus

$$\begin{array}{}\text{(6)}& fgf=f\end{array}$$

Similarly

$$\begin{array}{}\text{(7)}& g(b)\le (gf)g(b)=gfg(b)=g(fg)(b)\le g(b)\end{array}$$

Thus

$$\begin{array}{}\text{(8)}& gfg=g\end{array}$$

Thus $gf$$gf$ and $fg$$fg$ is idemponent.

Trivial but important example:

if $f:X\to Y$$f:X\to Y$ is a function, then $f:P(X)\to P(Y)$$f:P(X)\to P(Y)$ and $f^{-1}:P(Y)\to P(X)$$f^{-1}:P(Y)\to P(X)$ form a Galois Connection.

$$\begin{array}{}\text{(9)}& f(U)\subseteq H⟺U\subseteq f^{-1}(H)\end{array}$$

Immediately, $f(U_1\cup U_2)=f(U_1)\cup f(U_2),f^{-1}(H_1\cap H_2)=f^{-1}(H_1)\cap f^{-1}(H_2)$$f(U_1\cup U_2)=f(U_1)\cup f(U_2), f^{-1}(H_1\cap H_2)=f^{-1}(H_1)\cap f^{-1}(H_2)$.

Since left adjoint preserve direct product, right adjoint preserve inverse product.

Immediately, $f:X\to Y$$f:X\to Y$ is open map(map open set to open set) if and only if $f^{-1}:\mathrm{Op}(Y)\to \mathrm{Op}(X)$$f^{-1}:\mathrm{Op}(Y)\to \mathrm{Op}(X)$ has left adjoint.

Since the left adjoint should be $f:\mathrm{Op}(X)\to \mathrm{Op}(Y)$$f:\mathrm{Op}(X)\to \mathrm{Op}(Y)$,

$$\begin{array}{}\text{(10)}& f(U)\subseteq H⟺U\subseteq f^{-1}(H)\end{array}$$

One interesting example is the contraction and extension of the ideal.

Let $\phi :R⟶S$$\varphi: R\longrightarrow S$ be a ring homomorphism.

Then for an Ideal $I\subset S$$I\subset S$, ${\phi }^{-1}(I)$$\varphi^{-1}(I)$ is an ideal as well, denoted as $I^c$$I^c$.

Since if $a,b\in I^c$$a,b\in I^c$, then $\phi (a)+\phi (b)=\phi (a+b)\in I$$\varphi(a)+\varphi (b)=\varphi(a+b)\in I$, thus $a+b\in I^c$$a+b\in I^c$.

If $a\in I^c,r\in R$$a\in I^c,r\in R$, then $\phi (ra)=\phi (r)\phi (a)\in I$$\varphi(r a)=\varphi(r)\varphi(a)\in I$, thus $ra\in I^c$$ra\in I^c$. Thus $I^c$$I^c$ is an ideal in $R$$R$.

Let $I^{\prime }$$I'$ be an ideal in $R$$R$, then let $(\phi (I^{\prime }))$$(\varphi(I'))$ be the ideal generated by $\phi (I^{\prime })$$\varphi(I')$, denote as $I^{\prime e}$$I'^e$.

Remark $I^{\prime e}=\phi (I^{\prime })$$I'^e=\varphi(I')$ if $\phi$$\varphi$ is surjective. Since every $s\in S$$s\in S$ can be written as $\phi (r)$$\varphi(r)$. We will use it later.

Then $(-{)}^c:(I_S,\subseteq )⟶(I_R,\subseteq )$$(-)^c:(I_S,\subseteq)\longrightarrow (I_R,\subseteq)$, $(-{)}^e:(I_R,\subseteq )⟶(I_S,\subseteq )$$(-)^e: (I_R,\subseteq)\longrightarrow (I_S,\subseteq)$ form a Galois Connection.

Indeed,

$$\begin{array}{}\text{(11)}& (-{)}^e⊣(-{)}^c\end{array}$$

i.e.

$$\begin{array}{}\text{(12)}& I^e\subseteq J⟺I\subseteq J^c\end{array}$$

Proof

$$\begin{array}{}\text{(13)}& \phi (I)\subseteq J⟺(\phi (I))\subseteq J\text{ and }\phi (I)\subseteq J⟺I\subseteq {\phi }^{-1}J\end{array}$$

$◻$$\square$

Then, you can use the property of Galois Connection and adjoint to study the extension and contraction of Ideal.

For example, the right adjoint preserves inverse limit, thus $(I\cap J{)}^c=I^c\cap J^c$$(I\cap J)^c=I^c\cap J^c$.

Trivial example again.

Let $(\mathbb{Z},\le ),(\mathbb{R},\le )$$(\mathbb Z,\le),(\mathbb R,\le)$ be the posets, $i:\mathbb{Z}\to \mathbb{R}$$i:\mathbb Z\to\mathbb R$ be the inclusion map, $\lfloor -\rfloor$$\lfloor-\rfloor$ be the floor function.

$$\begin{array}{}\text{(14)}& i(n)\le x⟺n\le \lfloor x\rfloor \end{array}$$

In other words, the floor function is the right adjoint of the inclusion map. $i⊣\lfloor -\rfloor$$i\dashv\lfloor-\rfloor$.

By duality, if you change$(\mathbb{Z},\le )$$(\mathbb Z,\le)$ to $(\mathbb{Z},\ge )$$(\mathbb Z,\ge)$ $(\mathbb{R},\le )$$(\mathbb R,\le)$ to $(\mathbb{R},\ge )$$(\mathbb R,\ge)$, then:

$$\begin{array}{}\text{(15)}& i(n)\ge x⟺n\ge \lceil x\rceil \end{array}$$

If you do not want to change the order, then

$$\begin{array}{}\text{(16)}& \lceil x\rceil \le n⟺x\le i(n)\end{array}$$

The ceiling function is left adjoint of the inclusion map $\lceil -\rceil ⊣i$$\lceil - \rceil\dashv i$.

Some readers might observe that there exist an analogy between radical $\sqrt{-}$$\sqrt -$ and $\lceil -\rceil$$\lceil - \rceil$.

$\lceil -\rceil$$\lceil - \rceil$ send a real number to the least upper natural number, and $\sqrt{-}$$\sqrt-$ send a ideal to the least upper radical ideal.

Let $R$$R$ be a ring. and $(I,\subseteq )$$(I,\subseteq)$ be the partial order of Ideal in $R$$R$, $(\mathrm{rad}(I),\subseteq )$$(\mathrm{rad}(I),\subseteq)$ be the partial order of the radical ideal in $R$$R$.

Then

$$\begin{array}{}\text{(17)}& \sqrt{I}\subseteq J⟺I\subseteq i(J)\end{array}$$

Proof

$⟹$$\Longrightarrow$ :$I\subseteq \sqrt{I}\subseteq J=i(J)$$I\subseteq\sqrt I\sube J=i(J)$, $⟸$$\Longleftarrow$ : If $x^n\in I\subseteq J$$x^n\in I\subseteq J$ then $x\in J$$x\in J$. Thus $\sqrt{I}\subseteq J$$\sqrt I\subseteq J$.

Similarly, Let $(X,\tau )$$(X,\tau)$ be a topology.

Let $(\mathcal{C},\subseteq )$$(\mathcal C,\subseteq )$ be the lattice of closed sets.

Then $\mathrm{Clo}(-):P(X)\to \mathcal{C}$$\mathrm{Clo}(-):P(X)\to \mathcal C$ be the closure operator.

Let $B$$B$ be an closed set,we have

$$\begin{array}{}\text{(18)}& \mathrm{Clo}(A)\subseteq B⟺A\subseteq i(B)\end{array}$$

Then $\mathrm{C}\mathrm{l}\mathrm{o}({\mathrm{A}}_1\cup {\mathrm{A}}_2)=\mathrm{C}\mathrm{l}\mathrm{o}({\mathrm{A}}_1)\cup \mathrm{C}\mathrm{l}\mathrm{o}({\mathrm{A}}_2)$$\rm Clo(A_1\cup A_2)=Clo(A_1)\cup Clo(A_2)$, since the left adjoint preserves the direct limit.

Let $(\mathcal{O},\subseteq )$$(\mathcal O,\subseteq)$ be the lattice of open sets.

Then $\mathrm{Int}(-):P(X)\to \mathcal{O}$$\mathrm{Int}(-):P(X)\to\mathcal O$ be the interior operator.

Let $A^{\prime }$$A'$ be an open set we have

$$\begin{array}{}\text{(19)}& i(A^{\prime })\subseteq B^{\prime }⟺A^{\prime }\subseteq \mathrm{Int}(B^{\prime })\end{array}$$

Then $\mathrm{I}\mathrm{n}\mathrm{t}({\mathrm{B}}_1\cap {\mathrm{B}}_2)=\mathrm{I}\mathrm{n}\mathrm{t}({\mathrm{B}}_1)\cap \mathrm{I}\mathrm{n}\mathrm{t}({\mathrm{B}}_2)$$\rm Int(B_1\cap B_2)=Int(B_1)\cap Int(B_2)$, since the right adjoint preserves the inverse limit.

Thus closure is the left adjoint of inclusion, and interior is the right adjoint of inclusion.

You might want to compare this with the previous blog, which talk about the natural isomorphism betwenn interior and closure.

Another example comes from Algebraic Geometry.

Let $K$$K$ be an algebraic closed field and $K^n$$K^n$ be the affine space, $I(X)$$I(X)$ be all the polynomials vanishing at $X\subseteq K^n$$X\subseteq K^n$, $Z(J)$$Z(J)$ be the zero locus of ideal $J$$J$.

i.e.

$$\begin{array}{}\text{(20)}& I(X)=\{f\in K[X_1,...,X_n]|\mathrm{\forall }x\in X,f(x)=0\}\end{array}$$

$$\begin{array}{}\text{(21)}& Z(J)=\{x\in K^n|\mathrm{\forall }f\in J,f(x)=0\}\end{array}$$

Then

$$\begin{array}{}\text{(22)}& I(X)\subseteq J⟺X\supseteq Z(J)\end{array}$$

We might be able to induce closure and radical operator here.(I will back to it after I fully understand.)

Trivial example again, in Linear Algebra.

Let $(V,\subseteq )$$(V,\subseteq)$ be the subspace lattice. $X^{\mathrm{\perp }}$$X^{\bot}$ be the orthogonal complement.

Then

$$\begin{array}{}\text{(23)}& X^{\mathrm{\perp }}\subseteq Y⟺X\supseteq Y^{\mathrm{\perp }}\end{array}$$

Similarly, for the annihilator of a subspace $X\subseteq V$$X\subseteq V$ $\mathrm{ann}(X)\subseteq V^{\ast }$$\mathrm{ann}(X)\subseteq V^*$.

One interesting idea is $V^{\ast }$$V^*$ form an Algebra. Since $f\in V^{\ast }$$f\in V^*$ is some linear function $V\to \mathbb{F}$$V\to\mathbb F$.

Thus you can define $\times$$\times$ pointwise. Then Annilartor forms an ideal... It looks similar to the algebraic geometry case.

From this example, we can observe a trivial fact. if $f:A\to B,g:B\to A$$f:A\to B,g:B\to A$, and $gf={\mathrm{id}}_A$$gf=\mathrm{id}_A$, $fg={\mathrm{id}}_B$$fg=\mathrm{id}_B$.

Then we definitely have

$$\begin{array}{}\text{(24)}& f(a)⪯b⟺a\le g(b)\end{array}$$

In other world, adjoint is just like a kind of weak equivalence.

For example, Let $\begin{array}{c}\phi :R\to \frac{R}{I}\end{array}$$\varphi:R\to\frac{R}{I}\\$, then we have $\begin{array}{c}f:(\frac{R}{I},\subseteq )\to \uparrow I\end{array}$$f:\left(\frac{R}{I},\subseteq\right)\to \uparrow I \\$ and its inverse $g$$g$.

The $\begin{array}{c}(\frac{R}{I},\subseteq )\end{array}$$\left(\frac{R}{I},\subseteq\right)\\$ means the partial order set of ideals in $\begin{array}{c}\frac{R}{I}\end{array}$$\frac{R}{I}\\$.

The $\uparrow I$$\uparrow I$ means the upset of $I$$I$ in $R$$R$, i.e. $\{J\in (R,\subseteq ),J\supseteq I\}$$\{J\in (R,\subseteq),J\supseteq I\}$.

According to the remark, since $\phi$$\varphi$ is surjective, thus $J^e=\phi (J)$$J^e=\varphi(J)$.

Then $\mathrm{\forall }J\in \uparrow I,J^{ec}={\phi }^{-1}\phi (J)=J+I=J$$\forall J\in \uparrow I,J^{ec}=\varphi^{-1}\varphi (J)=J+I=J$, $\begin{array}{c}\mathrm{\forall }J\in (\frac{R}{I},\subseteq )\end{array}$$\forall J\in \left(\frac{R}{I},\subseteq\right)\\ $, $J^{ce}=\phi {\phi }^{-1}(J)=J$$J^{ce}=\varphi\varphi^{-1}(J)=J$. Thus $(e,c)$$(e,c)$ is a pair of inverse.

Another interesting example is the increasing function on $\mathbb{R}$$\mathbb R$.

$$\begin{array}{}\text{(25)}& f:(\mathbb{R},\le )\to (\mathrm{Im}f,\le ),f^{-1}:(\mathrm{Im}f,\le )\to (\mathbb{R},\le )\end{array}$$

Then

$$\begin{array}{}\text{(26)}& f(a)\le b⟺a\le f^{-1}(b)\end{array}$$

By duality

$$\begin{array}{}\text{(27)}& f^{-1}(b)\le a⟺a\le f(b)\end{array}$$

We already now that in Category $(\mathbb{R},\le )$$(\mathbb R,\le)$, what is the limit and colimit.

In Category Theory, if $F⊣G$$F\dashv G$, then $F$$F$ preserve $\begin{array}{c}\underset{⟵}{lim}\end{array}$$\lim_{\longleftarrow}\\$ , $G$$G$ preserve $\begin{array}{c}\underset{⟶}{lim}\end{array}$$\lim_{\longrightarrow}\\$.

But $f$$f$ is both left and right adjoint, thus for an increasing function, the left and right limit around a point exist.

One example I learned this term is the duality between Convex Body and Norm on ${\mathbb{R}}^n$$\mathbb R^n$.

Since norm is a continuous function $\parallel \parallel :{\mathbb{R}}^n\to \mathbb{R}$$\|\,\,\|:\mathbb R^n\to \mathbb R$. Thus we could define the order as usual.

i.e.

$$\begin{array}{}\text{(28)}& \parallel {\parallel }_1\le \parallel {\parallel }_2⟺\mathrm{\forall }x\in {\mathbb{R}}^n,\parallel x{\parallel }_1\le \parallel x{\parallel }_2⟺\mathrm{\forall }x\in S^{n-1},\parallel x{\parallel }_1\le \parallel x{\parallel }_2\end{array}$$

Then define the $\subseteq$$\subseteq$ be the order between convex body.

Let $F$$F$ be the map from norm to convex body and $G$$G$ be the map from the convex body back to the norm.

i.e.

$$\begin{array}{}\text{(29)}& F:\parallel \parallel \to {\mathbb{B}}^{\parallel \parallel }\end{array}$$

Where ${\mathbb{B}}^{\parallel \parallel }$$\mathbb B^{\|\,\,\|}$ is the unit ball, which is a convex body.

From the convex back to the unit ball, define $\parallel x{\parallel }_K=\frac{1}{inf\{r\in {\mathbb{R}}^{+},rx\notin K\}}$$\|x\|_K=\frac{1}{\inf\{r\in\mathbb R^{+},rx\notin K\}}$. We get a norm back.

Indeed, it is a one-one correspondence, $F,G$$F,G$ is pair of inverse, $\parallel {\parallel }_1\le \parallel {\parallel }_2⟺F(\parallel {\parallel }_1)\supseteq F(\parallel {\parallel }_2)$$\|\,\,\|_1\le\|\,\,\|_2\iff F(\|\,\,\|_1)\supseteq F(\|\,\,\|_2)$.

Thus we have

$$\begin{array}{}\text{(30)}& F(\parallel \parallel )\subseteq K⟺\parallel \parallel \ge G(K)\end{array}$$

Here is another example I write before, about the element of $\mathrm{PID}$$\mathrm{PID}$ and its ideal.

Now back to a trivial example. It translates from the Galois Connection in Logic.

Let $S$$S$ be a set and $P(S)$$P(S)$ is the power set (or a sigma-algebra).

Let $B\subseteq S$$B\subseteq S$, then $F(A)=A\cap B,G(C)=B^c\cup C$$F(A)= A\cap B, G(C)=B^c\cup C$, then

$$\begin{array}{}\text{(31)}& A\cap B\subseteq C⟺A\subseteq B^c\cup C\end{array}$$

We might use this to understand conditional probability.

Let $(X,\tau )$$(X,\tau)$ be a topology space, $\mathrm{Op}(X)$$\mathrm{Op}(X)$ be the Open set lattice. Let $B$$B$ be an open set.

Define $F(A)=A\cap B,G(C)=\mathrm{int}(B^c)\cup C$$F(A)=A\cap B,G(C)=\mathrm{int}(B^c)\cup C$.

Then

$$\begin{array}{}\text{(32)}& A\cap B\subseteq C⟺A\subseteq \mathrm{int}(B^c)\cup C\end{array}$$

Back to Logic again. Let us consider the Galois Connection between Syntax and Semantics.

Let $\mathcal{L}$$\mathcal L$ be a first order formal language.

Let $(\mathrm{S}\mathrm{y}\mathrm{n},\models )$$(\rm Syn,\models)$ be the Set of the axioms or the theories on the language, $\mathrm{S}\mathrm{e}\mathrm{m}$$\rm Sem$ be the Set of all the math strcutures or the models.

To explain $\models$$\models$ here means, consider the axiom of total order set $\models$$\models$ axiom of partial order set $\models$$\models$ axiom of pre order set.

Let us consider the power set of $\mathrm{S}\mathrm{e}\mathrm{m}$$\rm Sem$ and $\subseteq$$\subseteq$ be the order, i.e. $(P(\mathrm{S}\mathrm{e}\mathrm{m}),\subseteq )$$(P(\rm Sem),\subseteq)$.

Let $\mathrm{M}\mathrm{o}\mathrm{d}$$\rm Mod$ be the function send the axioms or the theories to its models.

For exaple, we have axiom of real number, and Cauchy Sequence, Dedekind Cut... many models.

Similarly, the natural number, the complex number $(a+bi),(a,b),\frac{\mathbb{R}[X]}{(x^2+1)},r{e}^{i\theta },{\mathrm{SO}}_2$$(a+bi),(a,b),\frac{\mathbb R[X]}{(x^2+1)},re^{i\theta},\mathrm{SO}_2$...

If the axiom is about poset or vector space... then you have the whole category be your models.

So as you see, actually we use the $\mathrm{M}\mathrm{o}\mathrm{d}$$\rm Mod$ function everyday. Everytime we say for example...

Let $\mathrm{T}\mathrm{h}$$\rm Th$ be the function send the models back to the axiom.

Then we have

$$\begin{array}{}\text{(33)}& \mathrm{Th}(A)\models B⟺A\subseteq \mathrm{Mod}(B)\end{array}$$

Proof

$⟹$$\implies$

If $\mathrm{T}\mathrm{h}(\mathrm{A})\models \mathrm{B}$$\rm Th(A)\models B$, that means all the models in $A$$A$ satisfied theory $B$$B$. Then $A\subseteq \mathrm{M}\mathrm{o}\mathrm{d}(\mathrm{B})$$A\subseteq\rm Mod(B)$.

$⟸$$\Longleftarrow$

If $A\subseteq \mathrm{M}\mathrm{o}\mathrm{d}(\mathrm{B})$$A\subseteq\rm Mod(B)$, that means all the models in $A$$A$ is model of theory $B$$B$. Thus the theory of Models $A$$A$ have to $\models B$$\models B$.

Using the property of Galois Connection(See $(3),(4)$$(3),(4)$) we have $A\subseteq \mathrm{Mod}\circ \mathrm{Th}(A)$$A\subseteq\mathrm {Mod\circ Th}(A)$ and $\mathrm{Th}\circ \mathrm{Mod}(\mathrm{B})\models \mathrm{B}$$\mathrm{Th\circ Mod( B)\models B}$.

.Let $(I(R),\subseteq )$$(I(R),\subseteq)$ be the partial order set of Ideal of $R$$R$, $S_I(R)$$S_I(R)$ be the partial order set of the fixed ideals under the $\mathrm{A}\mathrm{n}{\mathrm{n}}^2$$\rm Ann^2$.

i.e. ${\mathrm{Ann}}^2(I)=I$$\mathrm{Ann}^2(I)=I$. The $S_I(R)$$S_I(R)$ is not empty since $(0),R\in S_I(R)$$(0),R\in S_I(R)$.

One interesting fact is that let $F$$F$ be a field, than $(I(F),+,\cap ,\mathrm{Ann})\cong (P(\{\ast \}),\cup ,\cap {,}^c)$$(I(F),+,\cap,\mathrm{Ann})\cong (P(\{*\}),\cup,\cap,^c)$, as Boolean Algebra.

Lemma. $S\subseteq {\mathrm{Ann}}^2(S)$$S\subseteq \mathrm{Ann}^2(S)$, and $S_1\subseteq S_2⟹\mathrm{Ann}(S_1)\supseteq \mathrm{Ann}(S_2)$$S_1\subseteq S_2\implies\mathrm{Ann}(S_1)\supseteq\mathrm{Ann}(S_2)$.

Theorem. ${\mathrm{Ann}}^4(I)={\mathrm{Ann}}^2(I)$$\mathrm{Ann}^4(I)=\mathrm{Ann}^2(I)$,

Proof

Obviously ${\mathrm{Ann}}^2(I)\subseteq {\mathrm{Ann}}^4(I)$$\mathrm{Ann}^2(I)\subseteq\mathrm{Ann}^4(I)$ by $S\subseteq {\mathrm{Ann}}^2(S)$$S\subseteq\mathrm{Ann}^2(S)$. ${\mathrm{Ann}}^2(I)\supseteq {\mathrm{Ann}}^4(I)$$\mathrm{Ann}^2(I)\supseteq\mathrm{Ann}^4(I)$ by $\mathrm{Ann}(I)\subseteq {\mathrm{Ann}}^3(I)$$\mathrm{Ann}(I)\subseteq\mathrm{Ann}^3(I)$. $◻$$\square$

Corollary. ${\mathrm{Ann}}^2:I(R)\to S_I(R)$$\mathrm{Ann}^2: I(R)\to S_I(R)$

Galois Connection:

$$\begin{array}{}\text{(34)}& {\mathrm{Ann}}^2(A)\subseteq B⟺A\subseteq i(B)\end{array}$$

Proof

$$\begin{array}{}\text{(35)}& {\mathrm{Ann}}^2(A)\subseteq B,A\subseteq {\mathrm{Ann}}^2(A)⟹A\subseteq i(B)\end{array}$$

and by the property of partial order homomorphism

$$\begin{array}{}\text{(36)}& A\subseteq i(B)⟹{\mathrm{Ann}}^2(A)\subseteq B\end{array}$$

View $(\mathbb{N},|)$$(\mathbb N,|)$ as a Category, then, the Fibonacci Sequence is a functor.

i.e.

$$\begin{array}{}\text{(37)}& n|m⟹F_n|F_m\end{array}$$

Before we prove it, we need a lemma.

Lemma. $F_{m+n}=F_{m-1}{F}_n+F_m{F}_{n+1}$$F_{m+n}=F_{m-1}F_n+F_mF_{n+1}$.

Proof.

Fix $m$$m$ and do the induction for $n$$n$. Let $n=1$$n=1$, since $F_1=F_2=1,F_{m+1}=F_{m-1}+F_m$$F_1=F_2=1,F_{m+1}=F_{m-1}+F_m$ is true by definiton.

Suppose it is true for all $n\le k$$n\le k$, then $F_{m+k+1}=F_{m-1}{F}_{k+1}+F_m{F}_{k+2}=F_{m-1}(F_k+F_{k-1})+F_m(F_{k+1}+F_k)$$F_{m+k+1}=F_{m-1}F_{k+1}+F_mF_{k+2}=F_{m-1}(F_k+F_{k-1})+F_m(F_{k+1}+F_k)$.

i.e. $F_{m-1}(F_k+F_{k-1})+F_m(F_{k+1}+F_k)=(F_{m-1}{F}_k+F_m{F}_{k+1})+(F_{m-1}{F}_{k-1}+F_m{F}_k)=F_{m+k}+F_{m+k-1}$$F_{m-1}(F_k+F_{k-1})+F_m(F_{k+1}+F_k)=(F_{m-1}F_k+F_mF_{k+1})+(F_{m-1}F_{k-1}+F_mF_k)=F_{m+k}+F_{m+k-1}$. $◻$$\square$

Proposition. $n|m⟹F_n|F_m$$n|m\implies F_n|F_m$

Proof.

We need to use the induction again.

Let $m=nd$$m=nd$, when $d=1$$d=1$, $F_n|F_n$$F_n|F_n$. Suppose it is true for all $d\le k$$d\le k$, $F_{n(k+1)}=F_{m+n}=F_{m-1}{F}_n+F_m{F}_{n+1}$$F_{n(k+1)}=F_{m+n}=F_{m-1}F_n+F_{m}F_{n+1}$.

$F_n|F_n,F_n|F_{nk}⟹F_n|F_{n(k+1)}$$F_{n}|F_{n},F_n|F_{nk}\implies F_{n}|F_{n(k+1)}$. $◻$$\square$

Recall the property of Galois Connection, can we find $G$$G$

$$\begin{array}{}\text{(38)}& FGF=F,GFG=G\end{array}$$

The answer is yes!

Firstly, It should be one of the inverse function $GF(n)=n$$GF(n)=n$, since $F(n)$$F(n)$ is increasing.

Secondly, it should be a functor as well. i.e. $n|m⟹G(n)|G(m)$$n|m\implies G(n)|G(m)$.(it already true for $n,m\in \mathrm{Im}F$$n,m\in\mathrm{Im} F$.)

These two properties suggest us consider $G(n)$$G(n)$ be the least $k$$k$ such that $n|F_k$$n|F_{k}$.

But before we prove $G$$G$ is a functor, we need to prove the property of Galois Connection.

Proposition.

$$\begin{array}{}\text{(39)}& G(n)|m⟺n|F(m)\end{array}$$

Proof.

Suppose $G(n)|m,$$G(n)|m,$ since $FG(n)|F(m)$$FG(n)|F(m)$, and $n|FG(n)$$n|FG(n)$, we have $n|F(m)$$n|F(m)$.

For the reverse, $n|F(m)⟹G(n)|GF(m)=m$$n|F(m)\implies G(n)|GF(m)=m$. $◻$$\square$

Proposition. $n|m⟹G(n)|G(m)$$n|m\implies G(n)|G(m)$.

Proof.

$n|m=FG(m)⟺G(n)|G(m)$$n|m=FG(m)\iff G(n)|G(m)$ $◻$$\square$

Immediately, by the property of adjoint functor, we have

$$\begin{array}{}\text{(40)}& G(\mathrm{lcm}(a,b))=\mathrm{lcm}(G(a),G(b)),F(gcd(a,b))=gcd(F(a),F(b))\end{array}$$