Basic Set Theory Guide

This guide introduces you to the basic set theory required for Petra programming, a foundational branch of mathematics that deals with collections of objects. We’ll walk through the essential concepts step by step, from defining sets to performing common operations. By the end, you’ll have a solid understanding of how sets work and how to apply them in simple scenarios.

What is a Set?

A set is a collection of unique objects, called elements or members. Sets are typically denoted by capital letters, and elements are listed inside curly braces {}.

Example: The set of states representing traffic light colours A = {red, amber, green}.
Key properties:
- Elements are unique (no duplicates).
- Order doesn’t matter: {red, amber, green} is the same as {amber, red, green}.

To determine if something belongs to a set, use the symbol ∈ (element of). For example, x ∈ A means “x is an element of A.”

Describing Sets

There are two main ways to describe sets:

Roster Method: List all elements explicitly, e.g., B = {1, 2, 3, 4}.
Set-Builder Notation: Describe elements using a property, e.g., C = {x | x is a natural number less than 5}, which is the same as {1, 2, 3, 4}.

Special sets include:

The empty set ∅ = {}, which has no elements.
Universal set U, which contains all elements under consideration.

Set Operations

Sets support various operations to combine or compare them. Let’s explore the basics.

Union ∪

The union of sets A and B includes all elements in A or B (or both).

Example: If A = {1, 2, 3} and B = {3, 4, 5}, then A ∪ B = {1, 2, 3, 4, 5}.
Step-by-step:
1. List elements from A.
2. Add elements from B that aren’t already in the list.

Intersection ∩

The intersection includes elements common to both A and B.

Example: A ∩ B = {3}.
Step-by-step:
1. Identify elements present in both sets.
2. If none, the result is ∅ (disjoint sets).

Difference \

A \ B includes elements in A but not in B.

Example: A \ B = {1, 2}.
Step-by-step:
1. Start with elements of A.
2. Remove any that are also in B.

Subsets ⊆

A set A is a subset of B (A ⊆ B) if every element of A is in B.
- Example: {1, 2} ⊆ {1, 2, 3}.
- Proper subset (⊂) excludes equality.
- Two sets are equal if they have exactly the same elements.

To check subsets:

Verify each element of A is in B.
If yes, A ⊆ B.

Cardinality

The cardinality |A| is the number of elements in A.

Example: |{a, e, i, o, u}| = 5.

Cartesian Product ×

The Cartesian product of sets A and B, denoted A × B, is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.

Example: If A = {1, 2} and B = {a, b}, then A × B = {(1, a), (1, b), (2, a), (2, b)}.
Step-by-step:
1. Take each element of A.
2. Pair it with each element of B to form ordered pairs.
3. The result is a set of all such pairs.
Cardinality: |A × B| = |A| × |B|. For the example above, |A × B| = 2 × 2 = 4.

Cartesian Product of multiple sets Π

For multiple sets, the Cartesian product Π = A₁ × A₂ × … × Aₙ consists of all possible ordered combinations selected from A₁, A₂ and … Aₙ which results in a set of ordered tuples (a₁, a₂, …, aₙ) , essential a set of lists of size n, where n is the size of the product.

Example: If A = {on, off}, B = {on, off}, and C = {on, off}, then Π = A × B × C = {(on, on, on), (on, on, off), (on, off, on), (on, off, off), (off, on, on), (off, on, off), (off, off, on), (off, off, off)}.
Step-by-step:
1. Start with A × B as above.
2. For each pair in A × B, append each element of C to form triples.
3. Generalize for n sets by extending the process.
Cardinality: |Π| = |A₁ × A₂ × … × Aₙ| = |A₁| × |A₂| × … × |Aₙ|.
Application: Used in coordinate systems e.g. ℕ × ℕ × ℕ is the set of all possible ordered triples of natural numbers, which forms a three-dimensional grid or lattice of points in a plane where coordinates are natural numbers. Fun fact: Petra uses Cartesian products of multiple sets as the foundation for building for a programs state space, which is where Petra’s logo Π comes from, which is the capital of the greek symbol π.

Applying Set Theory

Sets are used in various fields:

In logic: Venn diagrams to visualize relationships.
In databases: Queries as set operations.
In probability: Events as sets.

Practice by solving simple problems, like finding unions and intersections of given sets.