Discrete Mathematics: Propositional Logic, Quantifiers, and Set Theory

Propositional Logic Fundamentals

• Definition of a Proposition:

  • A proposition is a declarative sentence that is either true or false, but not both.
  • Examples of propositions:
  • "Oregon is a state in the United States of America" is a proposition with a truth value of true.
  • "$1 + 1 = 3$" is a proposition with a truth value of false.
  • Sentences that fail to be propositions include questions, commands, and self-referential paradoxes.
  • For instance, the sentence "This statement is false" cannot be assigned a truth value because assuming it is true implies it is false, and assuming it is false implies it is true; hence, it is not a proposition.
  • Conventional notation uses lower-case propositional variables such as $p$, $q$, and $r$ to represent propositions (e.g., letting $p$ denote "$1 + 1 = 3$").

• Compound Propositions and Basic Logical Operations:

  • Compound propositions are formed by combining or modifying existing propositions using logical operators.
  • Negation ($\neg$):
  • The negation of a proposition $p$, denoted $\neg p$ and read as "not $p$", produces a proposition that is true when $p$ is false, and false when $p$ is true.
  • Disjunction ($\lor$):
  • The disjunction of propositions $p$ and $q$, denoted $p \lor q$ and read as "$p$ or $q$", is a compound proposition that is false strictly when both $p$ and $q$ are false; otherwise, it is true.
  • Conjunction ($\land$):
  • The conjunction of propositions $p$ and $q$, denoted $p \land q$ and read as "$p$ and $q$", is a compound proposition that is true strictly when both $p$ and $q$ are true; otherwise, it is false.

• Truth Tables:

  • Truth tables systematically display the truth values of compound propositions across every possible combination of truth values for their constituent input propositions.
  • Truth values are commonly represented using $T$ (true) and $F$ (false), or alternatively $1$ and $0$.

• Precedence and Order of Operations:
  • The negation operator ($\neg$) holds highest precedence and is evaluated prior to disjunction ($\lor$) and conjunction ($\land$).
  • For example, $\neg p \lor q$ represents $(\neg p) \lor q$ under standard precedence.
  • To apply negation across a compound expression, grouping parentheses are required, as in $\neg(p \lor q)$.
  • The evaluation order between $\lor$ and $\land$ is determined explicitly by parentheses.

Conditional and Biconditional Statements

• The Conditional Statement (Implication):
  • The conditional expression "If $p$ then $q$", denoted $p \rightarrow q$ or $p \Rightarrow q$, asserts that whenever $p$ holds true, $q$ must also hold true.
  • Terminology:
  • $p$ is designated as the hypothesis or antecedent.
  • $q$ is designated as the conclusion or consequent.
  • Truth Conditions:
  • The implication $p \rightarrow q$ evaluates to false solely when the hypothesis $p$ is true and the conclusion $q$ is false.
  • It evaluates to true in all other circumstances.
  • When $p \rightarrow q$ evaluates to true because $p$ is false, the implication is described as vacuously true or true by default.
  • Precedence:
  • The conditional operator ($\rightarrow$) shares the same level of operator precedence as $\lor$ and $\land$.

• Linguistic Variants of $p \rightarrow q$:

  • Implication can be expressed in natural language in multiple ways:
  • "$q$ if $p$"
  • "$q$ whenever $p$"
  • "$p$ only if $q$"
  • "$p$ implies $q$"
  • Caution: The expression "It is raining only if there are clouds in the sky" is equivalent to "If it is raining then there are clouds in the sky" ($p \rightarrow q$). This is distinct from the reversed conditional "If there are clouds in the sky then it is raining" ($q \rightarrow p$).

• Related Conditional Statements:

  • Given an original conditional statement $p \rightarrow q$:
  • Converse: $q \rightarrow p$
  • Inverse: $\neg p \rightarrow \neg q$
  • Contrapositive: $\neg q \rightarrow \neg p$
  • Worked Example:
  • Statement: "If Jack bought beer then Jack went to the store."
  • Definition of components:
    • $p$: Jack bought beer.
    • $q$: Jack went to the store.
  • Symbolic form: $p \rightarrow q$
  • Converse ($q \rightarrow p$): "If Jack went to the store then Jack bought beer."
  • Inverse ($\neg p \rightarrow \neg q$): "If Jack didn't buy beer then Jack didn't go to the store."
  • Contrapositive ($\neg q \rightarrow \neg p$): "If Jack didn't go to the store then Jack didn't buy beer."

