This comprehensive set of academic notes covers the complete curriculum for Unit 1 (Set Theory) of the Discrete Structure course (BCA 151). These notes combine foundational mathematical definitions, formal algebraic identities, rigorous proof methods, and practical computer science applications based on core standard references.


1.1 Basic Concepts of Set Theory


Definitions and Element Notation

A set is a well-defined collection of distinct objects. The term "well-defined" means that there is a clear, unambiguous, and objective rule to determine whether any given object belongs to the collection. The objects that make up a set are called its elements or members.

If an object x is an element of a set A, we denote this relationship as x ∈ A. Conversely, if x does not belong to the set A, we write x ∉ A.


Methods of Set Representation

Sets are traditionally described and represented using two primary notations:

  • Roster (or Tabular) Notation: All elements of the set are explicitly listed inside curly braces, separated by commas. This method is highly effective for finite sets with a relatively small number of elements. Example: The set of all positive even integers less than 10 is written as: E = {2, 4, 6, 8}
  • Set-Builder Notation: Instead of listing each element, the set is defined by stating the specific properties or conditions that its members must satisfy. This notation specifies a universal domain and a predicate statement. Example: The exact same set E can be written in set-builder notation as: E = {x ∈ ℤ⁺ | x is even ∧ x < 10} (read as: "E is the set of all x belonging to the positive integers such that x is even and x is less than 10").


Set Cardinality

The cardinality of a set is the measure of the number of distinct elements contained within it. For a set A, the cardinality is formally denoted as |A| or n(A).

  • Finite Sets: A set is finite if its cardinality is equal to a non-negative integer n. For example, if A = {a, b, c, d}, then |A| = 4. The empty set (denoted by ∅ or {}) contains no elements, so |∅| = 0.
  • Infinite Sets: A set is infinite if it cannot be matched with a finite set of integers. For instance, the set of all natural numbers ℕ = {1, 2, 3, ...} is an infinite set, and its cardinality is denoted by the transfinite number ℵ₀ (aleph-null).


1.2 Set Relationships and Classifications


Subsets (⊆)

A set A is considered a subset of a set B if and only if every element that belongs to A also belongs to B. Formally, this is written using the universal quantifier and the conditional operator:

A ⊆ B ⟺ ∀x (x ∈ A ⟶ x ∈ B)

From this definition, two foundational mathematical properties naturally follow:

  1. Every set is a subset of itself: A ⊆ A for any set A.
  2. The empty set is a subset of every existing set: ∅ ⊆ A for any set A.


Proper Subsets (⊂)

A set A is a proper subset of a set B if A is a subset of B, but A is not equal to B. This implies that B contains at least one element that is completely absent from A. Formally:

A ⊂ B ⟺ (A ⊆ B) ∧ (A ≠ B). Example: If A = {1, 2} and B = {1, 2, 3}, then A ⊂ B since all elements of A are in B, but B contains 3, which is not in A.


Universal Set (U)

The universal set is the overarching framework containing all possible objects under active consideration for a given context or mathematical discussion. All individual sets analyzed within that context are implicitly treated as subsets of this universal set, denoted as U.


Complement of a Set

The absolute complement of a set A consists of all elements in the predefined universal set U that do not belong to A. The complement is typically denoted as Aᶜ, A', or A̅. Formally:

A̅ = {x ∈ U | x ∉ A}


Disjoint Sets

Two sets A and B are defined as disjoint if they share absolutely no common elements. In terms of operations, their overlap or intersection forms an empty set:

A and B are disjoint ⟺ A ∩ B = ∅


1.3 Fundamental Set Operations

Set operations allow us to combine existing sets to form new ones, mirroring logical operators in propositional calculus. Below is a structured comparison table detailing the core operations:


table showing set operations


Detailed Operational Analysis

  • Union (A ∪ B): Gathers all unique elements that belong to set A, to set B, or to both. For example, if A = {1, 2, 3} and B = {3, 4, 5}, then A ∪ B = {1, 2, 3, 4, 5}.
  • Intersection (A ∩ B): Isolates elements that are concurrently shared by both sets. Using the same example sets, A ∩ B = {3}.
  • Set Difference (A - B): Also known as the relative complement, it creates a set containing elements that are strictly within A but completely excludes any that reside in B. Thus, A - B = {1, 2}. Note that A - B = A ∩ B̅.
  • Symmetric Difference (A Δ B): Creates a set composed of elements belonging to either A or B, but strictly excluding the elements that appear in both. It can also be formulated as: A Δ B = (A ∪ B) - (A ∩ B). For our sample sets, A Δ B = {1, 2, 4, 5}.


1.4 Venn Diagrams

A Venn Diagram is a visual framework used to graphically map set relationships and structural operations. Within this diagrammatic system:

  • The Universal Set (U) is traditionally mapped as a bounding exterior rectangle.
  • Subsets within that specific universe are represented by interior circles or closed geometric curves.
  • The intersecting space or overlapping "lens" region between two circles represents their mathematical intersection (A ∩ B).
  • Shading both complete circles altogether represents their union (A ∪ B).
  • Shading a single circle's outer crescent while preserving the overlap as unshaded represents the set difference (A - B).


1.5 Set Identities and Proof Methods


Table of Core Algebraic Set Identities

The operations of set theory adhere to rigorous algebraic laws, which directly parallel the laws of classical propositional logic:

