Introduction to Set Theory

• Set theory introduces notation and terminology used throughout mathematics
• It includes the formal definition of mathematical induction with examples

Sets and Elements

• A set is a well-defined collection of objects, known as elements or members
• Capital letters (A, B, X, Y) denote sets
• Lowercase letters (a, b, x, y) denote elements
• Synonyms for sets include "class," "collection," and "family"

Membership Notation

• a ∈ S indicates that element a belongs to set S
• a, b ∈ S indicates that elements a and b belong to set S
• ∈ signifies "is an element of"
• ∉ signifies "is not an element of"

Specifying Sets

• Listing members separated by commas and enclosed in braces { }
• Stating the properties that characterize the elements
• A = {1, 3, 5, 7, 9} is a set consisting of the numbers 1, 3, 5, 7, 9
• B = {x | x is an even integer, x > 0} represents the set of x such that x is an even integer and x is greater than 0
• The vertical line | means "such that," and the comma means "and."

Set Specification Examples

• A can also be written as {x | x is an odd positive integer, x < 10}
• B is often specified as {2, 4, 6, ...}, assuming the pattern is understood
• 8 ∈ B, while 3 ∉ B

Set Element Display

• A set remains the same if elements are repeated or rearranged
• Sets are described by listing elements only if the set contains a few elements
• Sets are described by the property which characterizes its elements if the set contains a lot of elements.
• Sets E = {x | x² – 3x + 2 = 0}, F = {2, 1}, and G = {1, 2, 2, 1} are equal (E = F = G)

Subsets

• If every element in A is also in B (a ∈ A implies a ∈ B), A is a subset of B, written as A ⊆ B or B ⊇ A
• Two sets are equal if they contain the same elements, i.e., A = B if and only if A ⊆ B and B ⊆ A
• A ⊈ B means A is not a subset of B, i.e., at least one element of A does not belong to B

Subset Examples

• Given A = {1, 3, 4, 7, 8, 9}, B = {1, 2, 3, 4, 5}, and C = {1, 3}, C ⊆ A and C ⊆ B
• Some elements of B (2 and 5) do not belong to A. Therefore B ⊈ A.
• A ⊆ B does not exclude the possibility that A = B
• For every set A, A ⊆ A
• If A ⊆ B and A ≠ B, A is a proper subset of B

Subset Properties and Theorem

• If every element of A belongs to B and every element of B belongs to C, then A ⊆ C
• Theorem: For any sets A, B, C:
  • A ⊆ A
  • If A ⊆ B and B ⊆ A, then A = B
  • If A ⊆ B and B ⊆ C, then A ⊆ C

Special Set Symbols

• N: the set of natural numbers or positive integers (1, 2, 3, ...)
• Z: the set of all integers (..., -2, -1, 0, 1, 2, ...)
• Q: the set of rational numbers
• R: the set of real numbers
• C: the set of complex numbers
• N ⊆ Z ⊆ Q ⊆ R ⊆ C

Universal and Empty Sets

• All sets under investigation are considered subsets of a fixed large set, the universal set (U)
• If no elements in U have a certain property P, the set is an empty set or null set, denoted by Ø
• Only one empty set exists
• The empty set is a subset of every other set
• Theorem: For any set A, Ø ⊆ A ⊆ U

Disjoint Sets

• Two sets A and B are disjoint if they have no elements in common
• If A and B are disjoint, then neither is a subset of the other (unless one is the empty set)
• Example: A = {1, 2}, B = {4, 5, 6}, and C = {5, 6, 7, 8} means A and B are disjoint, and A and C are disjoint, but B and C are not disjoint (5 and 6 are common)

Venn Diagrams

• Venn diagram: a pictorial representation of sets using enclosed areas in a plane
• The universal set U is represented by a rectangle
• Other sets are represented by disks within the rectangle
• If A ⊆ B, the disk representing A is entirely within the disk representing B
• If A and B are disjoint, the disks are separated

Arguments and Venn Diagrams

• Venn diagrams can represent verbal statements about sets
• Venn diagrams can determine whether arguments are valid

Set Operations: Union and Intersection

• The union of sets A and B (A ∪ B) is the set of elements in A or B: A ∪ B = {x | x ∈ A or x ∈ B}
• The intersection of sets A and B (A ∩ B) is the set of elements in both A and B: A ∩ B = {x | x ∈ A and x ∈ B}

Disjoint Union

• Sets A and B are disjoint or nonintersecting if they have no elements in common, or A ∩ B = Ø
• S = A ∪ B where A ∩ B = Ø S is the disjoint union of A and B

Union and Intersection Properties

• Every element x in A ∩ B belongs to both A and B
• A ∩ B is a subset of A and B (A ∩ B ⊆ A and A ∩ B ⊆ B)
• Every element x in A ∪ B belongs to A or B
• Every element in A belongs to A ∪ B, and every element in B belongs to A ∪ B (A ⊆ A ∪ B and B ⊆ A ∪ B)