• Necessary and Sufficient Conditions:

  • Necessary Condition: A condition that must be satisfied given that a proposition holds true. The conclusion $q$ of a true conditional $p \rightarrow q$ is a necessary condition of the hypothesis $p$.
  • Sufficient Condition: A condition that suffices to guarantee that a proposition holds true. The hypothesis $p$ of a true conditional $p \rightarrow q$ is a sufficient condition for the conclusion $q$.
  • Example Analysis:
  • Consider the true implication: "If $x$ is a non-zero whole number, then $x^2$ is a positive whole number."
  • "$x^2$ is a positive whole number" is a necessary condition of "$x$ is a non-zero whole number."
  • "$x$ is a non-zero whole number" is a sufficient condition for "$x^2$ is a positive whole number."
  • Counterexample demonstrating that "$x$ is a non-zero whole number" is not a necessary condition: Setting $x = \sqrt{2}$ yields $x^2 = 2$, which is a positive whole number, even though $\sqrt{2}$ is not a non-zero whole number.

• Biconditional Statement:

  • The proposition "$p$ if and only if $q$" (abbreviated "$p$ iff $q$") is denoted $p \leftrightarrow q$.
  • It is formally defined by the conjunction of forward and reverse implications:     $(p \rightarrow q) \land (q \rightarrow p)$

Logical Equivalences, Tautologies, and Contradictions

• Logical Equivalence ($\equiv$):

  • Two compound propositions $P$ and $Q$, constructed from constituent propositions $p_1, p_2, \dots, p_n$, are logically equivalent ($P \equiv Q$) if they produce identical truth values across all possible combinations of truth values of their constituents.
  • Fundamental Equivalences:
  • Double Negation Law: $\neg(\neg p) \equiv p$
  • Commutative Laws: $p \lor q \equiv q \lor p$ and $p \land q \equiv q \land p$
  • Contrapositive Equivalence: $p \rightarrow q \equiv \neg q \rightarrow \neg p$

• De Morgan's Laws for Propositional Logic:

  • $\neg(p \lor q) \equiv \neg p \land \neg q$
  • $\neg(p \land q) \equiv \neg p \lor \neg q$

• Disjunctive Form and Negation of Conditional Statements:

  • The conditional proposition $p \rightarrow q$ is false only when $p$ is true and $q$ is false, which corresponds to when $\neg p$ is false and $q$ is false. Thus, it can be expressed as a disjunction:     $p \rightarrow q \equiv \neg p \lor q$
  • Applying De Morgan's Laws yields the logical negation of an implication:     $\neg(p \rightarrow q) \equiv \neg(\neg p \lor q) \equiv \neg(\neg p) \land \neg q \equiv p \land \neg q$
  • Worked Example (Negation of Necessary Condition):
  • Statement to negate: "A necessary condition of Serena buying the car she wants is that Serena passes the credit check for the car loan."
  • Standard conditional formulation ($p \rightarrow q$):
    • $p$: Serena buys the car she wants.
    • $q$: Serena passes the credit check for the car loan.
    • "If Serena buys the car she wants then Serena passes the credit check for the car loan."
  • Negated form ($\neg(p \rightarrow q) \equiv p \land \neg q$):
    • "Serena buys the car she wants and Serena doesn't pass the credit check for the car loan."

• Tautologies and Contradictions:

  • Tautology: A compound proposition that evaluates to true across all possible truth assignments of its constituent variables.
  • Example: $(p \rightarrow p) \lor q$
  • Contradiction: A compound proposition that evaluates to false across all possible truth assignments of its constituent variables.
  • Example: $(p \land q) \land \neg q$

Quantified Logic

• Propositional Functions and Domains:

  • A propositional function (or predicate) is an open sentence containing a finite number of variables that becomes a well-defined proposition once specific values from a domain are substituted for those variables.
  • The domain of a variable denotes the set of all allowable values eligible for substitution.
  • Examples:
  • Predicate $P(x, y)$ defined as "$x > y$" over the domain of whole numbers $\{0, 1, 2, \dots\}$:
    • $P(1, 2)$ asserts "$1 > 2$", which evaluates to false.
    • $P(3, 2)$ asserts "$3 > 2$", which evaluates to true.
  • Predicate $P(x)$ defined as "$x$ is a former president of the USA" over the domain of human beings:
    • $P(\text{Barack Obama})$ is true.
    • $P(\text{Tom Cruise})$ is false.

