Basic Set Theory Concepts

Fundamental Set Concepts and Notations

  • Definition of a Set:

    • A set is defined as a collection of objects (termed elements) possessing well-determined properties.

  • Examples of Valid Sets:

    • Planets in the Solar System: Planets={Mercury,Venus,Earth,Mars,Jupiter,Saturn,Uranus,Neptune,Pluto}\text{Planets} = \{\text{Mercury}, \text{Venus}, \text{Earth}, \text{Mars}, \text{Jupiter}, \text{Saturn}, \text{Uranus}, \text{Neptune}, \text{Pluto}\}

    • Days of the Week: WeekDays={Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday}\text{WeekDays} = \{\text{Monday}, \text{Tuesday}, \text{Wednesday}, \text{Thursday}, \text{Friday}, \text{Saturday}, \text{Sunday}\}

    • American Coins: Coins={penny,nickel,dime,quarter,half-dollar,dollar}\text{Coins} = \{\text{penny}, \text{nickel}, \text{dime}, \text{quarter}, \text{half-dollar}, \text{dollar}\}

    • These sets possess well-determined properties that all member elements satisfy.

  • Collections Not Considered Sets:

    • Collections that rely on subjective judgment or lack precise criteria are not sets.

    • Examples include:

    • The set of colors I like (not a well-determined property; too subjective).

    • The set of "best" colleges (subjective criteria).

    • The set of all sets (logically inconsistent/invalid construction).

  • Methods for Specifying Sets:

    • Roster Notation:

    • Specifies all elements explicitly.

    • Uses ellipses (…\dots) to indicate a continuing pattern and make expressions shorter.

    • Examples:

      • Planets={Mercury,Venus,Earth,Mars,Jupiter,Saturn,Uranus,Neptune,Pluto}\text{Planets} = \{\text{Mercury}, \text{Venus}, \text{Earth}, \text{Mars}, \text{Jupiter}, \text{Saturn}, \text{Uranus}, \text{Neptune}, \text{Pluto}\}

      • Planets={Mercury,Venus,Earth,…,Pluto}\text{Planets} = \{\text{Mercury}, \text{Venus}, \text{Earth}, \dots, \text{Pluto}\}

      • WeekDays={Monday,Tuesday,…,Sunday}\text{WeekDays} = \{\text{Monday}, \text{Tuesday}, \dots, \text{Sunday}\}

      • Coins={penny,nickel,dime,quarter,half-dollar,dollar}\text{Coins} = \{\text{penny}, \text{nickel}, \text{dime}, \text{quarter}, \text{half-dollar}, \text{dollar}\}

      • Coins={penny,nickel,…,half-dollar,dollar}\text{Coins} = \{\text{penny}, \text{nickel}, \dots, \text{half-dollar}, \text{dollar}\}

    • Set-Builder Notation (Self-Builder Notation):

    • Specifies the exact mathematical or characteristic properties that elements must possess.

    • Examples:

      • Planets={x∣x is a solar planet}\text{Planets} = \{x \mid x \text{ is a solar planet}\}

      • WeekDays={d∣d is a day of the week}\text{WeekDays} = \{d \mid d \text{ is a day of the week}\}

      • Coins={c∣c is an American coin}\text{Coins} = \{c \mid c \text{ is an American coin}\}

  • Notations for Set Membership:

    • The symbol ∈\in denotes set membership:

    • Monday∈WeekDays\text{Monday} \in \text{WeekDays} indicates that Monday is an element of the set WeekDays\text{WeekDays}.

    • The symbol ∉\notin denotes non-membership:

    • Euro∉Coins\text{Euro} \notin \text{Coins} indicates that euro is not an element of the set Coins\text{Coins}.

