Introduction to Set Theory

Introduction to the Theory of Sets

• Sets are fundamental in mathematics
• Lecture Notes 1 introduces essential concepts for studying mathematics

Definitions and Notations of Sets

• A set is a list or collection of well-defined objects
• The objects in a set are called members or elements
• Sets are denoted by capital letters (A, B, X, Y, etc.)
• Elements are denoted by small letters (a, b, x, y, etc.)
• If element x is in set A, this is written as x ∈ A
• This means "x is a member of A" or "x belongs to A"
• If x is not in A, it's written as x ∉ A

Methods for Describing Sets

• Sets can be defined by listing elements explicitly or by specifying a defining property

Roster/Listing Method/Tabular Form

• Elements are listed explicitly, separated by commas and enclosed in braces
  • E.g., A = {a, e, i, o, u}

Rule Method/Set-builder

• Sets are defined by specifying a property its elements satisfy
  • E.g., B = {x : x is an integer, x > 0}, which reads as "B is the set of x such that x is an integer and x is greater than zero"
    • This defines the set B as positive integers

Types of Sets

Finite and Infinite Sets

• A finite set contains a finite number of elements or no elements
• An infinite set contains an infinite number of elements
• Examples:
  • X = {Monday, Tuesday, Wednesday, Thursday, Friday} is a finite set.
  • Y = {2, 4, 6, 8,...} is infinite.
  • P = {x : x is a river on the earth} is a finite set, even though the exact count is difficult

Cardinal Number of a Finite Set

• The number of elements in a finite set is the cardinal number, denoted by n(A)
• Examples:
  • A = {1, 3, 7, 11, 13, 17} has n(A) = 6
  • B = {a, b} has n(B) = 2

Empty/Null/Void Set

• A set containing no elements
• Denoted by ∅ or {}
• The empty set is considered finite
• The empty set is a subset of every other set A, expressed as ∅ ⊂ A ⊆ U
• Examples:
  • A = {x : x² = 4, x is odd} is an empty set because there are no odd numbers that satisfy x² = 4
  • B is the set of people older than 200 years. According to known statistics, it is an empty set

Singleton Set

• A set containing only one element
• Example:
  • A = {2} is a singleton set
  • B = {1, 2, 3} is not

Subset and Superset

• Set A is a subset of set B if every element of A is also an element of B
  • Denoted as A ⊆ B
  • B is considered a superset of A, denoted as B ⊇ A
• A is "contained in" B, or B "contains" A
• The negation of A ⊆ B is A ⊈ B
  • There exists at least one x ∈ A such that x ∉ B
• Example:
  • A = {1, 3, 5, 7,...}
  • B = {5, 10, 15, 20,...}
  • C = {x : x is prime, x > 2} = {3, 5, 7, 11,...}
  • C ⊆ A
  • B ⊈ A (10 ∈ B but 10 ∉ A)

Equal and Equivalent Sets

• Two sets A and B are equal (A ≡ B) if every element of A is a member of B, and vice versa
  • A and B contain exactly the same elements
• If A and B are not equal, then A ≠ B
• Two sets A and B are equivalent (A ≡ B) if they contain the same number of elements, i.e., n(A) = n(B)
• To prove sets A and B are equal, show A ⊆ B and B ⊆ A
• Example:
  • E = {2, 4, 6} is a subset of F = {6, 2, 4}, and E = F
  • For sets N (natural numbers), Z (integers), Q (rational numbers), R (real numbers), and C (complex numbers): N ⊆ Z ⊆ Q ⊆ R ⊆ C

Proper Subset

• Set A is a proper subset of set B if A ⊆ B and there is at least one element of B not in A (A ≠ B)
• Denoted as A ⊂ B

Disjoint Sets

• Sets A and B are disjoint if they have no common elements
  • A ⋢ B and B ⋢ A

Universal Set

• In any application of set theory, all sets are subsets of a fixed universal set, denoted by U
• The universal set consists of all possible elements being considered

Number of Subsets of a Finite Set

• A finite set with n elements has 2^n subsets

Class of Sets

• A class, collection, or family is a set of sets
• subclass, subcollection, and subfamily all have similar meanings
• If A = {1, 2, 3, 4}, A is the class of subsets of A containing three elements
  • A = {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}}

Power Set

• For a given set A, the class of all subsets of A is called the power set of A, denoted by P(A)
• If A is finite, then P(A) is also finite
• n(P(A)) = 2^(n(A)), where n(A) is the cardinal number of A
• The power set is also sometimes denoted by 2^A

Venn Diagram

• A pictorial representation of sets with sets shown as enclosed areas in a plane
• The universal set U is a rectangle
• Other sets are disks or closed geometrical figures within the rectangle
• If A ⊆ B, disk A is inside disk B
• If A and B are disjoint, their disks are separated

Operations on Sets

• Define methods to obtain new sets from given sets

Union of Sets

• Given nonempty sets A and B, and a universal set U, the union of A and B (A ∪ B) is the set of all elements which are in either A or B
  • A ∪ B = {x : x ∈ A or x ∈ B}