• Universal Quantification ($\forall$):

  • The statement "for all $x \in D$, $P(x)$", denoted $\forall x \in D, P(x)$ (or $\forall x, P(x)$), is a proposition that evaluates to true if and only if $P(x)$ is true for every element $x$ in domain $D$.
  • The statement is false if there exists at least one element in $D$ for which $P(x)$ is false.
  • Proof Techniques:
  • To prove $\forall x, P(x)$ is true: Demonstrate that $P(x)$ holds for an arbitrary, general choice of $x \in D$.
  • To prove $\forall x, P(x)$ is false: Provide a single counterexample, which is a specific element $x \in D$ for which $P(x)$ evaluates to false.
  • Worked Examples:
  • Statement: $\forall x \in \mathbb{R}, \frac{1}{1 + x^2} \le 1$
    • Evaluation: True.
    • Justification: Let $x \in \mathbb{R}$ be an arbitrary real number. Since $x^2 \ge 0$, adding $1$ gives $1 + x^2 \ge 1$. Taking reciprocals preserves the inequality direction relative to zero, yielding $\frac{1}{1 + x^2} \le 1$.
  • Statement: $\forall x \in \mathbb{R}, \frac{1}{1 + x^2} < 1$
    • Evaluation: False.
    • Justification: Consider the counterexample $x = 0$. When $x = 0$, $1 + x^2 = 1 + 0^2 = 1$, giving $\frac{1}{1 + 0^2} = 1$. Since $1 < 1$ is false, the universally quantified proposition is false.

• Existential Quantification ($\exists$):

  • The statement "there exists $x \in D$ such that $P(x)$", denoted $\exists x \in D, P(x)$ (or $\exists x, P(x)$), evaluates to true if and only if $P(x)$ is true for at least one element $x \in D$.
  • The statement is false if $P(x)$ is false for every element in $D$.
  • Proof Techniques:
  • To prove $\exists x, P(x)$ is true: Exhibit a single explicit witness $x \in D$ that satisfies $P(x)$.
  • To prove $\exists x, P(x)$ is false: Demonstrate that $P(x)$ is false for every choice of $x \in D$.
  • Worked Examples:
  • Statement: $\exists x \in \mathbb{R}, x^2 < x$
    • Evaluation: True.
    • Witness: Select $x = 0.5$. Then $x^2 = (0.5)^2 = 0.25$, and $0.25 < 0.5$.
  • Statement: $\exists x \in \mathbb{R}, \left( x > 1 \rightarrow \frac{x^2}{x + 1} \le \frac{1}{2} \right)$
    • Evaluation: True.
    • Witness: Select $x = 0$. The antecedent $0 > 1$ is false, making the conditional statement true by default.
  • Statement: $\exists x \in (1, \infty), \frac{x^2}{x + 1} \le \frac{1}{2}$
    • Evaluation: False.
    • Justification: Let $x \in (1, \infty)$, so $x > 1$. It follows that $x^2 > x$. Multiplying by $2$ gives $2x^2 > 2x$. Because $x > 1$, $2x = x + x > x + 1 > 2$. Thus $2x^2 > x + 1$. Dividing by the positive quantity $x + 1$ yields:         $\frac{2x^2}{x + 1} > 1$         Multiplying both sides by $\frac{1}{2}$ gives:         $\frac{x^2}{x + 1} > \frac{1}{2}$         Because $\frac{x^2}{x + 1} > \frac{1}{2}$ for all $x \in (1, \infty)$, the existential statement is false.

• De Morgan's Laws for Quantifiers:

  • Negating a universally quantified statement yields an existentially quantified statement:     $\neg(\forall x, P(x)) \equiv \exists x, \neg P(x)$
  • Negating an existentially quantified statement yields a universally quantified statement:     $\neg(\exists x, P(x)) \equiv \forall x, \neg P(x)$
  • Application Example:
  • Original statement: "All mammals cannot fly."
  • Symbolic formulation: Let $P(x)$ denote "Mammal $x$ cannot fly." The statement is $\forall x, P(x)$.
  • Negation: $\neg(\forall x, P(x)) \equiv \exists x, \neg P(x)$.
  • Natural language interpretation: "There exists a mammal such that the mammal can fly" (colloquially, "Some mammals fly").

• Linguistic Nuances in Negative Quantifications:

  • Statements meaning $\exists x, \neg P(x)$ (equivalent to $\neg(\forall x, P(x))$):
  • "Not all $x$ satisfy $P(x)$"
  • "Not each $x$ satisfies $P(x)$"
  • "Not every $x$ satisfies $P(x)$"
  • Statements meaning $\forall x, \neg P(x)$ (equivalent to $\neg(\exists x, P(x))$):
  • "Not any $x$ satisfies $P(x)$"
  • "No $x$ satisfies $P(x)$"

Nested Quantifiers and Advanced Applications

