# Unary algebra

$$(S,f)$$ is a mono-unary algebra iff $$S$$ is a type and $$f$$ is an endofunction on $$S$$. Other names of mono-unary algebra are ‘unar’ and ‘unary algebra’. We prefer unar. It’s short.

Literatures:

Related topics:

• fixpoint theory (fixed point theory)
• recursion theory
• algebraic theory of automata

Computation: Let $$A = (S,f)$$ be a unar. We define $$fun~A$$ (the function $$A$$ computes) as $$\newcommand\abs{\lvert#1\rvert} fun~(S,f) = w~f$$ where $$w~f$$ is the infinite iteration of $$f$$: \begin{align*} w~f &= f \circ w~f \\ &= f \circ f \circ f \circ \ldots \\ &= f^{\aleph_0}. \end{align*}

We can think of $$w$$ as a limit: $w~f~x = \lim_{n \to \infty} f^n~x.$

Totality: A unar $$(S,f)$$ is total iff $$w~f$$ is a total function; $$w~f$$ is total iff for each $$x$$ there exists natural number $$n$$ such that $$f^n~x = f^{n+1}~x$$. The function $$fun~A$$ is total iff $$A$$ is total.

Totality and iteration: If $$w~f~x = y$$ then $$w~f~y = y$$. If $$w~f$$ is total, then $$w~(w~f)$$ is also total. By induction, if $$w~f$$ is total, then $$w^n~f$$ will also be total for each natural number $$n$$. If $$(S,f)$$ is total, then $$(S,w~f)$$ is also total.

Number of total unars: How many total unars can we make from a set $$S$$? Is it $$\abs{S}^{\abs{S}}$$?

Surjection: There is a surjection from the set of all total unars made from set $$S$$ to the set of all endofunctions on $$S$$. (Proof?) Conclusion: For each endofunction $$f$$, there exists at least one total unar that computes $$f$$. This implies that an endofunction can be implemented by a machine. It doesn’t say whether the machine can be realized.

Cycle: If we keep applying $$f$$ to $$x$$, we may enter a cycle. We say “$$x$$ is the member of a cycle of size $$n$$” iff $$n$$ is the smallest natural number such that $$f^n~x = x$$, We say “$$x$$ is the member of a cycle” if there exists such $$n$$.

Transforming cycles: Each of $$(S,f)$$’s cycle whose size divides $$n$$ becomes a fixpoint in $$(S,f^n)$$.

Oracle: Let $$g : S\to S$$. An oracle for $$g$$ computes $$g$$ in one unit time. There is a bijection between the set of all canonical oracles on $$S$$ and the set of all endofunctions on $$S$$. We say that $$(\{0,1\} \times S, f)$$ is the canonical oracle for $$g$$ iff \begin{align*} f~(0,x) &= (1,g~x) \\ f~(1,x) &= (1,x). \end{align*}

Termination and time complexity: We say that $$x$$ terminates in $$n$$ steps, or $$x$$ is $$n$$ steps away from termination, or $$x$$ is $$n$$ steps to termination, or $$n$$ is the time-to-termination of $$x$$, iff $$time~f~x = n$$ where $$n$$ is the smallest natural number such that $$f^n~x = f^{n+1}~x$$. The type of $$time$$ is $$(S \to S) \to S \to \mathbb{N}$$. Iff $$n$$ is zero we say that $$x$$ is terminal.

Worst-case time complexity: $$T~f~n$$ is the worst-case number of steps $$f$$ needs to reach terminal state from an input of size $$n$$. The function $$size : S \to \mathbb{N}$$ defines the input size. The size depends on the encoding. We can define $$T$$ like this: $T~f~n = max~(map~(time~f)~(inputsWithSize~n)) \\ inputsWithSize~n = \{ x ~|~ x : S, ~size~x = n\}.$

Input size: In unary encoding, a natural number is its own size. In binary encoding, the size of a natural number $$n$$ is $$1 + \lceil \lg n \rceil$$, or $$1$$ if $$n=0$$.

Notation: We can write complexity bounds like this: \begin{align*} T~f &\in O~(\lambda n. n^2) \\ T~f &\in \Omega~(\lambda n. n^2) \\ T~f &\in \Theta~(\lambda n. n^2). \end{align*}

Example: In a lambda-calculus machine with Church numerals, the time complexity of adding two natural numbers $$m$$ and $$n$$ is in $$O(m+n)$$.

Finite unars: A unar $$(S,f)$$ is finite iff $$S$$ is finite. $$A = (N,f)$$ is a canonical finite unar with size $$n$$ iff $$N = \{ 0,1,2,\ldots,n-1 \}$$ is the set of the first $$n$$ natural numbers. There are $$n^n$$ canonical finite unars with size $$n$$. The set of all canonical finite unars is countable. Indeed the set of all finite subsets of a countable set is countable.

Number of unars: There are $$\abs{S}^{\abs{S}}$$ unars on set $$S$$.

Widening (superalgebra): Let $$A = (S,f)$$ and $$B = (T_\bot,g)$$ be unars where $$T_\bot = T \cup \{\bot\}$$ and $$S \subseteq T$$. We can widen $$A$$ to $$B$$: $g~x = \begin{cases} f~x &\text{if x \in S} \\ \bot &\text{otherwise} \end{cases}$ We can write in such case:

• $$B = widen~T~A$$,
• $$B \in widenings~A$$,
• $$B$$ is a widening of $$A$$,
• $$A$$ widens to $$B$$, or
• $$B$$ is a superalgebra of $$A$$.

Universal unar over a family: Let $$F = \{ F_0, F_1, F_2, \ldots \} = \{ F_k \}_{k\in\mathbb{N}}$$ be a family of all canonical finite unars. We can define an $$F$$-universal unar $$univ~F = (\mathbb{N} \times \mathbb{N}_\bot, f)$$ with $f~(k,x) = (k, ~f_k'~x)$ where $$(\mathbb{N}_\bot,f_k')$$ is a widening of $$F_k$$.

There is a bijection between $$\mathbb{N}\times\mathbb{N}_\bot$$ and $$\mathbb{N}$$. This implies the existence of $$\phi : \mathbb{N} \times \mathbb{N}_\bot \to \mathbb{N}$$ and its inverse function. We can rewrite the above $$F$$-universal unar as $$(\mathbb{N}, g)$$ where $g~(\phi~(k,x)) = \phi~(k,~f_k'~x).$ We call $$k$$ a program because $$k$$ selects the machine ($$F_k$$) that the $$F$$-universal machine ($$univ~F$$) shall use.

Unar product: $$A_0 \times A_1$$ represents a machine that runs $$A_0$$ and $$A_1$$ simultaneously. $A_0 \times A_1 = (S_0 \times S_1, f) \\ f~(x,y) = (f_0~x,f_1~y)$

## Mono-unary algebra of unars

$$S$$ is a set of unars and $$f$$ is an endofunction on unars.

Endofunction on unars: $t~(S,f) = (u~S,v~f)$

This is transforming a machine into another machine.

Chaining of unars:

$chain~(S,f)~(S,g) = (S,f\circ g)$

Unars and real numbers: There is a bijection between the unar $$(\mathbb{N},f)$$ and $$\mathbb{R}$$.

Subalgebras (narrowings) and ordering: $$(S',f')$$ is a subalgebra (a narrowing) of $$(S,f)$$ iff $$S' \subseteq S$$, and $$f' \subseteq f$$, and $$f'$$ is an endofunction on $$S'$$. Subalgebra relation forms an ordering on unars.

Empty unar: $$(\varnothing, \varnothing)$$.

Magmas of unars: Binary operation on unars: $t~(S_0,f_0)~(S_1,f_1) = (u~S_0~S_1, v~f_0~f_1).$

Union of two disjoint unars:

If $$S_0 \cap S_1 = \varnothing$$, $A_0 \cup A_1 = (S_0 \cup S_1, f_0 \cup f_1).$

Free unars: A free unar can be made from either a set or an endofunction. The free unar of set $$S$$ is $$(S,id)$$. The free unar of endofunction $$f$$ is $$(domain~f,f)$$.

## Semigroups of unars

$$(\Sigma,\cap)$$ is a commutative semigroup of unars where $$\Sigma$$ is the set of all unars and $\newcommand\leftunion{\sideset{_\bullet}{}{\cup}} A_0 \cap A_1 = (S_0 \cap S_1, f_0 \cap f_1).$

Left-prioritized union gives rise to $$(\Sigma,\leftunion)$$, a non-commutative semigroup of unars: \begin{align*} A_0 \leftunion A_1 &= (S_0 \leftunion S_1, f_0 \leftunion f_1). \\ S_0 \leftunion S_1 &= S_0 \cup S_1 \\ (f_0 \leftunion f_1)~x &= \begin{cases} f_0~x &\text{if x \in domain~f_0} \\ f_1~x &\text{otherwise.} \end{cases} \end{align*}

## Others

Digital physics hypothesizes that the Universe is a unar.