table showing Algebraic set identities


Formal Proof Methodologies

To establish set identities formally, two primary techniques are utilized:

  1. Venn Diagram Shading Method: A geometric approach where independent 3-circle diagrams are constructed for the Left-Hand Side (LHS) and Right-Hand Side (RHS) of an expression. By systematically filling sub-regions step-by-step, the equality is visually validated if the final shaded patterns match perfectly.
  2. Rigorous Membership Proof (Element Argument): An analytical method asserting that two sets X and Y are equal by establishing mutual subset relationships (X ⊆ Y and Y ⊆ X), or by performing chain-of-logic equivalences using biconditional operators.


Example Proof: Verification of De Morgan's Law (A ∪ B)̅ = A̅ ∩ B̅

Let x be an arbitrary element selected from the universal set universe.

x ∈ (A ∪ B)̅

⟺ ¬(x ∈ A ∪ B) — [By definition of absolute set complement]

⟺ ¬(x ∈ A ∨ x ∈ B) — [By structural definition of set union]

⟺ ¬(x ∈ A) ∧ ¬(x ∈ B) — [By application of logical De Morgan's Law]

⟺ (x ∈ A̅) ∧ (x ∈ B̅) — [By definition of absolute set complement]

⟺ x ∈ A̅ ∩ B̅ — [By structural definition of set intersection]

Since each logical link is fully reversible via biconditional equivalence (⟺), we have structurally confirmed that (A ∪ B)̅ = A̅ ∩ B̅.


1.6 Cartesian Products and Multi-Dimensional Spaces


Ordered Pairs and n-tuples

Unlike a standard unordered set where sequence is irrelevant (i.e., {a, b} = {b, a}), an ordered pair denoted by (a, b) accounts directly for positioning. Two ordered pairs are equivalent if and only if their respective positions match precisely: (a, b) = (c, d) ⟺ a = c ∧ b = d

This generalizes to an ordered sequence of n elements, formally termed an ordered n-tuple: (a₁, a₂, ..., a_n).


Cartesian Product Definition

The Cartesian Product (or cross product) of set A and set B, denoted as A × B, is the set composed of all possible ordered pairs where the first coordinate is selected from A and the second coordinate is selected from B. Formally: A × B = {(a, b) | a ∈ A ∧ b ∈ B}

Example: If A = {1, 2} and B = {x, y}, then:

A × B = {(1, x), (1, y), (2, x), (2, y)}


Cardinality Product Rule

The size of a product space is equal to the numeric multiplication of their separate individual cardinalities: |A × B| = |A| × |B|


1.7 Power Sets


Definition

Given a foundational set A, the Power Set of A, mathematically denoted as P(A) or 2ᴬ, is the comprehensive set containing all possible subsets of A. This includes the trivial boundaries: the empty set ∅ and the full original set A itself. P(A) = {X | X ⊆ A}


Power Set Cardinality Theorem

If a finite set A contains exactly n unique elements, its resulting power set will inevitably contain 2ⁿ unique elements:

|A| = n ⟶ |P(A)| = 2ⁿ


Comprehensive Computation Example

Find the power set for a set with three elements, A = {1, 2, 3}:

  • Determine expected count: Since |A| = 3, the power set size must be 2³ = 8.
  • Generate subsets systematically by item size:
  • Subsets with 0 elements: ∅
  • Subsets with 1 element: {1}, {2}, {3}
  • Subsets with 2 elements: {1, 2}, {1, 3}, {2, 3}
  • Subsets with 3 elements: {1, 2, 3}
  • Assemble the complete collection:
  • P(A) = { ∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }


1.8 Computer Science and Technology Applications


Relational Databases and SQL Queries

In modern relational database management systems (RDBMS), database tables represent sets of records (tuples). Query building maps directly to foundational set theory operations:

  • The SQL command UNION computes the set union of matching rows across two distinct queries.
  • The SQL command INTERSECT identifies rows common to both tables, directly computing a set intersection.
  • The SQL commands EXCEPT or MINUS isolate records present in a primary table while stripping records present in a secondary table, mirroring a set difference.


Native Programmatic Implementations

Modern high-level programming languages feature native implementations of sets. In Python, the set type strictly adheres to mathematical set definitions: duplicates are automatically collapsed, and ordering is undefined.


# Demonstrating set operations in Python

set_A = {1, 2, 3}

set_B = {3, 4, 5}


# Set Union

union_result = set_A.union(set_B)          # Output: {1, 2, 3, 4, 5}


# Set Intersection

intersect_result = set_A.intersection(set_B)  # Output: {3}


# Set Difference

diff_result = set_A.difference(set_B)      # Output: {1, 2}


Because sets utilize internal hashing algorithms, verifying whether an item is inside a set (if item in set_A:) runs in constant time, O(1), making it much more efficient for data lookup than an ordered array or list.


Bit Vectors and Hardware Optimization

When working with a fixed universal set, computers can represent subsets efficiently using Bit Strings (or Bit Vectors). Each element in the universal set is assigned a specific index position. A subset is mapped to a binary sequence where a 1 represents presence and a 0 represents absence.

For example, if the universal set is U = {x₁, x₂, x₃, x₄}, the subset {x₁, x₃} is represented by the bit vector 1010. This allows hardware to perform set operations like union and intersection using high-speed bitwise logic gates (AND, OR) at the processor level.