• Order Dependence of Quantifiers:

  • The semantic meaning and truth value of a quantified statement depend heavily on the sequential order of nested quantifiers.
  • Example: Multiplicative Inverses:
  • The statement "For every positive real number $x$ there exists a positive real number $y$ such that $xy = 1$" is written symbolically as:       $\forall x \in (0, \infty), \exists y \in (0, \infty), xy = 1$
  • This proposition is true; it conveys that every positive real number possesses a multiplicative inverse (reciprocal).
  • Reversing the quantifiers produces:       $\exists y \in (0, \infty), \forall x \in (0, \infty), xy = 1$
  • This proposition is false because the existential variable $y$ would have to be chosen independently of $x$, and no universal constant real number exists that produces $1$ when multiplied by any arbitrary real number.
  • Example: Strict Ordering:
  • Proposition: $\forall x \in \mathbb{R}, \exists y \in \mathbb{R}, x < y$
    • Evaluation: True.
    • Justification: For any given $x \in \mathbb{R}$, setting $y = x + 1$ guarantees $y \in \mathbb{R}$ and $x < x + 1$.
  • Reversing the order produces $\exists y \in \mathbb{R}, \forall x \in \mathbb{R}, x < y$, which is false because no single real number is strictly greater than every real number.
  • Example: Circle Equations:
  • Proposition: $\exists x \in \mathbb{R}, \forall y \in \mathbb{R}, x^2 + y^2 = 1$
    • Evaluation: False.
    • Justification: Let $x$ be an arbitrary real number. Selecting $y = 2$ yields $x^2 + y^2 = x^2 + 4 \ge 4 \ne 1$.
  • The reversed statement $\forall y \in \mathbb{R}, \exists x \in \mathbb{R}, x^2 + y^2 = 1$ is also false (e.g., choosing $y = 2$ requires $x^2 = -3$, which has no solution over $\mathbb{R}$).

• Sequential Application of De Morgan's Laws on Nested Quantifiers:

  • Multi-variable statements are negated by propagating the negation inwards and alternating each quantifier:     $\neg(\forall x \in \mathbb{R}, \exists y \in \mathbb{R}, x < y) \equiv \exists x \in \mathbb{R}, \neg(\exists y \in \mathbb{R}, x < y) \equiv \exists x \in \mathbb{R}, \forall y \in \mathbb{R}, x \ge y$

• Formal Analysis of Limits from Calculus:

  • The technical $\epsilon$-$\delta$ definition of a limit, $\lim_{x \to a} f(x) = L$, asserts:
  • For every $\epsilon > 0$, there exists $\delta > 0$ such that for all $x \in \mathbb{R}$, $0 < |x - a| < \delta \rightarrow |f(x) - L| < \epsilon$.
  • Predicates:
  • $P(x, \delta)$: $0 < |x - a| < \delta$
  • $Q(x, \epsilon)$: $|f(x) - L| < \epsilon$
  • Symbolic Formulation:     $\forall \epsilon > 0, \exists \delta > 0, \forall x \in \mathbb{R}, P(x, \delta) \rightarrow Q(x, \epsilon)$
  • Derivation of the Negation ($\lim_{x \to a} f(x) \ne L$):
  • Step 1: Push negation through quantifiers:       $\neg(\forall \epsilon > 0, \exists \delta > 0, \forall x, P(x, \delta) \rightarrow Q(x, \epsilon)) \equiv \exists \epsilon > 0, \forall \delta > 0, \exists x, \neg(P(x, \delta) \rightarrow Q(x, \epsilon))$
  • Step 2: Express implication in disjunctive form:       $\exists \epsilon > 0, \forall \delta > 0, \exists x, \neg(\neg P(x, \delta) \lor Q(x, \epsilon))$
  • Step 3: Apply De Morgan's Law to the predicate:       $\exists \epsilon > 0, \forall \delta > 0, \exists x, (P(x, \delta) \land \neg Q(x, \epsilon))$
  • Final Statement in Words:
  • There exists $\epsilon > 0$ such that for all $\delta > 0$, there exists $x \in \mathbb{R}$ such that $0 < |x - a| < \delta$ and $|f(x) - L| \ge \epsilon$.

Set Theory Fundamentals and Sets of Numbers

• Set Definitions and Axioms:

  • The formalization of set theory was introduced by Georg Cantor in 1879.
  • A set is an unordered collection of distinct objects where order and repetition are not taken into account.
  • Two sets are equal if and only if they share identical members.
  • Membership is denoted by $x \in S$ ($x$ is an element/member of $S$) or $x \notin S$ ($x$ is not an element/member of $S$).
  • A set is finite if its count of elements is finite, and infinite otherwise.

• Set Notations:

  • Set-bracket notation: Direct roster listing of elements enclosed within braces, e.g.:
  • $A = \{2, 3, 5\}$
  • $B = \{\text{red}, \text{white}, \text{blue}\}$
  • $C = \{\{1\}, \{1, 2\}\}$
  • $\emptyset = \{\}$ (the empty set or null set, containing zero elements).
  • Ellipses Notation: Used to denote ongoing patterns:
  • Finite set: $H = \{1, 2, 3, \dots, 100\}$
  • Infinite set of prime numbers: $P = \{2, 3, 5, 7, 11, \dots\}$
  • Set-builder notation: Defines a set by filtering a domain $D$ through conditions $c_1, c_2, \dots, c_k$:     $S = \{x \in D \mid c_1, c_2, \dots, c_k\}$
  • Example: Letting $D$ be all living humans, $S = \{x \in D \mid x \text{ owns a vehicle}, x \text{ is at least 65 years old}\}$.

