# Distinguishing between procedure-like and collection-like mathematical objects

Is it useful/productive to draw a distinction between "active" things with "computational force" (procedure-like) and "passive" things without such force (collection-like)? Does this distinction have a well-established name? Is adopting a perspective with these notions, even temporarily, just sloppiness?

As a programmer studying mathematics and logic informally, it seems natural to divide up mathematical objects into "objects that do things" and "objects that are basically just bags of data, possibly very large bags". When thinking about a program or explaining it to someone else, it is often useful to adopt a distinction between code and data, even if the language you are working in does not have a crisp code-data distinction.

I'm not saying that some objects are inherently "active" and others are inherently "passive", just that it frequently seems natural to adopt a perspective in which some things are active and others are not.

I'm not sure exactly how to formalize the distinction I'm trying to draw but maybe an example will help.

A mathematical function can be thought of "procedurally" as an opaque process that takes inputs and transforms them into outputs. The main "payoff" of this metaphor is that alarm bells immediately go off in your head when you think about whether two functions are equal. What does it even mean for two processes to be equal if you can't inspect their contents?

A mathematical function can also be thought of as a collection, in at least two obvious ways. One is as a set of pairs:

{ (0, 1), (1, 2), (2, 3), (3, 4), ... }


And the other is as an ordered triple consisting of a domain, a codomain, and a set of pairs:

( ℕ, ℕ, { (0, 1), (1, 2), (3, 4), ... } )


For another example, take classical first order logic with no function symbols.

In one perspective, individual elements of the domain can be thought of as lifeless data and predicates can be thought of peering inside elements of the domain to classify them.

In another perspective, the quantifiers ∀ and ∃ and the logical connectives (∧, ∨, ¬) are the active things and predicates are just collections of elements in the domain.

• Isn't this pretty much the same as philosophy.stackexchange.com/questions/59228 ? In that case, see my comment to the op about the lambda calculus, philosophy.stackexchange.com/questions/59228/… – user19423 Jan 1 '19 at 8:27
• @JohnForkosh The questions might be too similar; I didn't notice that particular question until after writing mine, so my timing isn't great. I think my question is different though because I'm asking about "what you're doing intuitively when you split the universe into data and ways of transforming data" and the other one seems to be about justifying math, especially arithmetic, with a theory that's as fundamental as possible and doesn't sweep details like the meaning of equality under the rug. – Gregory Nisbet Jan 1 '19 at 8:46
• Then the distinction is "functions as graphs" versus "functions as rules", like I mentioned to the earlier op. I'm not aware of any more standard and succinct name/terminology. The two quoted phrases (often quoted by others, as you'll find by googling them) come from page1 of Barendregt's book amazon.com/Calculus-Semantics-Studies-Foundations-Mathematics/… (which googlebooks doesn't seem to have scanned). As far as "equals", I'd suggest, instead, partitioning the space of all programs into equivalence classes, where all programs in a class calculate the same function... – user19423 Jan 1 '19 at 9:03
• ...Then programs in the same class wouldn't typically be identical, e.g., the computational and/or Kolmogorov complexity of each function in that class might be enormously different. But they'd all correspond to the same N-->N (or Pw-->Pw, etc) function. (Oh, I should explicitly say that equivalence class idea isn't my original idea -- the comment maybe sounds like I'm suggesting it is.) – user19423 Jan 1 '19 at 9:07

Take your last example seriously. Are the 'static' things the predicates? Or are they the statements, and are the axioms that permit proof the 'active' things? Or are the sets of things that are proven equivalent just furniture, and the premises that allow them to apply to models the active things? Maybe existing proofs are all static objects and the tools that combine them into potential future proofs are the only dynamic objects. Each of those perspectives is taken by different domains within mathematical logic: basic semantics, predicate calculus, model theory, and proof theory.

This is the problem with this perspective. Active behavior layers upon itself, and to proceed, one generally abstracts what was previously the active layer into something passive, and focusses on another layer of active processes. Metaphorically, you often trade time for space, making what was your previous 'active' temporal dimension into another 'passive' spatial one.

This is one of the reasons we move from FORTRAN with entirely separate functions and data to COBOL with the only ability to treat code as data being 'COPY {section} REPLACING {pattern} WITH {translation}.' and 'Alter {paragraph name} to proceed to {paragraph}.' (Which were what they say -- the compiler would copy a chunk of code replacing parts mechanically, or the Alter statement, when executed, would change a given named label to be a jump to a different named label), on toward C-ish languages that can point at functions and 'vector' through function pointers, to C++ templates or Java generics, and then toward languages like Python where functions are first-class objects that can be modified or constructed out of other things at whim, and beyond. (Ignoring that we started with LISP, and various von-Neumann assembly languages that completely ignored this distinction to good effect, but scared everyone off using them.)

So this is always a useful perspective, but it is also generally a temporary one, that will evolve. There is not really a place for it to extend all the way across mathematics in a uniform fashion. It would get in the way.

The overall notion is captured in Category Theory, where a 'category' is a collection of 'objects' connected by 'morphisms'. But then there are categories that have the morphisms of an existing category as its objects, or that have whole categories of a given form as objects, or the morphisms between types of categories as objects, or build from there.

I'm not sure whether this answers your question or not, but it is common in the philosophy of language to distinguish 'sense' and 'reference'. At least one common theory of meaning has it that predicate terms, names, and even sentences, have a meaning that can be divided up between the sense and the reference, and that it is the sense that determines the reference. The reference is often taken to be purely extensional, i.e. it is a thing, or a class of things, while the sense is intensional and serves as a function that identifies the referent within a given context. So, for example, the expression "the tallest person in the world" is a definite description with a referent, i.e. whoever that is in our world, and a sense, which might be a function that enables us to pick out this individual. A name, such as "Albert Einstein", has a referent, albeit deceased, and a sense, which is how we identify this individual and distinguish him from others. A property, such as "is blue", has a referent, the class of all blue things, and a sense, which is how we identify blueness. A sentence, according to Frege, has a sense, which is the proposition it expresses, and a reference, which is its truth value.

All of the details of this kind of account are subject to many arguments and disagreements. Frege, Russell, Kripke, Davidson, and David Lewis, in particular, all had rather different views of the matter.

The mathematical analog might be that the sense of a mathematical expression is a procedure or algorithm, while its referent is the mathematical object or class that the procedure determines. For example, we might think of the Fibonacci series as being both an algorithm that determines a sequence of numbers, and as the sequence so determined.

I don't think you are correct to suppose that logical constants are active, while predicate terms are just collections. It is true that mathematicians typically dispense with intensionality and treat coextensive properties as identical: the square of 2 is identical with the positive square root of 16, and the class of equilateral triangles is identical with the class of equiangular triangles. But out in the real world, a thing or a property can be identified in many different ways and these have different meanings. A person may have several names. Maybe Alice knows that George Orwell wrote 1984, but Alice does not know that Eric Blair wrote 1984. The fact that both names have the same referent is not sufficient for them to have the same meaning. Likewise, two predicate terms may be coextensive while having different meanings, e.g. Quine's example of 'cordate' meaning 'has a heart' and 'renate' meaning 'has kidneys'. All and only those animals that have hearts have kidneys, but the terms clearly have a different meaning. So, outside of mathematics at least, it is not correct to identify a predicate with its extension.