Set Theory, Set Relations, Cartesian Products, and Proof Methods

Fundamental Set Definitions and Set Operations

  • Set Operations and Formal Definitions:

    • Intersection: The intersection of two sets AA and BB in a universal set UU contains all elements belonging to both AA and BB:     A∩B={x∈U∣x∈A and x∈B}A \cap B = \{x \in U \mid x \in A \text{ and } x \in B\}

    • Union: The union of two sets AA and BB contains all elements belonging to AA, to BB, or to both:     A∪B={x∈U∣x∈A or x∈B}A \cup B = \{x \in U \mid x \in A \text{ or } x \in B\}

    • Set Difference (Relative Complement): The difference of set BB from set AA consists of all elements that belong to AA but do not belong to BB:     A−B={x∈U∣x∈A and x∉B}A - B = \{x \in U \mid x \in A \text{ and } x \notin B\}

  • Absolute Complement: The complement of a set AA consists of all elements in the universal set UU that are not in AA:   Ac={x∈U∣x∉A}=not AA^c = \{x \in U \mid x \notin A\} = \text{not } A

  • Foundational Theorems on Subsets:

    • Theorem 5.1: For any set BB, the empty set is a subset of BB, and BB is a subset of itself:     ∅⊆BandB⊆B\emptyset \subseteq B \quad \text{and} \quad B \subseteq B

    • Theorem 5.2 (Set Equality Criterion): Let AA and BB be subsets of a universal set UU. The sets AA and BB are equal (A=BA = B) if and only if both mutual subset inclusions hold:     A=B  ⟺  (A⊆B and B⊆A)A = B \iff (A \subseteq B \text{ and } B \subseteq A)

  • Power Sets and Cardinality:

    • Power Set Definition: If AA is a subset of the universal set UU, the power set of AA, denoted P(A)\mathcal{P}(A), is the set whose members are all the subsets of AA:     P(A)={X⊆U∣X⊆A}\mathcal{P}(A) = \{X \subseteq U \mid X \subseteq A\}

    • Cardinality Definition: The cardinality of a finite set AA represents the total number of elements contained in AA, denoted by:     card(A)\text{card}(A)

