Set Theory & Logic: Fundamentals, Operations, and Applications

TAKEAWAYS:

• Sets are collections of distinct objects, defined by elements and properties, with operations like union, intersection, and complement.
• Cartesian products enable ordered pairs (e.g., (a, b)), critical for relations and functions in databases and algorithms.
• Venn diagrams visually represent set operations, inclusion-exclusion, and logical relationships.
• Propositional logic uses truth tables and quantifiers to model statements and their validity in programming and AI.
• Predicate logic extends logic to quantified statements (e.g., "All students passed"), used in database queries and theorem proving.
• Applications span from eSewa’s transaction validation (sets) to Daraz’s inventory management (relations) and NTC’s network routing (graphs).

---

1. Introduction to Sets

A set is a well-defined collection of distinct objects, called elements. Sets are fundamental in discrete mathematics and computer science.

1.1 Definitions and Notation

• Set: Denoted by capital letters (e.g., $A=\{1,2,3\}$).
• Element: Denoted by lowercase letters (e.g., $2\in A$).
• Subset: $A\subseteq B$ if every element of $A$ is in $B$.
• Universal Set ($U$): The largest set under consideration.
• Empty Set ($\varnothing$): A set with no elements.

1.2 Cartesian Product

The Cartesian product $A\times B$ of two sets $A$ and $B$ is the set of all ordered pairs $(a,b)$ where $a\in A$ and $b\in B$.

Worked Example: Given $A=\{a,b,c\}$, find $A^3$ (i.e., $A\times A\times A$).

A^3 = {
  (a, a, a), (a, a, b), (a, a, c),
  (a, b, a), (a, b, b), (a, b, c),
  (a, c, a), (a, c, b), (a, c, c),
  (b, a, a), (b, a, b), (b, a, c),
  (b, b, a), (b, b, b), (b, b, c),
  (b, c, a), (b, c, b), (b, c, c),
  (c, a, a), (c, a, b), (c, a, c),
  (c, b, a), (c, b, b), (c, b, c),
  (c, c, a), (c, c, b), (c, c, c)
}

Visualization: The Cartesian product can be visualized as a grid where each row represents an element of $A$ and each column represents an element of $B$.

1.3 Power Set

The power set of a set $A$, denoted $P(A)$, is the set of all subsets of $A$, including the empty set and $A$ itself.

Worked Example: Find the power set of $A=\{1,2,3,4\}$.

P(A) = {
  ∅,
  {1}, {2}, {3}, {4},
  {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4},
  {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4},
  {1, 2, 3, 4}
}

Note: If $A$ has $n$ elements, $P(A)$ has $2^n$ subsets.

---

2. Set Operations

Set operations are analogous to logical operations and are visualized using Venn diagrams.

2.1 Basic Operations

2.2 Inclusion-Exclusion Principle

For any two sets $A$ and $B$: $$|A\cup B|=|A|+|B|-|A\cap B|$$

Worked Example: Given $A=\{1,2,3,4\}$ and $B=\{3,4,5,6\}$, find $|A\cup B|$.

|A| = 4, |B| = 4, |A ∩ B| = 2 (elements 3 and 4)
|A ∪ B| = 4 + 4 - 2 = 6

Visualization: The Venn diagram below shows the inclusion-exclusion principle in action.

2.3 Set Identities

Some useful identities:

1. $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$
2. $A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$
3. $A\setminus (B\cup C)=(A\setminus B)\cap (A\setminus C)$

---

3. Relations and Functions

3.1 Relations

A relation $R$ from set $A$ to set $B$ is a subset of the Cartesian product $A\times B$.

Example: Let $A=\{1,2\}$ and $B=\{a,b\}$. A relation $R$ could be: $$R=\{(1,a),(1,b),(2,a)\}$$

3.2 Functions

A function $f:A\to B$ is a special type of relation where each element of $A$ is mapped to exactly one element of $B$.

Example: Let $f:\mathbb{R}\to \mathbb{R}$ be defined by $f(x)=x^2$. This is a function because each $x$ maps to exactly one $y$.

---

4. Propositional Logic

Propositional logic deals with statements (propositions) that are either true or false.

4.1 Logical Connectives