Multiset arithmetic via trees

We introduce an alternative visual representation of pure msets as rooted (or roofed) trees as in combinatorics or computer science. This allows us to see the counting functions in a simple geometric way, and gives us a different view of the interesting new arithmetic supported by multisets. We illustrate this arithmetic with some concrete examples, and also introduce some useful shortcut notations that help us navigate in this new domain. Video Content Introductio Notation for rooted/roofed tree Multiplicity convention (left subindices Counting with trees Closed boxes/node Arithmetic with trees *********************** Here are the Insights into Mathematics Playlists: Elementary Mathematics (K-6) Explained: / playlistlist=PL8403C2F0C89B1333 Year 9 Maths: • Year9MathsAncient Mathematics: • Ancient MathematicsWild West Banking: • Wild West BankingSociology and Pure Mathematics: • Sociology and Pur...Old Babylonian Mathematics (with Daniel Mansfield): / playlistlist=PLIljB45xT85CdeBmQZ2QiCEnPQn5KQ6ov Math History: • MathHistory: A co...Wild Trig: Intro to Rational Trigonometry: • WildTrig: Intro t...MathFoundations: • Math FoundationsWild Linear Algebra: • Wild Linear AlgebraFamous Math Problems: • Famous Math ProblemsProbability and Statistics: An Introduction: • Probability and S...Boole's Logic and Circuit Analysis: • Boole's Logic and...Universal Hyperbolic Geometry: • Universal Hyperbo...Differential Geometry: • Differential Geom...Algebraic Topology: • Algebraic TopologyMath Seminars: • MathSeminars************************ And here are some of the Wild Egg Maths Playlists (some available only to Members!) Solving Polynomial Equations: • Solving Polynomia...Exceptional Structures in Maths and Physics via Dynamics on Graphs" • Dynamics on GraphsTriangle Centres: • ENCYCLOPEDIA OF T...Six: An elementary course in pure mathematics: • Six: An elementar...Algebraic Calculus One: • Algebraic Calculu...Algebraic Calculus Two: [ • Algebraic Calculu...](https://www.youtube.com/playlist?list=PLzdiPTrEWyz5VLVr-0LPPgm4T1mtU_DG-)

0:00

foreign [Music] everyone I'm Norman Wildberger today we're going to look at arithmetic with multi-sets

0:14

via trees so we're going to connect with computer science we have a novel way of

0:19

thinking about arithmetic where multi-sets are the basic foundational objects and basically

0:25

we create everything just from boxes inside boxes inside boxes but now we're going to have

0:30

a more two-dimensional perhaps somewhat easily visualized point of view towards them so here

0:39

is an example of a pure mset we have a lot of nested boxes here's an empty set an empty set

0:46

or rather we should say empty mset empty mset here's a pair of empty msets in a box here is a

0:54

bunch of nested ones and also the same repeated there now our notation is that an empty mset is

1:01

denoted by zero so we could replace this with zero this was Zero then this will be the M set 0 0. this will be the mset uh that inner one there is replaced with zero so we have zero

1:11

inside an M set inside an M set and this is the same as that one and then we could reduce that a

1:17

little bit further because this mset here the mset containing 0 and 0 is our number two and this mset

1:25

containing just a single zero is the number one so these two can be replaced with these ones so

1:30

this is a sort of alternate notation this is sort of the elemental point of view where we just have msets here we're introducing natural numbers also so today we want to see how this

1:45

arithmetic translates into the world of trees and what kind of trees are we talking about so

1:51

of course a tree is a graph okay that which is a cyclic doesn't have any Cycles in it

1:57

so there is a unique uh sort of path from any one vertex to another which doesn't repeat itself

2:06

and the trees we're talking about are rooted trees that means they have a distinguished node

2:12

and we're going to put that distinguished node at the top so we can also perhaps say this is

2:18

like a roofed tree with the roof up at the top now importantly this is a little bit different

2:23

from the roofed trees that appeared in my series on solving polynomial equations if you've watched

2:29

that we solved polynomial equations by introducing a broad extension of the Catalan story and trees

2:37

played an important role but those were planar trees okay so these are non-planar trees by which

2:43

we mean that the actual order on the page that we put these sort of sub branches is unimportant so

2:52

let's have a look at this one here okay it can be represented with this tree here so this top node

2:58

represents the outside brackets and then inside that there are these sort of subdivisions there's

3:07

an msat another mset another mset another one another one so there's these five sort of interior

3:13

msets there are corresponding to these nodes here which is one level down so the the lines here just

3:21

represent the inclusions of msets in msets now these ones here are empty so we're going to denote

3:27

them with just a node which is empty and this one here is represented here it has two empty ones

3:34

inside it this one here has another one inside it which then contains an empty set and this one

3:40

is similar so this representation is not unique because we can interchange the orders of things so

3:47

this is an alternate representation where we've taken these sort of two branches if you like

3:52

um and brought them on the other side I've brought these to the other side okay so these are equal

3:57

now in our um connection with algebra we've seen that a mset of this kind really corresponds to an

4:07

algebraic object a relatively familiar algebraic object so this is the number two the two zeros

4:13

here and this two that's appearing in the mset corresponds to Alpha 0 squared where Alpha zero

4:19

is some kind of basic variable that's introduced in the poly number context here and these two mset

4:26

ones that are appearing inside here give us 2 Alpha One corresponding to a second variable

4:33

Alpha One so we end up with an algebra not just in one variable but with a an unbounded number

4:39

of variables corresponding to natural numbers and so we want to see today how this algebra sort of

4:46

polynomial algebra corresponds to the tree story and how the tree representation sheds light and

4:55

gives us new ideas about the structure of this mathematics now rooted or roofed trees are very

Notation for rooted/roofed trees

5:02

important objects in combinatorics but they also play a very important role in computer science

5:08

where they're often used to store data structures in convenient ways that allow for you nice search

5:15

and and and sorting and so on so let's just review some standard probably familiar terminology in the

5:23

context of rooted or roofed trees so here's that same one that we had before and um so that node up

5:32

at the top will be called the root and it has the property that it doesn't have any parents so the

5:37

relationship between a node like this and a node directly below it is that of parent and child so

5:43

the top one is the parent and the one below is the child okay and those nodes which don't have any

5:50

children so they're sort of at the bottom of some Branch are called leaves so a leaf has no children

5:57

and then there's also this concept of height and depth so the height is the number of steps that

6:04

you need to go down to get to the furthest Leaf below you so for example if you're here uh you go

6:12

down one step so this is at the height of one this is also at the height of one this one here is also

6:18

at a height of one because that's the maximum that you can go down to get to a leaf there's another corresponding concept which is depth so it's a let's say you're swimming in an ocean okay

6:27

you're inside the ocean the height is how far you are from the bottom of the sea floor let's say

6:34

and the depth is how far you are from the surface of the water okay so the depth is measured how

6:42

far we have to go up to get to the root so the root has depth zero and say these ones here are

6:49

of depth two so we have to take one two steps to get to them from the root okay so those just some

6:57

basic terminology from uh from computer science so I should mention that this this development of

Multiplicity convention (left subindices)

7:06

arithmetic is somewhat new here right it we don't have a lot of experience with this yet so perhaps

7:14

some of the things that I'm telling you are to be thought of in a provisional fashion where

7:19

sort of exploring this territory I wouldn't say that anything is set in stone we're still trying

7:24

to find the sort of optimal ways of structuring this Theory and it's possible that I might make

7:29

some mistakes so I hope that if I do you will correct me and along the way I'm going to try to introduce perhaps some terminology or notation which I hope will help us in this exploration

7:40

that's what I want to do today here just with this slide I want to introduce a sort of Multiplicity

7:46

convention that will make it perhaps a little bit easier for us to display things so it's very easy

7:51

to get overwhelmed with all the brackets and and such that we have so here's that same mset that

7:57

we were considering and we could write it out as a a sum okay because there are two of these uh these

8:04

ones here and um and then we could um write this one here that's that one and then there are two

8:12

of these guys here so um we could then uh sort of think about this in another way by starting with

8:20

the same big outside mset and representing these two empty msets in here by a single mset with a

8:28

a little subscript two a left sub index okay so to the left and down and this here is telling us that

8:37

there are two of these guys in this bigger mset similarly this one here these guys here there's

8:43

two of them so we could also represent that with a two okay so that's just a little convention that

8:49

we could use especially useful if we have a lot of repetitions like if we're dealing with with much bigger multiples that we don't want to physically exhibit you know 300 different copies of the same

9:00

thing much easier just to put a little 300 under there note that we can also in fact go a little

9:06

bit further and actually replace this one also if we wanted to because we have two empty msets in

9:12

here so we could rub off one of them and just put a little two to the left of the other one

9:17

so this corresponds in the tree World also to a corresponding convention so here is our original a

9:25

and we could then maybe represent this a little bit more efficiently by saying okay look there's

9:32

two of these empty msets coming from the root okay why don't we just write one of them and

9:38

put a little two beside that node also to the left and maybe a little bit down representing

9:44

that this child here is to be thought of just as as one of a pair there's actually two of them

9:50

and here's another pair of branches that are sort of the same so this is a sub tree from here and

9:57

from here they're the same okay so instead of writing both of them out we could just write one of them out and put a little index there representing that there's two of them okay though

10:08

sort of corresponds to um to that one there and then we could actually also go one step further

10:14

so if we did the rubbing out here then these two here that are out uh coming from this one here

10:20

we can replace them with a single one also with the two okay so I just offer this as a potential

10:27

labor-saving device that will make it easier for us to make Expressions both in this mset point of

10:35

view and also in this tree or language so in my last video I also introduced the idea of counting

Counting with trees

10:42

and there are different kinds of counting functions starting with Z and then we had an N counting function a P counting function and M counting functions sort of corresponding to the

10:51

different levels of zero number poly number multi number okay so they have a nice interpretation in

11:03

this tree language so let's look at our example again there's our M set a they're written out in

11:09

the usual way here in in the tree form so the Z counting function is very simple just takes

11:16

any mset and sends it to zero the empty mset N of a which is the closest to our regular

11:24

counting function is this mset is the mset of Z of A's set of little A's where little a belongs

11:32

to Capital a so what we have to do is we have to take all of the constituent elements that

11:39

one that one that one that one and that one and replace them all with empty sets or empty msets

11:46

so they're there they are there an empty Ms that's the same as zero so similarly we just say that we're replacing each of them with zero and then the resulting m z is the number five

11:56

and what we're doing there in terms of the diagram you can see has a very natural simple

12:04

sort of representation what we're doing first of all with Z of a is we're just looking at the top

12:09

of it okay the top of it and there's a single node there and so that's the the zero node and

12:16

when we so that's sort of like Zed and then when we go to an of a what we're doing is we're just

12:21

going down one level to the level one or maybe we can say to the depth one that means sort of

12:27

we're sort of chopping it off there and looking at everything above that okay so if we just chop

12:33

the whole thing there then we get a much simpler mset which just has five leaves coming out of

12:39

the root and that's then the number five so that corresponds to the counting function n

12:47

and what about P of a well that's defined to be the M Set n of a where a is an A and so there

12:53

what we have to do is we have to look at in each one of these and replace each one of them with uh

13:00

the N of them so the end of this is is zero and if this is zero so we're just putting those zeros

13:06

n of this well that to do that we have to replace all the things inside it with with zeros okay so

13:13

just get zero zero but this one here we have to replace this the thing that's inside here with a

13:21

zero so instead of having a three nested brackets we end up only with two nested brackets so this

13:28

one and this one end up simplifying to msat zero and msat zero and what that amounts to is

13:37

truncating the story at that level so we're going down to depth two but no further okay

13:43

so that's that's our P County function so the P counting function looks at everything above that

13:49

says P of the M set is just what you get when you truncate right there the thing above it is p of a

13:58

so that's a very attractive way of counting and of course it's obvious how to extend that to further

14:04

depths or further levels in this case M of a well that's the mset of P of A's a and a that turns

14:13

out to be all of a in this case and that sort of corresponds to chopping off at that level there so that's the m and since this thing here is uh a multi number okay because it's um it's an M set of

14:31

poly numbers so the M accounting function actually just outputs uh the the mset itself so the general

14:42

rule here that we're seeing is that in this world at the level of trees sort of geometrically these

14:49

various counting functions just correspond to truncations and that makes arguments uh

14:56

about the sort of functorial properties that the counting functions have with

15:02

respect to the operations a lot easier to to sort of see because we just have to ask them what happens if you if we look at addition or multiplication so you up to a certain level okay

15:14

so that's a a nice aspect of the two-dimensional visual approach that we get with the tree point

15:21

of view I want to introduce another idea which I think is useful here the idea of you know taking a

Closed boxes/nodes

15:28

box and which might have stuff inside it and sort of closing the lid so that you can no longer look

15:34

inside and see what it has in it maybe you can shake it you know but now you we're just sort of

15:40

thinking about a box which may have stuff inside it but that content is maybe not visible to us

15:47

so I want to talk about the idea of close boxes or correspondingly closed nodes in the in the

15:53

tree version so here again is our familiar a okay there's a sort of more succinct way of

15:59

representing it here's another way of thinking about what a is sort of geometrically which is really more in the line of boxes so here the boxes are represented by rectangles so there's the big

16:10

rectangle which corresponds to that one up here and then these five here are the five elements of

16:16

a which themselves are rectangles or squares and these ones here are empty and this one here has

16:24

two boxes inside it which otherwise are empty and these ones here both have a box inside but that

16:31

box is not empty it rather has another box inside both of them so this is a also very attractive way

16:37

of thinking about things also has a bit more of a two-dimensional aspect so what we want to think

16:43

about now is is another way of sort of condensing sing this kind of thing because in principle these

16:49

things could be very big right we don't want to be writing these trees down if we really need to in all their messy details especially if they have lots of branches with a lot of depth

17:00

so we could maybe represent this thing in in a bit a more succinct way by replacing one of

17:08

these nodes with just a letter representing the contents representing that box and its contents

17:16

so for example let's consider this one here so when we look at this node here okay I want you

17:21

to think about this note as not really so much a node but actually as a sub tree so I want you to

17:28

think about this this thing here as representing the tree that's emanating from that point in other

17:34

words the tree that has that as a root okay so that's that one along with two edges and these

17:41

two two down here so that's like a little sub tree okay in fact there it is there and you can sort of see it's that's what's called B so what we can do is in this diagram here we can replace

17:52

this subtree with just a single node which is the root of it and we put a little say box around it

18:00

okay and letter B telling us that what we've done is we've made a substitution or we've

18:06

sort of rubbed some stuff out and this is then a placeholder for some additional stuff which

18:13

is perhaps off the page or is recorded in memory somewhere else okay so in this case here we see

18:20

there's a little square around it meaning there's actually more stuff there's another tree coming from that node but we have to find it somewhere else and so we look over here okay here's here's B

18:30

so then we could we could recover this by putting that back in similarly this one here that that

18:37

node there is is replaced with a little square around it and we forget about the stuff below and

18:42

the letter c you know so this this is representing this sort of subtree node node and a leaf there

18:51

so this is a more efficient way of representing this thing that sort of compresses some of the

18:58

information perhaps that we don't really need now there's a corresponding way of thinking about that over here in the sense of what we're doing is we're sort of closing the boxes okay but

19:09

recording the contents of the box somewhere else so corresponding to what I did over here this B

19:15

one over here is this one here so going from this diagram to this diagram what I've done is

19:20

I've I sort of shaded the box so you no longer can see inside there's something inside perhaps

19:27

it doesn't have to be but there could be something inside but we don't know what it is but over here

19:32

in different locations we see that actually this box is actually this one here and similarly this

19:38

box C which has also been shaded so we lose the information but it's over here somewhere okay so this is a way that if we're doing certain manipulations and we don't actually need to know

19:50

what the sort of finer structure is inside these boxes inside other boxes okay we might be making

19:57

a calculation that only requires us to look at things down to a certain depth and what's below

20:03

that is is sort of Irrelevant for the actual computation we're interested in so this kind of

20:10

representation or simplification I think can be helpful in that kind of context you see there's

20:16

a natural parallel between what we're doing here in the tree world and what we're doing here in the more familiar sort of mset or Box World okay so now let's get to the arithmetic with trace and

Arithmetic with trees

20:28

I'm just going to give you this one slide which has a lot of information and some computations and I'm going to go through it and I hope that you can check and and see that I've done it correctly

20:38

so I have to admit here that you know I'm not that familiar with this entire world I'm sort

20:44

of just making the initial forays into it myself and I have to admit that I often get a little bit confused making these calculations we just have to where exactly are we you know and what

20:53

level are we Etc so if I feel a little bit like perhaps a an intelligent but primitive person who

20:59

has never been to school might feel when they're subjected to Primary School mathematics and they

21:06

have to learn arithmetic for the first time it's not that hard but you know there's these various

21:11

conventions and you have to do quite a lot of practice actually before you get reasonably good at it after all in primary school we spend some years learning basic arithmetic addition

21:24

subtraction multiplication Etc even with just natural numbers so there's a fair amount to

21:30

learn there but it is admittedly of an elementary nature but still the unfamiliarity of it probably

21:36

does require some some practice so so actually in that direction while I'm talking about that maybe

21:41

I could ask some of my viewers to think about if you're interested in this topic of creating some

21:48

resources that will help us to sort of gain some experience in this world so I think it would be

21:55

nice to have some some problem sets like a little homework exercises that we could do maybe with

22:02

Solutions which have been carefully worked out so that we can see whether we are our intuition

22:08

um is a good one okay so here's an example of such a thing so here are two msets A and B represented

22:17

in tree form okay so here's the root we have three children one of them is a leaf the other

22:24

two have some branches that's of depth two and that's one that's depth three so in terms of our

22:31

familiar sort of algebra notation this corresponds to an algebraic expression in our variables well

22:39

in numbers and variables okay in this case 1 plus Alpha 0 plus alpha one the one corresponds to that

22:46

leaf down there okay so that's just a single zero inside the big mset that corresponds to the number

22:52

one this thing here it's like an mset in inside the big handset there's an mset which has a single

23:02

um zero in it so that's like this this combination here is one but it's inside the bigger mset so it

23:10

has the interpretation of alpha zero and when we go one more so when we have an mset inside

23:16

an mset with a zero in it then that's Alpha One over here B we have another one so there's the

23:23

root and there's a leaf coming down there and here's a node which has two leaves coming out here so this thing here by itself is the number two but when the number two is appearing as you

23:36

know down from the root it has to be interpreted in a different way okay that's like the number

23:42

two in in an mset that's different from the number two so that has the interpretation of being Alpha

23:48

zero squared in terms of this fundamental variable the zeroth variable Alpha zero so this is one plus

23:56

Alpha zero squared that's an interpretation of that okay so here are the various operations that we know so far how to do and so the simplest one is of course addition where we just take

24:08

these things and add them and what we're doing there one way of thinking about it is we're just

24:15

we're just sort of chopping these things off here and then taking these the constituent entries

24:25

which are themselves little trees okay and we're just putting them all together so this tree right

24:32

here gets copied that's a new element of this this new mset okay this one here gets copied

24:41

and this one here gets copied similarly this one gets copied and this one here gets copied

24:48

okay so you could think about it perhaps as sort of way we're sort of snipping or cutting

24:55

those edges there and cutting those edges there and taking those five edges and and putting them

25:00

together within a new node that's the tree version of taking the contents of these two

25:06

msets and dumping them out into into another box okay A times B this is a times B and how do we

25:18

get that well what we have to do is we have to look at the the elements of a so there are three

25:25

elements of a each of them is themselves a tree and there are two elements of B each of them is

25:30

itself a tree and we have to take all possible combinations of elements of a and elements of

25:36

B like pairs maybe that tree and that tree and we have to add them their msets so they can be added

25:45

so for example when we do that we take this thing here which is really like the mset which is what

25:51

we're calling one and this is the m set zero and we add one and zero we get one okay so the effect of adding this and and this is just to get this so that's why that's appearing over there and

26:01

similarly this plus this tree is it's this one here and this one plus this is also this one

26:07

here okay so now the the next three are obtained by taking these three and adding this one to it

26:14

okay so for example if we take this tree here and we take this tree here and we add them so this

26:20

is a tree with one leaf this is a tree with two leaves we add them we get a tree with three leaves

26:27

when we add this one and this one we get a tree that has a root there and then it has this

26:35

sub tree coming down and also two leaves coming out and finally when we add this to this well

26:42

this is zero again so we're just getting our our thing that we started with there so this is a

26:49

times B and what is it algebraically well sort of read through things this one here is is one okay

27:00

and this one here is a one but it's contained in a big bracket so that's Alpha zero this is Alpha One

27:08

this one here is um okay this one here is maybe the next simplest one this one here

27:14

is Alpha zero squared okay this one here is Alpha zero cubed and this one here is

27:21

a combination of alpha zeros there's two sort of two of them so Alpha zero squared there but there's also an alpha one so it corresponds to this polynomial in Alpha zero and Alpha a one

27:36

and what about a caret B okay so we're going to change our notation just a little bit I

27:44

was talking about exponentiation maybe that's not really such a great terminology a number of viewers have suggested that a step back away from that and I think that's

27:53

reasonable but I sort of like this symbol so I'm going to uh stick with a suggestion

28:00

that a viewer made that we stick with this thing here and call it the caret c-a-r-e-t okay so a carrot B what is that so by definition what we have to do is we have to take

28:11

these things here and take the various sub trees the elements of this one the elements of this one and we have to pairwise multiply them multiply them not add over here we were adding them here

28:23

we have to multiply them so for example we have to take this subtree and multiply it by this sub tree

28:28

okay but this sub tree is zero when we multiply it something by zero we get zero so we get a zero

28:35

zero zero the first three are going to be zeros in fact we're going to get another zero because

28:40

uh because when we multiply this one by by this one here we also get a zero so the two that are

28:47

non-trivial are the product of this and this which is this and this and this so let's just check that

28:54

so the product of this tree and this tree how do you take the product well you have to look at

29:02

um all possible pairs of of sub or elements this one has one element this one has two elements so

29:09

we have to take a pair like this and we have to add them all right so zero plus zero is zero zero plus zero zero so we're getting two possible zeros and when we do the same thing over here we have to

29:20

take this tree okay starting from there and this tree and we have to multiply them so how do we do

29:29

that well we have to take the elements of this one there's only one element namely the tree starting

29:35

there and there's two elements of this one and we have to add those okay so when we add this

29:41

one with with this one well we just get this thing and when we add it with this one we get this thing

29:47

because zero plus anything is the anything all right so that's what we end up getting by taking

29:53

this combination with this combination multiplying multiplying the this tree with this tree

30:01

and what does this look like algebraically well this is a four this is Alpha 0 squared same thing

30:11

like that and this thing here is well uh this was like an alpha alpha one and we have two of

30:20

them coming out here so that's like alpha one squared so that's the way the carrot operation

30:26

works on on these things which is you know a little bit strange to us admittedly this is

30:32

a kind of a strange new arithmetic we're in a kind of unusual World here so the natural

30:40

question though is is this a consistent world and is it is it an interesting World well if we just

30:45

restrict ourselves to addition and multiplication it's certainly useful because we're recovering polynomial algebra in actually an unbounded number of variables that's already a very rich discipline

30:58

and in fact in our next video we're going to see that this becomes even much richer

31:04

when we take the big step to extending our number system to include negative numbers so

31:11

a lot of viewers have asked me how are we going to do that and it's a really interesting question and I'm going to show you next time and we're going to see that that really again expands our vision in a

31:21

quite a fascinating way hope you'll join me for that I'm Norman Wildberger thanks for listening

31:28

[Music]