∞Intro to the Theory of Sets Unit 12 – Set Theory in Math and Computer Science

Key Concepts and Definitions

• Sets defined as collections of distinct objects or elements
• Elements can be numbers, symbols, or other objects
• Set theory provides a foundation for mathematics and computer science
• Membership determined by whether an object belongs to a set
• Cardinality refers to the number of elements in a set
• Finite sets contain a countable number of elements
• Infinite sets have an uncountable number of elements (natural numbers, real numbers)

Set Notation and Representation

• Sets denoted using curly braces { } with elements separated by commas
• Example set: {1, 2, 3, 4, 5}
• Empty set or null set represented by ∅ or { } contains no elements
• Set builder notation describes a set using a property or condition
  • Example: {x | x is a natural number less than 5} = {1, 2, 3, 4}
• Venn diagrams visually represent sets using circles or other closed shapes
  • Overlapping regions indicate shared elements between sets
• Roster notation lists all elements explicitly {a, b, c}

Basic Set Operations

• Union (A ∪ B) combines elements from sets A and B into a single set
  • Example: {1, 2, 3} ∪ {3, 4, 5} = {1, 2, 3, 4, 5}
• Intersection (A ∩ B) includes only elements common to both sets A and B
  • Example: {1, 2, 3} ∩ {3, 4, 5} = {3}
• Difference (A - B) includes elements in set A that are not in set B
  • Example: {1, 2, 3} - {3, 4, 5} = {1, 2}
• Complement (A') includes all elements in the universal set not in set A
• Cartesian product (A × B) creates ordered pairs from elements of sets A and B
  • Example: {1, 2} × {a, b} = {(1, a), (1, b), (2, a), (2, b)}

Set Properties and Relationships

• Reflexive property: A set is a subset of itself (A ⊆ A)
• Symmetric property: If A ⊆ B and B ⊆ A, then A = B
• Transitive property: If A ⊆ B and B ⊆ C, then A ⊆ C
• Associative property holds for union and intersection: (A ∪ B) ∪ C = A ∪ (B ∪ C)
• Commutative property holds for union and intersection: A ∪ B = B ∪ A
• Distributive property: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
• De Morgan's laws: (A ∪ B)' = A' ∩ B' and (A ∩ B)' = A' ∪ B'

Types of Sets

• Power set (P(A)) contains all subsets of set A, including the empty set and A itself
  • Example: P({1, 2}) = {∅, {1}, {2}, {1, 2}}
• Singleton set contains exactly one element
• Disjoint sets have no elements in common (A ∩ B = ∅)
• Equal sets have the same elements (A = B if A ⊆ B and B ⊆ A)
• Equivalent sets have the same cardinality but may contain different elements
• Ordered sets have elements arranged in a specific sequence (tuples, sequences)
• Unordered sets disregard the order of elements ({1, 2} = {2, 1})

Set Theory in Logic and Proofs

• Set theory used to formalize logical statements and proofs
• Logical connectives (and, or, not) correspond to set operations (intersection, union, complement)
• Universal quantifier (∀) states a property holds for all elements in a set
• Existential quantifier (∃) states a property holds for at least one element in a set
• Set theory axioms (ZFC) provide a rigorous foundation for mathematics
  • Axiom of extensionality: Sets with the same elements are equal
  • Axiom of pairing: For any two sets, there exists a set containing them as elements
• Proofs by contradiction assume the negation of a statement and derive a contradiction

Applications in Computer Science

• Sets used to model data structures and algorithms
  • Hash tables, trees, graphs
• Relational databases based on set theory concepts
  • Tables represented as sets of tuples
  • SQL operations (JOIN, UNION, INTERSECT) correspond to set operations
• Regular expressions and finite automata utilize set theory
  • Character classes define sets of characters
  • State transitions represent sets of strings
• Combinatorics and probability theory rely on set theory foundations
  • Counting techniques (permutations, combinations) based on set sizes
  • Event spaces modeled as sets of outcomes

Advanced Topics and Extensions

• Fuzzy sets assign degrees of membership to elements (between 0 and 1)
  • Example: A fuzzy set of tall people might assign a membership of 0.8 to someone 6'2"
• Rough sets deal with incomplete or imprecise information
  • Lower and upper approximations define boundaries of a set
• Multisets or bags allow duplicate elements
  • Example: {a, a, b, c, c, c} is a multiset
• Partially ordered sets (posets) have elements with a partial order relation
  • Example: Subsets of a set form a poset under the subset relation
• Transfinite numbers extend cardinal and ordinal numbers beyond infinity
  • Aleph numbers represent cardinalities of infinite sets
• Axiomatic set theory investigates alternative axiom systems and their consequences
  • Non-well-founded set theory allows sets to contain themselves as elements