What Does "Well Defined" Mean?
What does "Well Defined" Mean?
Sooner or later you will have to prove that something is "well defined". So what does this mean? Let's look at an example.
Example: Congruence Arithmetic
For integers a and b and a positive integer m, we say that a is congruent to b modulo m, written a = b mod(m), if a - b is evenly divisble by m. Another way of saying this is there is another integer k such that a = b + k m. For example, 1749 = 15 mod(17) because 1749 = 15 + (102)(17). We like to think of a and b as representing the same "number" modulo m. So there are m "numbers" in this system and they are 0, 1, 2, ..., m-1. For example, m = 0 mod(m) so we son't have to list 0.
It turns out that we can do arithmetic with these new "numbers". For example, we can define addition modulo m by standard addition. But there is a potential problem. What if a = b mod(m) and c = d mod(m), we should get the same result, modulo m, by adding a + b or c + d.
Theorem. Addition is well defined modulo m, that is, if a = b mod(m) and c = d mod(m), then (a+c) = (b+d) mod(m).
Strategy. What do we have to prove? (a+c) = (b+d) mod(m). What does this mean? It means we must show there is an integer k such that a+c = (b+d) + k m. What are we assuming? a = b mod(m) and c = d mod(m). This means there are integers k1 and k2 such that a = b + k1 m and c = d + k2m. What do we do? We can add these last two equations together to get: (a+c) = (b+d) + (k1+k2)m. So if we were to let k = k1 + k2, we would have what we want. Now we se what to do. So we write the proof.
Proof. By our assumption, there are integers k1 and k2 such that a = b + k1 m and c = d + k2m. Adding these two equations together gives us (a+c) = (b+d) + (k1+k2)m, which, by definition, means (a+c) = (b+d) mod(m).
So "well defined" means that the definition being made has no internal inconsistencies and is free of contradictions. To better understand this idea, let's look at an example where a definition turns out not to be well defined.
Example: Not Well Defined
Using modular arithmetic, consider division. For integers it makes since to talk about x/2 when x is even. Does this make since modulo 2? For example, let x = 2. In mod (2) arithmetic, the "number" 2/2 should be the unique solution (y) to the equation 2y = 2 mod (2). But, as you can see, any integer y will satisfy this equation. That is, x/2 is not well defined.
Example:Functions Modulo m
In the previous two examples, we looked at the "numbers" modulo m. In this system there are only m "numbers", represented by 0, 1, ..., m-1. It is traditional to call this set Zm. For example, Z4 has 4 elements, represented by 0, 1, 2, 3. Remember, all other integers are just other names for these 4. For example, 13 = 1 mod(4) and - 13 = 3 mod(4).
Theorem. The function f:Z4 -> Z4, given by f(x) = 2x+1 is well defined.
Strategy. It is easy to see that f(0) = 1, f(1) = 3, f(2) = 5 = 1 mod(4) and f(3) = 7 = 3 mod(4). What do we need to prove? We need to prove that f(a) = f(b) mod (4). That is, f(a) - f(b) is evenly divisble by 4, that is, (2a+1) - (2b+1) = 2(a - b) is evenly divisble by 4. What is our assumption? We are assuming a = b mod(4). What does this mean? It means that a - b is evenly divisble by 4. We can see immediately that our assumption implies 2(a - b) is divisible by 4, which is what we wanted.
Proof. If a = b mod(m), then (a - b) is divisble by 4. Hence so is (2a + 1) - (2b + 1), that is f(a) = f(b) mod (m).
Prove each of the following.
- Multiplication is well defined in arithmetic modulo m. That is, if a = b mod(m) and c = d mod(m), then (a c) = (b d) mod(m).
- The function f:Zm -> Zm given by f(x) = x2 + x is well defined.
Next==>The Pigeon Hole Principle
Proofs by Exhaustion (Case by Case)
Back to Proofs