Subsets inherit the laws¶

Level: 201 · for anyone who has seen the three-condition test for a subspace

One line: A subset of a vector space needs three checks, not eight, because every law that says "for all" is already true of its members, so the only thing that can go wrong is an answer landing outside the subset; the same argument, proved once, is also the subgroup test and the subring test.

Eight conditions become three¶

A definition is a test ran the eight conditions of a vector space against five candidates. A few pages later, Axler's Linear Algebra Done Right asks when a subset U of a vector space V is itself a vector space, and the answer is a much shorter list:

additive identity 0 ∈ U.

closed under addition u, w ∈ U implies u + w ∈ U.

closed under scalar multiplication a ∈ F and u ∈ U implies au ∈ U.

Commutativity, both kinds of associativity, the multiplicative identity and both distributive properties are not on the list. It looks like a shortcut someone forgot to justify. It is actually the most useful kind of repetition-avoidance there is: the work done to prove that V is a vector space is reused for every subset of V.

What the program prints¶

Verified output of subsets_inherit_the_laws.py — regenerated by tools/run_examples.py, never hand-typed.

1. THREE CONDITIONS INSTEAD OF EIGHT
   U, a subset of a vector space V, is a subspace when:
     additive identity                    0 is in U
     closed under addition                u, w in U  implies  u + w in U
     closed under scalar multiplication   a a scalar, u in U  implies  au in U

2. FIVE SUBSETS OF R^2
   subset U                   8 equations   3 conditions
   the line y = 2x                   hold   a subspace
   just the origin {(0, 0)}          hold   a subspace
   the half-plane x >= 0             hold   not a subspace
       scalar multiplication: (-2)(1, 2) = (-2, -4) is outside U
   the line y = 2x + 1               hold   not a subspace
       0 in U:                (0, 0) is not in U
       addition:              (0, 1) + (0, 1) = (0, 2) is outside U
       scalar multiplication: (-2)(0, 1) = (0, -2) is outside U
   the two axes together             hold   not a subspace
       addition:              (1, 0) + (0, 1) = (1, 1) is outside U
   The eight equations hold on every sample of every subset, because they
   are computed with the arithmetic of R^2. They cannot tell a subspace from
   a subset that is not one. Only the closure conditions can.

3. WHERE THE TWO 'THERE EXISTS' AXIOMS COME FROM
   Six of the eight say 'for all': true for every vector of R^2, so true for
   every vector of U. Two say 'there exists', and the witness must be IN U:
     additive identity:  0 must be in U                -> condition 1
     additive inverse:   -u must be in U, for each u   -> (-1)u = -u, and
                         U is closed under scalar multiplication
   the line y = 2x:  -(1, 2) = (-1)(1, 2) = (-1, -2),  in U: True
   the half-plane x >= 0:  -(1, 2) = (-1)(1, 2) = (-1, -2),  in U: False
   The inverse of (1, 2) exists in R^2 either way. In the half-plane it is
   outside U, so U has no inverse for (1, 2) of its own.

4. THE SAME TEST FOR A GROUP NEEDS A FOURTH CONDITION
   subset U of the integers       0 in U  closed under +  closed under -
   multiples of 3                    yes             yes             yes   a subgroup
   natural numbers 0, 1, 2, ...      yes             yes              no   not a subgroup
       the inverse of 1 is -1, which is outside U
   A vector space gets inverses from the scalar -1. A group has no scalars,
   so its subgroup test has to ask for inverses separately.

The equations come free¶

Commutativity says u + v = v + u for all u and v in V. If U is a subset of V, then every u and v in U are also in V, so u + v = v + u for them too. There is nothing to check. The same goes for the other five "for all" laws.

Section 2 shows this directly. The eight equations hold on the samples of all five subsets, including the three that are not subspaces. They have to, because every sum and every product is computed with the arithmetic of ℝ², where the laws are already true. The equations cannot tell a subspace from a subset that is not one.

