Adam Barr’s blog “Proudly Serving My Corporate Masters” has a post on the controversy over whether a Square class should be defined in object oriented programming as inheriting from a Rectangle class. You can find lots of argument about that by typing “square rectangle Liskov” (without the quotes!) into Google. This controversy is based on technical aspects of OOP, but the controversy about whether a square is a rectangle has been around for years.
According to modern mathematical usage, a square is a special case of a rectangle. (Euclid did not include squares in rectangles, although I can’t give a reference to this.) This post concerns some of the issues in math and logic connected with special cases.
A rectangle is given by two parameters, the length and the height. Call them L and H. A square is the special case of a rectangle satisfying L = H. (Note: I am talking about a rectangle independently of how it drawn in the plane. You need six parameters to define a rectangle embedded in the plane.)
Rectangles and squares are an example of the following phenomenon: A certain family of math objects is defined by parameters. A subfamily is defined by setting two (or more) of the parameters equal, or by fixing the value of one of the parameters. Such a subfamily may be called an equationally defined family or a variety. Sometimes such a subfamily is said to be degenerate.
Mathworld refers to a square as a degenerate rectangle. This says something interesting about the images and metaphors we use in math. I would have said a square is a specially nice kind of rectangle. Saying it is degenerate disses it. Of course, the technical definition of “degenerate” says nothing about a square’s moral failings, but the word’s connotations are negative.
Not all special cases fit this equational pattern. For many mathematical structures, the definition allows the structure with empty underlying set to be an example. For example, a topological space is allowed to be empty. If you define semigroup to be a set with an associative binary operation, that definition allows the underlying set to be empty, but in fact some texts explicitly add a requirement that excludes the empty set. This has been the source of considerable irritation between researchers in universal algebra and researchers in categorical model theory.
If your definition of the structure includes the requirement that some element with a certain property exists, then the structure must be nonempty. That’s why groups are nonempty – they have to have an identity. So the behavior of special cases depends on the logical form of the definition. In particular you could define rectangles as having two parameters L and H together with the requirement that L not equal H. Then squares would not be rectangles. But that is not the way we do it nowaways, not for rectangles.
But in some other math definitiions, we rule out two parameters being equal. The definition of field always requires 0 not equal 1, although Mathworld appears to add the requirement only as an afterthought. The definition of Boolean algebra sometimes requires that T not equal F and sometimes not. MathWorld gives several definitions, some allowing T = F and some not. Wikipedia’s definition of Boolean algebra said until recently that a Boolean algebra has “…two elements called 0 and 1…” It did not say they must be distinct in the axiom but in the examples it said that the two-element Boolean algebra is the simplest example. Since 18 October 2006 Wikipedia has said they must be “distinct.” This change was added by SixWingedSeraph, who is either a close relative of mine or not depending on your attitude toward special cases.
There must be some fairly deep seated psychology underlying the decision to allow some special cases and exclude others. Certainly the naïve abstract math newbie tends to assume (subconsciously) that special cases should be excluded, with the consequence that the uppity math majors (and sometimes the teacher) disses the student as stupid, etc.
Note: When I wrote this, Microsoft Word put a diaeresis over the “I” in “naïve” without asking me first. Who said it could?
Send to Kindle
I enjoyed this square-rectangle discussion. I had always considered a square to be a “special case” of a rectangle. My first indication that other people considered them as disjoint collections was when my son was in elementary school. He selected “rectangle” for a question where a “square” was pictured, and it was marked wrong. (Certainly math questions can only have one correct answer!) I knew better than to try to argue with an elementary teacher (they all seem very insecure and inflexible with their knowledge of mathematics), but I thought that it was sad that this could not lead to a productive discussion in the classroom.
I'm quite interested in the idea of degenerate structures, especially those related to the empty set. (My favourite number is zero, no question!)
You mentioned that groups cannot be empty because of the identity element. Fair enough, but consider this definition: a set equipped with a binary operation {a,b |-> a/b}, called division, such that:
* a/a = b/b;
* (a/a)/((a/a)/a) = a; and
* a/(b/c) = (a/((c/c)/c))/b.
Define a' to be (a/a)/a, and a*b to be b/a'; if this set has an element, then it is a group under the operation * (and a’ is the inverse of a, and a/b may be recovered as b’*a). Without the assumption that it has an element, however, the set may be empty.
Generally, I accept the forbidding of degenerate cases when this follows from the 0-ary version of a more general requirement. For example, 0 = 1 is forbidden in an integral domain (and in particular in a field) because we have the general rule that the product of any (finite) list of non-zero elements is non-zero. If you apply this rule to the product of the empty list elements, then you get precisely that 1 is nonzero. On the other hand, there is no reason to make this requirement for rings-with-identity in general (as some authors do), nor for Boolean rings/algebras (although the only Boolean ring that is an integral domain is the Boolean field {0,1} with two distinct elements).
Another example is the case of semigroups and monoids. These both have accepted definitions, so the real question is which concept to think of as the fundamental one, and which is second-class. Of course, you could determine this by experience, but I will be arrogantly theoretical. Now, an associative binary operation doesn’t just define the product of two elements but in fact defines the product of any (finite) list of elements. (Both this example and the example with integral domains shows why it’s often helpful, when trying to understand the degenerate n = 0 case, to first understand the case for n = 3,4,5,…). Therefore, we should have a notion of the product of the empty list of elements; this is the identity. (To prove that it is an identity, you specialise the generalised associative law for the product of a list of products of lists.) Therefore, monoids are better than mere semigroups (rather than the alternative: that monoids are degenerate semigroups).
Exercise: Show that the definition of possibly-empty-group given above in terms of the division operation is deficient in a way analogous to the deficiency of the definition of semigroup, and that this deficiency is fixed by requiring an element 1 such that a/a = 1 (which then allows you to simplify the statements of the axioms, by the way). Thus, we are correct to think that groups shouldn’t be empty.