a. Prove that powerset(A ∩ B) = powerset(A) ∩ powerset(B). b. Let aperm: N x N -> N, where aperm(m, n) = min(m, n) for all natural numbers m and n. Using induction, prove that max(m, n) + min(m, n) = m + n for all natural numbers m and n.

GATE 2001 · Discrete Mathematics · Set Theory · medium

Answer: Both proofs are complete; the identities P(A∩B) = P(A)∩P(B) and max(m,n)+min(m,n) = m+n hold for all sets A, B and all natural numbers m, n.

1. Prove P(A ∩ B) = P(A) ∩ P(B) by element chasing: (⊆) Let X ∈ P(A∩B). Then X ⊆ A∩B. For any x ∈ X, x ∈ A and x ∈ B, so X ⊆ A and X ⊆ B, giving X ∈ P(A) and X ∈ P(B), hence X ∈ P(A)∩P(B). (⊇) Let X ∈ P(A)∩P(B). Then X ⊆ A and X ⊆ B. Every x ∈ X satisfies x ∈ A and x ∈ B, so x ∈ A∩B, meaning X ⊆ A∩B, thus X ∈ P(A∩B). Both inclusions give equality.
2. Prove max(m,n) + min(m,n) = m + n by induction on m: Base: m=0. max(0,n)=n, min(0,n)=0, so max+min=n+0=n=0+n. True. Step: Assume max(m,n)+min(m,n)=m+n for all n. Consider m+1 and any n. Case 1: n <= m+1. Then max(m+1,n)=m+1, min(m+1,n)=n, sum=(m+1)+n. Case 2: n > m+1. Then max(m+1,n)=n, min(m+1,n)=m+1, sum=n+(m+1). Both equal (m+1)+n. QED.