Union and Intersection Theorem

• For any sets A and B:
  • A ∩ B ⊆ A ⊆ A ∪ B
  • A ∩ B ⊆ B ⊆ A ∪ B
• Theorem: A ⊆ B, A ∩ B = A and A ∪ B = B are equivalent

Complements

• All sets under consideration at a particular time are subsets of a fixed universal set U
• The absolute complement (or simply complement) of A (AC) is the set of elements in U that are not in A
• AC = {x | x ∈ U, x ∉ A}

Relative Complements

• The relative complement of B with respect to A (or the difference of A and B, A \ B) is the set of elements in A that are not in B
• A \ B = {x | x ∈ A, x ∉ B}
• A \ B is read as "A minus B."

Symmetric Difference

• The symmetric difference of sets A and B (A ⊕ B) includes elements in A or B but not both
• A ⊕ B = (A ∪ B) \ (A ∩ B) or A ⊕ B = (A \ B) ∪ (B \ A)

Fundamental Products

• A fundamental product of n distinct sets A₁, A₂, ..., Aₙ is of the form A₁* ∩ A₂* ∩ ... ∩ Aₙ* where Aᵢ* is either Aᵢ or AᵢC

Properties of Fundamental Products

• There are 2ⁿ such fundamental products
• Any two fundamental products are disjoint
• The universal set U is the union of all fundamental products

Algebra of Sets

• Sets under the operations of union, intersection, and complement satisfy various laws such as idempotent, associative, commutative, distributive, identity, involution, complement, and DeMorgan's laws

Duality Principle

• The dual E* of an equation E is obtained by replacing ∪ by ∩, ∩ by ∪, Ø by U, and U by Ø
• If any equation E is an identity, its dual E* is also an identity

Finite and Infinite Sets

• A set S is finite if S is empty or contains exactly m elements (m is a positive integer); otherwise, S is infinite

Countable and Uncountable Sets

• A set S is countable if S is finite or if its elements can be arranged as a sequence (countably infinite)
• Otherwise S is uncountable

Counting Principle

• n(S) or |S| denotes the number of elements in a set S

Lemmas for Finite Disjoint Sets

• If A and B are finite disjoint sets, then A ∪ B is finite, and n(A ∪ B) = n(A) + n(B)
• If S is the disjoint union of finite sets A and B, then S is finite, and n(S) = n(A) + n(B)

Corollary

• Let A and B be finite sets. Then n(A\B) = n(A) – n(A ∩ B)

Inclusion-Exclusion Principle

• Theorem: If A and B are finite sets, then A ∪ B and A ∩ B are finite, and n(A ∪ B) = n(A) + n(B) – n(A ∩ B)
• Corollary: If A, B, C are finite sets, then A ∪ B ∪ C is finite and n(A ∪ B ∪ C) = n(A) + n(B) + n(C) – n(A ∩ B) – n(A ∩ C) – n(B ∩ C) + n(A ∩ B ∩ C)

Classes of Sets

• A class of sets (or collection of sets) refers to some of the subsets in a given set S
• A subclass (or subcollection) refers to some of the sets in a given class of sets

Power Sets

• P(S) signifies the class of all subsets of S
• If S is finite, the number of elements in P(S) is 2 raised to the power n(S)
• n(P(S)) = 2n(S)

Partitions

• A partition of S is a subdivision of S into nonoverlapping, nonempty subsets
• A partition of S is a collection {Aᵢ} of nonempty subsets of S such that:
  • Each element in S belongs to one of the Aᵢ
  • The sets {Aᵢ} are mutually disjoint
• The subsets in a partition are called cells

Generalized Set Operations

• Union and intersection can be extended to any number of sets
• A₁ ∪ A₂ ∪ ... ∪ Am = ∪Aᵢ = {x | x ∈ Aᵢ for some Aᵢ}
• A₁ ∩ A₂ ∩ ... ∩ Am = ∩Aᵢ = {x | x ∈ Aᵢ for every Aᵢ}

DeMorgan's Laws for Generalized Set Operations

• For a collection 𝓐 of sets:
  • [∪(A|A ∈ 𝓐)]ᶜ = ∩(Aᶜ | A ∈ 𝓐)
  • [∩(A|A ∈ 𝓐)]c = ∪(Ac | A ∈ 𝓐)

Mathematical Induction

• Principle of Mathematical Induction I:
  • P is a proposition defined on the positive integers N
  • P(n) is either true or false for each n ∈ N
  • Suppose P has the following two properties:
    • P(1) is true
    • P(k + 1) is true whenever P(k) is true
  • Then P is true for every positive integer n ∈ N
• Principle of Mathematical Induction II:
  • Let P be a proposition defined on the positive integers N such that:
  • P(1) is true.
  • P(k) is true whenever P(j) is true for all 1 ≤ j < k.
  • Then P is true for every positive integer n ∈ Ν.