80-110: The Nature of Mathematical Reasoning

Carnegie Mellon University

Spring 2015

Homework 9

Due Monday, April 20

  1. Give an example of a finite set S, and an infinite set T such that S is a subset of T.
  2. Is your infinite set T from the previous problem countable or uncountable? Explain!
  3. Give an example of a countable set that we did NOT discuss in class (ie, not the natural numbers, integers, or rationals). Explain why it is countable.
  4. Recall that the intersection of two sets A and B is the set of objects that are elements of both A and B. If S and T are countable sets, is it possible for their intersection to be uncountable? If S and T are uncountable, is it possible for their intersection to be countable? Explain!
  5. The symbols ∪ (union) and ∩ (intersection) look a lot like the logical symbols for or and and, respectively. Recall that in propositional logic, the identities (A & (B v C)) <=> ((A & B) v (A & C)) and (A v (B & C)) <=> ((A v B) & (A v C)) hold. If we replace v with ∪ and & with ∩, what do these identities say about sets? Are they still true? (Hint: think about sets as Venn diagrams. If A and B are circles, A ∩ B is the area inside both A and B.)