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 k_{1} and k_{2} such that a = b + k_{1} m and c = d + k_{2}m. What do we do? We can add these last two equations together to get: (a+c) = (b+d) + (k_{1}+k_{2})m. So if we were to let k = k_{1} + k_{2}, we would have what we want. Now we se what to do. So we write the proof.

**Proof.** By our assumption, there are integers k_{1} and k_{2} such that a = b + k_{1} m and c = d + k_{2}m. Adding these two equations together gives us (a+c) = (b+d) + (k_{1}+k_{2})m, which, by definition, means (a+c) = (b+d) mod(m).

q

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.
q

## 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 Z_{m}. For example, Z_{4} 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:Z_{4} -> Z_{4}, 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).

q

## Exercises

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:Z
_{m} -> Z_{m} given by f(x) = x^{2} + x is well defined.

** Next==>**The Pigeon Hole Principle

**<==Back To
**Proofs by Exhaustion (Case by Case)

Back to Proofs