MATH.17:4 - Solution

Local mantra: state the change to the rule; construct its admissible inputs; establish composition; construct the higher-order operation; derive its consequence; use or revise it.

MATH.17:4.1 - Specify the operations and the question about them

Name the inputs and outputs of an operation. Write f:A -> B when f assigns an element of B to every element of A. Write g∘f for “first f, then g”; it is defined when f’s output is an allowed input to g.

Choose what counts as equality for the present question. In the main function route, f and g are equal when they have the same domain and codomain and f(x)=g(x) for every input x. If the question concerns the steps used, resource cost or another distinction between ways of producing that function, retain a construction or program representation carrying that distinction. A function value alone leaves it unavailable. MATH.1 supplies constructions retaining ordered steps; MATH.2 handles an identification when the needed operations respect it.

Formulate the intended operation on rules. It might take two operations and compose them, send an operation on individual inputs to an operation on collections, or turn an expression for a function into another expression. State which result matters: admissibility, an identity, a comparison, a changed construction, or a failed requirement.

MATH.17:4.2 - Construct the admissible collections

For each relevant pair A, B, specify Adm(A,B), the collection of operations allowed from A to B. Give a condition that can be used to establish membership. Examples include preserving an order, maintaining a relation between components, or mapping a designated subset into itself.

When the operations are functions, MATH.16 supplies the function object and evaluation ev(f,x)=f(x). Restrict that object by the required condition. A rule with several inputs can be represented by a function on their product when a tuple contains all the inputs it needs.

For a partial operation, include its domain of definition. If f is defined on D within A and g on E within B, their composite is defined on {x in D | f(x) in E}. Whether this is an acceptable domain belongs to the current question.

Changing the admissibility condition changes the collection. An update preserving a set of possible states and a map preserving an algebraic operation answer different requirements. State the requirement before using either as an admissible rule.

MATH.17:4.3 - Establish the composition that the work needs

Try to construct:

Adm(B,C) x Adm(A,B) -> Adm(A,C), (g,f) -> g∘f.

The formula already defines a function composite. To obtain the displayed operation, establish that the composite satisfies the selected admissibility condition. Establish identity membership when doing nothing must be an allowable operation. Associativity then follows from function composition.

For example, fix a subset P of X and admit every f:X -> X with f(P) contained in P. If f and g are admitted and x lies in P, then f(x) lies in P and g(f(x)) lies in P. Thus their composite is admitted, as is the identity. These operations form a monoid: a set with associative composition and an identity. Several object types with identities and compatible associative composition form a category. These names make the established structure reusable.

If closure fails, use the failing input or pair to choose the repair. You might restrict the operations, enlarge the permitted result class, or keep a sequence of operations whose total admissibility is checked separately. For a cumulative resource bound, for example, retain the sequence and accumulated cost needed to assess the whole. Calling each step allowable leaves that total unresolved.

An interchange of steps is another claim. Establish g∘f=f∘g when a proposed reordering needs it; associativity by itself only changes the grouping of a fixed order.

MATH.17:4.4 - Construct an operation on operations and its law

Give the higher-order operation its own input and output types. For a transformation sending a function f to a new function T(f), start with an arbitrary input x of the desired new function. Express its required output using f and the available operations. That expression defines T(f)(x). Then establish that the constructed function belongs to the promised output collection.

Choose the law from the needed use. If T is meant to translate a sequence stage by stage, test:

T(g∘f)=T(g)∘T(f) and T(id)=id.

The types on both sides must agree. When T also changes the objects, specify that object assignment and the corresponding operation collections. An assignment preserving these compositions and identities is a functor.

For instance, we want to apply f:A -> B separately to each entry indexed by a fixed set I. Represent the input by s:I -> A; the set of such inputs is A^I. At index i the input is s(i), so the required output is f(s(i)). Collecting these outputs gives the function i -> f(s(i)) from I to B. We have constructed:

L_I(f):A^I -> B^I, defined by [L_I(f)(s)](i)=f(s(i)).

To derive the composition law, take arbitrary s and i:

[L_I(g∘f)(s)](i)=g(f(s(i)))=[(L_I(g)∘L_I(f))(s)](i).

Equality at every index proves the composition law. The identity law follows by applying the identity at every index. If admissibility requires each entry to remain in P, the earlier membership argument applies entry by entry. A condition relating different entries needs a further preservation argument.

A different higher-order operation can have a different useful law. Differentiation of polynomials preserves sums and scalar multiples and obeys the product and chain rules. Use those laws when deriving a derivative; a composition-preservation requirement would ask it to do a different job. The needed mathematical operation determines which laws to establish.

MATH.17:4.5 - Use the construction to change or compare rules

Compute the proposed changed operation and derive the consequence that motivated it. When comparing “transform each step” with “transform the whole”, keep both expressions until their equality is established or a separating input is found.

The result consists of the usable construction and the conditions supporting the particular consequence. For a finite example, a counterexample can settle a failed universal claim. A general preservation claim needs an argument over its stated inputs.

Return to the affected condition when the task changes. A new interaction between entries may invalidate pointwise lifting. A narrower resource budget may invalidate closure. A new question about how the operation was obtained may require retaining the construction that an input-output function discarded.

When this mathematics describes a working method, use C.29’s correspondence to identify what the mathematical operations represent and which practical distinctions they retain. A proposed program transformation also needs its execution semantics. Those connections let the result inform actual work while keeping the mathematical and subject claims recoverable.