Friday, January 21, 2011

History topic: Abstract linear spaces


Cartesian geometry, introduced by Fermat and Descartes around 1636, had a very large influence on mathematics bringing algebraic methods into geometry. By the middle of the 19th Century however there was some dissatisfaction with these coordinate methods and people began to search for direct methods, i.e. methods of synthetic geometry which were coordinate free.
It is possible however to trace the beginning of the vector concept back to the beginning of the 19th Century with the work of Bolzano. In 1804 he published a work on the foundations of elementary geometry Betrachtungen über einige Gegenstände der Elementargoemetrie. Bolzano, in this book, considers points, lines and planes as undefined elements and defines operations on them. This is an important step in the axiomatisation of geometry and an early move towards the necessary abstraction for the concept of a linear space to arise.
The move away from coordinate geometry was mainly due to the work of Poncelet and Chasles who were the founders of synthetic geometry. The parallel development in analysis was to move from spaces of concrete objects such as sequence spaces towards abstract linear spaces. Instead of substitutions defined by matrices, abstract linear operators must be defined on abstract linear spaces.
In 1827 Möbius published Der barycentrische Calcul a geometrical book which studies transformations of lines and conics. The novel feature of this work is the introduction of barycentric coordinates. Given any triangle ABC then if weights a, b and c are placed at A, B and C respectively then a point P, the centre of gravity, is determined. Möbius showed that every point P in the plane is determined by the homogeneous coordinates [a,b,c], the weights required to be placed at A, B and C to give the centre of gravity at P. The importance here is that Möbius was considering directed quantities, an early appearence of vectors.
In 1837 Möbius published a book on statics in which he clearly states the idea of resolving a vector quantity along two specified axes.
Between these two works of Möbius, a geometrical work by Bellavitis was published in 1832 which also contains vector type quantities. His basic objects are line segments AB and he considers AB and BA as two distinct objects. He defines two line segments as 'equipollent' if they are equal and parallel, so, in modern notation, two line segments are equipollent if they represent the same vector. Bellavitis then defines the 'equipollent sum of line segments' and obtains an 'equipollent calculus' which is essentially a vector space.
In 1814 Argand had represented the complex numbers as points on the plane, that is as ordered pairs of real numbers. Hamilton represented the complex numbers as a two dimensional vector space over the reals although of course he did not use these general abstract terms. He presented these results in a paper to the Irish Academy in 1833. He spent the next 10 years of his life trying to define a multiplication on the 3-dimensional vector space over the reals. Hamilton's quaternions, published in 1843, was an important example of a 4-dimensional vector space but, particularly with Tait's work on quaternions published in 1873, there was to be some competition between vector and quaternion methods.