• Cardinality and Subsets:

  • Cardinality: The number of elements in a finite set $S$, denoted $|S|$.
  • Subset ($\subseteq$): $S \subseteq T$ if and only if every element of $S$ is also an element of $T$.
  • Proper Subset ($\subset$): $S \subset T$ if and only if $S \subseteq T$ and $S \ne T$.
  • Negations: $S \not\subseteq T$ indicates $S$ is not a subset of $T$; $S \not\subset T$ indicates $S$ is not a proper subset of $T$.
  • Default Rule: The empty set is a subset of every set ($\emptyset \subseteq S$ for all sets $S$).
  • Double Containment Proof Technique: Two sets are proved equal ($S = T$) by showing mutual inclusion: $S \subseteq T$ and $T \subseteq S$.
  • Recipe to prove $S \subseteq T$: Assume an arbitrary element $x \in S$, and deduce logically that $x \in T$.
  • Universe ($U$): An overarching universal set encompassing all sets under active consideration as subsets.

• Standard Number Systems:

  • Digits: The set $\{0, 1, 2, \dots, 9\}$.
  • Natural Numbers ($\mathbb{N}$): The set $\{1, 2, 3, \dots\}$.
  • Integers ($\mathbb{Z}$): The set $\{0, -1, 1, -2, 2, \dots\}$. Positive integers are denoted $\mathbb{Z}^+$, where $\mathbb{Z}^+ = \mathbb{N}$.
  • Rational Numbers ($\mathbb{Q}$): The set of fractions formed from integers:     $\mathbb{Q} = \left\{ \frac{p}{q} \;\middle|\; p, q \in \mathbb{Z}, q \ne 0 \right\}$
  • Real Numbers ($\mathbb{R}$): Defined as the set of all signed decimal expansions of the form:     $\pm \dots d_2 d_1 d_0 . d_{-1} d_{-2} \dots = \pm \sum_{i=-\infty}^{\infty} d_i 10^i$     where each $d_i$ is a digit, and all but finitely many digits $d_i$ where $i \ge 0$ are $0$.
  • Subsetting: Since elementary long division converts any fraction $p/q$ into a decimal expansion, $\mathbb{Q} \subseteq \mathbb{R}$.
  • Irrational Numbers ($\mathbb{I}$): The complement of the rationals within the reals:     $\mathbb{I} = \{x \in \mathbb{R} \mid x \notin \mathbb{Q}\}$
  • Complex Numbers ($\mathbb{C}$): The set of linear combinations of real numbers and the imaginary unit $i = \sqrt{-1}$:     $\mathbb{C} = \{a + bi \mid a, b \in \mathbb{R}, i^2 = -1\}$
  • The real numbers form a subset of the complex numbers with zero imaginary part:       $\mathbb{R} = \{a + bi \in \mathbb{C} \mid b = 0\}$

• Power Sets:

  • The power set of a set $X$, denoted $\mathcal{P}(X)$, is the set of all subsets of $X$, ranging from $\emptyset$ to $X$.
  • Example: For $X = \{a, b\}$, the power set is:     $\mathcal{P}(\{a, b\}) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$
  • Cardinality Rule: For any finite set $X$, the cardinality of its power set is given by:     $|\mathcal{P}(X)| = 2^{|X|}$

• Venn Diagrams:

  • Venn diagrams provide visual geometric representations of sets as circles enclosed inside a universal bounding rectangle $U$.

Set Operations and Principle of Inclusion-Exclusion

