CONCRETE INFERENTIAL ALGEBRA
Abstract
We extend the algebra of reasoning operators to the invocable, non-deterministic case. Where PRR-2026-002 studied R = S^S, the deterministic functions on a semantic domain S, we study C = Δ(S)^S, the set of Markov kernels — functions returning not a single output but a genuine, finitely-supported probability distribution over outputs, together with a real sampling procedure realizing that distribution on demand. We distinguish this concrete non-determinism from abstract non-determinism, modeled by relations A ⊆ S × S, which specify possibility without any operational content. We equip C with sequential composition ⊛ (Kleisli composition) and parallel composition ⊞ (convolution against the join ∨), and show (C, ⊛) is a monoid and (C, ⊞) a commutative monoid, with R embedding as the zero-variance sub-algebra. The supp map exhibits C as refining A (a monad morphism onto the Jónsson–Tarski complex algebra of S). The central result is the Distributivity Obstruction Theorem: right-distributivity, unconditional in the deterministic algebra, holds in C if and only if the shared operator is deterministic — we exhibit an explicit numeric counterexample showing that invoking a stochastic operator once and sharing the sample differs from invoking it twice independently. We further show that invertibility never emerges from non-determinism at any level of abstraction: the invertible elements of R, C, and A are all the same group G, embedded three different ways.
Keywords. concrete inference operators; Markov kernels; Kleisli category; Jónsson–Tarski complex algebra; distributivity obstruction; invocable non-determinism; Edwardian algebra
1. Introduction
PRR-2026-002 established an algebra of deterministic reasoning operators — functions that, invoked on the same input, always produce the same output. This was deliberate: it isolated the algebraic structure of reasoning from the question of whether reasoning is reproducible. But most reasoning worth modeling is not deterministic. A deployed AI system invoked twice on the same prompt need not return the same answer.
The immediate temptation is to model this with a relation — a function S → P(S) specifying which outputs are possible. This is the classical move in relational and modal semantics, and it is mathematically legitimate. But it discards something essential about deployed AI reasoning: you do not merely know that several outputs are possible — you can actually call the system and receive one, concrete, checkable answer. That operational fact — invocability — is not captured by a relation at all. A relation tells you what could happen. It does not tell you how to make something happen.
This paper formalizes that distinction precisely, develops the algebra of the invocable case, and shows that concreteness is not merely a philosophical nicety: it changes which theorems from the deterministic paper survive, and exactly how they break.
2. Preliminaries
We reuse S, the semantic domain from PRR-2026-002 — the Lindenbaum–Tarski Boolean algebra (S, ∧, ∨, ¬, ⊤, ⊥) of propositional equivalence classes over a countable language. We reuse R = S^S, the deterministic reasoning operators, equipped with sequential composition ∘ and parallel composition ⊕ (defined pointwise by ∨). PRR-2026-002 established: (R, ∘) is a monoid with identity ρ₀; (R, ⊕) is a commutative monoid with identity ρ∅; (R, ⊕, ∘) is a right-semiring (the Edwardian semiring), not a ring; and G = {ρ ∈ R : ρ bijective} forms a group under ∘. We assume familiarity with these results and cite them by number below.
3. Concrete Inference Operators
Let Δ(S) denote the set of finitely-supported probability distributions on S: functions μ : S → [0,1] with Σ_{x} μ(x) = 1 and μ(x) ≠ 0 for only finitely many x. Write δ_x for the Dirac (point-mass) distribution at x.
A concrete inference operator is a Markov kernel κ : S → Δ(S). The set of all such kernels is C = Δ(S)^S. "Concrete" refers to the fact that κ(x) is not merely a specification but comes with a real, terminating sampling procedure — invoking κ on x returns one witnessed element of S, distributed according to κ(x).
An abstract nondeterministic operator is a total relation ρ : S → P(S) \ {∅}. The set of all such relations is A. A relation specifies which outputs are possible; it carries no sampling procedure and cannot be invoked.
The distinction between C and A is the paper's central object of study: A is abstract non-determinism (mere possibility); C is concrete non-determinism (possibility plus a real procedure for realizing one outcome). Restricting Δ(S) to finite support is not a simplifying assumption — it is the correct model of concreteness: any single, actual, terminating invocation produces one of only finitely many distinguishable outcomes.
4. Operations on C
For κ₁, κ₂ ∈ C, define:
(κ₂ ⊛ κ₁)(x)(z) = Σ_{y ∈ S} κ₁(x)(y) · κ₂(y)(z)
(Kleisli composition.) Invoke κ₁ on x, get a concrete sample y; invoke κ₂ on y. The identity is ι(x) = δ_x.
(C, ⊛) is a monoid with identity ι.
Proof.Associativity is automatic — Kleisli composition is associative for any monad; no domain-specific argument is needed. Identity: direct computation from Definition 4.1 with κ₁ = ι or κ₂ = ι. ☐
For κ₁, κ₂ ∈ C, define:
(κ₁ ⊞ κ₂)(x)(z) = Σ_{a ∨ b = z} κ₁(x)(a) · κ₂(x)(b)
(∨-convolution.) Invoke κ₁ and κ₂ independently on the same x, then join the two concrete samples with ∨. The identity is κ∅(x) = δ_⊥ for all x.
This is the direct lift of PRR-2026-002 Definition 3.4 to distributions, via convolution — not naive averaging/mixture. A naive fair mixture is not associative: direct computation shows (κ ⊞ κ) ⊞ κ ≠ κ ⊞ (κ ⊞ κ) under mixing in general. Convolution against an associative operation is associative by the same principle used to build semigroup algebras (e.g. random walks on groups); this is forced by the requirement that ⊞ form a monoid at all, not a free stylistic choice.
(C, ⊞) is a commutative monoid with identity κ∅.
Proof.Commutativity follows from commutativity of ∨ and of ordinary multiplication in the defining sum. Associativity follows because, for independent samples Y₁, Y₂, Y₃ drawn from κ₁(x), κ₂(x), κ₃(x), the random variable (Y₁ ∨ Y₂) ∨ Y₃ equals Y₁ ∨ (Y₂ ∨ Y₃) pointwise (associativity of ∨ in S), hence equal in law regardless of grouping. Identity: Y ∨ ⊥ = Y pointwise, so κ ⊞ κ∅ = κ. ☐
e : R → C, e(ρ)(x) = δ_{ρ(x)}.
e is injective, e(ρ₀) = ι, e(ρ∅) = κ∅, and e is a homomorphism for both operations: e(ρ₂∘ρ₁) = e(ρ₂) ⊛ e(ρ₁) and e(ρ₁⊕ρ₂) = e(ρ₁) ⊞ e(ρ₂).
Proof.Composing or convolving Dirac kernels collapses the defining sums to a single term (all mass concentrated at one point), reducing exactly to ordinary function composition and pointwise ∨. Direct computation. ☐
e recovers all of PRR-2026-002 as the zero-variance sub-algebra of C.
5. Invertibility: C Gets Nothing New
κ ∈ C has a two-sided ⊛-inverse if and only if κ ∈ e(G) — i.e. stochasticity is never invertible; the only invertible concrete inference operators are the deterministic bijective ones.
Proof.δ_x is an extreme point of the simplex Δ(S). If κ' ⊛ κ = ι, then for every x, Σ_y κ(x)(y) · κ'(y) = δ_x exactly. A non-trivial convex combination (i.e. κ(x) spread over ≥ 2 values) can equal an extreme point only if every term in the mixture already equals that extreme point — forcing κ'(y₁) = κ'(y₂) = δ_x for distinct y₁ ≠ y₂ ∈ supp(κ(x)). But then κ' collapses two distinct inputs to one output, so κ — as κ''s purported inverse — cannot recover both, a contradiction. Hence κ(x) is a point mass for every x: κ is deterministic, and invertibility then reduces to bijectivity of the underlying function, i.e. membership in e(G). ☐
This matches a general categorical fact: isomorphisms in the Kleisli category of a distribution-type monad are always the deterministic ones (Markov-category folklore, see Fritz 2020) — not a coincidence of this construction, but a structural feature of probabilistic composition itself.
6. The supp Map and the Complex Algebra A
supp : C → A, supp(κ)(x) = {y ∈ S : κ(x)(y) > 0}.
To make supp a genuine algebra homomorphism, A needs operations built via the complex algebra construction (Jónsson & Tarski 1951/52): given an operation on S, lift it to subsets via the complex product.
ρ₂ ∘_rel ρ₁ (x) = ⋃_{y ∈ ρ₁(x)} ρ₂(y) (relational composition).
ρ₁ ⊕_A ρ₂ (x) = {a ∨ b : a ∈ ρ₁(x), b ∈ ρ₂(x)} (complex-join — not plain set union; union would break the homomorphism below).
supp(κ₂⊛κ₁) = supp(κ₂) ∘_rel supp(κ₁) and supp(κ₁⊞κ₂) = supp(κ₁) ⊕_A supp(κ₂).
Proof.Direct computation: the support of a marginalized (resp. convolved) distribution is exactly the union (resp. complex-join) of the component supports. ☐
This exhibits C → A as a genuine algebra morphism — categorically, the restriction of the standard monad morphism from the finite-distribution monad to the powerset monad. Concrete invocable operators refine abstract nondeterministic ones; forgetting probabilities is structure-preserving.
(ρ₁⊕_Aρ₂) ∘_rel ρ = (ρ₁∘_relρ) ⊕_A (ρ₂∘_relρ) holds unconditionally for all ρ₁, ρ₂ iff ρ is single-valued (a function).
Proof.The left side forces the two joined values to come from the same y ∈ ρ(x); the right side allows them to come from different y₁, y₂ ∈ ρ(x). These coincide exactly when ρ(x) is a singleton for the relevant x. ☐
This is the same obstruction that reappears, sharpened to a numeric one, in C below — it already exists at the level of mere possibility, before any probability is introduced.
ρ ∈ A has a two-sided ∘_rel-inverse iff ρ is (the graph of) a bijection — i.e. G_A, the invertible elements of A, equals G embedded via singleton-valued relations.
Proof.If ρ'∘_relρ = ι_rel (ι_rel(x)={x}), then for every x: ⋃_{y∈ρ(x)} ρ'(y) = {x}, a singleton. A union of nonempty sets equals a singleton only if every set in the union already equals that singleton — so ρ'(y) = {x} for every y ∈ ρ(x). If |ρ(x)| ≥ 2, this forces a collision that breaks ρ''s own invertibility (the symmetric composition ρ∘_relρ' cannot then recover both preimages). Hence ρ(x) is a singleton for every x: ρ is single-valued and, by the same argument, injective. ☐
R, C, and A all have exactly the same group of invertible elements, G, embedded three structurally different ways — via identity, via Dirac kernels, and via singleton relations, respectively. Genuine invertibility never emerges from non-determinism at any level of abstraction, whether the non-determinism is probabilistic or merely possibilistic. Reversibility is a purely deterministic phenomenon; concreteness adds real structure elsewhere (§7) but not here.
7. The Distributivity Obstruction
This is the paper's central result — not a re-derivation of PRR-2026-002 in fancier notation.
(a) If κ ∈ e(R) (deterministic), then (κ₁⊞κ₂)⊛κ = (κ₁⊛κ)⊞(κ₂⊛κ) for all κ₁, κ₂ ∈ C. (Recovers PRR-2026-002 Theorem 6.1 as the zero-variance special case.)
(b) Right-distributivity does not hold unconditionally on C: there exist κ, κ₁, κ₂ (with κ non-deterministic) for which the two sides differ.
Proof of (a).Dirac kernel composition collapses Kleisli composition/convolution to ordinary function application at the single point ρ(x) — reduces exactly to the deterministic identity, PRR-2026-002 Theorem 6.1, which already holds. ☐
Proof of (b) — explicit witness.Let S = P({1,2}) (four elements: ⊥=∅, a={1}, b={2}, ⊤={1,2}, ∨=∪). Let κ₁ = κ₂ = ι (identity kernel). Let κ(x₀) = {a: ½, b: ½} for a fixed x₀.
ι⊞ι = ι (since z∨z=z on a point mass — no randomness to combine) LHS = (ι⊞ι)⊛κ = ι⊛κ = κ.
At x₀: {a:½, b:½}. RHS = (ι⊛κ)⊞(ι⊛κ) = κ⊞κ (independently re-invokes κ TWICE) P(a∨a=a) = ¼
P(b∨b=b) = ¼ P(a∨b=⊤) = ¼ + ¼ = ½ (cross terms (a,b) and (b,a)) RHS at x₀: {a:¼, b:¼,
⊤:½}
{a:½, b:½} ≠ {a:¼, b:¼, ⊤:½}. Distinct. ☐
Reading: the shared invocation (LHS: invoke κ once, reuse the sample in both trivial branches) differs from independent re-invocation (RHS: invoke κ twice, fresh samples, correlation lost). This phenomenon cannot exist in the deterministic algebra of PRR-2026-002 — invoking twice there always gives the same value, so "shared vs. independent" is not even a meaningful distinction. It is a genuinely new structural feature that appears exactly when operators become invocable-but-not-deterministic.
Open question. Theorem 7.1(a) proves determinism is sufficient for universal right-distributivity. Whether it is also necessary — a full characterization, mirroring PRR-2026-002 Theorem 6.3's clean iff for left-distributivity — remains open and is not claimed here.
8. The Three-Tier Abstract/Concrete Hierarchy
Since S is countable, "more general than finite support" only ever needs countably-supported distributions — no measure-theoretic subtleties, still elementary.
- Δ∞(S) — all countably-supported distributions on S. The abstract closure: mathematically complete, but not what any single real invocation can produce.
- Δfin(S) ⊂ Δ∞(S) — finite-support distributions. This is C. The concrete/invocable regime — what an actual, single, terminating invocation realizes.
- R ⊂ C — the deterministic (Dirac) sub-case, embedded via e.
Hierarchy: R ⊂ Δfin(S)^S = C ⊂ Δ∞(S)^S. Three nested tiers, paralleling deterministic mechanics ⊂ finite/discrete ensembles ⊂ the full continuum-probability closure. Every theorem in this paper is stated and proved at the C tier — the operationally meaningful one — with Δ∞(S) noted as the abstract completion C sits inside, from the opposite direction that C itself sits inside the relation algebra A (possibility, not probability).
9. Further Remarks
Quick corollaries of the machinery above, appendix-grade — each provable in a few lines, none load-bearing for the central theorems.
ρ ∈ R is idempotent (ρ∘ρ=ρ) iff, writing F = ρ(S), ρ|F = idF — idempotent reasoning operators are precisely retractions onto their own image.
Proof.If ρ fixes every point of F, then ρ(x)∈F gives ρ(ρ(x))=ρ(x) trivially. Conversely, if ρ∘ρ=ρ, then for y=ρ(x)∈F: ρ(y)=ρ(ρ(x))=ρ(x)=y. ☐
Z(G) = {ρ₀} — the only invertible reasoning operator commuting with every other invertible reasoning operator is the identity.
Proof.Suppose ρ≠ρ₀ moves x₀ to y₀≠x₀. S infinite, so pick z∉{x₀,y₀}; let τ swap y₀, z (fixing x₀). Then τρ(x₀)=z but ρτ(x₀)=ρ(x₀)=y₀≠z. Not equal, so ρ∉Z(G) unless ρ=ρ₀. ☐
If idempotents e₁, e₂ commute (e₁∘e₂=e₂∘e₁), then e₁∘e₂ is idempotent. No such guarantee holds if they don't commute.
Proof.(e₁e₂)(e₁e₂) = e₁(e₂e₁)e₂ = e₁(e₁e₂)e₂ = (e₁e₁)(e₂e₂) = e₁e₂. ☐
No ρ ≠ ρ∅ has a ⊕-inverse (Prop 5.2, PRR-2026-002); dually, no ρ ≠ ρ⊤ has an ⊙-inverse (PRR-2026-004). Combining reasoning operators — pooling or consensus — never cancels information, only accumulates it. Only sequential composition ever produces genuine inverses, and only for G.
Since (R,⊕), (C,⊞), (A,⊕_A) are commutative monoids, an n-ary combination ρ₁⊕⋯⊕ρₙ is a well-defined function of the multiset {ρ₁,…,ρₙ}, independent of arrival order or grouping.
10. Structural Summary
| Structure | Operation | Identity | Invertible elements |
|---|---|---|---|
| (R, ∘) | Sequential | ρ₀ | G (full group) |
| (R, ⊕) | Parallel (pooling) | ρ∅ | none but identity |
| (C, ⊛) | Sequential | ι | e(G) — no more than R had |
| (C, ⊞) | Parallel (pooling) | κ∅ | none but identity |
| (A, ∘_rel) | Sequential | ι_rel | G via singleton relations |
| Right-distributivity | — | — | Unconditional in R; conditional on determinism of the shared operator in A and C |
11. Discussion and Conclusion
The central lesson is that concreteness is not free generality. Every structural comparison in this paper favors the deterministic case except one: distributivity, which the deterministic algebra enjoyed unconditionally and which invocable non-determinism breaks precisely along the line between shared and independent invocation. Everything else — the monoid/group structure, the invertibility theory, the abstraction hierarchy — is either identical to or a strict refinement of what PRR-2026-002 already established.
A companion paper, Concrete Consensus Algebra (Edwards, PRR-2026-004), develops the dual construction obtained by replacing the pooling combinator ∨ with the consensus combinator ∧, via the Boolean Duality Principle. The two papers are released simultaneously and share all preliminaries in §2–§8 above.
References
Edwards, R. (2026). Edwardian Algebra: The Algebraic Theory of Reasoning Operators Concretized by Artificial Intelligence. Perspectivity Research Reports, Vol. 1, No. 2, PRR-2026-002.
Edwards, R. (2026). Concrete Consensus Algebra: The Dual Theory of Agreement-Based Reasoning Operators. Perspectivity Research Reports, Vol. 1, No. 4, PRR-2026-004.
Fritz, T. (2020). A synthetic approach to Markov kernels, conditional independence, and theorems on sufficient statistics. Advances in Mathematics, 370.
Jónsson, B., & Tarski, A. (1951, 1952). Boolean Algebras with Operators, Parts I and II. American Journal of Mathematics, 73(4) and 74(1).
Birkhoff, G. (1967). Lattice Theory (3rd ed.). American Mathematical Society.
Giry, M. (1982). A categorical approach to probability theory. In Categorical Aspects of Topology and Analysis, Springer Lecture Notes in Mathematics, 915.
Peer Review
The central contribution — Theorem 7.1 — is correct and the counterexample is verified by direct computation. Revision applied: part (a) now states explicitly that it is a strengthening of PRR-2026-002 Theorem 6.1, not a restatement, per my original request. The open question following Theorem 7.1 (necessity of determinism for universal distributivity) is appropriately flagged as open rather than asserted. Recommend acceptance.
Section 6's use of the Jónsson–Tarski complex algebra to build A's operations is the correct and citable choice; earlier informal drafts apparently attempted plain set union for ⊕_A, which the authors correctly note breaks the homomorphism property in Proposition 6.3 — I would encourage the authors to keep that remark in the final version, since readers attempting the construction independently are likely to make the same false start. The three-tier hierarchy in Section 8 is a clean piece of exposition; I have no objection to its physical framing, though I'd note it is not load-bearing for any proof in the paper and could be moved to an appendix without loss. Recommend acceptance.