Proving Set Relationships and Inclusions

  • Element-Chasing Proof Methodology:

    • To establish that A⊆BA \subseteq B, an arbitrary element xx satisfying the defining property of AA (x∈Ax \in A) must be selected.

    • Specific elements cannot be chosen; the selection must be entirely arbitrary to ensure general validity.

  • Worked Example: Subset Inclusion with Multiples (PC 5.8):

    • Given Sets:     A={x∈Z∣∃m∈Z:x=9m}A = \{x \in \mathbb{Z} \mid \exists m \in \mathbb{Z} : x = 9m\}     B={y∈Z∣∃n∈Z:y=3n}B = \{y \in \mathbb{Z} \mid \exists n \in \mathbb{Z} : y = 3n\}

    • Claim: Prove that A⊆BA \subseteq B.

    • Proof:

    • Let x∈Ax \in A.

    • By definition of AA, there exists an integer m∈Zm \in \mathbb{Z} such that:       x=9mx = 9m

    • Rewrite 9m9m by factoring:       x=3⋅(3m)x = 3 \cdot (3m)

    • Since m∈Zm \in \mathbb{Z}, define k=3mk = 3m, where k∈Zk \in \mathbb{Z}.

    • Substituting gives:       x=3kx = 3k

    • Because xx is expressed as 33 times an integer, it satisfies the membership condition of BB:       x∈Bx \in B

    • Therefore, A⊆BA \subseteq B.

  • Proposition 5.10 (Contrapositive Membership):

    • Let A⊆BA \subseteq B.

    • If an arbitrary element satisfies x∈Bcx \in B^c, then by definition x∉Bx \notin B.

  • Since every element of AA must be in BB, having x∉Bx \notin B implies that:     x∉Ax \notin A

    • Consequently, x∈Acx \in A^c, establishing that Bc⊆AcB^c \subseteq A^c.

  • Proposition 5.B: Equivalence of Set Difference and Complement Intersection:

    • Theorem Statement: Let AA and BB be sets. Then:     A−B=A∩BcA - B = A \cap B^c

    • Proof of Direction 1 (A−B⊆A∩BcA - B \subseteq A \cap B^c):

    • Let x∈A−Bx \in A - B.

    • By definition of set difference, x∈Ax \in A and x∉Bx \notin B.

  • Because x∉Bx \notin B, it follows from the definition of complement that x∈Bcx \in B^c.

    • Since x∈Ax \in A and x∈Bcx \in B^c, by definition of intersection:     x∈A∩Bcx \in A \cap B^c

    • Hence, A−B⊆A∩BcA - B \subseteq A \cap B^c.

  • Proof of Direction 2 (A∩Bc⊆A−BA \cap B^c \subseteq A - B):

    • Let x∈A∩Bcx \in A \cap B^c.

    • By definition of intersection, x∈Ax \in A and x∈Bcx \in B^c.

    • Because x∈Bcx \in B^c, it follows that x∉Bx \notin B.

  • Since x∈Ax \in A and x∉Bx \notin B, by definition of set difference:       x∈A−Bx \in A - B

    • Hence, A∩Bc⊆A−BA \cap B^c \subseteq A - B.

    • Conclusion: Both subset inclusions hold, proving A−B=A∩BcA - B = A \cap B^c.

  • Counterexample Analysis: Investigating (A∪B)−B=A(A \cup B) - B = A:

    • Question: Is the equation (A∪B)−B=A(A \cup B) - B = A true for all sets AA and BB?

    • Counterexample Construction:

    • Let A={1,3,5}A = \{1, 3, 5\}.

    • Let B={1,2,3}B = \{1, 2, 3\}.

    • Computations:

    • Compute the union:       A∪B={1,2,3,5}A \cup B = \{1, 2, 3, 5\}

    • Remove the elements of BB:       (A∪B)−B={1,2,3,5}−{1,2,3}={5}(A \cup B) - B = \{1, 2, 3, 5\} - \{1, 2, 3\} = \{5\}

    • Comparison:     {5}≠{1,3,5}\{5\} \neq \{1, 3, 5\}

    • Result: The statement is false in general because (A∪B)−B=A−B(A \cup B) - B = A - B, which equals AA only when A∩B=∅A \cap B = \emptyset.

  • Worked Example: Modular Congruence Subsets (Exercise #3, 5.2):

    • Given Sets:     A={x∈Z∣x≡7(mod8)}A = \{x \in \mathbb{Z} \mid x \equiv 7 \pmod 8\}     B={y∈Z∣y≡3(mod4)}B = \{y \in \mathbb{Z} \mid y \equiv 3 \pmod 4\}

    • Set Elements:     A={…,−9,−1,7,15,23,… }A = \{\dots, -9, -1, 7, 15, 23, \dots\}     B={…,−9,−5,−1,3,7,11,… }B = \{\dots, -9, -5, -1, 3, 7, 11, \dots\}

    • Claim: Prove that A⊆BA \subseteq B.

    • Proof:

    • Let x∈Ax \in A. Then x≡7(mod8)x \equiv 7 \pmod 8.

    • By definition of congruence, there exists m∈Zm \in \mathbb{Z} such that:       x=8m+7x = 8m + 7

    • Decompose 8m+78m + 7 into multiples of 44:       x=4⋅2m+4+3=4(2m+1)+3x = 4 \cdot 2m + 4 + 3 = 4(2m + 1) + 3

    • Let k=2m+1k = 2m + 1. Since m∈Zm \in \mathbb{Z}, k∈Zk \in \mathbb{Z}.

    • Thus, x=4k+3x = 4k + 3, which means:       x≡3(mod4)x \equiv 3 \pmod 4

    • Therefore, x∈Bx \in B, confirming A⊆BA \subseteq B.

  • Disjoint Sets and Proof by Contradiction:

    • Definition: Two sets AA and BB are disjoint if and only if their intersection is empty:     A∩B=∅A \cap B = \emptyset

    • Problem: Let A={x∈Z∣x≡3(mod12)}A = \{x \in \mathbb{Z} \mid x \equiv 3 \pmod{12}\} and B={y∈Z∣y≡2(mod8)}B = \{y \in \mathbb{Z} \mid y \equiv 2 \pmod 8\}. Prove that AA and BB are disjoint.

    • Proof by Contradiction:

    • Assume there exists an integer xx such that x∈A∩Bx \in A \cap B.

    • Since x∈Ax \in A, x≡3(mod12)x \equiv 3 \pmod{12}, so there exists m∈Zm \in \mathbb{Z} such that:       x=12m+3x = 12m + 3

    • Since x∈Bx \in B, x≡2(mod8)x \equiv 2 \pmod 8, so there exists k∈Zk \in \mathbb{Z} such that:       x=8k+2x = 8k + 2

    • Equate the two expressions for xx:       12m+3=8k+212m + 3 = 8k + 2

    • Group terms to analyze algebraic parity:       2(6m+1)+1=2(4k+1)2(6m + 1) + 1 = 2(4k + 1)

    • The left-hand side is of the form 2(integer)+12(\text{integer}) + 1, which is an odd integer.

    • The right-hand side is of the form 2(integer)2(\text{integer}), which is an even integer.

    • Because an odd integer cannot equal an even integer (odd ≠\neq even), a contradiction is reached.

    • Therefore, the assumption is false, and A∩B=∅A \cap B = \emptyset.

  • Investigating Inclusions and Set Hypotheses (Exercise 5.2 #13):

    • Condition (a): Testing if A∩C⊆B∩C  ⟹  A⊆BA \cap C \subseteq B \cap C \implies A \subseteq B

    • If x∈Ax \in A and x∈Cx \in C, then x∈A∩C⊆B∩C  ⟹  x∈Bx \in A \cap C \subseteq B \cap C \implies x \in B.

    • However, if x∈Ax \in A and x∉Cx \notin C, the condition provides no information about whether x∈Bx \in B.

  • Counterexample: Let A={1,2,3,4}A = \{1, 2, 3, 4\}, B=∅B = \emptyset, and C={3}C = \{3\}. Here A∩C={3}A \cap C = \{3\} and B∩C=∅B \cap C = \emptyset, so the premise A∩C⊆B∩CA \cap C \subseteq B \cap C fails.

  • Alternative counterexample satisfying the premise: Let A={1,2,3,4}A = \{1, 2, 3, 4\}, C={3}C = \{3\}, and B={3}B = \{3\}. Then A∩C={3}A \cap C = \{3\} and B∩C={3}B \cap C = \{3\}, so A∩C⊆B∩CA \cap C \subseteq B \cap C holds, but A⊈BA \not\subseteq B because 1∈A1 \in A and 1∉B1 \notin B.

  • Condition (c): Testing if A∪C=B∪C  ⟹  A=BA \cup C = B \cup C \implies A = B

    • Counterexample:

    • Let A={1,2,3,4}A = \{1, 2, 3, 4\}.

    • Let B={1,2,4,5}B = \{1, 2, 4, 5\}.

    • Let C={3,5}C = \{3, 5\}.

    • Evaluate unions:     A∪C={1,2,3,4}∪{3,5}={1,2,3,4,5}A \cup C = \{1, 2, 3, 4\} \cup \{3, 5\} = \{1, 2, 3, 4, 5\}     B∪C={1,2,4,5}∪{3,5}={1,2,3,4,5}B \cup C = \{1, 2, 4, 5\} \cup \{3, 5\} = \{1, 2, 3, 4, 5\}

    • Although A∪C=B∪CA \cup C = B \cup C, A≠BA \neq B because 3∈A3 \in A but 3∉B3 \notin B, and 5∈B5 \in B but 5∉A5 \notin A (3≠53 \neq 5).

  • Hence, the implication is false.

Properties of Set Operations and Algebraic Proofs

  • De Morgan's Laws for Sets:

    • Complement of a Union:     (A∪B)c=Ac∩Bc(A \cup B)^c = A^c \cap B^c

    • Proof of De Morgan's Law for Union:

    • Part 1 ((A∪B)c⊆Ac∩Bc(A \cup B)^c \subseteq A^c \cap B^c):

      • Let x∈(A∪B)cx \in (A \cup B)^c.

      • By definition of complement, x∉A∪Bx \notin A \cup B.

  • By the logical negation of union, x∉Ax \notin A and x∉Bx \notin B.

    • Thus, x∈Acx \in A^c and x∈Bcx \in B^c.

    • By definition of intersection, x∈Ac∩Bcx \in A^c \cap B^c.

  • Part 2 (Ac∩Bc⊆(A∪B)cA^c \cap B^c \subseteq (A \cup B)^c):

    • Let x∈Ac∩Bcx \in A^c \cap B^c.

    • By definition of intersection, x∈Acx \in A^c and x∈Bcx \in B^c.

    • Thus, x∉Ax \notin A and x∉Bx \notin B.

  • Consequently, x∉A∪Bx \notin A \cup B.

    • By definition of complement, x∈(A∪B)cx \in (A \cup B)^c.

      • Generalized De Morgan's Laws across nn Sets:

      • The complement of an arbitrary finite union is the intersection of the complements:       (⋃i=1nAi)c=⋂i=1nAic\left(\bigcup_{i=1}^n A_i\right)^c = \bigcap_{i=1}^n A_i^c

      • The complement of an arbitrary finite intersection is the union of the complements:       (⋂i=1nAi)c=⋃i=1nAic\left(\bigcap_{i=1}^n A_i\right)^c = \bigcup_{i=1}^n A_i^c

      • Both generalized forms can be proven formally using mathematical induction.

  • Distributive Laws (Theorem 5.18):

    • Theorem Statement: For any subsets A,B,CA, B, C of a universal set UU:     A∩(B∪C)=(A∩B)∪(A∩C)A \cap (B \cup C) = (A \cap B) \cup (A \cap C)     A∪(B∩C)=(A∪B)∩(A∪C)A \cup (B \cap C) = (A \cup B) \cap (A \cup C)

    • Element-Chasing Proof of A∩(B∪C)=(A∩B)∪(A∩C)A \cap (B \cup C) = (A \cap B) \cup (A \cap C):

    • Direction 1 (⊆\subseteq):

      • Let x∈A∩(B∪C)x \in A \cap (B \cup C).

      • Then x∈Ax \in A and x∈(B∪C)x \in (B \cup C).

      • Since x∈(B∪C)x \in (B \cup C), either x∈Bx \in B or x∈Cx \in C.

      • Case 1: If x∈Bx \in B, then since x∈Ax \in A, x∈A∩Bx \in A \cap B. Therefore, x∈(A∩B)∪(A∩C)x \in (A \cap B) \cup (A \cap C).

      • Case 2: If x∈Cx \in C, then since x∈Ax \in A, x∈A∩Cx \in A \cap C. Therefore, x∈(A∩C)∪(A∩B)=(A∩B)∪(A∩C)x \in (A \cap C) \cup (A \cap B) = (A \cap B) \cup (A \cap C).

      • In either case, x∈(A∩B)∪(A∩C)x \in (A \cap B) \cup (A \cap C).

    • Direction 2 (⊇\supseteq):

      • Let x∈(A∩B)∪(A∩C)x \in (A \cap B) \cup (A \cap C).

      • Case 1: If x∈A∩Bx \in A \cap B, then x∈Ax \in A and x∈Bx \in B. Since x∈Bx \in B, x∈B∪Cx \in B \cup C. Combining with x∈Ax \in A yields x∈A∩(B∪C)x \in A \cap (B \cup C).

      • Case 2: If x∈A∩Cx \in A \cap C, then x∈Ax \in A and x∈Cx \in C. Since x∈Cx \in C, x∈C∪B=B∪Cx \in C \cup B = B \cup C. Combining with x∈Ax \in A yields x∈A∩(B∪C)x \in A \cap (B \cup C).

      • In either case, x∈A∩(B∪C)x \in A \cap (B \cup C).

  • Algebraic Proof of Set Identity (Theorem 5.20):

    • Target Identity: Prove algebraically that:     A−(B−C)=(A−B)∪(A−Cc)=(A−B)∪(A∩C)A - (B - C) = (A - B) \cup (A - C^c) = (A - B) \cup (A \cap C)

    • Step-by-Step Derivation:

    • Apply the definition of set difference (X−Y=X∩YcX - Y = X \cap Y^c):       A−(B−C)=A∩(B−C)cA - (B - C) = A \cap (B - C)^c

    • Rewrite the internal difference as an intersection with complement:       =A∩(B∩Cc)c= A \cap (B \cap C^c)^c

    • Apply De Morgan's Law and the double complement law ((Cc)c=C(C^c)^c = C):       =A∩(Bc∪C)= A \cap (B^c \cup C)

    • Apply the distributive law of intersection over union:       =(A∩Bc)∪(A∩C)= (A \cap B^c) \cup (A \cap C)

    • Convert the terms back to difference notation:       =(A−B)∪(A∩C)=(A−B)∪(A−Cc)= (A - B) \cup (A \cap C) = (A - B) \cup (A - C^c)

Cartesian Products

  • Definition of Ordered Pairs and Equality:

    • For elements a,c∈Aa, c \in A and b,d∈Bb, d \in B, two ordered pairs are equal if and only if their corresponding coordinates are equal:     (a,b)=(c,d)  ⟺  (a=c and b=d)(a, b) = (c, d) \iff (a = c \text{ and } b = d)

  • Cartesian Product of Sets:

    • The Cartesian product A×BA \times B is the set of all ordered pairs where the first coordinate is from AA and the second coordinate is from BB:     A×B={(a,b)∣a∈A and b∈B}A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}

    • Cartesian Square: The Cartesian product of a set with itself is denoted A2A^2:     A2=A×A={(a,b)∣a∈A and b∈A}A^2 = A \times A = \{(a, b) \mid a \in A \text{ and } b \in A\}

  • Discrete Examples of Cartesian Products:

    • Let A={a,b,c}A = \{a, b, c\} and B={1,2}B = \{1, 2\}.

    • Compute A×BA \times B:     A×B={(a,1),(a,2),(b,1),(b,2),(c,1),(c,2)}A \times B = \{(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)\}

    • Compute B2B^2:     B2={(1,1),(1,2),(2,1),(2,2)}B^2 = \{(1, 1), (1, 2), (2, 1), (2, 2)\}

  • Set Operations with Cartesian Products (Exercise 1h & 1i):

    • Let A={1,2,3}A = \{1, 2, 3\}, B={a,b}B = \{a, b\}, and C={a,c}C = \{a, c\}.

    • Compute A×(B−C)A \times (B - C):

    • Determine B−CB - C:       B−C={a,b}−{a,c}={b}B - C = \{a, b\} - \{a, c\} = \{b\}

    • Compute the product:       A×(B−C)={(1,b),(2,b),(3,b)}A \times (B - C) = \{(1, b), (2, b), (3, b)\}

    • Compute (A×B)−(A×C)(A \times B) - (A \times C):

    • Expand each product:       A×B={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)}A \times B = \{(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)\}       A×C={(1,a),(1,c),(2,a),(2,c),(3,a),(3,c)}A \times C = \{(1, a), (1, c), (2, a), (2, c), (3, a), (3, c)\}

    • Remove common elements from A×BA \times B:       (A×B)−(A×C)={(1,b),(2,b),(3,b)}(A \times B) - (A \times C) = \{(1, b), (2, b), (3, b)\}

    • The evaluation confirms the distribution of Cartesian product over difference:       A×(B−C)=(A×B)−(A×C)A \times (B - C) = (A \times B) - (A \times C)

  • Geometric Interpretation of Cartesian Products:

    • Let continuous intervals be defined as A=[2,5]A = [2, 5] and B=[4,7]B = [4, 7].

    • The product A×BA \times B in the coordinate plane represents the set of points:     A×B={(x,y)∈R2∣2≤x≤5 and 4≤y≤7}A \times B = \{(x, y) \in \mathbb{R}^2 \mid 2 \le x \le 5 \text{ and } 4 \le y \le 7\}

    • Geometrically, this forms a solid rectangle in the Cartesian plane with horizontal span from x=2x = 2 to x=5x = 5 and vertical span from y=4y = 4 to y=7y = 7.

    • Theorem 5.25: Outlines standard distributive and algebraic relationships for Cartesian products across unions, intersections, and set differences.

