#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass article
\begin_preamble
\usepackage{url}
\end_preamble
\use_default_options false
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding utf8
\fontencoding global
\font_roman "times" "default"
\font_sans "helvet" "default"
\font_typewriter "courier" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref true
\pdf_bookmarks true
\pdf_bookmarksnumbered false
\pdf_bookmarksopen false
\pdf_bookmarksopenlevel 1
\pdf_breaklinks true
\pdf_pdfborder true
\pdf_colorlinks true
\pdf_backref false
\pdf_pdfusetitle true
\papersize default
\use_geometry false
\use_package amsmath 2
\use_package amssymb 2
\use_package cancel 1
\use_package esint 0
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 0
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 0
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header
\begin_body
\begin_layout Title
Tensors
\end_layout
\begin_layout Author
Linas Vepstas
\end_layout
\begin_layout Date
26 August 2020
\end_layout
\begin_layout Abstract
This chapter defines a tensor in a general setting, extending the conventional
definition of a tensor valued in a field.
The definition here allows the tensor to be valued over
\begin_inset Quotes eld
\end_inset
anything
\begin_inset Quotes erd
\end_inset
, with only minor algebraic constraints on what
\begin_inset Quotes eld
\end_inset
anything
\begin_inset Quotes erd
\end_inset
can be.
The tensor product can then be seen as a kind of concatenation or
\begin_inset Quotes eld
\end_inset
forgetting
\begin_inset Quotes erd
\end_inset
, while the inner product becomes a
\begin_inset Quotes eld
\end_inset
plugging together of connectors
\begin_inset Quotes erd
\end_inset
.
The definition given here is more-or-less compatible with the idea of a
\begin_inset Quotes eld
\end_inset
tensor category
\begin_inset Quotes erd
\end_inset
, but avoids category theory.
The focus is different: the focus here is concerned with knowledge representati
on, computer algorithms and artificial intelligence.
\end_layout
\begin_layout Abstract
This is a part of a sequence of articles exploring inter-related ideas;
it is meant to provide details for a broader context.
The current working title for the broader text is
\begin_inset Quotes eld
\end_inset
Connectors and Variables
\begin_inset Quotes erd
\end_inset
.
\end_layout
\begin_layout Section*
Tensors
\end_layout
\begin_layout Standard
This text reviews the concept of a tensor, starting from the conventional
definition, which gives its most narrow form, and broadening it to a general
setting.
It is hoped that the reader already knows what a tensor is, as otherwise,
most of this may seem pointless.
The explanation begins very simply, at the freshman level; do not be mislead
by the simplicity, there are a few tricks in here.
\end_layout
\begin_layout Standard
Three properties of tensors will be exposed and articulated.
These may seem strange and idiosyncratic, if you already know what a tensor
is; but communicating the strangeness is why we write.
\end_layout
\begin_layout Itemize
A means of storing data in a particular form or shape.
\end_layout
\begin_layout Itemize
The tensor product as a kind of concatenation and
\begin_inset Quotes eld
\end_inset
forgetting
\begin_inset Quotes erd
\end_inset
.
\end_layout
\begin_layout Itemize
The inner product as a kind of
\begin_inset Quotes eld
\end_inset
plugging together of connectors
\begin_inset Quotes erd
\end_inset
.
\end_layout
\begin_layout Standard
These properties can be taken in contrast to conventional expositions, which
emphasizes multi-linearity and and behavior under change-of-basis.
The change in focus is required to build the abstract notion of a tensor.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
There is a different abstract formalization of tensor products, that used
in category theory.
It is briefly reviewed in the appendix.
It is far more abstract and daunting, thus we avoid it.
Note also the definition of a tensor category does not include the notion
of an inner product, so our focus here really is different.
\end_layout
\end_inset
\end_layout
\begin_layout Subsection*
Tensors as databases
\end_layout
\begin_layout Standard
The conventional definition of a tensor in science and engineering starts
with the introduction of the concept of a scalar
\begin_inset Formula $s$
\end_inset
: a single number usually taken to be a real number or a complex number
or even, abstractly, taken from some ring
\begin_inset Formula $R$
\end_inset
.
A vector
\begin_inset Formula $v=\left[v_{1},v_{2},\cdots,v_{n}\right]$
\end_inset
is a sequence of numbers.
A matrix
\begin_inset Formula $M=\left[M\right]=M_{ij}=M(i,j)$
\end_inset
is a square of numbers, indexed by rows and columns
\begin_inset Formula $i,j$
\end_inset
.
The equality signs here just suggest different ways (different notations)
of writing the same thing.
A 3-tensor
\begin_inset Formula $T_{ijk}=T(i,j,k)$
\end_inset
is a cube of numbers; a 4-tensor
\begin_inset Formula $T_{ijkm}=T(i,j,k,m)$
\end_inset
is a 4-dimensional
\begin_inset Quotes eld
\end_inset
hypercube
\begin_inset Quotes erd
\end_inset
of numbers, and so on.
\end_layout
\begin_layout Standard
That tensors can be used to
\begin_inset Quotes eld
\end_inset
store data
\begin_inset Quotes erd
\end_inset
sounds a bit silly, or perhaps painfully obvious, given the conventional
definition.
None-the-less, tensors are a form of
\begin_inset Quotes eld
\end_inset
database
\begin_inset Quotes erd
\end_inset
, where
\begin_inset Quotes eld
\end_inset
data
\begin_inset Quotes erd
\end_inset
(the number) has been
\begin_inset Quotes eld
\end_inset
stored
\begin_inset Quotes erd
\end_inset
at a
\begin_inset Quotes eld
\end_inset
location
\begin_inset Quotes erd
\end_inset
determined by the indexes (which are taken as ordinal numbers).
This becomes a slightly more interesting observation when one realizes
that computer-science has a small armada of similar devices for storing
data: arrays and vectors and lists and lookup tables and the like.
In comp-sci, considerations such as speed, space, accessibility, mutability
become important, and strongly affect algorithms.
That a tensor has the form of a database becomes even more interesting
when one ponders how to store extremely sparse tensors: those whose entries
are mostly zero, with a scattering of non-zero entries.
Consider a matrix with one million rows and one million columns: this has
\begin_inset Formula $10^{6}\times10^{6}=10^{12}$
\end_inset
locations; were we to splat a 64-bit floating-point number down at each
location, this would require
\begin_inset Formula $8\times10^{12}$
\end_inset
bytes of storage: 8 terabytes.
If all of those locations were zero, except for possibly for
\begin_inset Formula $10^{6}$
\end_inset
here or there ...
that would be an insane waste of RAM: storing a million non-zero numbers
requires only 8 megabytes, not 8 terabytes.
\end_layout
\begin_layout Standard
For sparse tensors, the preferred storage mechanism takes the form of a
\begin_inset Quotes eld
\end_inset
seed
\begin_inset Quotes erd
\end_inset
, illustrated in previous sections.
Lets repeat it:
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/seed-unlabelled.eps
lyxscale 60
width 25col%
\end_inset
\end_layout
\begin_layout Standard
The black dot at the center is the
\begin_inset Quotes eld
\end_inset
data
\begin_inset Quotes erd
\end_inset
(the number).
The white dots are the
\begin_inset Quotes eld
\end_inset
tensor indexes
\begin_inset Quotes erd
\end_inset
– the ordinal-number valued tuple identifying the location of the data.
The figure shows five connectors, and thus an entry in a 5-tensor.
\end_layout
\begin_layout Subsection*
Tensor products
\end_layout
\begin_layout Standard
We begin with the conventional definition of the tensor product, before
generalizing it in a later section.
\end_layout
\begin_layout Standard
The tensor product is conventionally denoted with the
\begin_inset Quotes eld
\end_inset
otimes
\begin_inset Quotes erd
\end_inset
symbol
\begin_inset Formula $\otimes$
\end_inset
.
This intimidating symbol is used to emphasize the multi-linearity of the
tensor product.
That is, if
\begin_inset Formula $u,v$
\end_inset
and
\begin_inset Formula $w$
\end_inset
are vectors, and
\begin_inset Formula $a$
\end_inset
and
\begin_inset Formula $b$
\end_inset
are constant numbers, then
\begin_inset Formula
\[
\left(au+bv\right)\otimes w=au\otimes w+bv\otimes w
\]
\end_inset
for the left side of the product, and likewise for the right: that this
works on both sides is what makes it multi-linear.
The
\begin_inset Formula $\otimes$
\end_inset
symbol is required because the Cartesian product symbol
\begin_inset Formula $\times$
\end_inset
does not work; it is not multi-linear.
Consider, for example, the two ordered pairs
\begin_inset Formula $u\times w=\left(u,w\right)$
\end_inset
and
\begin_inset Formula $v\times w=\left(v,w\right)$
\end_inset
.
How can we multiply a scalar times an ordered pair? Conventionally, one
re-scales all of the components.
That is,
\begin_inset Formula $a.\left(u,w\right)=\left(a.u,a.w\right)$
\end_inset
but this fails spectacularly in terms of multi-linearity:
\end_layout
\begin_layout Standard
\begin_inset Formula
\[
a.\left(u,w\right)+b.\left(v,w\right)=\left(a.u,a.w\right)+\left(b.v,b.w\right)=\left(au+bv,aw+bw\right)\ne\left(au+bv,w\right)
\]
\end_inset
The tensor product
\begin_inset Formula $\otimes$
\end_inset
is not the Cartesian product
\begin_inset Formula $\times$
\end_inset
.
There is a way to construct the tensor product from the Cartesian product,
this is developed next.
\end_layout
\begin_layout Subsubsection*
Tensor products as equivalence
\end_layout
\begin_layout Standard
The tensor product can be constructed from the Cartesian product by declaring
an equivalence.
From the multi-linearity property above, it's clear that we wish to say
that
\begin_inset Formula $au\times w$
\end_inset
is the same thing as
\begin_inset Formula $u\times aw$
\end_inset
.
That is, we already have defined the tensor product so that
\begin_inset Formula $au\otimes w=u\otimes aw$
\end_inset
as strict equality; yet this is patently false for ordinary ordered pairs.
\end_layout
\begin_layout Standard
The procedure to rectify this situation is to introduce a new notion of
equivalence.
Using the symbol
\begin_inset Formula $\sim$
\end_inset
to denote
\begin_inset Quotes eld
\end_inset
the same as
\begin_inset Quotes erd
\end_inset
, one writes
\begin_inset Formula $au\times w\sim u\times aw$
\end_inset
.
The usual laws of algebra should apply, so subtraction can be used to bring
everything over to one side:
\begin_inset Formula $au\times w-u\times aw\sim0$
\end_inset
.
That is, the difference of these two ordered pairs is the
\begin_inset Quotes eld
\end_inset
same as
\begin_inset Quotes erd
\end_inset
zero.
Switching notation for ordered pairs, one may write
\begin_inset Formula $\left(au,w\right)-\left(u,aw\right)\sim0$
\end_inset
.
The algebra is meant to behave
\begin_inset Quotes eld
\end_inset
as expected
\begin_inset Quotes erd
\end_inset
, and so
\end_layout
\begin_layout Standard
\begin_inset Formula
\[
\left(au,w\right)-\left(u,aw\right)=\left(au-u,w-aw\right)=\left(\left(a-1\right)u,\left(1-a\right)w\right)\sim0
\]
\end_inset
But
\begin_inset Formula $a-1$
\end_inset
is just a number
\begin_inset Formula $c=a-1$
\end_inset
, so the above says
\begin_inset Formula
\[
\left(cu,-cw\right)\sim0
\]
\end_inset
for all numbers
\begin_inset Formula $c$
\end_inset
.
Such ordered pairs are
\begin_inset Quotes eld
\end_inset
equivalent
\begin_inset Quotes erd
\end_inset
to zero.
\end_layout
\begin_layout Standard
The formal way to write the tensor product is as a quotient over this equivalenc
e.
This is conventionally written as a quotient
\begin_inset Formula
\[
U\otimes W=U\times W/\sim
\]
\end_inset
which is meant to denote the set of all equivalent ordered pairs.
In set notation,
\begin_inset Formula
\[
u\otimes w=\left\{ \mbox{all pairs }\left(s,t\right)\mbox{ such that }\left(s,t\right)=\left(u,w\right)+\left(cu,-cw\right)\mbox{ for some const }c.\right\}
\]
\end_inset
This is to be read
\begin_inset Quotes eld
\end_inset
the set of all pairs to which we have added the equivalent of zero
\begin_inset Quotes erd
\end_inset
.
Formally, the set on the right is called
\begin_inset Quotes eld
\end_inset
coset
\begin_inset Quotes erd
\end_inset
.
By treating all members of this coset as
\begin_inset Quotes eld
\end_inset
equivalent
\begin_inset Quotes erd
\end_inset
, we
\begin_inset Quotes eld
\end_inset
forget
\begin_inset Quotes erd
\end_inset
their identity and uniqueness (stemming from their origins as Cartesian
pairs), and treat them as being all the same.
Choosing any one exemplar from the coset will do; it is a form of
\begin_inset Quotes eld
\end_inset
forgetting
\begin_inset Quotes erd
\end_inset
of differences, or an
\begin_inset Quotes eld
\end_inset
erasure
\begin_inset Quotes erd
\end_inset
of origins.
It is a denial of identity politics, it is a certain racial homogenization,
it is a democratic notion that
\begin_inset Quotes eld
\end_inset
all are created equal
\begin_inset Quotes erd
\end_inset
.
\end_layout
\begin_layout Standard
In a conventional exposition, there would be a verification to make sure
that the result after quotienting is consistent: specifically, that the
cosets are disjoint, that no exemplar ever belongs to two different cosets,
and that the resulting mapping is one-to-one and onto – thus, an isomorphism.
This can be taken for granted here; it needs verification only after the
more abstract definition is given.
\end_layout
\begin_layout Subsubsection*
Tensor products as concatenation
\end_layout
\begin_layout Standard
The above was needlessly complicated.
There is a wildly simpler way of saying the same thing, which, remarkably,
arrives at the same place.
Let
\begin_inset Formula $F\left(x,y,z\right)$
\end_inset
be a function of variables
\begin_inset Formula $x,y,z$
\end_inset
which are understood to be ordinal numbers, that is, integers.
Without any further restrictions (for the moment, as we ignore change-of-basis,
for now), the function
\begin_inset Formula $F\left(x,y,z\right)$
\end_inset
is a tensor, and the
\begin_inset Formula $x,y,z$
\end_inset
are the tensor indexes.
Given another function aka tensor
\begin_inset Formula $G\left(s,t\right)$
\end_inset
, the tensor product is simple the tensor
\begin_inset Formula
\[
T\left(x,y,z,s,t\right)=F\left(x,y,z\right)G\left(s,t\right)
\]
\end_inset
where the product is simply the scalar product (for whatever field or ring
that
\begin_inset Formula $F$
\end_inset
and
\begin_inset Formula $G$
\end_inset
are valued in).
This seems almost trivial in it's definition – how hard can a scalar product
be? Its just the ordinary multiplication of numbers.
This seems effectively trivial, but it hides a bit of trickery: there's
a sleight-of-hand.
The tensor on the left-hand side is written as
\begin_inset Formula $T\left(x,y,z,s,t\right)$
\end_inset
and not as
\begin_inset Formula $T\left(\left(x,y,z\right),\left(s,t\right)\right)$
\end_inset
.
If we look at
\begin_inset Formula $\left(x,y,z\right)$
\end_inset
and
\begin_inset Formula $\left(s,t\right)$
\end_inset
as two ordered lists, then
\begin_inset Formula $\left(x,y,z,s,t\right)$
\end_inset
is the concatenation of those lists.
It is NOT the Cartesian product of them!
\end_layout
\begin_layout Standard
As always, let's belabor the painfully obvious:
\begin_inset Formula
\[
\left(x,y,z,s,t\right)\ne\left(x,y,z\right)\times\left(s,t\right)=\left(\left(x,y,z\right),\left(s,t\right)\right)
\]
\end_inset
The left side is a list.
The right side is a list of lists.
List concatenation
\begin_inset Quotes eld
\end_inset
erases
\begin_inset Quotes erd
\end_inset
the nested parenthesis that appear on the right-hand-side.
It
\begin_inset Quotes eld
\end_inset
forgets
\begin_inset Quotes erd
\end_inset
where the indexes came from.
Indeed, it might have been the case that the list was the result of concatenati
ng
\begin_inset Formula $\left(x,y\right)$
\end_inset
with
\begin_inset Formula $\left(z,s,t\right)$
\end_inset
– we simply don't know, we forgot this bit of information.
We
\begin_inset Quotes eld
\end_inset
erased
\begin_inset Quotes erd
\end_inset
it, the origins have been
\begin_inset Quotes eld
\end_inset
democratized
\begin_inset Quotes erd
\end_inset
: we only have a list
\begin_inset Formula $\left(x,y,z,s,t\right)$
\end_inset
but know not whence it came.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
The formal term for this property is that the product is
\begin_inset Quotes eld
\end_inset
associative
\begin_inset Quotes erd
\end_inset
: re-arranging the parenthesis will not change the result.
\end_layout
\end_inset
\end_layout
\begin_layout Standard
To illustrate the correspondence, list concatenation can also be written
with an equivalence principle.
Using the symbol
\begin_inset Formula $\sim$
\end_inset
to denote
\begin_inset Quotes eld
\end_inset
the same as
\begin_inset Quotes erd
\end_inset
, one writes
\begin_inset Formula
\[
\left(x,y,z\right)\times\left(s,t\right)\sim\left(x,y\right)\times\left(z,s,t\right)
\]
\end_inset
Using the equivalence
\begin_inset Formula $\sim$
\end_inset
to write a quotient space of concatenated products requires the development
of some additional concepts.
This is partly undertaken in the next section.
\end_layout
\begin_layout Standard
This works for conventional tensors because
\begin_inset Formula $F,G$
\end_inset
and
\begin_inset Formula $T$
\end_inset
are considered to be maps to
\begin_inset Quotes eld
\end_inset
numbers
\begin_inset Quotes erd
\end_inset
, elements of a field or maybe a ring.
The multiplication of numbers (members of a field or ring) is also
\begin_inset Quotes eld
\end_inset
forgetful
\begin_inset Quotes erd
\end_inset
: when we write
\begin_inset Quotes eld
\end_inset
42
\begin_inset Quotes erd
\end_inset
, we don't know if it was constructed from the product of 6 and 7, or from
the product of 2 and 21.
It could have been either of these, or yet more.
To put it differently, if
\begin_inset Formula $F\left(a,b,c\right)=6$
\end_inset
and
\begin_inset Formula $G\left(d,e\right)=7$
\end_inset
for fixed constants
\begin_inset Formula $a,b,c,d,e$
\end_inset
, and we construct the product
\begin_inset Formula $T\left(a,b,c,d,e\right)=F\left(a,b,c\right)G\left(d,e\right)$
\end_inset
, we no longer know where the 42 came from.
It might have come from
\begin_inset Formula $T\left(a,b,c,d,e\right)=H\left(a,b\right)K\left(c,d,e\right)$
\end_inset
where
\begin_inset Formula $H\left(a,b\right)=2$
\end_inset
and
\begin_inset Formula $K\left(c,d,e\right)=21$
\end_inset
.
The forgetfulness of list concatenation goes hand-in-hand with the forgetfulnes
s of multiplication in fields and rings.
Tensors work because the exploit both of these properties.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
This is effectively what the abstract definition of a tensor category (or
monoidal category) in category theory is saying.
This text mostly tries to avoid category theory, as there is a heavy conceptual
overhead required to learn category theory, and that complexity conceals,
hides the points we are trying to make explicit, here.
That said, some category theory is unavoidable.
\end_layout
\end_inset
\end_layout
\begin_layout Subsubsection*
Cartesian products and lambda calculus
\end_layout
\begin_layout Standard
The simply-typed lambda calculus is famously the internal language of Cartesian-
closed categories.
Let's take a moment to unpack that statement.
The treatment here is informal; our goal is not to teach category theory.
Consider a class
\begin_inset Formula $S$
\end_inset
of symbols.
We call it a class because it could be a finite set, or an infinite set;
it may be uncountable, or it may be so horridly structured that it cannot
be expressed as a set.
For the purposes of comp sci, things are always finite, so calling it a
class
\begin_inset Formula $S$
\end_inset
is merely conventional.
The elements of
\begin_inset Formula $S$
\end_inset
are
\begin_inset Quotes erd
\end_inset
symbols
\begin_inset Quotes erd
\end_inset
because, for the purposes here, symbols, and the connotation that they
\begin_inset Quotes eld
\end_inset
stand for something
\begin_inset Quotes erd
\end_inset
, is an important property.
\end_layout
\begin_layout Standard
The Cartesian product of elements of
\begin_inset Formula $S$
\end_inset
is an ordered list: we already wrote above that
\begin_inset Formula $a\times b\times c=\left(a,b,c\right)$
\end_inset
is two different ways of writing the same thing.
It is convenient to drop the commas, and write
\begin_inset Formula $\left(a,b,c\right)=\left(a\;b\;c\right)$
\end_inset
as is standard in Lisp-dialect programming languages.
Of course, one can likewise construct lists-of-lists, and so on.
Consider now the collection (class) of all such nested lists-of-lists-of-lists...
A typical exemplar might look like
\begin_inset Formula
\[
\left(a\;b\;\left(c\;d\right)\;e\;\left(f\;g\;\left(h\left(j\left(k\left(m\right)\right)\right)\right)\right)\right)
\]
\end_inset
whence the acronym LISP -
\begin_inset Quotes eld
\end_inset
Lots of InsidiouS Parenthesis
\begin_inset Quotes erd
\end_inset
comes from.
Here, the letters were taken to be symbols drawn from the class
\begin_inset Formula $S$
\end_inset
.
It is, however, convenient to introduce the notion of variables; for these,
we write
\begin_inset Formula $x,y,z,\cdots$
\end_inset
as always, by convention.
One can then consider the class of lists with embedded variables in them.
OK, but things really get interesting when one then considers replacing
variables by values.
To do this, the special notation of
\begin_inset Formula $\lambda$
\end_inset
is introduced, and one conventionally writes
\begin_inset Formula
\[
\left(\lambda x.A\right)B\to A\left[x:=B\right]
\]
\end_inset
where both
\begin_inset Formula $A$
\end_inset
and
\begin_inset Formula $B$
\end_inset
are lists (possibly containing variables), and the expression on the left-hand
side of the arrow is a lambda-binding of the variable
\begin_inset Formula $x$
\end_inset
such that any occurrence of the variable
\begin_inset Formula $x$
\end_inset
in the list
\begin_inset Formula $A$
\end_inset
is to be replaced by the list
\begin_inset Formula $B$
\end_inset
.
By convention, that is also what the expression on the right hand side
of the arrow is supposed to mean.
The arrow itself is meant to denote beta-reduction, the actual act of plugging
in or substitution of the variable
\begin_inset Formula $x$
\end_inset
by the thing
\begin_inset Formula $B$
\end_inset
that is to be plugged in.
\end_layout
\begin_layout Standard
Beta reduction takes actual effort and work, it is a computational problem.
Done by hand, it requires transcribing symbols on sheets of paper.
Done by computer, it requires copying and moving bytes.
Vastly complex schemes have been developed to perform beta reduction rapidly.
From the comp-sci perspective, it is a highly non-trivial process, no matter
how obvious it may seem from the short expression above.
\end_layout
\begin_layout Standard
That's it.
That's the effective definition of simply-typed lambda calculus.
It is
\begin_inset Quotes eld
\end_inset
simply typed
\begin_inset Quotes erd
\end_inset
because all members of the class
\begin_inset Formula $S$
\end_inset
are taken to be of the same type.
There were only four ingredients in the construction:
\end_layout
\begin_layout Itemize
The Cartesian product, which allows the construction of lists (and of lists
of lists ...).
\end_layout
\begin_layout Itemize
The use of variables as
\begin_inset Quotes eld
\end_inset
placeholders
\begin_inset Quotes erd
\end_inset
.
\end_layout
\begin_layout Itemize
The use of a special symbol
\begin_inset Formula $\lambda$
\end_inset
which is used to call out or bind or name a specific variable.
\end_layout
\begin_layout Itemize
The performance of substitution, named
\begin_inset Quotes eld
\end_inset
beta-reduction
\begin_inset Quotes erd
\end_inset
, for historical reasons.
\end_layout
\begin_layout Standard
There is, of course, much more that can be said about lambda calculus; this
hardly scratches the surface.
But it does show the centrality of the Cartesian product to the construction.
\end_layout
\begin_layout Standard
It also helps highlight just how different list concatenation is from the
Cartesian product of lists.
This is a source of tremendous confusion for students of engineering and
science, and so (as always) it is worth belaboring here.
By convention, one is introduced to the notion of
\begin_inset Formula $\mathbb{R}^{n}$
\end_inset
as the
\begin_inset Formula $n$
\end_inset
-dimensional Cartesian space.
It is a coordinate space – the points of Cartesian space are labeled by
\begin_inset Formula $n$
\end_inset
coordinates, taken to be real numbers,
\emph on
i.e.
\emph default
taken as elements of
\begin_inset Formula $\mathbb{R}$
\end_inset
.
By convention the Cartesian product of such spaces is
\begin_inset Formula $\mathbb{R}^{m}\times\mathbb{R}^{n}\cong\mathbb{R}^{m+n}$
\end_inset
where the
\begin_inset Formula $\cong$
\end_inset
symbol denotes isomorphism.
By convention, this works as list concatenation: if one has spatial coordinates
\begin_inset Formula $\left(x,y,z\right)$
\end_inset
in the 3D space
\begin_inset Formula $\mathbb{R}^{3}$
\end_inset
and the spatial coordinates
\begin_inset Formula $\left(s,t\right)\in\mathbb{R}^{2}$
\end_inset
, then,
\begin_inset Quotes eld
\end_inset
of course
\begin_inset Quotes erd
\end_inset
,
\begin_inset Formula $\left(x,y,z,s,t\right)\in\mathbb{R}^{5}=\mathbb{R}\times\mathbb{R}\times\mathbb{R}\times\mathbb{R}\times\mathbb{R}$
\end_inset
.
Notationally, this is a bit unfortunate for our purposes, as it seems to
be a form of list concatenation.
Even worse, the right hand side is not a tensor product! Are you confused
yet? Posed as a riddle, the solution to the riddle is to realize that when
one writes a tensor
\begin_inset Formula $T_{ijklm}$
\end_inset
of five indices, these indices are ordinal numbers: integers.
They are not real-number-valued coordinates of Euclidean space.
The value of
\begin_inset Formula $T$
\end_inset
might be real, but the indexes are not.
The abundance of notations - parenthesis of various shapes, and commas
and what-not, can be a bit of a trap.
\end_layout
\begin_layout Subsubsection*
Tensor product, in general
\end_layout
\begin_layout Standard
We now have enough machinery developed to allow a general definition of
the tensor product.
Lets return to the form
\begin_inset Formula
\[
T\left(x,y,z,s,t\right)=F\left(x,y,z\right)G\left(s,t\right)
\]
\end_inset
as a simple product of
\begin_inset Formula $F\left(x,y,z\right)$
\end_inset
and
\begin_inset Formula $G\left(s,t\right)$
\end_inset
.
This time, we allow
\begin_inset Formula $F$
\end_inset
and
\begin_inset Formula $G$
\end_inset
to be
\begin_inset Quotes eld
\end_inset
anything with a forgetful product
\begin_inset Quotes erd
\end_inset
– not numbers, but anything which can be
\begin_inset Quotes eld
\end_inset
multiplied
\begin_inset Quotes erd
\end_inset
together, in some forgetful way, so that the origin of the factors is no
longer identifiable.
We had been previously vague as to whether the
\begin_inset Formula $x,y,z,s,t$
\end_inset
were variables or constants; we may proceed with this vagueness, except
that now we generalize them not to be ordinals, but to be members of some
class
\begin_inset Formula $S$
\end_inset
.
The ordinal property of the indexes is not relevant, here.
\end_layout
\begin_layout Standard
Replacing numbers by things that can be forgetfully multiplied discards
the addition of tensors.
This, however, is an important property that we want to maintain.
This can be done by going
\begin_inset Quotes eld
\end_inset
meta-mathematical
\begin_inset Quotes erd
\end_inset
in the conventional sense, and using the disjunctive-or to combine generalized
tensors.
The disjunctive-or is a
\begin_inset Quotes eld
\end_inset
menu choice
\begin_inset Quotes erd
\end_inset
: it says
\begin_inset Quotes eld
\end_inset
pick this or pick that, pick at least one, but don't pick both
\begin_inset Quotes erd
\end_inset
.
If we have generalized tensors
\begin_inset Formula $T$
\end_inset
and
\begin_inset Formula $U$
\end_inset
, we can no longer write
\begin_inset Formula $T+U$
\end_inset
because there is no addition, but we can still combine them with disjunctive
choice: I can present you with
\begin_inset Formula $T\vee U$
\end_inset
and demand that you pick either
\begin_inset Formula $T$
\end_inset
or
\begin_inset Formula $U$
\end_inset
.
By convention, the disjunctive-or is denoted with
\begin_inset Formula $\vee$
\end_inset
.
\end_layout
\begin_layout Standard
One can still use the
\begin_inset Formula $\otimes$
\end_inset
symbol to write the tensor product, or one can omit it entirely, as was
done above, when we wrote
\begin_inset Formula $T=FG$
\end_inset
.
It is often useful keep a tensor product symbol, but, as we've generalized,
it's conventional to use a slightly different symbol: the ampersand
\begin_inset Formula $\&$
\end_inset
, and so write
\begin_inset Formula $T=F\&G$
\end_inset
.
We now have two symbols:
\begin_inset Formula $\&$
\end_inset
and
\begin_inset Formula $\vee$
\end_inset
and can ask what the algebra of these symbols is.
Note very carefully that it is NOT the Boolean algebra.
We have one distributive property, but not the other.
So,
\begin_inset Formula
\[
\left(u\vee v\right)\&w=\left(u\&w\right)\vee\left(v\&w\right)
\]
\end_inset
is the alternate (generalized) form of the conventional distributive property
\end_layout
\begin_layout Standard
\begin_inset Formula
\[
\left(u+v\right)\otimes w=u\otimes w+v\otimes w
\]
\end_inset
However, the other one, that would have made things Boolean, does not hold:
\begin_inset Formula
\[
\left(u\&v\right)\vee w\ne\left(u\&w\right)\vee\left(v\&w\right)
\]
\end_inset
This is hardly a surprise, since it is also the case that
\begin_inset Formula
\[
\left(u\otimes v\right)+w\ne u\otimes w+v\otimes w
\]
\end_inset
which is once again obvious and trivial: tensor products do not form a Boolean
algebra.
\end_layout
\begin_layout Subsubsection*
Tensor logic
\end_layout
\begin_layout Standard
To round out the algebraic constructions for the tensor product, we can
do the same thing that was done to obtain (simply-typed) lambda calculus:
\end_layout
\begin_layout Itemize
Define the algebra of
\begin_inset Formula $\&$
\end_inset
and
\begin_inset Formula $\vee$
\end_inset
over a class of symbols
\begin_inset Formula $S$
\end_inset
.
\end_layout
\begin_layout Itemize
Introduce variables as
\begin_inset Quotes eld
\end_inset
placeholders
\begin_inset Quotes erd
\end_inset
.
\end_layout
\begin_layout Itemize
Employ the symbol
\begin_inset Formula $\lambda$
\end_inset
to bind or call out a specific variable.
\end_layout
\begin_layout Itemize
Enable beta-reduction.
\end_layout
\begin_layout Standard
This glosses over the need for alpha-conversion and possibly eta-reduction.
I will call this algebraic system
\begin_inset Quotes eld
\end_inset
tensor logic
\begin_inset Quotes erd
\end_inset
, as I am not aware of any conventional name for it.
It is similar to
\begin_inset Quotes eld
\end_inset
linear logic
\begin_inset Quotes erd
\end_inset
, but is not the same, as it is missing an important ingredient, that of
conjugation.
\end_layout
\begin_layout Subsection*
Inner product
\end_layout
\begin_layout Standard
Tensors become interesting in engineering and science only after the addition
of one more ingredient: the inner product.
The inner product allows tensors to be combined by
\begin_inset Quotes eld
\end_inset
contracting tensor indices
\begin_inset Quotes erd
\end_inset
.
For example, given tensors
\begin_inset Formula $A_{ijk}$
\end_inset
and
\begin_inset Formula $B_{lm}$
\end_inset
, one might consider the contraction
\begin_inset Formula
\[
C_{ijm}=A_{ijk}B_{km}=\sum_{k}A_{ijk}B_{km}
\]
\end_inset
where the middle expression uses the so-called
\begin_inset Quotes eld
\end_inset
Einstein convention
\begin_inset Quotes erd
\end_inset
of summing repeated indexes, whereas on the right the sum is explicit.
For the moment, the distinction between covariant and contra-variant indices
will be ignored; as any discussion of change-of-basis has been ignored,
it remains appropriate to also ignore issues of contra/covariance.
\end_layout
\begin_layout Standard
The prototypical inner product is that of two vectors, say
\begin_inset Formula $\vec{a}=\left[a_{1},a_{2},\cdots,a_{n}\right]$
\end_inset
and
\begin_inset Formula $\vec{b}=\left[b_{1},b_{2},\cdots,b_{n}\right]$
\end_inset
.
One writes:
\begin_inset Formula
\[
i\left(\vec{a},\vec{b}\right)=\vec{a}\cdot\vec{b}=a_{1}b_{1}+a_{2}b_{2}+\cdots+a_{n}b_{n}
\]
\end_inset
For the general case, one needs only to convert notation:
\begin_inset Formula
\[
i\left(\vec{a},\vec{b}\right)=a_{1}\&b_{1}\vee a_{2}\&b_{2}\vee\cdots\vee a_{n}\&b_{n}
\]
\end_inset
which clearly has the same algebraic form despite a vastly different interpretat
ion of the symbols.
\end_layout
\begin_layout Subsubsection*
Properties of the inner product
\end_layout
\begin_layout Standard
Inner products are compatible with tensors in that they are linear.
For ordinary vectors, this is expressed as
\begin_inset Formula
\[
i\left(\vec{a}+\vec{b},\vec{c}\right)=i\left(\vec{a},\vec{c}\right)+i\left(\vec{b},\vec{c}\right)
\]
\end_inset
It is apparent that this property of linearity is consistent with the algebraic
properties of
\begin_inset Formula $\&$
\end_inset
and
\begin_inset Formula $\vee$
\end_inset
, in that the distributive property of
\begin_inset Formula $\&$
\end_inset
over
\begin_inset Formula $\vee$
\end_inset
is sufficient to guarantee linearity:
\begin_inset Formula
\[
\left(\left(a_{1}\vee b_{1}\right)\&c_{1}\right)\vee\left(\left(a_{2}\vee b_{2}\right)\&c_{2}\right)\vee\cdots=\left(a_{1}\&c_{1}\right)\vee\left(b_{1}\&c_{1}\right)\vee\left(a_{2}\&c_{2}\right)\vee\left(b_{2}\&c_{2}\right)\vee\cdots
\]
\end_inset
\end_layout
\begin_layout Standard
Inner products over a field or a ring are taken to obey several additional
properties: they are typically conjugate or symmetric; they are typically
linear in multiplication by a scalar, and they are positive definite.
These properties are discarded here.
There is no conjugation or symmetry, as we have an express interest in
the non-symmetric, non-conjugate case, as needed for linguistics.
There is no natural scalar multiplication in our generalized definition
of tensors above; it makes no sense to suddenly require one.
Our generalized notion of tensors also lacks a partial order
\begin_inset Formula $\ge$
\end_inset
, and so there is no way to express positive definiteness.
There are cases where partial orders or pre-orders may be available; for
example, string-rewriting systems (which include lambda calculus) do have
a notion of
\begin_inset Quotes eld
\end_inset
lexicographic order
\begin_inset Quotes erd
\end_inset
, and so allow ideas like
\begin_inset Quotes eld
\end_inset
monoidal preorders
\begin_inset Quotes erd
\end_inset
to be defined.
These assumptions are not needed or relevant here.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
That is, we are appealing to the existence of an inner product as a
\begin_inset Quotes eld
\end_inset
universal property
\begin_inset Quotes erd
\end_inset
of the tensor product.
The universal property is the mechanism by which all of the excess baggage
of symmetry and partial orders can be discarded.
\end_layout
\end_inset
Note that discarding all of these notions means that many derived properties,
such as norms, homogeneity, triangle inequalities, polarization identities
and so on all fall by the wayside.
\end_layout
\begin_layout Subsubsection*
Inner product as connection
\end_layout
\begin_layout Standard
Diagrammatically, the contraction of tensor indices was depicted earlier
in this series with a puzzle-shaped diagram.
This is repeated below, with slightly different labeling.
\end_layout
\begin_layout Standard
\align center
\begin_inset Graphics
filename graphics/puzzle-vector.eps
lyxscale 60
width 45col%
\end_inset
\end_layout
\begin_layout Standard
The diagram is slightly awkward here; the upper row is meant to depict the
two vectors, with naked, uncontracted indexes.
The lower part depicts a scalar, with Einstein-convention repeated indexes
that are summed over.
The two different mating puzzle-tab shapes hint at a hidden contra/covariance.
They are also meant to indicate compatible types.
That is to say, the type of
\begin_inset Formula $a_{j}$
\end_inset
is compatible with the type of
\begin_inset Formula $b_{k}$
\end_inset
, and so can be multiplied: so, they might both be numbers, or both be something
else, as long as they can compatibly be multiplied with each-other using
the product
\begin_inset Formula $\&$
\end_inset
between them.
The next chapter will return to types; the tensors defined here remain
simply-typed.
The point of the diagram is to re-assert the claim that the inner product
is just a form of
\begin_inset Quotes eld
\end_inset
connecting things together
\begin_inset Quotes erd
\end_inset
, this time made notationally explicit.
\end_layout
\begin_layout Subsubsection*
Beta reduction as inner product
\end_layout
\begin_layout Standard
Earlier chapters claimed that beta-reduction was a form of connecting things
together.
How can this be? To recap the argument so far: when one plugs in 42 for
\begin_inset Formula $x$
\end_inset
in
\begin_inset Formula $f\left(x\right)$
\end_inset
to get
\begin_inset Formula $f\left(42\right)$
\end_inset
, one is
\begin_inset Quotes eld
\end_inset
connecting
\begin_inset Quotes erd
\end_inset
42 to
\begin_inset Formula $f\left(x\right)$
\end_inset
.
This is intuitively obvious, and one can even intuit how the jigsaw-puzzle
diagram captures this idea.
Yet it is not (yet) obviously an inner product.
\end_layout
\begin_layout Standard
To demonstrate that it is, one may appeal to the most basic type theory
to elucidate.
Here, 42 is an exemplar of the set of
\begin_inset Quotes eld
\end_inset
integers
\begin_inset Quotes erd
\end_inset
, and
\begin_inset Formula $f\left(x\right)$
\end_inset
is a
\begin_inset Quotes eld
\end_inset
function that takes integers
\begin_inset Quotes erd
\end_inset
.
They can mate together because the types are compatible.
We can write an integer as
\begin_inset Formula
\[
1\vee2\vee3\vee\cdots
\]
\end_inset
which is a menu choice - the disjoint union, again.
It says that
\begin_inset Quotes eld
\end_inset
you should choose either 1 or choose 2 or choose 3 ...
but choose at least one, and chose no more than one
\begin_inset Quotes erd
\end_inset
.
Likewise, the result of plugging in is
\begin_inset Formula
\[
f\left(1\right)\vee f\left(2\right)\vee f\left(3\right)\vee\cdots
\]
\end_inset
This begins to look like an inner product; the resemblance can be completed
by writing it as
\begin_inset Formula
\[
f_{1}\&1\,\vee\,f_{2}\&2\,\vee\,f_{3}\&3\,\vee\cdots
\]
\end_inset
where, of course,
\begin_inset Formula $f_{1}\&1=f\left(1\right)$
\end_inset
is how one writes
\begin_inset Quotes eld
\end_inset
the value of
\begin_inset Formula $f$
\end_inset
at one can be obtained by mating together the value one, as a jigsaw-puzzle-tab
, with
\begin_inset Formula $f_{1}$
\end_inset
as the corresponding matching jigsaw-puzzle mate
\begin_inset Quotes erd
\end_inset
.
With the revised notation, its now clear that beta-reduction is a form
of the inner product.
\end_layout
\begin_layout Standard
To write it this way, there was a slight abuse of the notation
\begin_inset Formula $\&$
\end_inset
.
Previously, it was defined as the
\begin_inset Quotes eld
\end_inset
product of two things of the same type
\begin_inset Quotes erd
\end_inset
; yet here it is used to denote
\begin_inset Quotes eld
\end_inset
the mating of matching types
\begin_inset Quotes erd
\end_inset
.
It is convenient to read it both ways; for the moment we sweep this under
the rug, along with the co/contravariance issue.
They are not entirely unrelated.
Later chapters will return to these topics.
\end_layout
\begin_layout Subsection*
Appendix/FAQ
\end_layout
\begin_layout Standard
A few related points and commonly-raised questions are addressed here.
\end_layout
\begin_layout Subsubsection*
Monoidal categories
\end_layout
\begin_layout Standard
The definitions above correspond with the conventional definition of tensor
products in monoidal categories; the goal has been not to invent something
new, but rather to change perspective.
Thus, the forgetfulness of the placement of parenthesis,
\emph on
viz.
\emph default
that
\begin_inset Formula $\left(a\left(b\,c\right)\right)\sim\left(\left(a\,b\right)c\right)$
\end_inset
is more commonly called the
\begin_inset Quotes eld
\end_inset
associative property of a binary operation
\begin_inset Quotes erd
\end_inset
.
The definition of the monoidal category elaborates on associativity: the
tensor product only needs to be associative
\begin_inset Quotes eld
\end_inset
up to isomorphism
\begin_inset Quotes erd
\end_inset
.
The isomorphism that does this is called the
\begin_inset Quotes eld
\end_inset
associator
\begin_inset Quotes erd
\end_inset
\begin_inset Formula $\alpha$
\end_inset
and it is a one-to-one, onto map
\begin_inset Formula $\alpha:A\otimes\left(B\otimes C\right)\mapsto\left(A\otimes B\right)\otimes C$
\end_inset
.
\end_layout
\begin_layout Standard
The category must contain also have a
\begin_inset Quotes eld
\end_inset
unit object
\begin_inset Quotes erd
\end_inset
or
\begin_inset Quotes eld
\end_inset
identity object
\begin_inset Quotes erd
\end_inset
\begin_inset Formula $I$
\end_inset
; multiplication by the unit, on either the left or the right, must preserve
the multiplied object,
\begin_inset Quotes eld
\end_inset
up to isomorphism
\begin_inset Quotes erd
\end_inset
.
These two isomorphisms are called the
\begin_inset Quotes eld
\end_inset
left and right unitors
\begin_inset Quotes erd
\end_inset
; for example, the right unitor is the one-to-one, onto map
\begin_inset Formula $\rho:A\otimes I\mapsto A$
\end_inset
.
\end_layout
\begin_layout Standard
With explicit left and right unitors, one must then verify several
\begin_inset Quotes eld
\end_inset
coherence conditions
\begin_inset Quotes erd
\end_inset
: there is a triangle diagram, which verifies that the re-arrangement of
parenthesis involving the identity object gives
\begin_inset Quotes eld
\end_inset
what is expected
\begin_inset Quotes erd
\end_inset
.
Adding the associator into the mix requires the verification of a pentagon-shap
ed diagram.
The Wikipedia article on monoidal categories provides an adequate summary
of the definition of a monoidal category.
Of course, much more can be said: there is a 350-page book on the topic
\begin_inset CommandInset citation
LatexCommand cite
key "Etingof2010"
literal "false"
\end_inset
.
\end_layout
\begin_layout Standard
Strict monoidal categories are those where the associator and the unitors
are identities; that is all that is called upon, in the above.
There is also the concept of a
\begin_inset Quotes eld
\end_inset
lax monoidal category
\begin_inset Quotes erd
\end_inset
, where the associativity properties are slightly weakened.
Some of the concepts discussed in this collection of chapters are properly
lax monoidal categories; no particular effort is made to call attention
to this, and it seems harmless, as every such lax category has a corresponding
equivalent strict category.
\end_layout
\begin_layout Standard
There are several important aspects of the definition of monoidal categories
that are relevant to the current text:
\end_layout
\begin_layout Itemize
The definition of a monoidal category makes no appeal to the concept of
\begin_inset Quotes eld
\end_inset
addition
\begin_inset Quotes erd
\end_inset
, or anything
\begin_inset Quotes eld
\end_inset
additive
\begin_inset Quotes erd
\end_inset
.
This is not required to create a monoidal category.
\end_layout
\begin_layout Itemize
Many tensor categories in mathematics are
\begin_inset Quotes eld
\end_inset
symmetric
\begin_inset Quotes erd
\end_inset
, in that they have a natural isomorphism
\begin_inset Formula $A\otimes B\cong B\otimes A$
\end_inset
.
This is manifestly
\emph on
not
\emph default
the case here; we are very much concerned with the case where such symmetry
is entirely lacking.
This is precisely why the concept of tensors can be applied to linguistics:
sentences are not palindromes.
\end_layout
\begin_layout Itemize
No mention is made of inner products.
The concept of a tensor category is unrelated to the concept of an inner
product.
\end_layout
\begin_layout Subsubsection*
Change of basis and isometries
\end_layout
\begin_layout Standard
Discarding the concept of a norm in the definition of the inner product
has serious consequences.
In particular, all conceptions of change-of-basis and isometries are thrown
out the window.
It's worth exploring this a bit.
\end_layout
\begin_layout Standard
Consider the conventional case of Euclidean space.
A change of basis involves multiplication by an orthonormal matrix
\begin_inset Formula $M$
\end_inset
having the property
\begin_inset Formula $M^{T}M=I$
\end_inset
so that
\begin_inset Formula $M\in SO(n)$
\end_inset
.
Then for some basis vector
\begin_inset Formula $\vec{e}_{k}$
\end_inset
, the transformed basis vector is
\begin_inset Formula $\vec{e}_{k}^{\prime}=M\vec{e}_{k}$
\end_inset
.
Writing out indexes, one has
\begin_inset Formula $\left[\vec{e}_{k}\right]_{j}=\delta_{kj}$
\end_inset
and of course
\begin_inset Formula $\left[M\right]_{ij}=M_{ij}$
\end_inset
so that
\begin_inset Formula $\left[\vec{e}_{k}^{\prime}\right]_{i}=\left[M\right]_{ij}\left[\vec{e}_{k}\right]_{j}=M_{ij}\delta_{jk}=M_{ik}$
\end_inset
.
What happens if instead, we only have
\begin_inset Formula $\&$
\end_inset
and
\begin_inset Formula $\vee$
\end_inset
as operators? Attempting to reproduce the above gives
\begin_inset Formula
\[
\left[\vec{e}_{k}^{\prime}\right]_{i}=M_{i1}\&\left[\vec{e}_{k}\right]_{1}\vee M_{i2}\&\left[\vec{e}_{k}\right]_{2}\vee M_{i3}\&\left[\vec{e}_{k}\right]_{3}\vee\cdots
\]
\end_inset
The construction on the right reads, as always
\begin_inset Quotes eld
\end_inset
choose
\begin_inset Formula $M_{i1}\&\left[\vec{e}_{k}\right]_{1}$
\end_inset
or choose
\begin_inset Formula $M_{i2}\&\left[\vec{e}_{k}\right]_{2}$
\end_inset
...
choose one and only one
\begin_inset Quotes erd
\end_inset
and so the item on the left, the symbol
\begin_inset Formula $\left[\vec{e}_{k}^{\prime}\right]_{i}$
\end_inset
is not some reduced thing in the same class as
\begin_inset Formula $\left[\vec{e}_{k}\right]_{j}$
\end_inset
but is an entirely different beast: its a list of choices, or rather, just
a name for a list of choices.
Of course, this can be made a bit more consistent, if one claims that
\begin_inset Formula $\left[\vec{e}_{k}\right]_{j}$
\end_inset
is nothing but a singleton, with the commandment
\begin_inset Quotes eld
\end_inset
here is exactly one thing, and one you choose one and only one thing
\begin_inset Quotes erd
\end_inset
.
Thus, here, a single change-of-basis merely creates an accretion or conglomerat
ion: some initial collection of
\begin_inset Formula $\vec{e}_{k}$
\end_inset
gets an extra
\begin_inset Formula $M$
\end_inset
stuck onto the side.
Connecting connectors cause things to stick to each-other; the result is
still typically some thing with connectors that are still exposed.
\end_layout
\begin_layout Standard
The inner product is also conventionally used to define a norm, and then
a metric, allowing concepts of a metric space to be layered on.
Here, we've discarded these notions.
There is one, though, that naturally remains: the ultrametric.
We can take, for example, the ultrametric to be a count, a cardinal number,
of the number of connectors that have been connected, or the distance between
two points, by counting the number of times the
\begin_inset Formula $\&$
\end_inset
symbol appears between them.
This is fine, and an interesting thing to do, but this count is naturally
a number (an integer), and we have not defined any kind of natural scalar
product between integers and the elements of the algebra.
One may exist; only that we've not defined one.
\end_layout
\begin_layout Standard
For example, when writing
\begin_inset Formula $M^{T}M=I$
\end_inset
, the thing on the right hand side is the identity, and so this equation
states that when two
\begin_inset Formula $M$
\end_inset
's are connected in some appropriate way, the identity results.
If the algebra was, for example, the algebra of first-order logic, then
the associated ultrametric might be the number of steps required to prove
something, or the number of rewriting steps needed to convert one expression
into another.
Performing a sequence of operations
\emph on
e.g
\emph default
.
applying a sequence of inference rules in natural deduction, and then reversing
them, can be interpreted as some transformation
\begin_inset Formula $M$
\end_inset
and it's inverse.
There does not seem top be any particular insight here.
One might ask for the shortest proof: the proof with the smallest number
of steps from here to there, and take this as the (ultra-)metric on the
space of proofs.
This is interesting, but lies outside the immediate need for building up
machinery of knowledge representation.
\end_layout
\begin_layout Standard
\begin_inset CommandInset bibtex
LatexCommand bibtex
btprint "btPrintCited"
bibfiles "lang"
options "plain"
\end_inset
\end_layout
\end_body
\end_document