Chapter 1: Brownian Forms
Form arithmetic
Form algebra
Isomorphic twice to Boolean logic
Normal forms
Complete deduction
Incomplete re-entrance
1A . Form Arithmetic
Let empty space on a page be called a form:
Let us be able to mark such a space by placing brackets in it:
[ ]
Let the first such form be called void, and the second be called
mark.
For any forms, let us be able to make these new forms:
Bracket: [
x ]
Juxtaposition:
x y
The brackets distinguish only inside from out, not left from
right; so juxtaposition is commutative:
x y =
y x
- where “=” means “is confused
with”.
Let two marks juxtaposed denote the same mark:
[ ] [ ] = [
]
Call this the Law of Calling:
To call twice is to
call.
Let a bracket within a bracket denote crossing a boundary twice,
and hence not at all:
[ [ ] ] =
Call this the Law of
Crossing:
To cross twice is not to
cross.
Let there be a ‘void mark’, or ‘parenthesis’, or ‘doublecross’,
defined as:
( x ) = [ [ x ] ]
= x
With the double-cross
(x), we can say that juxtaposition is
associative:
x(yz)
= (xy)z
To avoid confusing empty spaces on the page, let us use these
symbols for void and mark:
0
= ()
= [[]] =
1
= []
That implies these tables for bracket and juxtaposition:
x 0 1
y
-|------------------
0 | 0 1
|
1 | 1 1
[x] | 1 0
Define the operation ‘rejuxtaposition’:
[ [x] [y] ]
It has this table:
x 0 1
y -|------------------
0 | 0 0
|
1 | 0 1
This is the Form Arithmetic of G. Spencer-Brown, in his “Laws of
Form”.
Exercises for the student:
Prove that any form made from only doublecross, void and
juxtaposition equals void.
Prove Spencer-Brown’s
Arithmetic Theorem:
Any form made from void,
bracket and juxtaposition equals mark or void.
1B. Form Algebra
These are the arithmetic
axioms for brackets:
Calling: [] []
= []
Crossing: [[]] =
Exercise
for the student:
Prove the validity of
these bracket axioms:
Position: [[x]x] =
Transposition: [[x][y]]
z = [[xz][yz]]
Exercises for the student:
From the bracket axioms,
prove these identities:
Doublecross: [[a]] = a
Generation: [ab] b = [a] b
Attractor: []
a = []
Occultation: [[a]b]a = a
Recall: a
a = a
Extension: [[a][b]]
[[a]b] = a
Echelon: [[[a]b]c] = [ac]
[[b]c]
Retransposition:
[ax][bx]
= [
[[a][b]] x ]
General
Retransposition:
[a1x][a2x]…[anx]
= [
[[a1][a2]…[an]] x ]
Crosstransposition:
[ax]
[b[x]] = [ [[a]x]
[[b][x]] ]
1C. Isomorphic twice to
Boolean logic
Consider these tables for Boolean
logic, where T means ‘true’, F means ‘false’, ~ means ‘not’, & means ‘and’,
and V means ‘or’;
V x F T
y -|------------------
F | F T
|
T | T T
&
x F T
y
-|------------------
F | F F
|
T | F T
~x | T F
Note the similarity to the form tables
previously. In fact these systems are isomorphic twice:
(
[[]], [], [x], xy, [[x][y]]
) is isomorphic to:
(
F, T, ~x, xVy, x&y ) ,
and to:
(
T, F, ~x, x&y, xVy )
Boolean logic is isomorphic to itself.
Its automorphism group is S2; the symmetries of two objects.
1D. Normal forms
Recall Echelon, General
Retransposition and Crosstransposition:
Echelon: [[[a]b]c] = [ac] [[b]c]
General
Retransposition: [a1x][a2x]…[anx] = [
[[a1][a2]…[an]] x ]
Crosstransposition: [ax] [b[x]] = [ [[a]x]
[[b][x]] ]
These results imply a normal form for
all bracket expression, in five steps:
Step 1: Any bracket expression F is
provably equal to one no more than two brackets deep.
Proof: use Echelon enough times.
Step 2: Any bracket expression,
containing variable x, is provably equal to the bracket expression:
[ A x ] [ B [x] ]
C
where A, B and C do not contain the
variable x.
Proof: use step 1, then use General
Retransposition to collect all the x terms in one bracket, and all the [x]
terms in another bracket.
Step 3: Such a bracket expression
equals, by Crosstransposition:
[
[ [A] x ] [ [B] [x] ] ] C
Step 4: It therefore equals, by
Transposition:
[
[ [A] C x ] [ [B] C [x] ] ]
Step 5: Let F(x) denote that
expression, then substitution yields
F(0) = [A]C
F(1) = [B]C
Therefore
F(x) =
[ [ F(0) x ] [ F(1) [x] ]
]
Call this the standard normal form.
1E. Complete deduction
Complete Deduction Theorem:
If the bracket form equation
F = G
is necessarily true, then the equation
is provable from the bracket axioms.
Proof is by induction on the number of
variables.
Case
0. If F and G have no variables,
then the equation F=G is a bracket-arithmetic equation; these can be calculated
from the tables, which are a consequence of the bracket axioms. Therefore F=G
is provable from the axioms.
Case
N implies Case N+1. Suppose that all N-variable identities are provable
from the bracket axioms. Now suppose that F=G contains variable N+1; call it x.
Then these equations are provable:
F(0) = G(0)
F(1) = G(1)
since these have only N variables.
Therefore:
F(x)
= [ [ F(0) x ]
[ F(1) [x] ] ] by standard normal form
= [ [ G(0)
x ] [ G(1) [x] ] ] by the preceding equations
=
G(x) by
standard normal form
Case 0 holds; recurrence holds;
therefore the theorem is true, by induction.
Note that any proof thus constructed
will be equivalent to table look-up, as it will check all 2^n cases, for n =
number of variables; and thus take 2^n steps.
In complexity theory, finding exceptions is an NP-complete
problem.
1F. Incomplete re-entrance
Bracket forms are built of brackets
and juxtaposition of other bracket forms; a chain ultimately ending in the
void. Or does it? Could there be a form founded upon itself? Or even systems of
forms founded upon each other?
Consider the forms
A = [B]
B = [A]
This system, a ‘toggle’, has two
solutions:
A=0, B=1
A=1, B=0
Both make sense, but which is it?
Now consider a worse case; the form
L = [L]
L can equal neither 0 or 1.
Therefore Brownian bracket forms are
incomplete for re-entrance. To solve the equation, you need a third form.
No comments:
Post a Comment