Power Sets, Cartesian Products, and Partitions

  1. Sets, Sequences, and Ordered Tuples.

    1. Definitions:

      A set is a list of elements or terms, which is completely determined or defined by its elements, and the order in which the elements are listed is irrelevant. We enclose the elements of a set in braces.

      A sequence is a list of elements or terms, which is determined or defined by its elements and the order in which they are listed.

      An ordered n-tuple is a list of n elements or terms, which is determined or defined by its elements and the order in which they are listed. We enclose the elements of an ordered tuple in parentheses. An ordered 2-tuple is called an ordered pair, an ordered 3-tuple is called an ordered triple.

    2. Examples:

      These sets are the same: {1, 5, 3, 17} and {17, 1, 3, 5}

      These sequences are not the same: 1, 5, 3, 17 and 17, 1, 3, 5

      These ordered pairs are not the same: (5, 3) and (3, 5)

  2. Power Set.

    1. Definition: If S is a set, then the power set of S is the set of all subsets of S.

    2. Notation: We will use script P to denote power set. Thus, we will write power set(S) for the power set of S.

    3. Examples:

      1. Let S = {1, 5}. Then power set(S) = {empty set, {1}, {5}, S}, a set with 4 elements.

      2. Let S = empty set. Then power set(S) = ?

      3. Let S = {empty set}. Then power set(S) = ?

      4. Let S = {x, y, z}. Then power set(S) = ?

  3. Cartesian Product of Sets.

    1. Definition: If A and B are sets, then the cartesian product of A and B is the set of all ordered pairs (a, b), such that a is in A and b is in B.

    2. Notation: We will use cross product to denote the cartesian product, and we will read A cross product B as A cross B.

    3. A cross product B = {(a, b) | a element of A and b element of B}

    4. Examples:

      1. Let A = {1, 5} and B = {17, 4}. Then A cross product B = {(1, 17), (1, 4), (5, 17), (5, 4)}

      2. Let A = {x, y} and B = {17, 4}. Then A cross product B = ?

      3. Let A = {17, 4}. Then A cross product A = ?

      4. Let A = {1, 5, 17, 4, -45, 3019, -2} and B = {17, 4, -13, 12}.
        Then how many elements are there in the set A cross product B?

  4. Disjoint Sets, Partition of a Set.

    1. Definition: Two sets are disjoint if they have no elements in common.
      Thus, two sets A and B are disjoint if and only if A intersection B = empty set.

    2. Definition: Sets A1, A2, ..., An are mutually disjoint (or pairwise disjoint, or nonoverlapping) if for all i, j in 1, 2, ..., n, Ai and Aj are disjoint whenever i not equal j.

      Thus, A1, A2, ..., An are mutually disjoint if and only if for all i, j element of {1, 2, ..., n} i not equal j implies A intersection B = empty set

    3. Definition: A set of nonempty sets {A1, A2, ..., An} is a partition of a set A if:
      1. A = A1 union A2 union ... union An
      2. A1, A2, ..., An are mutually disjoint
      Note: In this case we would say that A is a union of mutually disjoint subsets.

    4. Examples:

      1. A = {5, 17, 4, 3}, A1 = {17}, A2 = {5, 3}, A3 = {4}
        Is {A1, A2, A3} a partition of A?

      2. A = {5, 17, 4, 3}, A1 = {17}, A2 = {4, 5, 3}, A3 = empty set
        Is {A1, A2, A3} a partition of A?

      3. B = integers
        B1 = {n element of integers | there exists k element of integers | n = 2k}, the even integers
        B2 = {n element of integers | there exists k element of integers | n = 2k+1}, the odd integers
        Is {B1, B2} a partition of B?

      4. S = integers
        C1 = integers+, the positive integers
        C2 = integers-, the negative integers
        C3 = {0}
        Is {C1, C2, C3} a partition of S?

      5. N = integers+, the positive integers, aka natural numbers {1, 2, 3, ...}
        P = {n element of integers+ | the only positive divisors of n are n and 1}, the prime numbers
        C = {n element of integers+ | there is a positive divisor of n other than n and 1}, the composite numbers
        Is {P, C} a partition of N?

      6. P = the xy plane
        Q1 = the upper left quadrant
        Q2 = the upper right quadrant
        Q3 = the lower right quadrant
        Q4 = the lower right quadrant
        Is {Q1, Q2, Q3, Q4} a partition of P?