What they cannot see is whether an answer stays in U. An addition on a set, in Axler's definition 1.19, has to give an element of that same set. If u + w leaves U, then + is not an operation on U at all, and U is not a candidate for anything. That is what the closure conditions check, and section 2 has a witness for every one that fails:

The half-plane x ≥ 0 is closed under addition, but not under scalar multiplication: (−2)(1, 2) = (−2, −4) is on the wrong side. Any subset that goes in one direction only fails in the same way.
The line y = 2x + 1 fails all three. It misses the origin, and adding two of its points or scaling one leaves the line. A line is a subspace only if it passes through 0.
The two axes together are closed under scalar multiplication, since scaling a point on an axis keeps it on that axis. They are not closed under addition: (1, 0) + (0, 1) = (1, 1) is on neither axis. Two subspaces put together are usually not a subspace.

The line y = 2x passes. So does the origin on its own, the smallest subspace there is. The only other subspace of ℝ² is ℝ² itself. So every subspace of the plane is the origin, a line through the origin, or the whole plane.

Where the two "there exists" axioms come from¶

Six of the eight conditions say "for all". Two say "there exists": there exists a 0, and each v has an inverse. For those it is not enough that the element exists somewhere in V. It has to be in U, and section 3 shows where each one comes from:

0 ∈ U is the first condition on the list. (It could be replaced by "U is not empty": if u is in U, then 0u is in U by closure, and 0u = 0 in every vector space.)
−u ∈ U comes free from closure under scalar multiplication, because −u = (−1)u, which was the second theorem in a definition is a test. For the line y = 2x, −(1, 2) = (−1, −2) is on the line. For the half-plane, the same vector is outside it. The inverse of (1, 2) exists in ℝ² either way. The half-plane just does not contain it.

A group needs a fourth condition¶

Section 4 runs the same test on subsets of the integers under +. The multiples of 3 contain 0, are closed under +, and are closed under negation: a subgroup. The natural numbers 0, 1, 2, … contain 0 and are closed under + too, but the inverse of 1 is −1, and that is not a natural number. So they are not a subgroup.

A vector space got inverses from the scalar −1. A group has no scalars, so the subgroup test has to ask for inverses as a separate condition: a subset H of a group is a subgroup when it contains the identity and is closed under the operation and under inverses. Many books pack those into one condition, that a · b⁻¹ is in H for all a and b in H.

One proof for all of them¶

An algebra course proves a subgroup test, then a subring test, then a subspace test, and each proof is the argument above with the names changed. There is a single statement behind all of them.

Treat a structure as a set with some operations, counting constants as operations with no inputs (0 and 1) and negation as an operation with one input. Suppose every law is an equation that holds for all members. Then any subset closed under all of the operations satisfies all of the laws, by the argument of section 2. This is the starting point of universal algebra. Garrett Birkhoff proved the full version in 1935. The classes of structures that can be defined by equations alone are exactly the ones closed under three constructions: taking substructures (this lesson), taking products, and taking images under structure-preserving maps (the next lesson).

The fine print is the word equation. A law with a condition in it does not pass down. In a field every member except 0 has an inverse, and "except 0" is not an equation. So a subset of a field can be closed under +, −, × and contain 0 and 1 without being a field. The integers inside the fractions are the example, since 2 has no inverse among the integers. That is the same row, "commutative ring", that the laws of an operation found for the integers.

Run it yourself¶

From the root of your clone of this repository:

python3 06_Algebraic_Structures/subsets_inherit_the_laws/examples/subsets_inherit_the_laws.py

Auf Deutsch: Stichwörter¶

Eine Teilmenge erbt Assoziativität und Kommutativität umsonst; ein Unterraum braucht nur drei Prüfungen, nicht acht.

Stichwörter: Unterraum, Untergruppe, Abgeschlossenheit (closure), geerbte Gesetze, Unterraumkriterium, Teilmenge.