Linear Algebra: Set Theory

In the late nineteenth century, Georg Cantor was the first to realize the potential usefulness of investigating properties of sets in general as distinct from properties of the elements that comprise them. Many mathematicians of his time resisted accepting the validity of Cantor’s work. Now, however, abstract set theory is regarded as the foundation of mathematical thought. All mathematical objects (even numbers!) can be defined in terms of sets, and the language of set theory is used in every mathematical subject.

29 flashcards · Mathematics · by lakesare

1. Express Cartesian product AxB in a set-builder notation.

2. Express a set of { 3, 4, 5... } using a set builder notation.

   { x ∈ Z | x >= 3 }

3. What is set, how is it denoted?

   Collection of unordered elements: {6, 11} = {11, 6} = {11, 6, 6, 11}

4. What is a Cartesian product?

   Operation on two sets, that returns a set of 2-tuples, which contain all possible combinations of elements between A and B.

5. What is a Cartesian product of { a, b } x { 5 } sets?

   { (a, 5), (b, 5) } Links: exercises

6. Give an example of a set that has a closure under a + operation.

   A set of integers: Z, because: 2 + 3 + 5 = 10 [all are integers] No matter what integers we +, the result will always be an integer again. A set has closure under an operation if performance of that operation on members of the set always produces a member of the same set.

7. A is a subset of B. Express it with notation!

8. Name 2 subsets of a set A.

   ∅ (empty set) A (set itself)

9. but B has one element that's not in A. What's A?

   A is a proper subset of B. Some notate it as ⊂, some as ⊊.

10. A = { -43, 3, 3, 3, 3, Pi } What's the cardinality of A?

    Cardinality as the amount of distinct elements in a finite set. 3.

11. How many subsets are there in a set of { 5 elements }? Why?

    25. Every subset of a set can be represented as a binary string, as in: Set: { bean, carrot, tomato } Subset: { 0, 1, 0 } - if we only take carrot So amount of subsets = amount of 5-bit binary strings.

12. What's a P({ 1, 2 })?

    Power set of { 1, 2 }! That is, a set of all subsets of { 1, 2 }. That is, { ∅, { 1, 2 }, { 1 }, { 2 } }.

13. What is a complement of set A = { 1, 5 }?

    Complement of A only makes sense in relation to some A's superset, e.g. U. A' = { x ∈ U | x ∉ A }

14. Express in set notation ({ ... }): A ∪ B A ∩ B B - A A'

    A ∪ B = { x ∈ U | x ∈ A or x ∈ B } A ∩ B = { x ∈ U | x ∈ A and x ∈ B } B − A = { x ∈ U | x ∈ B and x ∉ A } A' = { x ∈ U | x ∉ A }.

15. How are those called: A ∪ B A ∩ B B - A A'

    A ∪ B - union A ∩ B - intersection B - A - difference A' - complement

16. A and B are disjoint. Express this in math notation!

    A ∩ B = ∅.

17. Sets are frequently represented by Venn diagrams. What's the alternative representation?

    Membership table (like truth tables for boolean values). Sets can be partitioned into disjoint regions: And each region can be encoded with a 3-bit string (this region is a ⊆ of A? of B? of C?): Second row: Region R = { x | x ∈ A and x ∉ B } Is this region a subset of A ∩ B then? R ⊆ (A ∩ B)? No! We write in 0.

18. Describe { 2t | t ∈ Z and 0 <= t <= 5 } by the listing method.

    { 1, 2, 4, 8, 16, 32 }

19. Let A, B be subsets of a universal set U. Construct a membership table for: (A-B)' and A' ∪ B.

    These sets are equal.

20. Prove that (A' ∪ B')' = A ∩ B.

    Using De Morgan's Law ( (a or b)' = a' and b' ): (A' ∪ B')' = A'' ∩ B'' = A ∩ B.

21. Why is Cartesian product called a product?

    A × B = C Because amount of tuples in C is equal to the amount of elements in A, multiplied by the amount of elements in B. Let A = {1, 2, 3} and B = {u, v}.How many elements are in A × B, B × A, and B × B?A × B has six elements. Note that this is the number of elements in A times the number of elements in B. B × A has six elements, the number of elements in B times the number of elements in A. B × B has four elements, the number of elements in B times the number of elements in B.

22. Why is the Cartesian plane called so?

    R × R is the set of all ordered pairs (x, y) where both x and y are real numbers.

23. Prove that A ⊆ B: A = {m ∈ Z | m = 6r + 12 for some r ∈ Z} B = {n ∈ Z | n = 3s for some s ∈ Z}

    Suppose x is a particular but arbitrarily chosen element of A. Therefore, x is an element of B.

24. How to prove that set A = set B?

    We must prove that: A ⊆ B B ⊆ A

25. Define sets A and B as follows: A = {m ∈ Z | m = 2a for some integer a} B = {n ∈ Z | n = 2b − 2 for some integer b} Is A = B?

    1. Prove A ⊆ B Suppose x is a particular but arbitrarily chosen element of A. We must show that x ∈ B. By definition of B, this means we must show that x = 2·(some integer) − 2. 2. Prove B ⊆ A

26. What can be considered partition of set A?

    A = A1 ∪ A2 ∪ A3... Sets A1, A2, A3,... are mutually disjoint.

27. Let A = {1, 2, 3, 4, 5, 6}, A1 = {1, 2}, A2 = {3, 4}, and A3 = {5, 6}. Is {A1, A2, A3} a partition of A?

    Yes. A = A1 ∪ A2 ∪ A3 the sets A1, A2, and A3 are mutually disjoint.

28. Find (A1 × A2) × A3

    (A1 × A2) × A3 = {(u, v)| u ∈ A1 × A2 and v ∈ A3} = {((x, 1), a), ((x, 2), a), ((x, 3), a), ((y, 1), a), ((y, 2), a), ((y, 3), a), ((x, 1), b), ((x, 2), b), ((x, 3), b), ((y, 1), b), ((y, 2), b), ((y, 3), b)}

29. Find A1 × A2 × A3

    A1 × A2 × A3 = {(u, v, w)| u ∈ A1, v ∈ A2, and w ∈ A3} = {(x, 1, a), (x, 2, a), (x, 3, a), (y, 1, a), (y, 2, a), (y, 3, a), (x, 1, b), (x, 2, b), (x, 3, b), (y, 1, b), (y, 2, b), (y, 3, b)}