• "Or" in this context means "and/or"
• In the context of students at a university, if M represents male students and F represents female students, M ∪ F = U

Intersection of Sets

• The intersection of A and B (A ∩ B) is the set of elements which belong to both A and B
• A ∩ B = {x : x ∈ A and x ∈ B}
• If A ∩ B = ∅, then A and B are disjoint or non-intersecting
• In the context of students at a university, if M represents male students and F represents female students and since each students has to be, M ∩ F = Ø

Complement of a Set

• The complement of A (Aᶜ) is the set of elements in the universal set U that do not belong to A
  • Aᶜ = {x : x ∈ U, x ∉ A}
• A is sometimes denoted as A' or Ā
• In the English Alphabet context, if V consists of the vowels in set U, then Vᶜ consists of the consonants

Relative Complement of a Set

• The relative complement, or difference, of set B with respect to set A (A \ B) is the set of elements in A that do not belong to B
  • A \ B = {x : x ∈ A and x ∉ B} = A ∩ Bᶜ
• A \ B is also read as "A minus B" denoted A – B or A ~ B

Symmetric Difference of Sets

• The symmetric difference of sets A and B (A ⊕ B) is the set of elements which belong to A or B, but not to both
  • A ⊕ B = {x : x ∈ A or x ∈ B, x ∉ A ∩ B}
  • A ⊕ B = (A ∪ B) \ (A ∩ B) = (A \ B) ∪ (B \ A)

Laws of Set Algebra

• Sets under set operations obey laws or identities

Idempotent Laws

• A ∪ A = A
• A ∩ A = A

Commutative Laws

• A ∪ B = B ∪ A
• A ∩ B = B ∩ A

Associative Laws

• (A ∪ B) ∪ C = A ∪ (B ∪ C)
• (A ∩ B) ∩ C = A ∩ (B ∩ C)

Distributive Laws

• A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
• A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Identity Laws

• A ∪ ∅ = A
• A ∩ ∅ = ∅
• A ∪ U = U
• A ∩ U = A

Complement Laws

• A ∪ Aᶜ = U, A ∩ Aᶜ = ∅
• (Aᶜ)ᶜ = A
• Uᶜ = ∅, ∅ᶜ = U

De-Morgan's Laws

• (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ
• (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Sets of Numbers

• Sets of numbers including standard notations

Sets of numbers

• Natural numbers: N := {1, 2, 3,...}
• Whole numbers: W := {0, 1, 2, 3,...}
• Integers: Z := {0, ±1, ±2, ±3,...}
• Rational numbers: Q = {m/n : m, n ∈ Z} = {all terminating or repeating decimals}
• Irrational numbers: = {all nonterminating or non-repeating decimals}
• Even numbers: := {2n : n ∈ Z} = {0, ±2, ±4, ±6,...}
• Odd numbers = {2n + 1 : n ∈ Z} = {±1, ±3, ±5,...}
• Real numbers R = {all rational or irrational numbers}
• Complex numbers C := {x ± iy : x, y ∈ R}

Rational and Irrational Numbers

• Rational numbers are numbers whose decimal form terminates or repeats
• 0.75 is a terminating decimal
• 0.245̅ = 0.245454545...

Rational Numbers Forms

• Can be expressed in the form p/q, where p and q are integers and q ≠ 0
• Integers are rational numbers
• Decimal form can be found by dividing the numerator by the denominator
• Irrational numbers do not terminate and do not repeat
• E.g., 0.272272227... is irrational
• Other irrational numbers include π, √2, √3, √5

Prime and Composite Numbers

• A prime number is a positive integer greater than 1 that has no positive integer factors other than itself and 1
  • The 10 smallest prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29
• A composite number is a positive integer greater than 1 that is not a prime number
• The 10 smallest composite numbers are 4, 6, 8, 9, 10, 12, 14, 15, 16, and 18

Properties for real numbers

• Every real number is either rational or irrational
• A real number is written in decimal form, and will be a terminating decimal, a repeating decimal or a nonterminating and non repeating decimal

Interval

• A set {x : x > 2} of real numbers greater than 2
• Can be written in interval notation as (2, ∞)

Interval Notations

• (a, b) all real numbers between a and b, not including a and b (open interval)
  • {x : a < x < b}
• [a, b] all real numbers between a and b, including a and b (closed interval)
  • {x : a ≤ x ≤ b}
• (a, b] all real numbers between a and b, not including a but including b (half-open interval)
  • {x : a < x ≤ b}
• [a, b) all real numbers between a and b, including a but not including b (half-open interval)
  • {x : a ≤ x < b}
• Subsets extending forever can be represented by the symbol ∞ or -∞

Other Interval Notations

• (-∞, a) all real numbers less than a {x : x < a}
• (b, ∞) all real numbers greater than b {x : x > b}
• (-∞, a] all real numbers less than or equal to a {x : x ≤ a}
• [b, ∞) all real numbers greater than or equal to b {x : x ≥ b}
• (-∞, ∞) represents all real numbers {x : -∞ < x < ∞}