Tuesday, October 10, 2006

We're Closed. Topic: Algebra/Sets. Level: AIME.

Problem: (1995 Putnam - A1) Let $S$ be a set of real numbers which is closed under multiplication (that is, if $a$ and $b$ are in $S$, then so is $ab$). Let $T$ and $U$ be disjoint subsets of $S$ whose union is $S$. Given that the product of any three (not necessarily distinct) elements of $T$ is in $T$ and that the product of any three elements of $U$ is in $U$, show that at least one of the two subsets $T, U$ is closed under multiplication.

Solution: Let's attack this problem using contradiction. Suppose that both $T$ and $U$ are NOT closed under multiplication. What happens? Well, we then know that there are $a, b \in T$ such that $ab \in U$ (since $ab \in S$ and $ab \not\in T$) and $c, d \in U$ such that $cd \in T$. However, we then have

$abcd = a \cdot b \cdot (cd) \in T$ (three elements in $T$)

$abcd = (ab) \cdot c \cdot d \in U$ (three elements in $U$),

which is a contradiction since $T$ and $U$ are disjoint. Hence at least one of them must be closed under multiplication. QED.

--------------------

Comment: Ha, that wasn't so bad was it. Well it took a bit to come up with, but after just realizing contradiction was an easy way to do it and listing out what you knew, putting everything together was pretty quick. Working with sets is a good way to develop your thinking skills since it's quite theoretical.

--------------------

Practice Problem: Which of the standard operations (addition, subtraction, multiplication, division) are the following sets closed under: (a) the reals, (b) the rationals, (c) the integers, (d) the odd integers, (e) the natural numbers, and (f) powers of $2$. Exclude zero from all of these sets.