In 1857 Cayley introduced matrix algebras, helping the move towards more general abstract systems by adding to the different types of structural laws being studied. In 1858 Cayley noticed that the quaternions could be represented by matrices.
In 1867 Laguerre wrote a letter to Hermite Sur le calcul des systèmes linéaires. His systèmes linéaires is a table of coefficients of a system of linear equations denoted by a single upper-case letter and Laguerre defines addition, subtraction and multiplication of of these linear sysyems. In this work Laguerre aims to unify algebraic systems such as complex numbers, Hamilton's quaternions and notions introduced by Galois and by Cauchy.
Laguerre's work on linear systems was followed up by a paper by Carvallo in 1891. In this paper he defines operators on vector functions and draws a clear distinction between operators and matrices.
To understand the difference between the notions of an operator and a matrix, it suffices to say that, if one changes the coordinate system, one obtains a different matrix to represent the same vector function, but the same operator.
Another mathematician who was moving towards geometry without coordinates was Grassmann. His work is highly original but the notion of barycentric coordinates introduced by Möbius was his main motivation. Grassmann's contribution Die Ausdehnungslehre appeared in several different versions. The first was in 1844 but it was a very difficult work to read, and clearly did not find favour with mathematicians, so Grassmann tried to produce a more readable version which appeared in 1862. Clebsch inspired Grassmann to work on this new version.
Grassmann studied an algebra whose elements are not specified, so are abstract quantities. He considers systems of elements on which he defines a formal operation of addition, scalar multiplication and multiplication. He starts with undefined elements which he calls 'simple quantities' and generates more complex quantities using specified rules.
But ... I go further, since I call these not just quantities but simple quantities. There are other quantities which are themselves compounded quantities and whose characteristics are as distinct relative to each other as the characteristics of the different simple quantities are to each other. These quantities come about through addition of higher forms ...
His work contains the familiar laws of vector spaces but, since he also has a multiplication defined, his structures satisfy the properties of what are today called algebras. The precise structures are now known as Grassmann algebras. The ideas of linearly independent and linearly dependent sets of elements are clearly contained in Grassmann's work as is the idea of dimension (although he does not use the term). The scalar product also appears in Grassmann's 1844 work.
Grassmann's 1862 version of Die Ausdehnungslehre has a long introduction in which Grassmann gives a summary of his theory. In this introduction he also defends his formal methods which had clearly been objected to by a number of mathematicians. Grassmann's justification comes very close to saying that he is setting up an axiomatic theory and this shows that he is well ahead of his time.
Cauchy and Saint-Venant have some claims to have invented similar systems to Grassmann. Saint-Venant's claim is a fair one since he published a work in 1845 in which he multiples line segments in an analogous way to Grassmann. In fact when Grassmann read Saint-Venant's paper he realised that Saint-Venant had not read his 1844 work and sent two copies of the relevant parts to Cauchy, asking him to pass one copy to Saint-Venant.
However, rather typically of Cauchy, in 1853 he published Sur les clefs algébrique in Comptes Rendus which describes a formal symbolic method which coincides with that of Grassmann's method (but makes no reference to Grassmann). Grassmann complained to the Académie des Sciences that his work had priority over Cauchy's and, in 1854, a committee was set up to investigate who had priority. We still await the committee's report!
The first to see the importance of Grassmann's work was Hankel. In 1867 he wrote a paper Theorie der complexen Zahlensysteme concerning formal systems where combination of the symbols are abstractly defined. He credits Grassmann's Die Ausdehnungslehre as giving the foundation for his work.
The first to give an axiomatic definition of a real linear space was Peano in a book published in Torino in 1888. He credits Leibniz, Möbius's 1827 work, Grassmann's 1844 work and Hamilton's work on quaternions as providing ideas which led him to his formal calculus.
Peano's 1888 book Calcolo geometrico secondo l'Ausdehnungslehre di H. Grassmann preceduto dalle operazioni della logica deduttiva is remarkable. It gives the basic calculus of set operation introducing the modern notation ∩, , belongsfor intersection, union and an element of. It was many years before this notation was to become accepted, in fact Peano's book seems to have had very little influence for many years. It is equally remarkable for containing an almost modern introduction to linear spaces and linear algebra.
In Chapter IX of the book Peano gives axioms for a linear space.
It is hard to believe that Peano writes the following in 1888. It could almost come from a 1988 book! The first is for equality of elements

  1. (a = b) if and only if (b = a), if (a = b) and (b = c) then (a = c).
  2. The sum of two objects a and b is defined, i.e. an object is defined denoted by a + b, also belonging to the system, which satisfies:
    If
    (a = b) then (a + c = b + c), a + b = b + a, a + (b + c) = (a + b) + c,
    and the common value of the last equality is denoted by a + b + c.
  3. If a is an object of the system and m a positive integer, then we understand by ma the sum of m objects equal to a. It is easy to see that for objects a, b, ... of the system and positive integers m, n, ... one has
    If
    (a = b) then (ma = mb), m(a+b) = ma+mb, (m+n)a = ma+na,
    m(na) = mna, 1a = a.
    We suppose that for any real number m the notation ma has a meaning such that the preceeding equations are valid.