• Fundamental Operations on Sets:

  • Union ($\cup$): The set of all elements belonging to $S$ or $T$ (or both):     $S \cup T = \{x \mid x \in S \lor x \in T\}$
  • Example: $\{1, 2, 3, 4, 5\} \cup \{2, 3, 5, 7\} = \{1, 2, 3, 4, 5, 7\}$
  • Intersection ($\cap$): The set of all elements belonging simultaneously to $S$ and $T$:     $S \cap T = \{x \mid x \in S \land x \in T\}$
  • Example: $\{1, 2, 3, 4, 5\} \cap \{2, 3, 5, 7\} = \{2, 3, 5\}$
  • Disjoint Sets: Two sets $S$ and $T$ are disjoint if they share no elements, meaning $S \cap T = \emptyset$.
  • Relative Difference ($\setminus$ or $-$): Elements present in $S$ that are not in $T$:     $S \setminus T = \{x \mid x \in S \land x \notin T\}$
  • Example: $\{1, 2, 3, 4, 5\} \setminus \{2, 3, 5, 7\} = \{1, 4\}$
  • Complement ($\overline{T}$, $T^c$, or $T'$): Elements of universe $U$ that do not belong to $T$:     $\overline{T} = \{x \in U \mid x \notin T\}$
  • Example: In the universe of digits, $\overline{\{2, 3, 5, 7\}} = \{0, 1, 4, 6, 8, 9\}$
  • Cartesian Product (Direct Product, $\times$): The set of all ordered pairs formed from two sets:     $S \times T = \{(s, t) \mid s \in S, t \in T\}$
  • Example: $\mathbb{R} \times \mathbb{R} = \mathbb{R}^2$ represents the continuous two-dimensional $xy$-plane.
  • Cardinality Rule: For finite sets, $|S \times T| = |S| \cdot |T|$.
  • Generalization to $k$ sets:       $S_1 \times S_2 \times \dots \times S_k = \{(s_1, s_2, \dots, s_k) \mid s_i \in S_i \text{ for } i = 1, 2, \dots, k\}$$|S_1 \times S_2 \times \dots \times S_k| = |S_1| \cdot |S_2| \cdots |S_k|$

• Principle of Inclusion-Exclusion:

  • When adding cardinalities of two finite sets, the elements in their intersection are counted twice. Correcting for double counting yields:     $|S \cup T| = |S| + |T| - |S \cap T|$
  • If $S$ and $T$ are disjoint, $|S \cap T| = 0$, simplifying the formula to $|S \cup T| = |S| + |T|$.
  • Worked Application (Multiples in a Finite Domain):
  • Goal: Count how many multiples of $3$ or $5$ exist within the set $D = \{1, 2, 3, \dots, 999\}$.
  • Multiples of $3$: $T = \{3, 6, 9, \dots, 999\}$, with cardinality $|T| = \frac{999}{3} = 333$.
  • Multiples of $5$: $F = \{5, 10, 15, \dots, 995\}$, with cardinality $|F| = 200 - 1 = 199$.
  • Multiples of both $3$ and $5$ (multiples of $15$): $T \cap F = \{15, 30, 45, \dots, 990\}$, with cardinality $|T \cap F| = \lfloor \frac{999}{15} \rfloor = 66$.
  • Total count via inclusion-exclusion:       $|T \cup F| = |T| + |F| - |T \cap F| = 333 + 199 - 66 = 466$

Theory of Functions

• Formal Set-Theoretic Definition:

  • Let $X$ and $Y$ be non-empty sets. A function $f$ from $X$ to $Y$, denoted $f : X \to Y$, is a subset of the Cartesian product $X \times Y$ satisfying the property that for every $x \in X$, there exists a unique $y \in Y$ such that $(x, y) \in f$.
  • Structural Properties:
  • A function is formally a set of ordered pairs.
  • The expression $y = f(x)$ serves as shorthand notation for $(x, y) \in f$.
  • The function assigns to each element of $X$ exactly one element of $Y$.
  • Functions are typically defined by an assignment rule, such as $f(x) = x^2$, which denotes $f = \{(x, x^2) \mid x \in \mathbb{R}\}$.
  • Formally, there is no distinction between a function and its geometric graph in $X \times Y$; a function is identical to its graph.

• Domain, Codomain, and Range:

  • In $f : X \to Y$, $X$ is the domain and $Y$ is the codomain.
  • The range (or image) is the set of elements in $Y$ mapped to by elements in $X$:     $f(X) = \{y \in Y \mid \exists x \in X \text{ such that } y = f(x)\} \subseteq Y$
  • Worked Example (Finding Range):
  • Function: $f : \mathbb{R} \to \mathbb{R}$ given by $f(x) = \sqrt{x^2 + 1}$.
  • Proof: For any real number $x$, $x^2 \ge 0 \implies x^2 + 1 \ge 1 \implies f(x) = \sqrt{x^2 + 1} \ge 1$.
  • For any arbitrary $y \ge 1$, solving $y = \sqrt{x^2 + 1}$ yields $x = \sqrt{y^2 - 1}$, which is a valid real number satisfying $f(x) = y$.
  • Thus, the range of $f$ is the interval $[1, \infty)$.

• Arrow Diagrams:

  • Arrow diagrams depict functions by drawing two ovals representing domain $X$ and codomain $Y$, with directional arrows connecting each point $x \in X$ to its uniquely assigned image $y \in Y$.

• Classifications of Functions:

  • One-to-One (Injective):
  • $f : X \to Y$ is injective if for each $y \in Y$, there exists at most one $x \in X$ such that $y = f(x)$.
  • Proof strategy: Assume $f(x_1) = f(x_2)$ for arbitrary $x_1, x_2 \in X$, and prove that $x_1 = x_2$.
  • Disproof strategy: Identify two distinct elements $x_1, x_2 \in X$ ($x_1 \ne x_2$) such that $f(x_1) = f(x_2)$.
  • Onto (Surjective):
  • $f : X \to Y$ is surjective if for each $y \in Y$, there exists at least one $x \in X$ such that $y = f(x)$.
  • Proof strategy: Let $y \in Y$ be arbitrary and solve for an element $x \in X$ satisfying $y = f(x)$.
  • Disproof strategy: Find a specific target $y \in Y$ such that for all $x \in X$, $y \ne f(x)$.
  • Bijection:
  • A function $f : X \to Y$ is a bijection if it is both one-to-one (injective) and onto (surjective).

• Classification Case Studies:

  • Case Study 1: Identification Numbers:
  • Let $X$ be the set of OSU students, faculty, and staff, and let $Y$ be the set of 9-digit strings. A function maps each person to an assigned identification number.
  • The function is $1-1$ because each 9-digit string maps to at most one person, with ID assignments chosen outside existing identifiers.
  • The function is not onto because the cardinality of $X$ is strictly less than the total number of available 9-digit strings ($10^9 = 1\text{ billion}$).
  • Case Study 2: Rational Function from Integers:
  • Let $f : \mathbb{N} \to \mathbb{Q}$ be defined by:       $f(n) = \frac{n}{1 + n^2}$
  • Injectivity Proof:
    • Let $m, n \in \mathbb{N}$ and assume $f(m) = f(n)$.         $\frac{m}{1 + m^2} = \frac{n}{1 + n^2}$$m(1 + n^2) = n(1 + m^2)$$m + mn^2 = n + nm^2$$(m - n) = nm^2 - mn^2 = mn(m - n)$$(m - n)(1 - mn) = 0$
    • This factors into two cases: $m - n = 0$ or $1 - mn = 0$.
    • In the first case, $m = n$.
    • In the second case, $mn = 1$. Since $m, n \in \mathbb{N}$, the only natural solution is $m = 1$ and $n = 1$, which also yields $m = n$.
    • Since $m = n$ in all cases, $f$ is $1-1$.
  • Surjectivity Proof:
    • Consider $0 \in \mathbb{Q}$. For any $n \in \mathbb{N}$, $n \ne 0$, so $f(n) = \frac{n}{1 + n^2} \ne 0$.
    • Because $0$ has no pre-image in $\mathbb{N}$, $f$ is not onto, and consequently $f$ is not a bijection.

• Inverse Functions:

  • If $f : X \to Y$ is a bijection, the relation $g = \{(y, x) \mid (x, y) \in f\} \subseteq Y \times X$ defines a bijection from $Y$ to $X$.
  • The relation $g$ is called the inverse function of $f$, denoted $f^{-1} : Y \to X$.
  • Example: For $f : \mathbb{Q} \to \mathbb{Q}$ defined by $f(n) = 2n + 1$, the inverse function is:     $f^{-1}(n) = \frac{n - 1}{2}$

• Function Composition:

  • Let $g : X \to Y$ and $f : Y \to Z$ be functions. The composition of $f$ with $g$, denoted $f \circ g : X \to Z$, is defined by:     $(f \circ g)(x) = f(g(x))$
  • Well-definedness: For each $x \in X$, $g(x)$ is the unique element of $Y$ assigned to $x$, and $f(g(x))$ is the unique element of $Z$ assigned to $g(x)$; thus, $(f \circ g)(x)$ assigns a unique element of $Z$ to $x$.
  • Example:
  • Let $X = Y = Z = \{a, b, c\}$.
  • Let $f = \{(a, a), (b, c), (c, b)\}$ and $g = \{(a, b), (b, c), (c, a)\}$.
  • The composite function is:       $f \circ g = \{(a, c), (b, b), (c, a)\}$
  • Injectivity Properties of Compositions:
  • If $g$ is $1-1$, is $f \circ g$ necessarily $1-1$? No.
    • Counterexample: Let $g = \{(1, 2), (2, 3)\}$ and $f = \{(2, 5), (3, 5)\}$.
    • Here $g$ is $1-1$, but $f \circ g = \{(1, 5), (2, 5)\}$, which is not $1-1$.
  • Theorem: If $f \circ g$ is $1-1$, then $g$ must be $1-1$.
    • Proof: Let $X, Y, Z$ be non-empty sets, $f : Y \to Z$, $g : X \to Y$, and assume $f \circ g$ is $1-1$.
    • Let $x_1, x_2 \in X$, and assume $g(x_1) = g(x_2)$.
    • Applying function $f$ to both sides gives $f(g(x_1)) = f(g(x_2))$.
    • By composition definition, $(f \circ g)(x_1) = (f \circ g)(x_2)$.
    • Since $f \circ g$ is injective, it follows that $x_1 = x_2$.
    • Therefore, $g$ is $1-1$.

Families of Sets, Partitions, and Foundational Paradoxes

• Indexed Families of Sets:

  • Let $I$ be an index set. If a set $S_i$ exists for each $i \in I$, the collection $S = \{S_i \mid i \in I\}$ is an indexed family of sets.
  • Elements with distinct indices can be identical sets: $S_i = S_j$ is permissible for $i \ne j$.
  • Pairwise Disjoint Families: An indexed family $S = \{S_i \mid i \in I\}$ is pairwise disjoint if for all $i, j \in I$, either $S_i = S_j$ or $S_i \cap S_j = \emptyset$.
  • Example: The family of half-open intervals $F = \{[n, n + 1) \mid n \in \mathbb{N}\}$ over $\mathbb{R}$.
  • For $m, n \in \mathbb{N}$ with $[m, m + 1) \ne [n, n + 1)$, either $m \ge n + 1$ or $n \ge m + 1$, meaning $[m, m + 1) \cap [n, n + 1) = \emptyset$. Hence, $F$ is pairwise disjoint.

• Arbitrary Unions and Intersections:

  • Intersection of an Indexed Family:$\bigcap S = \bigcap_{i \in I} S_i = \{x \mid x \in S_i \text{ for all } i \in I\}$
  • Union of an Indexed Family:$\bigcup S = \bigcup_{i \in I} S_i = \{x \mid x \in S_i \text{ for some } i \in I\}$
  • Worked Example (Intervals of Real Numbers):
  • Consider the family of open intervals $S = \left\{ \left( 0 - \frac{1}{n}, 1 + \frac{1}{n} \right) \;\middle|\; n \in \mathbb{N} \right\}$.
  • Intersection evaluation:       $\bigcap S = \bigcap_{n \in \mathbb{N}} \left( -\frac{1}{n}, 1 + \frac{1}{n} \right) = [0, 1]$
    • Proof: Every number in the closed interval $[0, 1]$ lies in $\left(-\frac{1}{n}, 1 + \frac{1}{n}\right)$ for all $n \in \mathbb{N}$. For any real number outside $[0, 1]$, choosing a sufficiently large $n \in \mathbb{N}$ makes the interval too narrow to contain that number.
  • Union evaluation:       $\bigcup S = \bigcup_{n \in \mathbb{N}} \left( -\frac{1}{n}, 1 + \frac{1}{n} \right) = (-1, 2)$
    • Proof: Setting $n = 1$ yields the interval $(-1, 2)$. For every integer $n > 1$, the interval is a strict subset of $(-1, 2)$.

• Partitions of a Set:

  • A partition of a set $S$ is a family $C = \{P_i \mid i \in I\}$ of non-empty, pairwise disjoint sets indexed by $I$ whose union equals $S$:     $\bigcup C = \bigcup_{i \in I} P_i = S$
  • Examples:
  • $C = \{\{1\}, \{2, 3\}, \{4, 5\}\}$ is a partition of the set $S = \{1, 2, 3, 4, 5\}$.
  • The family $F = \{[n, n + 1) \mid n \in \mathbb{N}\}$ is a partition of the continuous ray $[1, \infty)$.
  • The Sum Rule of Counting:
  • If $C = \{P_i \mid i \in I\}$ is a partition of a finite set $S$, then the cardinality of $S$ is the sum of the cardinalities of the partition blocks:       $|S| = \sum_{i \in I} |P_i|$

• Foundational Crisis and Russell's Paradox:

  • In classic (naive) set theory, sets could be defined arbitrarily using conditions. This leads to mathematical inconsistency.
  • Russell's Set Theory Paradox:
  • Let $U$ denote the universe of all sets.
  • Define $R$ as the set of all sets that are not members of themselves:       $R = \{S \in U \mid S \notin S\}$
  • Contradiction:
    • If $R \notin R$, then by the defining condition of $R$, $R$ must belong to $R$ ($R \in R$).
    • If $R \in R$, then by definition $R$ cannot be a member of itself ($R \notin R$).
  • Conclusion: The set $R$ cannot exist; it is an ill-defined set.
  • Remedy: Modern axiomatic set theory restricts the universe to well-defined sets, excluding self-contradictory formulations.

• De Morgan's Laws for Sets:

  • The complement of a union is the intersection of the complements:     $\overline{S \cup T} = \overline{S} \cap \overline{T}$
  • The complement of an intersection is the union of the complements:     $\overline{S \cap T} = \overline{S} \cup \overline{T}$