Parity and Set Theory Proofs: Even, Odd, Absolute Value Identities

Parity and Set Theory Proofs

1. Direct proof: odd + even is odd

Statement: If x is an odd integer and y is an even integer, then x + y is odd.

Proof: Suppose x = 2k + 1 and y = 2l for integers k, l. Then
x + y = 2k + 1 + 2l = 2(k + l) + 1, which is of the form 2·(integer) + 1, hence odd. ∎

2. Contrapositive proof: even implies next is odd

Theorem: If n is an even integer, then n + 1 is odd.

Proof by contraposition: The contrapositive is: If n + 1 is not odd (i.e., even), then n is not even (i.e., odd). Suppose n + 1 is even. Then n + 1 = 2k for some integer k. Thus n = 2k − 1 = 2(k − 1) + 1, which is odd. Therefore the contrapositive is true, and so the original implication holds. ∎

3. Proof by contradiction: even implies next is odd

Theorem: If n is an even integer, then n + 1 is odd.

Proof by contradiction: Assume for contradiction that n is even and n + 1 is even. Write n = 2k and n + 1 = 2l for integers k, l. Then 2k + 1 = 2l, which implies an odd number equals an even number — a contradiction. Hence n + 1 must be odd. ∎

4. Equivalent parity of n and n²

Theorem: n is even if and only if n² is even.

Proof:

• If n is even, write n = 2k. Then n² = (2k)² = 4k² = 2(2k²), so n² is even.
• If n is odd, write n = 2k + 1. Then
  n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd.

Therefore, n is even exactly when n² is even. ∎

5. Product of two evens is multiple of 4

Statement: If m and n are even integers, then mn is a multiple of 4.

Proof: Write m = 2k and n = 2l for integers k, l. Then mn = (2k)(2l) = 4kl, which is divisible by 4. ∎

6. Absolute value: |xy| = |x| |y|

Statement: For real numbers x and y, |xy| = |x|·|y|.

Recall: The absolute value |a| equals a if a ≥ 0 and equals −a if a < 0.

Proof: Consider signs of x and y.

• If both x and y are nonnegative, then |xy| = xy = |x|·|y|.
• If one of x or y is negative and the other nonnegative, then xy ≤ 0 and |xy| = −xy. Also exactly one of |x| or |y| introduces a negation, so again |xy| = |x|·|y|.
• If both are negative, say x = −u, y = −v with u, v ≥ 0, then xy = uv ≥ 0 and |xy| = uv = |x|·|y|.

In all cases |xy| = |x|·|y|. ∎

Set identities

A − (B ∩ C) = (A − B) ∪ (A − C)

Problem: Prove or disprove: A 6(B 6 C) = (A 6 B) 6 (A 6 C).

Proof: We show both inclusions.

First, let x ∈ A 6 (B 6 C). Then x ∈ A and x ∉ (B 6 C). The latter means not(x ∈ B and x ∈ C), so x ∈ A and (x ∉ B or x ∉ C). If x ∉ B then x ∈ (A 6 B); if x ∉ C then x ∈ (A 6 C). In either case x ∈ (A 6 B) 6 (A 6 C). Thus
A 6 (B 6 C) 81 (A 6 B) 6 (A 6 C).

Second, let x ∈ (A 6 B) 6 (A 6 C). Then x ∈ A and (x ∉ B or x ∉ C). Hence x ∉ (B 6 C), and so x ∈ A 6 (B 6 C). Therefore
(A 6 B) 6 (A 6 C) 81 A 6 (B 6 C).

Combining the two inclusions gives the equality
A 6 (B 6 C) = (A 6 B) 6 (A 6 C). ∎

Logical equivalences and De Morgan's Law

Below is a clear sequence of logical equivalences that underpins De Morgan's laws for sets. Let x be an arbitrary element.

1. x ∈ A and x ∉ (B ∩ C) — definition of A \ (B ∩ C).
2. Equivalently, x ∈ A and not(x ∈ B and x ∈ C).
3. By De Morgan's law for logical connectives: not(P and Q) ↔ (not P) or (not Q). So
   x ∈ A and (x ∉ B or x ∉ C).
4. Distribute conjunction over disjunction:
   (x ∈ A and x ∉ B) or (x ∈ A and x ∉ C).
5. These two disjuncts are exactly x ∈ (A \ B) and x ∈ (A \ C), so
   x ∈ (A \ B) or x ∈ (A \ C), i.e. x ∈ (A \ B) 6 (A \ C).

Thus the chain of equivalences shows the identity and demonstrates the role of De Morgan's laws in set algebra.