Peano goes on to state the existence of a zero object 0 and says that 0a = 0, that a - b means a + (-b) and states it is easy to show that a - a = 0 and 0 + a = a.
Peano defines a linear system to be any system of objects satisfying his four conditions. He goes on to define dependent objects and independent objects. He then defines dimension.
Definition: The number of the dimensions of a linear system is the maximal number of linearly independent objects in the system.
He proves that finite dimensional spaces have a basis and gives examples of infinite dimensional linear spaces. Peano considers entire functions f(x) of a variable x, defines the sum of f1(x) and f2(x) and the product of f(x) by a real number m. He says:-
If one considers only functions of degree n, then these functions form a linear system with n + 1 dimensions, the entire functions of arbitrary degree form a linear system with infinitely many dimensions.
Peano defines linear operators on a linear space, shows that by using coordinates one obtains a matrix. He defines the sum and product of linear operators.
In the 1890's Pincherle worked on a formal theory of linear operators on an infinite dimensional vector space. However Pincherle did not base his work on that of Peano, rather on the abstract operator theory of Leibniz and d'Alembert. Like so much work in this area it had very little immediate impact and axiomatic infinite dimensional vector spaces were not studied again until Banach and his associates took up the topic in the 1920's.
Although never attaining the level of abstraction which Peano had achieved, Hilbert and his student Schmidt looked at infinite dimensional spaces of functions in 1904. Schmidt introduced a move towards abstraction in 1908 introducing geometrical language into Hilbert space theory. The fully axiomatic approach appeared in Banach's 1920 doctoral dissertation.

    

Saturday, December 25, 2010

FUZZY SETS

Before illustrating the mechanisms which make fuzzy logic machines work, it is important to realize what fuzzy logic actually is. Fuzzy logic is a superset of conventional(Boolean) logic that has been extended to handle the concept of partial truth- truth values between "completely true" and "completely false". As its name suggests, it is the logic underlying modes of reasoning which are approximate rather than exact. The importance of fuzzy logic derives from the fact that most modes of human reasoning and especially common sense reasoning are approximate in nature.
The essential characteristics of fuzzy logic as founded by Zader Lotfi are as follows.
  • In fuzzy logic, exact reasoning is viewed as a limiting case of approximate reasoning.
  • In fuzzy logic everything is a matter of degree.
  • Any logical system can be fuzzified
  • In fuzzy logic, knowledge is interpreted as a collection of elastic or, equivalently , fuzzy constraint on a collection of variables
  • Inference is viewed as a process of propagation of elastic constraints.
The third statement hence, define Boolean logic as a subset of Fuzzy logic.Fuzzy Sets

Fuzzy Set Theory was formalised by Professor Lofti Zadeh at the University of California in 1965. What Zadeh proposed is very much a paradigm shift that first gained acceptance in the Far East and its successful application has ensured its adoption around the world.
A paradigm is a set of rules and regulations which defines boundaries and tells us what to do to be successful in solving problems within these boundaries. For example the use of transistors instead of vacuum tubes is a paradigm shift - likewise the development of Fuzzy Set Theory from conventional bivalent set theory is a paradigm shift.
Bivalent Set Theory can be somewhat limiting if we wish to describe a 'humanistic' problem mathematically. For example, Fig 1 below illustrates bivalent sets to characterise the temperature of a room.

The most obvious limiting feature of bivalent sets that can be seen clearly from the diagram is that they are mutually exclusive - it is not possible to have membership of more than one set ( opinion would widely vary as to whether 50 degrees Fahrenheit is 'cold' or 'cool' hence the expert knowledge we need to define our system is mathematically at odds with the humanistic world). Clearly, it is not accurate to define a transiton from a quantity such as 'warm' to 'hot' by the application of one degree Fahrenheit of heat. In the real world a smooth (unnoticeable) drift from warm to hot would occur.This natural phenomenon can be described more accurately by Fuzzy Set Theory. Fig.2 below shows how fuzzy sets quantifying the same information can describe this natural drift.