Special Types of Sets and Numeric Sets

  • Empty Set:

    • The empty set (denoted by ∅\emptyset) is defined as a set containing no elements.

    • Examples:

    • ∅={x∣x is a coin and worth 3 cents}\emptyset = \{x \mid x \text{ is a coin and worth } 3 \text{ cents}\}

    • ∅={p∣p is a solar planet and not running around the Sun}\emptyset = \{p \mid p \text{ is a solar planet and not running around the Sun}\}

    • ∅={num∣num<25 and num>30}\emptyset = \{\text{num} \mid \text{num} < 25 \text{ and } \text{num} > 30\}

  • Finite and Infinite Sets:

    • A set is a finite set if its total number of elements is finite.

    • If the number of elements is not finite, the set is an infinite set.

  • Standard Numeric Sets:

    • Natural Numbers (N\mathbb{N}):

    • N={1,2,3,…,10,…,1000,… }\mathbb{N} = \{1, 2, 3, \dots, 10, \dots, 1000, \dots\}

    • N\mathbb{N} is an infinite set.

    • Examples of membership: 10∈N10 \in \mathbb{N} and 12∉N\frac{1}{2} \notin \mathbb{N}.

    • Integers (Z\mathbb{Z}):

    • Z={…,−1000,…,−10,…,−1,0,1,2,…,10,…,1000,… }\mathbb{Z} = \{\dots, -1000, \dots, -10, \dots, -1, 0, 1, 2, \dots, 10, \dots, 1000, \dots\}

    • Set-builder representation: Z={x∣x is an integer number}\mathbb{Z} = \{x \mid x \text{ is an integer number}\}

    • Z\mathbb{Z} is an infinite set.

    • Rational Numbers (Q\mathbb{Q}):

    • Q={n∣n is a rational number}={n  |  n=pq, where p∈Z,q∈N}\mathbb{Q} = \{n \mid n \text{ is a rational number}\} = \left\{n \,\,\middle|\,\, n = \frac{p}{q}, \text{ where } p \in \mathbb{Z}, q \in \mathbb{N}\right\}

    • Rational elements: 12∈Q\frac{1}{2} \in \mathbb{Q}, 85∈Q\frac{8}{5} \in \mathbb{Q}, 2.134576∈Q2.134576 \in \mathbb{Q}, 3.171717⋯∈Q3.171717\dots \in \mathbb{Q} (repeating decimals).

    • Irrational elements (non-members of Q\mathbb{Q}): 2∉Q\sqrt{2} \notin \mathbb{Q}, 2.13133133313333…∉Q2.13133133313333\dots \notin \mathbb{Q}.

    • Q\mathbb{Q} is an infinite set.

    • Real Numbers (R\mathbb{R}):

    • R={x∣x is rational or x is irrational}\mathbb{R} = \{x \mid x \text{ is rational or } x \text{ is irrational}\}

    • R\mathbb{R} is an infinite set.

  • Classification of Specific Example Sets:

    • Set RF\text{RF} defined as: RF={x∣x is a Ford car & is a red one}\text{RF} = \{x \mid x \text{ is a Ford car } \& \text{ is a red one}\}

    • Summary of set finiteness:

    • N,Z,Q,R\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R} are infinite sets.

    • ∅\emptyset contains no elements.

    • RF\text{RF} is a finite set.

  • Even Numbers Exercise:

    • Expressing the set of even natural numbers in roster and set-builder notation:

    • Roster notation: EvenN={2,4,6,8,… }\text{Even}\mathbb{N} = \{2, 4, 6, 8, \dots\}

    • Set-builder notation: EvenN={x∣x∈N and x=2k for some k∈N}\text{Even}\mathbb{N} = \{x \mid x \in \mathbb{N} \text{ and } x = 2k \text{ for some } k \in \mathbb{N}\}

Review of Inequality on Real Numbers

  • Geometric Representation on R\mathbb{R}:

    • On a standard real number line, if a point xx lies to the left of a point yy, this positional relationship expresses the inequality x<yx < y.

  • Custom Subset Examples:

    • Natural Numbers Between 20 and 30:

    • Notation label: N20_30N_{20\_30}

    • Plain statement: Set of all natural numbers between 20 and 30.

    • Roster notation: N20_30={21,22,23,24,25,26,27,28,29}N_{20\_30} = \{21, 22, 23, 24, 25, 26, 27, 28, 29\}

    • Set-builder notation: N20_30={x∈N∣20<x<30}N_{20\_30} = \{x \in \mathbb{N} \mid 20 < x < 30\}

    • Odd Natural Numbers:

    • Notation label: OddN\text{Odd}\mathbb{N}

    • Plain statement: Set of all odd natural numbers.

    • Roster notation: OddN={1,3,5,7,… }\text{Odd}\mathbb{N} = \{1, 3, 5, 7, \dots\}

    • Set-builder notation: OddN={x∈N∣x=2k−1 for k∈N}\text{Odd}\mathbb{N} = \{x \in \mathbb{N} \mid x = 2k - 1 \text{ for } k \in \mathbb{N}\}

