Mathematics Behind the Project

Lattice of Ideals of a Finite Semiring
 
Content:
 
A Little Bit of History
What is B(n,i)?
Ideals
Lattice of Ideals
More Advanced Stuff (Check this page if you want to see a few theorems with proofs dealling with semirings. You will need some abstract algebra background to follow the proofs.)

Links:
 
More about Dedekind
More about Kummer
More about Kronecker
Download a Free Scientific Notebook Viewer
Download a Free Acrobat Reader

 
 
 
A Little Bit of History

In the nineteenth century, there were many mathematicians researching problems in what would become the theory of ideals. However, the theory of ideals, in the form we know it today,  is the result of work of one mathematician - Julius Wihelm Richard Dedekind. Even though both Kummer and Kronecker researched the same topics as Dedekind, only Dedekind's theory has found wide acceptance among mathematicians. Today, the formulation of ideal theory is quite standardized and most mathematicians do not realize how innovative it was in the nineteenth century. Also, Dedekind's ideas are considered a birthplace of the modern set-theoretic approach to the foundations of mathematics.
 

Julius Wihelm Richard Dedekind
(1831-1916)

   What is B(n,i)?

I bet that even a 7 year old kid knows one B(n,i), and this B(n,i) is B(12,0). Think for a second about the way we measure time. If it is 12 o'clock, one hour later we will have 1 o'clock not 13 (we are not talking about the military time right now). 5 hours after 10 o'clock we will have 3 o'clock not 15, and 12 hours after 6 we have again 6 o'clock. So, 

12+1=1
10+5=3
6+12=6
etc.

Now, if instead of 12 we take 0 we get B(12,0). So, B(12,0)  is a set consisting of 12 elements: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, and:

0+1=1
10+5=3
6+0=6
etc.
We can always use a "clock" to do the calculations:
Exercise 1
Working in B(12,0) find the following:
(a) 8+7 =
(b) 2+11=
(c) 6+(6+10) =
(d) (9+5)+4 =
(e) 5*2 =
(f) 5*4 =
(g) 3*(5+7) =
 
answers

All of the B(n,i) such that i=0 work in the same way, and the only difference is the number of elements. If we take the military time, we get B(24,0) with 24 elements from 0 to 23 and 23+1=0. In this case the clock will have 24 hours. Also, for B(6,0), we have the set {0,1,2,3,4,5} where 5+1=0, and the clock has only 6 hours.

Exercise 2
Draw the clock for B(6,0) and calculate:
(a) 4+5 =
(b) 4*5 =
(c) 3*(5+3) =
 

answers

What if i is not equal to 0? For example in B(9,3).
In B(9,0), there are 9 elements: 0, 1, 2, 3, 4, 5, 6, 7, 8. and 8+1=0. 
B(9,3) has also nine elements: 0, 1, 2, 3, 4, 5, 6, 7, 8, but 8+1 = 3 not 0. In this case, we need to modify our clock:

Now, our clock has a tail, but we do the calculations in the same way, and:
1+1=2
2+3=5
5+3=8
5+7=6 
Observe that 5+7=(5+3)+1+3=8+1+3 and since 8+1=3 we get that 5+7=3+3=6.

Exercise 3
Working with B(9,3) calculate:
(a) 4+7 = 
(b) 8+6 = 
(c) 3*4 =
(d) 2*(4+5) =
 

answers

Exercise 4
Draw the clock for B(6,2) and caculate [in B(6,2)]:
(a) 5+3=
(b) 2+4=
(c) 3*5=
(d) 2*(1+5)=
[Hint: Remember that 5+1=2 in B(6,2)]
 

answers

   Ideals

An ideal I is a subset of B(n,i) that is closed under addition (for all a,b in I, a+b is also in I) and closed under arbitrary products (for all a in I and all c in B(n,i) a*c is in I). 
Let's go back to B(12,0), and consider a set {0}. We can see that {0} is a subset of B(12,0); also, 0+0=0, so {0} is closed under addition, and since 0 times anything is 0, {0} is closed under arbitrary products. Therefore {0} is an ideal of B(12,0).

Now, consider a set {0,6}. Observe that 0+0=0, 0+6=6, 6+6=0, so {0,6} is closed under addition. {0,6} is also closed under abitrary products because:
(1) 0*a = 0 for all a in B(12,0)
(2) 6*b = 0 for b = 0, 2, 4, 6, 8, 10, and
(3) 6*b = 6 for b = 1, 3, 5, 7, 9, 11.

Finding ideals of B(n,i) is not easy and takes a lot of calculations.
  

Lattice of Ideals

Take all ideals of B(12,0): {0}, {0,6}, {0,4,8}, {0,3,6,9}, {0,2,4,6,8,10}, {0,1,2,3,4,5,6,7,8,9,10,11}. Since ideals are sets, we can order them using inclusion. And, for example {0,6} is a subset of {0,3,6,9} but it is not a subset of {0,4,8}, etc. To see all the relations between ideals we can draw a diagram:

Exercise 5
Take all ideals of B(6,2): {0},{0,4},{0,2,4},{0,2,3,4,5},{0,1,2,3,4,5} and draw the diagram.
 
answers
 


More Advanced Stuff

Below you can find two types of files: TEX - to read this one you need to have  Scientific Notebook, and PDF - use Acrobat to view this one. Enjoy!!!
 
 

semiring.tex
semiring.pdf

  
 

ANSWERS:
(1) (a) 3 (b) 1 (c) 10 (d) 6 (e) 10 (f) 8 (g) 0
(2) 

(a) 3 (b) 2 (c) 0
(3)
(a) 5 (b) 8 (c) 6 (d) 6
(4)

(a) 4 (b) 4 (c) 3 (d) 4
(5)