The whole concept can be illustrated with this example. Let's talk about people and "youthness". In this case the set S (the universe of discourse) is the set of people. A fuzzy subset YOUNG is also defined, which answers the question "to what degree is person x young?" To each person in the universe of discourse, we have to assign a degree of membership in the fuzzy subset YOUNG. The easiest way to do this is with a membership function based on the person's age.young(x) = { 1, if age(x) <= 20,

(30-age(x))/10, if 20 < age(x) <= 30,

0, if age(x) > 30 }

A graph of this looks like:


Given this definition, here are some example values:
Person    Age    degree of youth
--------------------------------------
Johan     10        1.00 
Edwin     21        0.90
Parthiban 25        0.50
Arosha    26        0.40
Chin Wei  28        0.20
Rajkumar  83        0.00 

So given this definition, we'd say that the degree of truth of the statement "Parthiban is YOUNG" is 0.50.Note: Membership functions almost never have as simple a shape as age(x). They will at least tend to be triangles pointing up, and they can be much more complex than that. Furthermore, membership functions so far is discussed as if they always are based on a single criterion, but this isn't always the case, although it is the most common case. One could, for example, want to have the membership function for YOUNG depend on both a person's age and their height (Arosha's short for his age). This is perfectly legitimate, and occasionally used in practice. It's referred to as a two-dimensional membership function. It's also possible to have even more criteria, or to have the membership function depend on elements from two completely different universes of discourse.

Fuzzy Set Operations.

Union

The membership function of the Union of two fuzzy sets A and B with membership functions and  respectively is defined as the maximum of the two individual membership functions. This is called themaximum criterion.
The Union operation in Fuzzy set theory is the equivalent of the OR operation in Boolean algebra.

Intersection

The membership function of the Intersection of two fuzzy sets A and B with membership functions  and  respectively is defined as the minimum of the two individual membership functions. This is called theminimum criterion.
The Intersection operation in Fuzzy set theory is the equivalent of the AND operation in Boolean algebra.

Complement

The membership function of the Complement of a Fuzzy set A with membership function is defined as the negation of the specified membership function. This is caleed the negation criterion.

The Complement operation in Fuzzy set theory is the equivalent of the NOT operation in Boolean algebra.
The following rules which are common in classical set theory also apply to Fuzzy set theory.

De Morgans law

 , 

Associativity

Commutativity

Distributivity

Glossary
Universe of Discourse
The Universe of Discourse is the range of all possible values for an input to a fuzzy system.
 Fuzzy Set
A Fuzzy Set is any set that allows its members to have different grades of membership (membership function) in the interval [0,1].
 Support
The Support of a fuzzy set F is the crisp set of all points in the Universe of Discourse U such that the membership function of F is non-zero.
 Crossover point
The Crossover point of a fuzzy set is the element in U at which its membership function is 0.5.
 Fuzzy Singleton
A Fuzzy singleton is a fuzzy set whose support is a single point in U with a membership function of one.

FUZZY SETS



Before illustrating the mechanisms which make fuzzy logic machines work, it is important to realize what fuzzy logic actually is. Fuzzy logic is a superset of conventional(Boolean) logic that has been extended to handle the concept of partial truth- truth values between "completely true" and "completely false". As its name suggests, it is the logic underlying modes of reasoning which are approximate rather than exact. The importance of fuzzy logic derives from the fact that most modes of human reasoning and especially common sense reasoning are approximate in nature.
The essential characteristics of fuzzy logic as founded by Zader Lotfi are as follows.


  • In fuzzy logic, exact reasoning is viewed as a limiting case of approximate reasoning.
  • In fuzzy logic everything is a matter of degree.
  • Any logical system can be fuzzified
  • In fuzzy logic, knowledge is interpreted as a collection of elastic or, equivalently , fuzzy constraint on a collection of variables
  • Inference is viewed as a process of propagation of elastic constraints.
The third statement hence, define Boolean logic as a subset of Fuzzy logic.Fuzzy Sets

