Home › Mathematics › Topology › Answers to Burt Mendelson's text - "Introduction to topology - third edition" › Questions with answers › Theory of Sets

Sets and subsets

Tue, 2006-10-10 08:20 — ashley
  1. Prove that for any set $ A $, $ \O \subset A $

    Assume $ \O \not \subset A $ then $ \exists_{x \in \O} : x \not \in A $, but this is impossible because $ \O $ is empty, hence our assumption is false and it is true that $ \O \subset A $.

  2. Prove that $ \O \neq \{\O\} $

    Assume $ \O = \{\O\} $ then $ \O \subset \{\O\} $ and $ \{\O\} \subset \O $. Now $ \O \in \{\O\} $ but $ \O \not \in \O $ because $ \O $ contains nothing, therefore $ \{\O\} \not \subset \O $ so the assumption is false and it is true that $ \O \neq \{\O\} $.

  3. Prove that for any set $ A $, $ A \subset A $.

    Clearly $ x \in A \implies x \in A $ so that $ A \subset A $. $ A $ is called an improper subset of $ A $.

  4. Determine whether each of the following statements is true or false:
    1. For each set $ A $, $ A \in 2^A $.

      True. By definition $ 2^A $ is the power set of $ A $ and contains all subsets of $ A $. Since $ A \subset A $ it follows that $ A \in 2^A $.

    2. For each non-empty set $ A $, $ A \subset 2^A $.

      %False. For $ A \subset 2^A $ to be true it must hold that if $ x \in A $ then $ x \in 2^A $. But if $ A $ is any non-empty set it contains elements and an element of $ A $ is not a subset of $ A $, it is therefore not in $ 2^A $ and hence $ A \not \subset 2^A $.

      False. Assume $ A \subset 2^A $, then $ \forall_{x \in A} (x \in A \implies x \in 2^A) $. Consider any such $ x $, $ x \in A $ but $ x \not \subset A $. Therefore the assumption, namely that $ A \subset 2^A $, is false.

    3. For each set $ A $, $ \{A\} \subset 2^A $.

      True. $ \{A\} $ contains only the element $ A $ and $ A \subset A $ so $ A \in 2^A $. Everything in $ \{A\} $ is thus in $ 2^A $ so it follows from the definition of subset that $ \{A\} \subset 2^A $.

    4. For each set $ A $, $ \O \in 2^A $.

      True. It was proven above that for any set $ A $, $ \O \subset A $. $ 2^A $ contains all subsets of $ A $ by definition, $ \O \subset A $, therefore $ \O \in 2^A $.

      %Since $ 2^A $ contains all subsets of $ A $ it clearly contains $ \O $.

    5. For each set $ A $, $ \O \subset 2^A $.

      True. $ \O $ is a subset of any set $ A $ therefore $ \O \subset 2^A $ irrespective of $ A $.

    6. There are no members of the set $ \{\O\} $.

      False. The set $ \{\O\} $ contains the element $ \O $.

    7. Let $ A $ and $ B $ be sets. If $ A \subset B $, then $ 2^A \subset 2^B $.

      %True. Assume that it is not true that if $ A \subset B $, then $ 2^A \subset 2^B $. It follows that there exists a subset $ X $ of $ A $ which is not a subset of $ B $, but since any element in $ A $ is also in $ B $, this is impossible. By the same construction steps that we apply to the elements of $ A $ to construct $ X $ we can construct $ X $ from the elements of $ A $ as they occur in $ B $. Therefore the assumption is false and it is true that if $ A \subset B $, then $ 2^A \subset 2^B $.

      True. Let $ A \subset B $ and assume $ 2^A \not \subset 2^B $. By the assumption, $ \exists_{X \in 2^A} : X \not \in 2^B $. Consider this $ X $, by definition of $ 2^A $, $ X \subset A $ and therefore $ \forall_{x \in X} (x \in X \implies x \in A) $ but $ A \subset B $ which means $ \forall_{x \in A} (x \in A \implies x \in B) $, therefore $ \forall_{x \in X} (x \in X \implies x \in A \implies x \in B) $ which by definition means that $ X \subset B $.

      Now if $ X \subset B $ then by definition of $ 2^B $, $ X \in 2^B $ but this is a contradiction since it was claimed that $ X \not \in 2^B $. Therefore the assumption, namely that $ 2^A \not \subset 2^B $ given $ A \subset B $, is false, and it is therefore true that if $ A \subset B $, then $ 2^A \subset 2^B $.

    8. There are two distinct objects that belong to the set $ \{\O,\{\O\}\} $.

      True since $ \O $ and $ \{\O\} $ are distinct objects and they belong to the set.

  5. Let $ A $,$ B $,$ C $ be sets. Prove that if $ A \subset B $ and $ B \subset C $ then $ A \subset C $.

    If $ B \subset C $, then $ \forall_{x \in B} (x \in C) $, and if $ A \subset B $, then $ \forall_{x \in A} (x \in B) $. It follows from the former, given the latter, that $ \forall_{x \in A} (x \in C) $, and hence $ A \subset C $.

    Alternative proof: If $ A \subset B $ then $ x \in A \implies x \in B $, and if $ B \subset C $ then $ x \in B \implies x \in C $. Thus $ x \in A \implies x \in B \implies x \in C $ and hence $ x \in A \implies x \in C $ thus $ A \subset C $.

    Alternative proof (by contradiction): Assume that $ A \subset B $ and $ B \subset C $ but $ A \not \subset C $, this means that $ \exists_{x \in A} : x \not \in C $. Taking this $ x $ since $ A \subset B $, $ x \in B $, and since $ B \subset C $, $ x \in C $ which is a contradiction. Therefore the assumption is false, namely that $ A \not \subset C $, and hence it is true that if $ A \subset B $ and $ B \subset C $, then $ A \subset C $.

  6. Let $ A_1,...,A_n $ be sets. Prove that if $ A_1 \subset A_2, A_2 \subset A_3, ..., A_{n-1} \subset A_n $ and $ A_n \subset A_1 $, then $ A_1 = A_2 = ... = A_n $.

    Proof by induction on $ n $.

    The base case, $ n=1 $ is trivially true since $ A_1 = A_1 $. %For the base case $ n=1 $, $ A_1 \subset A_2 $ and $ A_2 \subset A_1 $, therefore by definition of set equality $ A_1 = A_2 $.

    Now it is required to show that for any $ n \geq 1 $, if the claim holds for $ n $ then it holds for $ n+1 $. For $ n+1 $ we have

    \[ A_1 \subset A_2 \subset ... \subset A_n \subset A_{n+1} \]

    and $ A_{n+1} \subset A_1 $. Now $ A_1 \subset A_2 \subset .. \subset A_n $ and $ A_n \subset A_{n+1} \subset A_1 $ which means that $ A_n \subset A_1 $, therefore $ A_1 \subset A_2 \subset ... \subset A_n $ and $ A_n \subset A_1 $ both hold. Given that the claim holds for $ n $ it follows that

    \[ A_1 = A_2 = ... = A_n \]

    and therefore because $ A_1 = A_n $ that $ A_1 \subset A_{n+1} $ because $ A_n \subset A_{n+1} $. Given that it is also true that $ A_{n+1} \subset A_1 $, this means that $ A_{n+1} = A_1 $ and since $ A_1 = A_2 = ... = A_n $ it follows that

    \[ A_1 = A_2 = ... = A_{n+1} \]

    and the induction step holds.