Abstraction, Categorization, and Mappings

George Weaver
Center for Science in Society
Working Group on Information

(material stemming from and relevant to 14 June 2004 conversation)

Many discussions of abstraction begin with a set A and a relation, R, on the set A where R is an equivalence relation on A (i.e. R is reflexive, symmetric and transitive on A). When x is a member of A the equivalence class of x relative to R is the collection of all y in A such that (x,y) is in R. [x]R denotes the equivalence class of x relative to R. The collection of all the equivalence classes of members of A relative to R is the partition on A induced by R. This set is a collection of non-empty disjoint subsets of A that covers A in the sense that an object is in A iff it is in some member of the partition. This partition is denoted by A/R. More generally, a collection of sets is a partition on A iff the members are a collection of non-empty, disjoint subsets of A that covers A. Members of a partition are sometimes called cells in the partition. It is easy to show that every partition on A is induced by some equivalence relation on A. Intuitively, think of A as a collection of sensory inputs and R as defined in terms of certain distinctive features of these inputs. [x]R is the set of those inputs that are indistinguishable from x so far as these distinctive features are concerned. (In previous discussions, [x]R has been called a category. Thus, distinctive features give rise to categories.)

It is perhaps less well known that abstraction/categorization on A can be accomplished by mapping A onto another set. Let B be a set and f be a function defined on A. For the purposes of this discussion it is assumed that f is onto B in that for any y in B there is an x in A such that f(x)=y. For y in B, the preimage of y under f is the collection of all members x in A such that f(x)=y. The collection of preimages of members of B under f forms a partition on A. This partition is called the partition on A induced by f. We let A/f denote this collection. Intuitively, think of A as above, B as receptors and f as an input function. It is easy to show that every partition on A is the partition induced by some function defined on A. (If you will, that every categorization of A can be accomplished by some function defined on A.) There is an easy result that relates the partition on A induced by f and the action of f. Call a partition on A atomic iff each of the cells in the partition is a set with only one member. There is only one atomic partition on A and it is the partition induced by the identity relation on A. The function f defined on A is one-to-one iff if x and y are members of A and x~=y, then f(x)~=f(y).

PROPOSITION Assume that f is a function from A onto B. Then the following are equivalent:

1) A/f is atomic;

2) f is one-to-one.

The point of this proposition is that one-to-one and onto functions do not induce interesting (non-atomic) categorizations. There is a second and related point. Notice that A/f and B have the same number of elements. If A/f is atomic, then A and B have the same number of elements. Hence, to insure non-atomic partitions, we need only map A to sets that have strictly fewer objects than A. When A is finite this is the only way to assure non-atomic partitions. When A is infinite, there are functions from A onto sets of the same size as A that induce non-atomic partitions.

Home | Calendar | About | Getting Involved | Groups | Initiatives | Bryn Mawr Home | Serendip Home

Director: Liz McCormack - emccorma@brynmawr.edu | Faculty Steering Committee | Secretary: Lisa Kolonay
© 1994- , by Center for Science in Society, Bryn Mawr College and Serendip
Last Modified: Wednesday, 02-May-2018 10:51:19 CDT