Fuzzy Set Theory was formalised by Professor Lofti Zadeh at the University of California in 1965. What Zadeh proposed is very much a paradigm shift that first gained acceptance in the Far East and its successful application has ensured its adoption around the world.
A paradigm is a set of rules and regulations which defines boundaries and tells us what to do to be successful in solving problems within these boundaries. For example the use of transistors instead of vacuum tubes is a paradigm shift - likewise the development of Fuzzy Set Theory from conventional bivalent set theory is a paradigm shift.
Bivalent Set Theory can be somewhat limiting if we wish to describe a 'humanistic' problem mathematically. For example, Fig 1 below illustrates bivalent sets to characterise the temperature of a room.


The most obvious limiting feature of bivalent sets that can be seen clearly from the diagram is that they are mutually exclusive - it is not possible to have membership of more than one set ( opinion would widely vary as to whether 50 degrees Fahrenheit is 'cold' or 'cool' hence the expert knowledge we need to define our system is mathematically at odds with the humanistic world). Clearly, it is not accurate to define a transiton from a quantity such as 'warm' to 'hot' by the application of one degree Fahrenheit of heat. In the real world a smooth (unnoticeable) drift from warm to hot would occur.This natural phenomenon can be described more accurately by Fuzzy Set Theory. Fig.2 below shows how fuzzy sets quantifying the same information can describe this natural drift.


The whole concept can be illustrated with this example. Let's talk about people and "youthness". In this case the set S (the universe of discourse) is the set of people. A fuzzy subset YOUNG is also defined, which answers the question "to what degree is person x young?" To each person in the universe of discourse, we have to assign a degree of membership in the fuzzy subset YOUNG. The easiest way to do this is with a membership function based on the person's age.young(x) = { 1, if age(x) <= 20,

(30-age(x))/10, if 20 < age(x) <= 30,

0, if age(x) > 30 }

A graph of this looks like:


Given this definition, here are some example values:
Person    Age    degree of youth
--------------------------------------
Johan     10        1.00 
Edwin     21        0.90
Parthiban 25        0.50
Arosha    26        0.40
Chin Wei  28        0.20
Rajkumar  83        0.00 

So given this definition, we'd say that the degree of truth of the statement "Parthiban is YOUNG" is 0.50.Note: Membership functions almost never have as simple a shape as age(x). They will at least tend to be triangles pointing up, and they can be much more complex than that. Furthermore, membership functions so far is discussed as if they always are based on a single criterion, but this isn't always the case, although it is the most common case. One could, for example, want to have the membership function for YOUNG depend on both a person's age and their height (Arosha's short for his age). This is perfectly legitimate, and occasionally used in practice. It's referred to as a two-dimensional membership function. It's also possible to have even more criteria, or to have the membership function depend on elements from two completely different universes of discourse.

Fuzzy Set Operations.

Union

The membership function of the Union of two fuzzy sets A and B with membership functions and  respectively is defined as the maximum of the two individual membership functions. This is called themaximum criterion.
The Union operation in Fuzzy set theory is the equivalent of the OR operation in Boolean algebra.

Intersection

The membership function of the Intersection of two fuzzy sets A and B with membership functions  and  respectively is defined as the minimum of the two individual membership functions. This is called theminimum criterion.
The Intersection operation in Fuzzy set theory is the equivalent of the AND operation in Boolean algebra.

Complement

The membership function of the Complement of a Fuzzy set A with membership function is defined as the negation of the specified membership function. This is caleed the negation criterion.

The Complement operation in Fuzzy set theory is the equivalent of the NOT operation in Boolean algebra.
The following rules which are common in classical set theory also apply to Fuzzy set theory.

De Morgans law

 , 

Associativity

Commutativity

Distributivity

Glossary
Universe of Discourse
The Universe of Discourse is the range of all possible values for an input to a fuzzy system.
 Fuzzy Set
A Fuzzy Set is any set that allows its members to have different grades of membership (membership function) in the interval [0,1].
 Support
The Support of a fuzzy set F is the crisp set of all points in the Universe of Discourse U such that the membership function of F is non-zero.
 Crossover point
The Crossover point of a fuzzy set is the element in U at which its membership function is 0.5.
 Fuzzy Singleton
A Fuzzy singleton is a fuzzy set whose support is a single point in U with a membership function of one.