Set Equality, Cardinality, and Enumeration

  • Equality of Sets:

    • Two sets AA and BB are defined as equal (A=BA = B) if they contain exactly the same elements.

    • Order Independence: The sequence in which elements are listed does not alter the set.

    • Example: If A={1,2,3}A = \{1, 2, 3\} and B={2,3,1}B = \{2, 3, 1\}, then A=BA = B.

    • Repetition Independence: Listing an element multiple times does not change the set.

    • Example: If A={1,2,3}A = \{1, 2, 3\} and B={1,2,2,2,3}B = \{1, 2, 2, 2, 3\}, then A=BA = B.

    • Core Principle: What matters in set theory is the presence of an element.

  • Cardinality of a Set:

    • For any set AA, the cardinality n(A)n(A) represents the total number of distinct elements in AA.

    • Property: If A=BA = B, then n(A)=n(B)n(A) = n(B).

  • Enumerating Elements of a Set:

    • Example: Let AA be the set of lowercase letters in the English alphabet.

    • Roster definition: A={a,b,c,d,…,z}A = \{a, b, c, d, \dots, z\} (a finite set).

    • One-to-one counting map between letters and position indices:

      • a↔1a \leftrightarrow 1

      • b↔2b \leftrightarrow 2

      • c↔3c \leftrightarrow 3

      • d↔4d \leftrightarrow 4

      • e↔5e \leftrightarrow 5

      • f↔6f \leftrightarrow 6

      • g↔7g \leftrightarrow 7

      • h↔8h \leftrightarrow 8

      • i↔9i \leftrightarrow 9

      • j↔10j \leftrightarrow 10

      • k↔11k \leftrightarrow 11

      • l↔12l \leftrightarrow 12

      • m↔13m \leftrightarrow 13

      • n↔14n \leftrightarrow 14

      • o↔15o \leftrightarrow 15

      • p↔16p \leftrightarrow 16

      • q↔17q \leftrightarrow 17

      • r↔18r \leftrightarrow 18

      • s↔19s \leftrightarrow 19

      • t↔20t \leftrightarrow 20

      • u↔21u \leftrightarrow 21

      • v↔22v \leftrightarrow 22

      • w↔23w \leftrightarrow 23

      • x↔24x \leftrightarrow 24

      • y↔25y \leftrightarrow 25

      • z↔26z \leftrightarrow 26

    • Total element count: n(A)=26n(A) = 26

    • Equivalence relation: Set AA is equivalent to the index set {n \mid 1 \le n \le 26}.

Equivalence of Sets

  • Definition of Set Equivalence:

    • Two sets AA and BB are equivalent if a one-to-one correspondence can be established between their elements.

    • Symbolic condition: Set AA is equivalent to set B  ⟺  n(A)=n(B)B \iff n(A) = n(B).

  • Equivalence vs. Equality:

    • Equivalence≠Equality\text{Equivalence} \neq \text{Equality}.

    • Equal sets must contain identical elements, whereas equivalent sets need only have the same number of elements (same cardinality).

  • Equivalence in Infinite Sets:

    • Establishing equivalence becomes more complex with infinite sets.

    • Example: The set of even natural numbers EvenN\text{Even}\mathbb{N} is equivalent to the set of all natural numbers N\mathbb{N} (via the one-to-one pairing n↔2nn \leftrightarrow 2n), even though EvenN\text{Even}\mathbb{N} is simultaneously a proper subset of N\mathbb{N} (EvenN⊂N\text{Even}\mathbb{N} \subset \mathbb{N}).

Homework and Exercise Problem Assignments

  • Assigned Reading:

    • Learn Section 2.1

  • Assigned Homework Exercises:

    • Exercises # 1, 3, 5, 8, 13, 22, 27, 31, 32, 43, 52, 65, 69, 73, 80, 83, 86, 92, 95, 96