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

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

q

## Exercises

Prove each of the following.

1. 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).

2. The function f:Zm -> Zm given by f(x) = x2 + x is well defined.

Next==>The Pigeon Hole Principle

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