This page gathers together definitions of various important entities in mathematics and points readers to more extensive discussion of those entities. All definitions here are built on my discussion of relations and the denotations I (used to) introduce for these.
This is a mapping: it accepts any relation, s, and converts it into
the relation, r, for which s relates y to x
is equivalent to r
relates x to y
. A relation, s, is described as symmetric (under reversal)
if s = reverse(s); reverse, read as a relation, is symmetric. For a symmetric
s, s relates x to y
implies s relates y to x
.
s relates x to yimplies
r relates x to y.
That is, s is a sub-relation of r precisely if s relating x to y implies that r does the same: r may, of course, relate some values to one another over and above those related by s. Two relations are deemed equal precisely when each is a sub-relation of the other: indeed, sub-relation's intersection with its reverse is just the identity on relations. [See discussion under relations.]
I'll say that
one relation subsumes
another if the latter is a sub-relation of the
former. In particular, any set subsumes each of its subsets and any map
subsumes any of its restrictions. Long ago, I used the word contains
to mean sometimes has as a member
and sometimes has as a
sub-whatever
: I now use subsumes
for the latter meaning,
to avoid ambiguity.
This is a mapping and is symmetric (under
reversal). Its sub-relations are called collections: a value x is described
as in
a collection A precisely if A relates x to x. This is equivalent
to x being an left or right value of A, given that A is a sub-relation of
identity.
Equality also appears under the synomym embed, as its
restriction (D: embed :S), when S is a sub-collection of D: this is
the natural embedding
of S in D. Note that, more generally, (D:
x←x :S) is the identity on (|S:)'s intersection with (:D|).
This is the relation which doesn't relate anything to anything. It is a sub-relation of every relation – including identity, so it is a collection. It is also a mapping.
I mainly use this as a place-holder, but it does show up (in its true naked form) if we try to intersect empty collections. As a place-holder, its typical use is in (A:all:B) which relates each right value of A to every left value of B (so it's akin to a Cartesian product).
Note that any (::empty) is trivially a zero, hence so is any ({(::empty)}::), as well as every ({({zeros}::)}::). This is a strongly-inductive definition, so handle with care; but combining it with the natural reading of 0 as {} suffices to make every ({0}::) a zero.
This is a mapping: it accepts any value, c, as input and produces a constant mapping as output: this mapping, produce(c), accepts (and ignores) any value, producing c as its output. Notice that produce is not, itself, a constant mapping, though its outputs are (and every constant mapping is a restriction of one of produce's outputs).
When r is a mapping, this relates it to those
values which it preserves. Not all relations (or mappings) have fixed
points. Identities have nothing else: fixed-point relates any collection to
each of its members. A relation is described as reflexive if it has, as fixed
points, all of its values, both left and right. I'll say x is in r
as
a short-hand for x is a fixed point of r
: this coincides with the usual
meaning of in
on collections and is convenient in other
contexts.
This
is the union of all the left values of r
. When r is a collection of
relations, unite(r) is the union of its members
. I'll refer to a
union of
pickles as a short-hand for the union of some relation of
which each left value is
a pickle, with anything in place of pickle
for which that makes sense. Likewise for an intersection of
.
By the nature of the definition, unite(f) = unite(|f:) for any relation f: when f is a collection, f = (|f:) so this says little; but when f is some more general relation (especially if given as some lengthy denotation, rather than as a simple name) I'll often write unite(|f:) to remind readers that unite only cares about f's left values. (Long ago, I used to define unite as uniting f's fixed points: but analogy with summation and similar operations calls for bulk actions to work on the left values of a relation, allowing for repetition even though unite ignores repeats.) If I want to refer to the union of the right values of some relation, f, I can still do so as unite(:f|), of course – or as unite(reverse(f)).
This and unite generalise the binary operators &intersect; and &unite;, which combine two relations, A and B, as if the collection {A, B} had been the argument to intersect or unite, as appropriate. Fixed points of unite and intersect are rather interesting. If some value e has no left values (e.g. empty, but equally any non-relation), unite(e) is empty, while intersect(e) is all, the all-relation, which relates every value to every value: and unite(all) is all, while intersect(all) is empty.
Rene(:r|N) relates (:u|N) to (:v|N) precisely if, for each i in N, each x that u relates to i and y that v relates to i: r(i) relates x to y. The condiition for each i in N may alternatively be stated as: the composition r(i)&on;(:v:{i}) is clean and its composite subsumes (:u:{i}).
When r is a list, [S, T], of two relations (so r is a mapping whose outputs are relations: its inputs are 0 and 1), Rene(r) is written S×T. When S and T are collections, S×T is the collection of lists, [a, b] with a in S and b in T.
When r is a mapping whose outputs are collections, Rene(r) is a collection whose members are mappings: each f in Rene(r) satisfies: (f:x←x:) = (r:x←x:) and, for each x in (r:x←x:), f(x) is in r(x). A list of two collections is just a special case of this with (r:x←x:) = {0, 1} = 2.
When r is a mapping whose outputs are mappings, so is Rene(r). It accepts, as input, any mapping u which accepts the same inputs as r and, for each such, x, r(x) accepts u(x) as input. It maps each such u to (: r(x,u(x)) ←x :), i.e. Rene(r,u) accepts any input, x, accepted by r, feeds it to each of u and r, then feeds u's output as input to r's output.
When r is a collection of collections, Rene(r) is a collection whose members are mappings: a member of Rene(r) maps each member, x, of r to one of its members; u(x) is in x = r(x).
This is a mapping: it accepts any value,
x, and produces a mapping, singleton(x). This accepts any value, y, and
produces a mapping, singleton(x,y), which accepts x but nothing else,
producing y as its output for x. Any such (second-stage) output of singleton
is known as a singleton
: these can be used in some contexts which might
otherwise deploy a pair
(e.g. disjoint sum).
Thus shred(r) is the collection of singleton sub-relations of r; and unite&on;shred is the identity on relations, since unite(shred(r)) trivially relates x to y precisely if r does.
This is a mapping: disjoin(r) relates s to x precisely if s is a singleton of some relation w that r relates to x – notice that r may relate several such w to x, for any given s. This generalises the disjoint sum (which is the case where r is a list of collections), in some sense.
This extracts a mapping from an arbitrary relation by throwing out any right value to which more than one left value is related. It is a mapping; whereMap(whereMap) = whereMap = whereMap&on;whereMap; and its restriction to mappings is the identity on mappings.
This extracts a mapping from an arbitrary relation. Like whereMap, it is a mapping and acts as the identity on mappings, so long as their outputs are all relations: also, uniteMap&on;uniteMap = uniteMap. It throws away any left values (of its input, r) which aren't relations: given input r, its output uniteMap(r) is a mapping which, given input x, yields as output a relation, uniteMap(r,x). This relates u to v precisely if r relates, to x, some relation which relates u to v.
This maps any relation to its collection of right values.
This maps any relation to its collection of left values.
This relates y to x precisely if r relates, to x, some u of which y is an right value. When r is a mapping whose outputs are mappings (i.e. it accepts at least two inputs), shred(pairs(r)) is the set of singletons y←x for which r(x, y) makes sense.
Pack is a mapping: it converts a relation, r, into a relation, pack(r), which relates singletons to relations. For a mapping f whose outputs are all mappings, pack(f) is a mapping, and its outputs are all singletons. For any x which f accepts and y which f(x) accepts, pack(f) accepts the singleton relation y←x and maps it to the singleton f(x,y)←f(x). Thus pack(f)'s inputs are obtained by gathering up two inputs to f using singleton: it produces an audit trail of outputs – one is usually interested in f(x,y), but pack(f) tells you how you got there, via f(x).
When f is a mapping, this is the equivalence on its right values which relates x to y precisely if f(x)=f(y). For a general relation, r, under(r) is a relation on (r:x←x:), still, and trivially symmetric and reflexive, but not necessarily transitive. [As an example, let a, b, x, y, z stand for some distinct values, consider the relation unite({a←x, a←y, b←y, b←z}) – this unites the singleton relations which are the members (hence left values) of the {…} collection – and let e be the relation to which under maps this union. Then e relates x and y to one another; e relates y and z to one another; but e does not relate x to z.] Under(r) relates x to y precisely if there is some a for which r relates a to both x and y.
This mapping turns a relation, r, into a mapping: it maps a value x to {y: r relates y to x}, a.k.a. (: y←y :r&on;{x}), the collection of values which r relates to x. Thus uniteMap, above, is just (: unite&on;(quotient(r)) ←r :). When r is an equivalence, quotient can be very useful – and every equivalence is a fixed point of under&on;quotient. When f is a mapping, there is some mapping g for which g&on;(quotient&on;under(f)) = f; that is, f can be factorised via quotient&on;under(f).
This is a mapping. It only
cares about those left value of its input which are non-empty relations: and
all of its outputs are mappings. The constraint on x, x in (u:i←i:),
u in (:j←j:f)
, can be read as x is a right value of some left
value of f
; it serves to avoid having transpose(r) relates empty to all
manner of values for which this isn't true. When transpose's input, f, is a
mapping whose outputs are mappings, we can read transpose(f) as (: (: f(y,x)
←y :) ←x :), where f = (: (: f(x, y) ←y :) ←x :) is
fatuously true.
Composing it with itself, we find transpose&on;transpose = uniteMap&on;(: ({non-empty relations}:r:) ←r :{relations}). The pre-filter given to uniteMap here just thins down any relation (or, indeed, any mapping) to one whose left values are all non-empty relations. If f relates x to empty (and to no other relations), then (transpose&on;transpose)(f) doesn't accept x as input: whereas uniteMap(f) relates x to empty (and to nothing else). On a mapping whose outputs are non-empty mappings (i.e. they accept at least one input each), transpose&on;transpose acts as the identity.
[By contrast, without any need for filtering, transpose composes with uniteMap (in either order) to give transpose. Sounds similar to the way triple-negation equates to negation, in logic, with double-negation being a slightly trickier subject.]
This is a mapping: for any value y, final(y) is a relation: it relates f to x precisely if f relates x to y. This acts as reverse&on;(transpose(reverse)) when all values involved are non-empty relations.
Pause to notice the subtle distinction between:
in which g is composed before f, x is fed to g as an argument, producing g(x), which is then fed to f; if the result is a mapping, we can feed it some y as input, obtaining f(g(x), y); and
which composes g(x) before f; this composite maps any given input y via g(x, y) to f(g(y, x)).
Likewise, transpose(transpose) is quite another thing from transpose&on;transpose, which is (: ({non-empty relation}: r :) ←r :{relations}) – transpose is self-inverse on relations whose left values are all non-empty relations.
Notice that final(y) relates f to x
iff f relates y to
x
, so that f in (: i←i :final(y))
is equivalent to y in (:
i←i :f)
. Since, for every x, y, there is a singleton(x,y) which does
relate x to y, every x and y have x in (final(y): i←i :) and (see below)
y in (: i←i :evaluate(x)).
This is the transpose of the identity on relations. It is a
mapping: for any value x, evaluate(x) is a relation: it relates y to f
precisely if f relates y to x. Notice that f in (evaluate(x): i←i
:)
iff x in (f: i←i :)
.
When f is a mapping, evaluate(x, f) is unambiguously f(x) – there is exactly one y for which f relates y to x – and this is indeed true even if f is not generally a mapping, so long as the particular right value x has only one left value related to it, which is just when f acts on x as if f were a mapping. The restriction ({mappings}: evaluate :) thus justifies the name I here give to the generalised form of it.
This is a mapping which accepts any relation:
successor(r) is a relation which relates x to y precisely if: r relates x
to y or x=r=y
. If r is a fixed point of r, this is just r: otherwise, it
is one atomic relation, r←r or {r}, bigger. This is the tool with which
the natural numbers are manipulated; its
action on them is what we're more used to calling (: 1+n ←n :).
This is a mapping which accepts any relation, f: delegate(f) subsumes f well as each of its left or right values which is a relation.
On {relation f: f is neither a left nor right value of delegate(f),
whose left and right values are all relations}, successor is closed and
one-to-one. [The trailing whose …
clause can be amended to allow
other things than relations, so long as these are all defined a priori
to any relation.] There is a strong sense in which these are the only
constructible relations.
Whether Bertrand relates Bertrand to Bertrand is, of course, undecidable – in the strong sense that taking either case as an assumption is guaranteed to yield a contradiction. Only in accepting our ignorance can we hope for consistency: but Heisenberg's heirs will not be scared by that ! [foldoc].
This is equally thought of as unite({r, r&on;r, r&on;r&on;r, …}), or defined inductively.
Note that this leads to paradox if it is used without restraint; we can define naturals to be finite ordinals, because we can show that {naturals} is then not finite; but, absent any restriction on the collections involved, {ordinals} would be an ordinal – yet one can prove that no ordinal is a member of itself.
Thus {naturals} is the collection {0, 1, 2,
…} wherein: 0 is another name for empty; 1 is another name for
successor(empty) = {0}; and, generally, 1+n
(in common parlance) is {0,
…, n} = successor(n) is natural for each natural n.
wherein repeat(n, f) is defined inductively by repeat(0,f) = (f:i←i:) and, for each natural n, repeat(successor(n),f) = f&on;repeat(n,f). [Transitive-closure(f) is then just unite(: repeat(successor(n),f) ←n :{naturals}).] Notice that, when f is a mapping, so is each repeat(n,f) with n natural.
Thus add(1) is successor's restriction to {naturals} amd add(0) is {naturals} itself. The value of add(n,m), i.e. add(n)(m), is generally written as m+n. In particular, successor(n) is n+1.
When add is interpreted as a binary operator on {naturals}, various theorems about it can be proved. It is abelian (that is, n+m=m+n: I will usually write successor(n) as 1+n rather than n+1), associative – so k+(n+m) = (k+n)+m – and cancellable (n+m=n+k implies m=k). It has an identity, 0, and respects the natural order on {naturals} – namely, n<m precisely if n is in m – in the sense: n<m implies, for any natural k, n+k<m+k. Furthermore, for any n<m, there is a unique natural k>0 for which n+k=m. The collection {natural n: 0<n} is called the positive integers: it is equally (|successor:{naturals}).
I'll also discuss contexts in which other things than naturals can be
added and will use +
for the binary operator involved and call the
associated function add
, as here.
When read as a binary operator, this has 1 as identity, is abelian, is associative and distributes over add. Its restriction to the positive integers is cancellable, respects order and can be expressed as multiply(1+n) = (: repeat(n,add(m),m) ←m :) without mention of an additive identity.
For any natural, n, we can extend this last expression of multiply(1+n)
to any context in which we have an addition. This induces a multiplicative
action of the (positive) naturals on every additive domain, which I'll always
write as n.m ←m. I'll also use .
as the binary operator for other
multiplications which distribute over addition, generally those which may be
viewed as extending
this natural action of the naturals (typically
involving some suitable image of the naturals among the multiplicative
domain's members). (Other multiplications will usually be denoted
with ·
or ×
as operator.)
We can read this as a binary operator, too, power(n,m) = m^n, but it: isn't abelian; has no left identity (no m for which m^n=n for all n); yet has a right-identity, 1, as m^1=m for each m; its restriction to n>0 is right cancellable (p^n = q^n implies p=q for n>0) and its restriction to m>1 is left cancellable (m^p = m^q implies p=q for m>1).
For any natural, n, we can extend power(n) to any context in which we
have a multiplication, save that power(0) requires a multiplicative
identity. I won't generally use ^ as a binary operator, preferring power(,)
as the denotation. We may also be able to extend power to accept some other
inputs than naturals, e.g. power(1/2) = (: √x ←x :), in some
contexts: in particular, wherever we have suitable log and exp functions at
our disposal, for which power(n,x) = exp(n.log(x)) gives the right
properties.
defined inductively by:
Notice that transpose(supply) maps a relation, r, to a relation whose right values are lists. This is transpose(supply, r): it relates [] to r, [a] to z iff r relates a to z, [a,b] to z iff r relates a to some y which relates b to z, [a,b,…,l,m] to z iff there are some n,o,…,x,y for which r relates a to n, n relates b to o, …, x relates l to y and y relates m to z.
The second condition means that reduce(a,(:s|1+n)) relates x to z precisely if a relates, to s(n), some q for which reduce(a,(:s:n))&on;q relates x to z. When a is a mapping, the definition just simplifies to the bulk action of compose, applied to the result of composing the first two inputs to reduce: reduce(a, (:s|n)) = bulk(&on;, a&on;s) = a(s(0))&on;a(s(1))…&on;a(s(n)).
When a encodes a binary operator in the form (: (Y: a(x, y) ←y |Y) ←x |X), with a(x, y) written as a*x for some symbol * (such as ×, + or &on;), each left value a(x) is a mapping (Y: |Y); when s is a list (X:s|n), a&on;s is a list of such mappings; so composing these mappings gives, again, a mapping (Y: |Y), of form reduce(a, [p,q,…x]) = (Y: p*(q*(…*(x*y)…)) ←y |Y).
If, for some mapping (X| star :{mapping (Y|:Y)}) with star(x,y) written y*x, every w, x in X imply a unique z in X for which a(z) = reduce(a,[w,x]), we can infer a binary operator on X, (X| stir :{X|:X}), defined by reduce(star,[w,x]) = a(stir(w,x)). [That uniqueness will involve a being cancellable.] (When X is Y, star=stir iff star is associative.) Writing stir(w,x) as x.w, we obtain reduce(star, (X:s|1+n)) = (Y: s(0)*(…*(s(n)*y)…) ←y |Y) = star(reduce(stir, (:s:n), s(n))).
Written by Eddy.