---

Introduction to Set Theory

Set theory is the branch of mathematical logic that studies sets, which are collections of objects.

• Foundation of modern mathematics

• Core to discrete mathematics, computer science, and logic

• Introduced by Georg Cantor (1845–1918)

• Language for defining relations, functions, graphs, and more

“A set is a Many that allows itself to be thought of as a One.” — Georg Cantor

What is a Set?

A set is a well-defined collection of distinct objects, called elements or members.

• Notation: A={1,2,3,4,5}

• x∈A means “x is an element of A”

• x∉A means “x is not an element of A”

Common Sets

Symbol	Set
N	Natural numbers
Z	Integers
Q	Rational numbers
R	Real numbers
C	Complex numbers
∅	Empty set

Ways to Describe a Set

Roster method (tabular form): list all elements.

A={2,4,6,8}

Set-builder notation: describe properties.

A={x∈N∣x is even and x<10}

Rule form:

B={x∣x2=4}={−2,2}

R Example: Creating Sets

A <- c(2, 4, 6, 8) B <- c(1, 2, 3, 4) # Membership test 2 %in% A 5 %in% A # Cardinality length(A) length(B)

Subsets and Equality

• A⊆BA⊆B: A is a subset of B — every element of AA is in BB.

• A⊂BA⊂B: proper subset — A⊆BA⊆B and A≠BA=B.

• A=BA=B: equality — A⊆BA⊆B and B⊆AB⊆A.

Example: If A={1,2}A={1,2}, B={1,2,3,4}B={1,2,3,4}

A⊂B,A⊆B,A≠BA⊂B,A⊆B,A=B

Power set P(A)P(A): set of all subsets of AA.

∣P(A)∣=2∣A∣∣P(A)∣=2∣A∣

Power Set Example in R

{r}

power_set <- function(s) {   n <- length(s)   result <- list()   for (i in 0:(2^n - 1)) {     bits <- as.logical(intToBits(i)[1:n])     result[[i + 1]] <- s[bits]   }   result }  power_set(c("a", "b", "c"))

Set Operations — Union

The union of AA and BB:

A∪B={x∣x∈A or x∈B}A∪B={x∣x∈A or x∈B}

{r}

A <- c(1, 2, 3, 4) B <- c(3, 4, 5, 6) union(A, B)

Set Operations — Intersection

The intersection of AA and BB:

A∩B={x∣x∈A and x∈B}A∩B={x∣x∈A and x∈B}

{r}

intersect(A, B)

Two sets are disjoint if A∩B=∅A∩B=∅.

Set Operations — Difference & Complement

Difference: A∖B={x∣x∈A and x∉B}A∖B={x∣x∈A and x∈/B}

Complement: A‾=U∖AA=U∖A (relative to universal set UU)

{r}

setdiff(A, B)   # A \ B setdiff(B, A)   # B \ A  U <- 1:10 setdiff(U, A)   # complement of A

Symmetric Difference

The symmetric difference A△BA△B contains elements in exactly one of the sets:

A△B=(A∖B)∪(B∖A)=(A∪B)∖(A∩B)A△B=(A∖B)∪(B∖A)=(A∪B)∖(A∩B)

{r}

sym_diff <- union(setdiff(A, B), setdiff(B, A)) sym_diff

Venn Diagrams

• Visual representation of sets as circles inside a rectangle (universal set).

• Shading illustrates operations.

{r,

library(VennDiagram) grid.newpage() venn.plot <- draw.pairwise.venn(   area1 = 2, area2 = 2, cross.area = 1,   category = c("A", "B"),   fill = c("skyblue", "salmon"),   lty = "solid", cex = 1.5, cat.cex = 1.5,   ind = FALSE )

Laws of Set Theory

Law	Expression
Identity	A∪∅=A A∩U=A
Idempotent	A∪A=A A∩A=A
Commutative	A∪B=B∪A A∩B=B∩A
Associative	(A∪B)∪C = A∪(B∪C) (A∩B)∩C = A∩(B∩C)
Distributive	A∩(B∪C)=(A∩B)∪(A∩C) A∪(B∩C)=(A∪B)∩(A∪C)
De Morgan	(A∪B)‘=A’ ∩ B’ (A∩B)‘=A’ ∪ B’

De Morgan’s Laws — Verification in R

{r}

U <- 1:10 A <- c(1, 2, 3, 4) B <- c(3, 4, 5, 6)  lhs1 <- setdiff(U, union(A, B)) rhs1 <- intersect(setdiff(U, A), setdiff(U, B)) identical(lhs1, rhs1)   # TRUE  lhs2 <- setdiff(U, intersect(A, B)) rhs2 <- union(setdiff(U, A), setdiff(U, B)) identical(lhs2, rhs2)   # TRUE

Cartesian Product

The Cartesian product of AA and BB:

A×B={(a,b)∣a∈A,b∈B}A×B={(a,b)∣a∈A,b∈B}

∣A×B∣=∣A∣⋅∣B∣∣A×B∣=∣A∣⋅∣B∣

{r}

A <- c("x", "y") B <- c(1, 2, 3) expand.grid(A = A, B = B)

Cardinality

Cardinality ∣A∣∣A∣ = number of elements in AA.

• Finite set: finite number of elements

• Infinite set: infinite elements (countable or uncountable)

• Countably infinite: bijection with NN (e.g., ZZ, QQ)

• Uncountably infinite: no bijection with NN (e.g., RR)

Inclusion–Exclusion Principle

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣∣A∪B∣=∣A∣+∣B∣−∣A∩B∣

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣

Inclusion–Exclusion Example

Problem: In a class of 40 students, 25 like math, 20 like physics, and 10 like both. How many like at least one?

{r}

A <- 25   # like math B <- 20   # like physics AB <- 10  # like both A_union_B <- A + B - AB A_union_B

Applications of Set Theory

• Databases: relational algebra (union, join, projection)

• Computer science: data structures (sets, hash tables), type theory

• Probability: events as sets, sample spaces

• Logic: quantification, Boolean algebra

• Graph theory & automata: languages as sets of strings

• Machine learning: feature sets, clustering

Summary

• Set: collection of distinct objects

• Notation: ∈∈, ⊆⊆, ⊂⊂, ∅∅, UU

• Operations: ∪∪, ∩∩, ∖∖, △△, A‾A

• Key laws: Distributive, De Morgan, Inclusion–Exclusion

• Power set: 2∣A∣2∣A∣ subsets

• Cartesian product: pairs from two sets

• Cardinality: size, finite vs. infinite

References & Further Reading

• Rosen, K. H. Discrete Mathematics and Its Applications. McGraw-Hill.

• Halmos, P. R. Naive Set Theory. Springer.

• Enderton, H. B. Elements of Set Theory. Academic Press.

• R Documentation: base::union, base::intersect, base::setdiff

Thank You!

Questions?

cat(“Slides rendered on:”, format(Sys.Date(), “%B %d, %Y”))