Set Theory: Sets and Functions

Definitions of \(\{\} \in \notin \subset \subseteq = \emptyset\).

Further definitions on \(\cup \cap\), arbitrary, disjoint, pairwise disjoint. Shows how union and intersection are associative, commutative, and distributive. Defines difference, symmetric difference, complement. Shows the duality principle, leading to dual theorems.

Definitions of (real) function \(f\) on \(X\), domain, range, mapping of \(M\) into \(N\), image, preimage, image of \(A\), preimage of \(B\), map into, map onto, one-to-one, one-to-one correspondence, inverse of \(f\).

Theorem 1

\(f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)\)

Theorem 2

\(f^{-1}(A \cap B) = f^{-1}(A) \cap f^{-1}(B)\)

Theorem 3

\(f(A \cup B) = f(A) \cup f(B)\)

Note \(f(A \cap B) \neq f(A) \cap f(B)\). Also note that Theorems 1-3 hold for an arbitrary number of sets.

Definitions of decomposition or partition into classes, a is related to b by the (binary) relation R, equivalence relation, reflexitivity, symmetry, transitivity.

Theorem 4

\(M\) can be partitioned into classes by a relation \(R\) \(\Leftrightarrow\) \(R\) is an equivalence relation on \(M\).

Problems

  1. Show \(A \cup B = A\) and \(A \cap B = A\) \(\Rightarrow\) \(A = B\)

    \(B \subseteq A\) since \(A \cup B = A\) and \(A \subseteq B\) since \(A \cap B = A\). Hence, \(A = B\)

  2. Show \((A - B) \cup B \neq A\)

    Take \(A\) to be the empty set and \(B\) to be any non-empty set.

  3. Let \(A = \{2, 4, ..., 2n, ...\}\) and \(B = \{3, 6, ..., 3n, ... \}\). Find \(A \cap B\) and \(A - B\)

    \(A \cap B = \{6, 12, ..., 6n, ...\}\). \(A - B = \{2, 4, 8, 10, 14, 16, ...\}\)

  4. Prove that \((A - B) \cap C = (A \cap C) - (B \cap C)\) and \(A \triangle B = (A \cup B) - (A \cap B)\)

    Step through using definitions, complements, idempotence, duality principle, distributivity, associativity, commutativity.

  5. Prove \(\cup_{\alpha} A_{\alpha} - \cup_{\alpha} B_{\alpha} \subseteq \cup_{\alpha} (A_{\alpha} - B_{\alpha})\)

    Evident once some thought has been applied.

  6. Let \(A_n\) be the set of all positive integers divisible by \(n\). What are \(\cup_{n = 2}^{\infty} A_n\) and \(\cap_{n = 2}^{\infty} A_n\)?

    \(\cup_{n = 2}^{\infty} A_n = \{2, 3, 4, ..., n, ...\}\)
    \(\cap_{n = 2}^{\infty} A_n = \emptyset\)

  7. What are \(\cup_{n = 1}^{\infty} [a+\dfrac{1}{n}, b-\dfrac{1}{n}]\) and \(\cap_{n = 1}^{\infty} (a-\dfrac{1}{n}, b+\dfrac{1}{n})\)?

    If \(b-a > 1\) \(\cup_{n = 1}^{\infty} [a+\dfrac{1}{n}, b-\dfrac{1}{n}] = (a, b)\)
    If \(b-a \leq 1\) \(\cup_{n = 1}^{\infty} [a+\dfrac{1}{n}, b-\dfrac{1}{n}] = [b-1, a+1]\)
    \(\cap_{n = 1}^{\infty} (a-\dfrac{1}{n}, b+\dfrac{1}{n}) = [a, b]\)

  8. Let \(A_{\alpha}\) be the set of points lying on the curve \(y = \dfrac{1}{x^{\alpha}}\) with \(0 < x < \infty\). What is \(\cap_{\alpha \geq 1} A_{\alpha}\)?

    \((1, 1)\)

  9. \(y = f(x) = \{x\}\) (fractional part of \(x\)). Prove every closed interval of length one has the same image under \(f\). What is this image? Is \(f\) one-to-one? What is the preimage of the interval \(\dfrac{1}{4} \leq y \leq \dfrac{3}{4}\)? Partition the real line into classes of points with the same image.

    Simple enough.

  10. Given set \(M\), let \(\mathcal{R}\) be the set of all ordered pairs \((a, a)\) with \(a \in M\). Let \(aRb \Leftrightarrow (a, b) \in \mathcal{R}\). Interpret \(R\).

    Equality.

  11. Find a binary relation which is:

    1. Reflexive and symmetric, but not transitive.

    2. Reflexive, but neither symmetric nor transitive.

    3. Symmetric, but neither reflexive nor transitive.

    4. Transitive, but neither reflexive nor symmetric.

    Blood relative. Remembers name of (provided everybody knows their own name). Not equal to. Strictly greater than. (Credit to CoveredInChocolate for the first two answers.)

Christian Christiansen.