Realization Calculus: twin edition

Download original file

This is the original TeX manuscript source. Use the paper’s PDF for typeset equations.

1 \chapter{What a realization must supply}
2 \label{ch:contracts}
3 \chapterintro{Before constructing a boundary, one must specify what is allowed to cross it. A finite seed family, a finite description, and an effective presentation impose different requirements.}
4 
5 \section{Four questions, not one}
6 The expression ``finitely realizable'' is incomplete unless it names a contract. A group may be infinite but cyclic. A group may require infinitely many algebraic generators but have a short recursive construction. A description may select an exact group through a noncomputable set. Finally, a topology may allow limits that are not present in the underlying algebraic construction.
7 
8 The integer group $\Z$ illustrates only the first distinction. One generator and its integer multiples produce infinitely many elements. The groups developed below separate the other distinctions as well. Their purpose is not to make infinite objects mysterious. It is to account for the information that a construction actually consumes.
9 
10 \begin{definition}[Operator-seed realization]
11 Let $M$ be an abelian group and let $\mathcal O\subseteq\End(M)$ be a declared collection of endomorphisms. For $S\subseteq M$, its operator hull is the subgroup generated by all $T(s)$, where $s\in S$ and $T$ is a finite composition of members of $\mathcal O$, including the identity. A finite operator-seed realization requires a finite $S$ whose hull is $M$.
12 \end{definition}
13 The allowed addition and inverse operations are part of the group structure. An arbitrary target-dependent map is not automatically an admissible endomorphism. In particular, one cannot evade a generation obstruction by introducing a map that simply returns the desired answer.
14 
15 If all endomorphisms are allowed, this is module generation over the unital ring $\End(M)$. We write $\srank_{\End(M)}(M)$ for its least generating cardinal. An infinite value can therefore express a strong obstruction even when the operator collection itself is unrestricted.
16 
17 \begin{definition}[Finite semantic description]
18 A finite-description grammar consists of a countable alphabet, a class of valid finite strings, and a semantics assigning each valid string one group isomorphism type. The semantics need not be computable. Any permitted parameters must have a declared coding convention.
19 \end{definition}
20 This definition allows a finite sentence to specify a noncomputable group. It does not count an arbitrary real or subset of $\N$ as a free symbol. If such a parameter is admitted, its information must be recorded separately.
21 
22 \begin{definition}[Computable copy]
23 A computable copy of a countable group is an isomorphic group on a computably named domain, with decidable equality and computable group operations. An $X$-computable copy permits an oracle $X$ in those computations. Infinite groups may equivalently be presented on $\N$.
24 \end{definition}
25 A presentation by generators and relators is a different object. Enumerating the relators need not decide whether two words represent the same element. The effective presentations in this book always include decidable equality in the named copy.
26 
27 \begin{definition}[Topological generation]
28 For a topological group $M$, a subset $S$ topologically generates $M$ when the closure of the subgroup generated by $S$ is all of $M$. Its least possible size is denoted $\trank(M)$. An operator version takes the closure of the operator hull instead.
29 \end{definition}
30 The closure is taken in the stated topology. A change of topology is a change of contract, not an innocuous notational adjustment.
31 
32 \section{Finite descriptions and infinite information}
33 There are countably many finite strings over a countable alphabet. Consequently a grammar with single-valued semantics realizes at most countably many group isomorphism types. This observation requires neither an algorithm for checking validity nor an algorithm for evaluating the semantics.
34 
35 \begin{proposition}[Countable-code bound]
36 \label{thm:codecount}
37 Let $\mathfrak G$ be a finite-description grammar as above. Then its class of realized group isomorphism types has cardinal at most $\aleph_0$.
38 \end{proposition}
39 \begin{proof}
40 For each length $n$, the set of strings of length $n$ is countable. The union over $n\in\N$ is countable. The valid strings form a subset, and a single-valued image of a countable set is countable.
41 \end{proof}
42 This is a boundary of description, not of existence. It also says nothing about whether a particular named group lies outside a chosen grammar. The later constructions supply structural examples and an explicit relative diagonal argument.
43 
44 For quantitative description length, fix an injective encoding of descriptions by finite binary strings. A symbol from a countable alphabet must carry its finite code rather than count as a free unit of information. This encoding convention does not require the semantic evaluation to be computable.
45 
46 \begin{definition}[Grammar-relative description complexity]
47 For a fixed binary coding of $\mathfrak G$, let $\lvert d\rvert$ be its bit length and set
48 \[
49 K_{\mathfrak G}(G)=\inf\{\lvert d\rvert:\ d\text{ is valid and }\operatorname{Realize}_{\mathfrak G}(d)\cong G\},
50 \]
51 with value $+\infty$ when there is no such description.
52 \end{definition}
53 The value depends on the grammar and the coding. A fixed finite description can be long without being impossible. Conversely, a group with $K_{\mathfrak G}(G)=+\infty$ may have a short description in an expanded language.
54 
55 \begin{boundary}[No uncharged infinite parameters]
56 The expression $G=q^{-1}(\Q q(u))$ is short. If $u$ is an arbitrary infinite coordinate vector, that expression is not a finite specification of $G$ without a specification of $u$. Counting its surrounding symbols does not count the information in the parameter.
57 \end{boundary}
58 This boundary will become exact: the computational information in a selected $u_A$ is precisely what is needed to compute the corresponding group.
59 
60 \section{A reusable support obstruction}
61 A finite-seed failure can sometimes be certified without examining every possible operator word. The packet structure supplies a witness.
62 
63 \begin{theorem}[Reachability obstruction]
64 \label{thm:reach}
65 Let $M=\bigoplus_{i\in I}M_i$ be a direct sum of abelian groups with coordinate projections $P_i$. Suppose every primitive operator $T$ is an endomorphism and its transfer block $P_jTP_i$ vanishes unless $i\to j$ is an allowed edge of a directed graph $E$. If $F$ is the union of the supports of a seed family $S$, then
66 \[
67 \Hull_{\mathcal O}(S)\subseteq
68 \bigoplus_{j\in\operatorname{Reach}_E(F)}M_j.
69 \]
70 If $M_j\ne0$ and $j$ is not reachable, $P_j$ annihilates the entire hull but not $M$.
71 \end{theorem}
72 \begin{proof}
73 An element of the direct sum has finite support. Applying one primitive operator can move its support only along allowed edges. Induction on word length confines every operator image of a seed to packets reachable by a finite path. Finite sums and inverses cannot introduce a coordinate outside that set. The final assertion follows by taking the projection onto an omitted nonzero packet.
74 \end{proof}
75 Reachability is necessary, not sufficient. A permitted path may carry zero action on the particular seed, or its image may be a proper subgroup of the target packet. The theorem therefore gives a non-generation certificate but does not assert generation whenever the graph is connected.
76 
77 If the packet projections are continuous into Hausdorff groups, the kernel of an omitted projection is closed. The same witness then obstructs topological generation in that topology. Later we will use precisely this argument after allowing every abstract endomorphism of the group.
78 
79 \section{Observations and the original object}
80 An observation system also needs a contract. For a residually finite group, finite quotients separate distinct elements. This is an elementwise assertion: if two elements differ, at least one quotient distinguishes them. It does not assert that the unmarked family of quotients identifies the source isomorphism type.
81 
82 The distinction is easiest to express in terms of an embedding
83 \[
84 G\longrightarrow \varprojlim G/N.
85 \]
86 Residual finiteness makes this map injective. The inverse limit includes all compatible tuples. The image of the original $G$ can nevertheless be a proper dense subgroup. Forgetting that image can forget the object even while retaining enough coordinates to distinguish every element once the object is supplied.
87 
88 The later examples do not contradict the construction of an inverse limit. They show that reconstructing the complete ambient realization and identifying a specified noncomplete realization are different tasks. This is the point at which compatibility must be separated from admissibility.

Back to source controls

Back to Realization Calculus: twin edition