Fundamentals of Set Theory

Introduction to Set Theory

Set theory forms the foundation of modern mathematics. Understanding how to describe, combine, and manipulate sets is essential for anyone studying mathematics, computer science, or related fields. This course will walk you through the fundamental concepts tested in a typical introductory quiz, providing clear explanations, examples, and memory aids to help you master the material.

1. Set Builder Notation

Set builder notation is a concise way to describe a set by specifying a property that its elements must satisfy. The general form is:

Set = { x | property of x }

For example, the set of all odd positive integers less than 10 is written as:

O = { x | x is an odd positive integer less than 10 }

This notation tells us exactly which numbers belong to the set without listing them individually.

2. Union of Sets

The union combines all distinct elements from two sets. Symbolically, A ∪ B means “the set of elements that are in A, in B, or in both.”

Consider:

• A = {1, 2, 3, 4}
• B = {3, 4, 5, 6}

The union is:

A ∪ B = {1, 2, 3, 4, 5, 6}

Notice that each element appears only once, even if it is present in both original sets.

3. Representing Subsets with Bit Strings

When the universal set U is finite and ordered, a subset can be encoded as a bit string. Each position corresponds to an element of U; a 1 indicates inclusion, while a 0 indicates exclusion.

For U = {1,…,10}, the even numbers are {2, 4, 6, 8, 10}. The bit string (starting with element 1) is:

0101 0101 0101

Positions 2, 4, 6, 8, and 10 contain a 1, matching the even numbers.

4. The Empty Set (∅)

The empty set contains no elements. It is a unique set that plays a crucial role in set theory.

• ∅ is a subset of every set. This follows from the definition of a subset: every element of ∅ (there are none) is also an element of any set.
• ∅ does not contain the number zero; zero is a number, while ∅ is a set with no members.
• ∅ can be an element of another set, e.g., {∅}, but it is not prohibited from being a member.

Remember: "Nothing is inside nothing, so the statement is always true."

5. Power Sets

The power set P(S) of a set S is the set of all possible subsets of S, including the empty set and S itself.

If S = {a, b, c}, the number of subsets is 2ⁿ, where n is the cardinality of S. Here, n = 3, so:

|P(S)| = 2³ = 8

The eight subsets are: ∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}.

6. Cartesian Product

The Cartesian product A × B pairs each element of A with each element of B in ordered pairs (a, b).

Given:

• A = {1, 2, 3}
• B = {3, 4, 5}

The product is:

A × B = {(1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,3), (3,4), (3,5)}

Notice the order matters: (1,3) is different from (3,1).

7. Proper Subsets

A proper subset contains some, but not all, elements of the original set. It must be strictly smaller.

For the set {0,1,2,3,4}, the set {0,1,2} is a proper subset because:

• All its elements belong to the original set.
• It does not contain every element of the original set.

Mnemonic: “P‑R‑E‑S‑S” – Proper = Partial, Really Excludes Some, Stays Safe (no outsiders).

8. Set Complement

The complement of a set A with respect to a universal set U consists of all elements in U that are not in A. It is denoted Aʹ or U \ A.

Example:

• A = {1,2,3,4,5}
• U = {1,…,10}

The complement is:

U \ A = {6,7,8,9,10}

9. Quick Review Checklist

• Set Builder: Identify the property that defines the set.
• Union (∪): Combine all distinct elements.
• Bit Strings: Map each element of the universal set to a binary digit.
• Empty Set (∅): Always a subset of any set.
• Power Set: Number of subsets = 2ⁿ.
• Cartesian Product (×): Form ordered pairs.
• Proper Subset: Must be strictly smaller than the original set.
• Complement: Elements in U not in A.

10. Practice Problems

Apply what you have learned with these additional questions:

1. Write the set of all even integers between 1 and 12 using set builder notation.
2. Find the union of C = {a, b} and D = {b, c, d}.
3. Given U = {1,2,3,4,5}, represent the subset {2,5} as a bit string.
4. Is the set { } (the empty set) a proper subset of {1,2,3}?
5. How many elements are in the power set of a set with 4 elements?
6. List the Cartesian product of X = {0,1} and Y = {a,b}.
7. Determine the complement of M = {3,4} with respect to U = {1,2,3,4,5,6}.

Try solving these on your own, then compare your answers with a textbook or instructor to reinforce the concepts.

Conclusion

Mastering the basics of set theory equips you with a powerful language for mathematics and computer science. By understanding notation, operations, and the relationships between sets, you can approach more advanced topics—such as functions, relations, and probability—with confidence.

Keep revisiting these core ideas, use the mnemonic devices provided, and practice regularly. Your proficiency in set theory will grow steadily, laying a solid groundwork for all future mathematical learning.