Mathematical Induction and Number Theory Review

  • Summation Proof by Mathematical Induction:

    • Proposition: Prove that for all n∈Nn \in \mathbb{N}:     1⋅2+2⋅3+3⋅4+⋯+n(n+1)=n(n+1)(n+2)31 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \dots + n(n+1) = \frac{n(n+1)(n+2)}{3}     (Note: The numerator corresponds to the product of 3 consecutive integers).

    • Basis Step (n=1n = 1):

    • Left-hand side:       LHS=1⋅(1+1)=1⋅2=2\text{LHS} = 1 \cdot (1 + 1) = 1 \cdot 2 = 2

    • Right-hand side:       RHS=1⋅(1+1)⋅(1+2)3=1⋅2⋅33=2\text{RHS} = \frac{1 \cdot (1 + 1) \cdot (1 + 2)}{3} = \frac{1 \cdot 2 \cdot 3}{3} = 2

    • Since LHS=RHS=2\text{LHS} = \text{RHS} = 2, the basis step holds.

    • Inductive Step:

    • Inductive Hypothesis: Assume the statement holds for some k∈Nk \in \mathbb{N}:       1⋅2+2⋅3+⋯+k(k+1)=k(k+1)(k+2)31 \cdot 2 + 2 \cdot 3 + \dots + k(k+1) = \frac{k(k+1)(k+2)}{3}

    • Goal: Prove the statement holds for k+1k + 1:       1⋅2+⋯+k(k+1)+(k+1)(k+2)=(k+1)(k+2)(k+3)31 \cdot 2 + \dots + k(k+1) + (k+1)(k+2) = \frac{(k+1)(k+2)(k+3)}{3}

    • Proof Derivation:

      • Substitute the inductive hypothesis into the sum of k+1k+1 terms:         k(k+1)(k+2)3+(k+1)(k+2)\frac{k(k+1)(k+2)}{3} + (k+1)(k+2)

      • Find a common denominator:         =k(k+1)(k+2)+3(k+1)(k+2)3= \frac{k(k+1)(k+2) + 3(k+1)(k+2)}{3}

      • Factor out the common term (k+1)(k+2)(k+1)(k+2) from the numerator:         =(k+1)(k+2)(k+3)3= \frac{(k+1)(k+2)(k+3)}{3}

    • The formula is valid for k+1k + 1. By mathematical induction, the identity is true for all n∈Nn \in \mathbb{N}.

  • Divisibility via Modular Arithmetic:

    • Problem: Determine whether 9n−19^n - 1 is divisible by 88 for all n∈Nn \in \mathbb{N}.

    • Empirical Validation:

    • For n=1n = 1:       91−1=8(divisible by 8)9^1 - 1 = 8 \quad (\text{divisible by } 8)

    • For n=2n = 2:       92−1=81−1=80(divisible by 8)9^2 - 1 = 81 - 1 = 80 \quad (\text{divisible by } 8)

    • General Proof using Modular Arithmetic:

    • Note the base congruence modulo 88:       9≡1(mod8)9 \equiv 1 \pmod 8

    • By Theorem 2.28 (modular power compatibility: if a≡b(modm)a \equiv b \pmod m, then an≡bn(modm)a^n \equiv b^n \pmod m):       9n≡1n(mod8)9^n \equiv 1^n \pmod 8       9n≡1(mod8)9^n \equiv 1 \pmod 8

    • Subtracting 11 from both sides:       9n−1≡0(mod8)9^n - 1 \equiv 0 \pmod 8

    • Hence, 9n−19^n - 1 is divisible by 88 for all n∈Nn \in \mathbb{N}.

  • Congruence of Sum of Squares Modulo 2:

    • Claim: Prove that for all a,b∈Za, b \in \mathbb{Z}:     (a+b)2≡a2+b2(mod2)(a+b)^2 \equiv a^2 + b^2 \pmod 2

    • Algebraic Derivation:

    • Expanding the left side gives:       (a+b)2=a2+2ab+b2(a+b)^2 = a^2 + 2ab + b^2

    • Since 2ab2ab is a multiple of 22, 2ab≡0(mod2)2ab \equiv 0 \pmod 2 for any integers aa and bb.

    • Therefore, (a+b)2≡a2+b2(mod2)(a+b)^2 \equiv a^2 + b^2 \pmod 2.

    • Proof by Exhaustive Case Analysis Modulo 2:

    • Case 1: a≡0,b≡1(mod2)a \equiv 0, b \equiv 1 \pmod 2       (0+1)2=12≡1(mod2)and02+12=1(mod2)(0+1)^2 = 1^2 \equiv 1 \pmod 2 \quad \text{and} \quad 0^2 + 1^2 = 1 \pmod 2

    • Case 2: a≡1,b≡0(mod2)a \equiv 1, b \equiv 0 \pmod 2       (1+0)2=12≡1(mod2)and12+02=1(mod2)(1+0)^2 = 1^2 \equiv 1 \pmod 2 \quad \text{and} \quad 1^2 + 0^2 = 1 \pmod 2

    • Case 3: a≡1,b≡1(mod2)a \equiv 1, b \equiv 1 \pmod 2       (1+1)2=22=4≡0(mod2)and12+12=2≡0(mod2)(1+1)^2 = 2^2 = 4 \equiv 0 \pmod 2 \quad \text{and} \quad 1^2 + 1^2 = 2 \equiv 0 \pmod 2

    • Case 4: a≡0,b≡0(mod2)a \equiv 0, b \equiv 0 \pmod 2       (0+0)2=0≡0(mod2)and02+02=0≡0(mod2)(0+0)^2 = 0 \equiv 0 \pmod 2 \quad \text{and} \quad 0^2 + 0^2 = 0 \equiv 0 \pmod 2

    • Generalization (Freshman's Dream):

    • When pp is any prime number, the binomial coefficients (pk)\binom{p}{k} are divisible by pp for all 1≤k≤p−11 \le k \le p-1, yielding:       (a+b)p≡ap+bp(modp)(a+b)^p \equiv a^p + b^p \pmod p

  • Inequality Proof by Contradiction:

    • Proposition: For all x,y>0x, y > 0 with x≠yx \neq y:     xy+yx>2\frac{x}{y} + \frac{y}{x} > 2

  • Proof by Contradiction:

    • Assume the negation: suppose there exist x,y>0x, y > 0 with x≠yx \neq y such that:       xy+yx≤2\frac{x}{y} + \frac{y}{x} \le 2

  • Multiply both sides by xyxy (valid without changing inequality direction because x>0x > 0 and y>0  ⟹  xy>0y > 0 \implies xy > 0):   x2+y2≤2xyx^2 + y^2 \le 2xy

  • Rearrange the inequality:   x2−2xy+y2≤0x^2 - 2xy + y^2 \le 0   (x−y)2≤0(x - y)^2 \le 0

  • For all real numbers x,yx, y, the square of a real number is non-negative: (x−y)2≥0(x - y)^2 \ge 0.

  • The only way (x−y)2≤0(x - y)^2 \le 0 and (x−y)2≥0(x - y)^2 \ge 0 can both hold is if:   (x−y)2=0  ⟹  x−y=0  ⟹  x=y(x - y)^2 = 0 \implies x - y = 0 \implies x = y

  • This contradicts the premise that x≠yx \neq y.

  • Thus, the assumption is false, concluding that xy+yx>2\frac{x}{y} + \frac{y}{x} > 2.