Use of induction in the proof of the Chinese Remainder Theorem

[Hill]

Consider the following proof:

My question is, does it in fact use induction?

It says, "Assume now that the theorem is true for k-1 elements...," but I don't think it uses this assumption to prove that it is true for k elements, which would be an induction step.

 

[fresh_42]

It uses induction even if a bit hidden. I think we need induction for the repetitive application of A.3.10 to find all $x_i.$

 

[mathwonk]

Do you like this argument: the natural map Z---> Z/d1 x....xZ/dk, sends n to 0 iff each dj divides n, iff their product does (since they are relatively prime). Hence the induced map from Z/(d1.....dk) is injective, hence also surjective. Qed.

 

[Hill]

Do you like this argument: the natural map Z---> Z/d1 x....xZ/dk, sends n to 0 iff each dj divides n, iff their product does (since they are relatively prime). Hence the induced map from Z/(d1.....dk) is injective, hence also surjective. Qed.

I am not sure. In this argument, e.g., Z/d1 has d1 elements, while in the Theorem, r1 can be anything.

 

[mathwonk]

Oh wait! forgive me, your theorem is stated for R any domain. My argument is only for the integers!

But in that case, the theorem says exactly that the map
Z/(d1....dk)--->Z/d1x....Z/dk is surjective; i.e. for every r1,...,rk, there is an a in Z/(d1...dk) that maps to the k-tuple ([r1],...,[rk]). i.e. there exists an a in Z such that a is equivalent to every rj, mod dj, i.e. such that for every j, a-rj is a multiple of dj. But probably you knew that case, where the argument is easier by finiteness of the quotient rings involved.

 

[mathwonk]

ok here is a general argument. by hypothesis, for all j ≥ 2, we may choose cj, bj such that cjd1 + bjdj = 1. Now multiply the left hand sides all together getting a big product = 1, and let a1 = the product of just the terms bjdj, for j≥2. then a1 is one term of the big product, the only term not divisible by d1. hence a1 ≈ 1 (mod d1), and a1 ≈ 0 (mod dj, all j≥2). Hence a1 maps to (1,0,...,0) under the map R--->R/d1x...xR/dk. Similarly we can find elements a2,...,ak mapping to (0,1,0,....,0), and ... to (0,....,0,1). Since the image of the map contains all R-linear combinations of these elements, and they generate, the map
R--->R/d1x...xR/dk is surjective*. Qed.
(note use of ..... instead of induction!)

*more precisely, given r1,...,rk, the element a = r1a1+...+rkak maps to ([r1],...,[rk]).

 

[Hill]

ok here is a general argument. by hypothesis, for all j ≥ 2, we may choose cj, bj such that cjd1 + bjdj = 1. Now multiply the left hand sides all together getting a big product = 1, and let a = the product of just the terms bjdj, for j≥2. then a is one term of the big product, the only term not divisible by d1. hence a ≈ 1 (mod d1), and a ≈ 0 (mod dj, all j≥2). Hence e maps to (1,0,...,0) under the map
R--->R/d1x...xR/dk. Similarly we can find elements mapping to (0,1,0,....,0), and ... to (0,....,0,1). Since the image of the map contains all R-linear combinations of these elements, and they generate, the map R--->R/d1x...xR/dk is surjective. Qed.
(note use of ..... instead of induction!)

Yes, I like the argument.
(However, using .... does not constitute mathematical induction.)

 

[mathwonk]

I'm not an expert on induction, and I tend to skip it when the result looks true, but it can be very powerful. Still it probably needs to be used to give complete proofs of many things I skip over. Certainly the use of ellipsis does not constitute induction, but their use can sometimes disguise the absence of an inductive argument. E.g. when I assume that in a product of form (a1+b1)(a1+b2)...(a1+bk), that every term of the expansion except (b1...bk) is divisible by a1, this probably needs induction to actually prove. In fact even defining these products uses induction, since multiplication in a ring is only given for two terms. In fact to prove the product (b1...bk) makes sense, without further information, one needs also to use associativity, which is not true for all multiplications. I.e. from the associativity axiom that (ab)c = a(bc) for any three elements, it requires an inductive argument that also (b1....bk) has only one value, no matter how we associate it into products of two terms at a time. One can do this by induction e.g. on the number of factors , but I do not recommend it. (In the case of addition, this is Prop. 5.1, page 6, of my copy of Advanced Calculus, by Spencer, Steenrod, and Nickerson, the only book in which I have ever seen this statement actually proved.)