Wherever the restriction denotation above allows a [filter]
,
with accompanying :
, it may be replaced by an assert
(which
must be a relation) with accompanying |
. This denotation stands for a
relation: indeed, the relation in question is the one obtained by replacing the
| with a :. However, in addition to denoting that relation, this
denotation asserts that its initial or final values are exactly the final or
initial values of assert. Thus, for example (with A, f, B general
relations - but note that when A is a collection, (|A) = A = (A|), and likewise
for B):
- (A|f:B) denotes (A:f:B) and asserts that (|f:B) subsumes (A|), hence
(|(A:f:B):B) is (A|). Having (|f:B) subsume (A|), for some collections A and B
and mapping f, means that (:f:B) accepts every member of A: f is then described
as a mapping
from
A to B. - (A:f|B) stands for (A:f:B) and asserts that (A:f|) subsumes (|B).
- (A|f|) will denote (A:f|) and assert that (|f) subsumes (A|) - see next denotations.
-
any mapping (A|:B)
is a mapping which accepts every final value of A and whose outputs are all initial values of B: if its name is not needed (as when I can refer to it asit
), the denotation is not obliged to name it. - {mappings (A|:B)} is the collection of mappings from A to B. The short-form which many contexts will use for this or some suitably-restricted (eg by linearity or continuity) sub-collection of it - {(A|:B)}, will crop up plenty. In particular, when discussing linear algebra, I want to be able to write {(V|:U)} rather than {linear (V|:U)} or Linear(V, U) for the space of linear maps from V to U - albeit I shall also refer to this as U⊗dual(V)).
Wherever the asserted denotations just given may have (:
or :)
, the
colon, :
, may be replaced with a |
to denote the initial or final values of
the relation (as if the assert's | were replaced by a
:), while at the same time making the given assertion about the
final or initial values of (:relation:) subsuming the initial or final
values of assert.
Leap-frog this aside to another.
An aside: symbols
I introduced &unite;, &intersect; and &on; as symbols. I would be pretty happy to replace &unite; with the U-shaped symbol usually used to denote the union operator. Sadly, that's not in the character set.
I could burden some ordinary character, such as U or a punctuator, with the rôle of &unite;. But this would have overloaded other characters, especially as that U isn't going to be the only symbol I want. I tried ;- for a while, but it looks no better (and is easier to fail to notice) than &unite; and the latter at least gives a hint at what it means.
I could produce (or find) a standard set of little image files which (when displayed using a web browser which supports in-lined images) appear as the symbols I want. I'd then be writing <IMG SRC="/img/math/union.png" ALT="union"> where, at present, I type &union;, though I could probably persuade emacs to let me produce these with only a few keystrokes. Font-changes wouldn't affect them, but they'd do the job reasonably well. However, the source file containing my HTML then gets ugly, and I dislike that.
On the other hand, &unite;, though not at all pretty, will do as well as any
other token for the purpose in hand: and is of the form required for HTML (or,
perhaps, a style sheet) to be able to specify that it be rendered as a suitable
U. I could as readily have introduced the word unite
with a special meaning,
it would be shorter, but &unite; gives me the opportunity to mark
the word as
one token
where it appears, in an expression, adjacent to a name.
Those folk using raw text, or old, browsers are going to be meeting ×
in a similar form wherever I use it, and I don't consider it an unreasonable
burden to intelligibility - it's the form in which I read them when using my
authoring tool
(emacs). Indeed, a reader seeing ×, once cued to
know that &...; is to be read as a single token, even gets to be reminded of
what that symbol means (in case it is unfamiliar to them). Anyway, that's as
much apology as you'll get from me for using such ugly denotations rather than,
say, just the word on
. I'll use &symbol; to denote a symbol, using
some (at least vaguely) appropriate word as the symbol where I so chose -
and maybe I'll one day have a way of telling your browser a nice
way to
present it.
Leapfrog this aside to denotations for lists.
Another aside: standard denotation
I have used the standard denotation, f(x), for the output of a mapping, f, produces in response to an input, x, it has accepted: this leads naturally to defining composition as (f&on;g)(x) = f(g(x)). I have a problem with this, in that mappings, thus written, accept their input from the right: yet when we want to draw the behaviour of a mapping, those of us who read text from left to right generally want to draw the arrow pointing from input on the left to output on the right. Indeed, left-to-right denotations are in common use for functions, as when the input-set is written, then an arrow pointing rightwards to the output-set, to denote a function from the former to the latter: see, likewise, my formulaic denotation for relations (above).
Some mathematicians, I'm told, work consistently from left to right: so that f's output for input x is (x)f or just xf, perhaps. I can see the appeal of this. However, as readily as I can pass f's output, when given x as input, to some second mapping, g, I can equally notice that f's output was itself a mapping, and give it a second input, y. With one convention we get g(f(x)) and (f(x))(y), with the other we get ((x)f)g and (y)((x)f): f comes before g and x comes before y, so one way round forces us to read composition in right-to-left order, the other forces that order on successive presentation of arguments. Either way, we have to live with reading in each order in some places: and this inevitably leads to having to deal with some order-twisting - which I've tried to keep to a minimum and make plain wherever it arises.
Anyway, I want to be understood by physicists, so I'm going to use the f(x) form for function application, with its consequent order for composition. It's taken some work to keep this sweet with plain words (which here read from left to right) and various things which I'll introduce in the order suggested thereby. It is, however, possible: with some studiously judicious choices along the way - such as numbering the rightmost element of a list, when I introduce their denotation, as 0. This will create minor friction when representing a relation as a collection of pairs (lists of length 2), but resolves peacefully.
Notice that supplying a succession of arguments to a mapping (which you can
do so long as its output from the previous argument is a mapping) is written
f(x)(y)(z) when x is the argument f receives, y being then given to f(x) and z
to the resulting f(x)(y). Argument consumption, unlike the composition of
mappings, reads from left to right in formulae: so when I come to identify
mappings which accept several arguments with mappings which accept lists
(wrapping up the arguments to be handed to the mapping), I'll identify f with a mapping which maps [x, y, z] to f(x)(y)(z), so
that the first argument passed to a mapping with several arguments will be the
highest-numbered (or last
) in the list which packs up the arguments.
As discussed earlier, f(x)(y)(z), which really stands for ((f(x))(y))(z),
may also be written as f(x,y,z).
Lists
In this bit, you'll have to watch out for the font of [, ... and ] - when [ italic ... ] they're this page's meta-notation, enclosing or denoting something optional, when [ bold ... ] they're part of the denotation for lists. (When actually used, in the examples and real discourses, they'll be used in the ambient font of their context.)
- list
- [ [item [ , item ...] ]]
- [ [item [ , item ...] , ] ... [ , item [ , item ...] , ... ...] [ , [item , ...] item] ]
The first of these denotes a list of definite length; the second denotes a list of indefinite length. In the latter, if there is a sequence of items to the left of the (leftmost) ellipsis, ..., this is known as the tail of the denotation; if there are items to the right (of the rightmost), they are known as the denotation's head.
The pattern for a list of definite length matches an arbitrary sequence of items separated by commas: if no items are present, we have only [], denoting the empty list; otherwise, let n be the number of commas present (n may be 0, and we ignore any commas which may be present inside items); the list denoted is then (1+n| :); it implicitly labels the right-most item 0 and, for each item with label i in n, gives label 1+i to the item to its left; the list maps each i in 1+n to the value of the (unique) item labelled i. (The left-most item gets the label n: indeed, the label of each item is the number of commas to its right.)
A denotation using ellipsis isn't as definite about the length of the list denoted: it can be used to say things about a list of any length, subject to a minimum. The simplest case, [...], stands for an entirely arbitrary list (but gives us no name for its length or for any of its entries, so I don't use it much). Otherwise, the list denoted is at least as long as the longest sequence of items separated by commas (ie not be ellipsis): that is the minimum, but it may be longer.
For any comma-separated sequence of items in an ellipsis denotation, we could enclose that sequence in [ ] to get a denotation for a list, s, of definite positive length: the presence of this sequence in our denotation states that the list denoted subsumes s&on;(:n+i -> i:) for some natural n - that is, the list maps n to s(0), 1+n to s(1) and so on: s appears as a sub-list of the list denoted. If the sequence is the head, n is zero: if the tail, then n+(|s) is the length of the list denoted (where (|s) is the length of s); the last (leftmost) item of s is then equally the last item of the list denoted.
- [ [item [ , item ...] , ] ... [ , item [ , item ...] , ... ...] [ , [item , ...] item] ]
Note that the sub-lists given in an ellipsis denotation may overlap, and I
make no assertion here about the order of sub-lists separated by ellipsis: [...,
r,q,p, ..., k,j,i, ...] has the same meaning as [..., k,j,i, ..., r,q,p, ...]
and either may indicate [r=k,q=j,p=i] or [..., k,r=j,q=i,p]. However, the
context specifying such a list may call for p to come after
(ie really
to the left of) k or no earlier than
it (ie possibly allowing [...,
r,q,p=k,j,i, ...], but otherwise with p after k) if that is appropriate.
Most commonly, lists with ellipsis will have no more sub-lists than head and tail, for which we do have a statement about ordering: the left-most item of the tail is the list's last item and the right-most item of the head is its first, so we know the head's right-most item is no later than that of the tail and the tail's left-most is no earlier than that of the head. Thus [z,y,...,c,b,a] may be [z,y=c,b,a] or [z=c,y=b,a]: but, otherwise, the head and tail given can't overlap. Indeed, similarly, [z,..., k,j,i, ..., a] is, at its extremes, [z=k,j,i, ..., a], [z, ..., k,j,i=a] or, even, [z=k,j,i=a]. As a final example, which will arise often, I'll write [z,...,a] for an arbitrary non-empty list: this may be [z=a] with one item, [z,a] with two, or some longer list starting in a and ending in z: for any natural n, a list (1+n|f:) is then [f(n),...,f(0)] without having to treat the case n=0, hence (1|f:), specially. I'll generally give [] special treatment, though - it tends to warrant it.
Lists suffice for a definition of the binary operator ×, denoting the Cartesian product: for relations r, s, we get s×r = Rene([s,r]) relating [u,v] to [x,y] precisely if s relates u to x and r relates v to y: when r and s are collections, this is the collection of pairs [u,v] with u in s and v in r. More generally, we have (| s×r :) = (|s)×(|r) and (: s×r |) = (s|)×(r|).
Of course, I should really write an XML description of that and an XSL program to convert it into the denotational forms given above.
Written by Eddy.