Lecture Notes: Set Theory

1. Introduction

Why Learn Set Theory?

• It's an important language and tool for reasoning in computer science.
• It is the foundation for other topics like functions, relations, and logic.
• Even complex problems like AI classification are about determining members in a set.

Symbol Quick Reference

A good practice is to keep a list of all symbols at the top.

2. Sets and Membership

Definition: What is a Set?

A Set is a collection of distinct objects. The objects are called elements or members of the set.

• We use capital letters to name sets (e.g., , , ).
• We use curly braces { } to define the elements.

Example:

Membership

• means "is a member of".
  • Belgium
• means "is not a member of".
  • Malaysia

Common Number Sets

• Integers ():
  
• Natural Numbers ():
  
• Rational Numbers ():
  
• Real Numbers ():
  

3. Set Properties

Equal Sets

Two sets are equal if they contain the exact same elements.

• Order and repetition do not matter.

Example:
Given the sets:

We can conclude they are all equal:

However, if and , then .

Describing Sets (Set-Builder Notation)

Listing elements with ... (like ) is not always precise.

A better way is set-builder notation, which uses a rule to define the members. We use a vertical bar | or a colon : which both mean "such that".

Format: { variable | rule } or { variable : rule }

Examples:

1. "A is the set of all x such that x is a positive integer."

   • 
     (Note: This means is the same as )

2. "B is the set of all x such that x is a real number between 1 and 3 (inclusive)."

3. "C is the set of the squares of all natural numbers."

   • (This means

4. Subsets and Power Sets

Subset ()

Set is a subset of set if every element in is also in .

• Examples:

• Property (Set Equality): If is a subset of AND is a subset of , they must be equal.
  

Proper Subset ()

Set is a proper subset of set if is a subset of , but is not equal to .

• Example:
  • Given: , ,
  • (True)
  • (True, because )
  • (True)
  • (True, B is not a proper subset of C, because )

Universal Set ()

The Universal Set () is the set of all elements being considered in a particular discussion.

• Example: If we are discussing , , and , the universal set could be (the "Number" universe).
• All other sets in the discussion are subsets of .

Empty Set ()

The Empty Set (or null set) is a set with no elements.

• Symbols: or simply .
• Example:
• Key Property: The empty set is a subset of all sets, including itself.
  

Power Set ()

The Power Set of is the set of all possible subsets of .

• Example: If
• The power set is:
  

5. Set Operations & Venn Diagrams

Venn Diagrams are illustrations used to show the relationships between sets. The rectangle represents the Universal Set .

Union () - "OR"

The union of and contains all elements that are in , or in , or in both.

• Venn Diagram: The entire area of both circles combined.
• Example:

Intersection () - "AND"

The intersection of and contains all elements that are in both and .

• Venn Diagram: The overlapping area of the two circles.
• Example:

Difference ( )

The difference contains all elements that are in , but not in .

• Venn Diagram: The area of circle that does not overlap with .
• Example:

Complement ( or )

The complement of contains all elements in the universal set that are not in .

• Venn Diagram: The entire area outside of circle .
• Example:

6. Set Identities

These are rules that are always true for sets.

• Commutative Laws:
• Associative Laws:
• Distributive Laws:
• De Morgan's Laws:

7. Cardinality (Size of Sets)

Order of a Set:

The order (or cardinality) of a set is the number of elements in it, denoted .

• Examples:
  • If , then .
  • If , then .

The Principle of Inclusion-Exclusion

This is a formula to find the cardinality of a union of sets.

For 2 Sets:
The number of elements in the union of A and B is the sum of their individual sizes, minus the size of their intersection (which was "double-counted").

• Example: A survey shows 25 people have brown eyes (A) and 15 have black hair (B). 10 have both. How many have either?
  • , ,
  • If 23 people had neither, the total people surveyed is .

For 3 Sets:

8. Cartesian Products

The Cartesian Product of sets and , written , is the set of all possible ordered pairs where and .

• Key Property: Order matters! The pair is not the same as .

• Therefore, (unless or one is ).

• Example:

9. Exercises

From slide 21

List 5 elements in each of the following sets:

1. • (e.g., ; , ...)
   • Answer:
2. • Answer:
3. • Answer:
4. • (e.g., (Prime); (Prime); (Prime), ...)
   • Answer:
5. • Answer: