MTH202 — Midterm Summary (Lectures 1–22)

📘 Lecture 1 — Logic

📖 Overview: This lecture introduces the fundamental concepts of logic, which is the study of valid and invalid arguments. It defines simple statements (propositions) and how they can be combined using logical connectives to form compound statements. Understanding logic is essential for precise reasoning in mathematics and computer science.

🗂️ Topics Covered

The lecture begins with an overview of the Discrete Mathematics course, its objectives, and recommended books. It then defines what Discrete Mathematics is and introduces the core concept of logic. The main body covers simple statements (propositions), their truth values, and how to identify them. Finally, it explains compound statements formed using logical connectives (negation, conjunction, disjunction), symbolic representation, translation between English and symbols, and how to construct truth tables.

📝 Lecture Summary

Course Introduction

The course covers 12 main topics: Logic, Sets & Operations on sets, Relations & Their Properties, Functions, Sequences & Series, Recurrence Relations, Mathematical Induction, Loop Invariants, Combinatorics, Probability, and Graphs and Trees.

🔑 Definition — Discrete Mathematics: Discrete mathematics concerns processes that consist of a sequence of individual steps.

What is Logic?

Logic is the study of the principles and methods that distinguish between a valid and an invalid argument.

Simple Statement

A statement (or proposition) is a declarative sentence that is either true or false but not both. If a proposition is true, it has a truth value of "true" (denoted T). If false, its truth value is "false" (denoted F).

📌 Example: "Grass is green" (true). "4 + 2 = 7" (false). "Close the door" is NOT a proposition (it's a command). "x is greater than 2" is not a proposition unless x is defined.

Rule: If the sentence is preceded by other sentences that make the pronoun or variable reference clear, then the sentence is a statement.

📌 Example: If x = 1, then "x > 2" is a statement with truth value FALSE.

📌 Example: "Bill Gates is an American. He is very rich." — "He is very rich" is a statement with truth value TRUE.

Compound Statement

Simple statements can be used to build a compound statement using logical connectives.

The logical connectives are: AND (conjunction), OR (disjunction), and NOT (negation).

Symbolic Representation

Statements are symbolically represented by letters such as p, q, r...

Translating from English to Symbols

Let p = "It is hot", and q = "It is sunny".

📌 Example: Let h = "Zia is healthy", w = "Zia is wealthy", s = "Zia is wise".

1. "Zia is healthy and wealthy but not wise." → (h ∧ w) ∧ (~ s)
2. "Zia is not wealthy but he is healthy and wise." → ~ w ∧ (h ∧ s)
3. "Zia is neither healthy, wealthy nor wise." → ~ h ∧ ~ w ∧ ~ s

📌 Example: Let m = "Ali is good in Mathematics", c = "Ali is a Computer Science student".

1. ~ c → "Ali is not a Computer Science student"
2. c ∨ m → "Ali is a Computer Science student or good in Maths."
3. m ∧ ~ c → "Ali is good in Maths but not a Computer Science student"

Truth Table

A truth table specifies the truth value of a compound proposition for all possible truth values of its constituent propositions.

Negation (~)

If p is a statement, then the negation of p, "not p", is denoted as "~p". It has the opposite truth value from p.

Conjunction (∧)

The conjunction of p and q is "p and q", denoted as "p ∧ q". p ∧ q is true only when both p and q are true; otherwise it is false.

Disjunction (∨) or Inclusive OR

The disjunction of p and q is "p or q", denoted as "p ∨ q". p ∨ q is true when at least one of p or q is true; it is false only when both p and q are false.

💡 Why this matters: For conjunction, you find T in both statements; for disjunction, you find F in both statements.

⭐ Key Takeaways

A statement (proposition) must be a declarative sentence that is either true or false, but not both. Logical connectives (negation, conjunction, disjunction) combine simple statements into compound statements. A truth table systematically shows the truth value of a compound statement for all possible truth values of its components. The negation (~p) flips the truth value of p. The conjunction (p ∧ q) is true only when both p and q are true, while the disjunction (p ∨ q) is false only when both p and q are false.

🧠 Quick Revision Questions

1. What are the two essential properties a declarative sentence must have to be considered a statement (proposition)?
2. What is the truth value of the conjunction p ∧ q when p is false and q is true?
3. Translate the sentence "It is not hot but sunny" into symbolic form using p = "It is hot" and q = "It is sunny".
4. For what combination of truth values of p and q is the disjunction p ∨ q false?
5. What is the name and symbol for the logical connective that represents "if...then..."?

📘 Lecture 2 — Truth Tables

📖 Overview: This lecture introduces truth tables as a systematic method for determining the truth values of compound logical statements. It explores inclusive and exclusive OR, logical equivalence, De Morgan’s Laws, tautologies, contradictions, and the fundamental laws of logic that govern propositional reasoning.

🗂️ Topics Covered

The lecture covers truth table construction for statements involving negation, conjunction, disjunction, and exclusive OR. It then explains logical equivalence with the double negative property and De Morgan’s Laws applied to statements and inequalities. Finally, it defines tautologies, contradictions, and presents the complete set of laws of logic including commutative, associative, distributive, identity, negation, and absorption laws.

📝 Lecture Summary

Truth Tables for: ~ p ∧ q

A truth table lists all possible truth values for statement variables and shows the resulting truth value of a compound statement for each combination. For ~ p ∧ q, first compute the negation of p, then find the conjunction with q.

🔑 Definition — Truth Table: A table showing all possible truth values of statement variables and the resulting truth values of a compound statement.

Truth Table for ~ p ∧ (q ∨ ~ r)

When constructing truth tables with three variables (p, q, r), there are 2³ = 8 rows. Compute ~r first, then q ∨ ~r, then ~p, and finally their conjunction.

📌 Example: For p = F, q = T, r = F, we get ~p = T, q ∨ ~r = T ∨ T = T, so result = T ∧ T = T.

Truth Table for (p∨q) ∧ ~(p∧q) — Exclusive OR

The exclusive OR (XOR) means “p or q but not both.” It is symbolically written as p ⊕ q or (p∨q) ∧ ~(p∧q).

🔑 Definition — Exclusive OR (XOR): A logical operation that is true when exactly one of the two statements is true, and false otherwise.

USAGE OF “OR” IN ENGLISH

In English, “OR” is used in two senses:

1. Inclusive OR (p or q or both) — e.g., “I shall buy a pen or a book” (true if you buy either or both)
2. Exclusive OR (p or q but not both) — e.g., “Tomorrow at 9, I’ll be in Lahore or Islamabad” (false if you are in both places)

The symbol ∨ represents the inclusive OR.

💡 Why this matters: Understanding the difference between inclusive and exclusive OR prevents misinterpretation of logical statements in programming, mathematics, and everyday reasoning.

Truth Table for Exclusive OR

The exclusive OR can also be expressed as: p ⊕ q ≡ (p ∧ ~q) ∨ (~p ∧ q)

Note the equivalence: p ⊕ q ≡ (p ∧ ~q) ∨ (~p ∧ q) ≡ (p ∨ q) ∧ ~(p ∧ q) ≡ (p ∨ q) ∧ (~p ∨ ~q)

LOGICAL EQUIVALENCE

Logical equivalence means two statement forms have identical truth values for all possible truth assignments to their variables. The symbol ≡ denotes logical equivalence.

Double Negative Property: ~(~p) ≡ p

📌 Example: Rewrite “It is not true that I am not happy.” Let p = “I am happy.” Then ~(~p) ≡ p, so the statement simplifies to “I am happy.”

📌 Example: Show that ~(p∧q) and ~p ∧ ~q are not logically equivalent.

Different truth values in row 2 and row 3 prove they are NOT equivalent.

DE MORGAN’S LAWS

Law 1: The negation of an AND statement is logically equivalent to the OR statement with each component negated. ~ (p ∧ q) ≡ ~p ∨ ~q

Law 2: The negation of an OR statement is logically equivalent to the AND statement with each component negated. ~ (p ∨ q) ≡ ~p ∧ ~q

Truth table for ~(p ∨ q) ≡ ~p ∧ ~q:

Same truth values confirm the equivalence.

APPLICATION of De Morgan’s Laws

📌 Example: Give negations for: a) “The fan is slow or it is very hot.” → Negation: “The fan is not slow and it is not very hot.” b) “Akram is unfit and Saleem is injured.” → Negation: “Akram is not unfit or Saleem is not injured.”

INEQUALITIES AND DEMORGAN’S LAWS

📌 Example: Write the negation of -1 < x ≤ 4 for some real number x. Here, -1 < x ≤ 4 means x > –1 AND x ≤ 4. Let p: x > –1, q: x ≤ 4. Then ~p: x ≤ –1, ~q: x > 4. Negation of (x > –1 AND x ≤ 4) = ~(p ∧ q) ≡ ~p ∨ ~q = x ≤ –1 OR x > 4.

TAUTOLOGY

🔑 Definition — Tautology: A statement form that is always true regardless of the truth values of its statement variables. Represented by the symbol t.

📌 Example: The statement form p ∨ ~p is a tautology.

p ∨ ~p ≡ t

CONTRADICTION

🔑 Definition — Contradiction: A statement form that is always false regardless of the truth values of its statement variables. Represented by the symbol c.

📌 Example: The statement form p ∧ ~p is a contradiction.

p ∧ ~p ≡ c

Remarks:

• Most statements are neither tautologies nor contradictions.
• The negation of a tautology is a contradiction and vice versa.
• Two statements are contradictory if their conjunction is a contradiction.

LOGICAL EQUIVALENCE INVOLVING TAUTOLOGY

📌 Example: Show that p ∧ t ≡ p

The entries in the first and last columns are identical, so p ∧ t ≡ p.

LOGICAL EQUIVALENCE INVOLVING CONTRADICTION

📌 Example: Show that p ∧ c ≡ c

Same truth values in indicated columns, so p ∧ c ≡ c.

📌 Example (Exercise): Show that (p ∧ q) ∨ (~p ∨ (p ∧ ~q)) is a tautology.

All entries in the last column are T, so it is a tautology.

📌 Example (Exercise): Show that (p ∧ ~q) ∧ (~p ∨ q) is a contradiction.

All entries in the last column are F, so it is a contradiction.

LAWS OF LOGIC

1. Commutative Laws: p ∧ q ≡ q ∧ p, p ∨ q ≡ q ∨ p
2. Associative Laws: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r), (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
3. Distributive Laws: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r), p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
4. Identity Laws: p ∧ t ≡ p, p ∨ c ≡ p
5. Negation Laws: p ∨ ~p ≡ t, p ∧ ~p ≡ c
6. Double Negation Law: ~(~p) ≡ p
7. Idempotent Laws: p ∧ p ≡ p, p ∨ p ≡ p
8. De Morgan’s Laws: ~(p ∧ q) ≡ ~p ∨ ~q, ~(p ∨ q) ≡ ~p ∧ ~q
9. Universal Bound Laws: p ∨ t ≡ t, p ∧ c ≡ c
10. Absorption Laws: p ∨ (p ∧ q) ≡ p, p ∧ (p ∨ q) ≡ p
11. Negation of t and c: ~t ≡ c, ~c ≡ t

⭐ Key Takeaways

1. Truth tables systematically evaluate compound logical statements by listing all possible truth value combinations and computing results step-by-step following the order of operations (negation first, then conjunction/disjunction in parentheses).
2. The exclusive OR (XOR) is true when exactly one operand is true, expressed as (p∨q)∧~(p∧q) or (p∧~q)∨(~p∧q), and differs from inclusive OR which is also true when both are true.
3. De Morgan’s Laws are critical for negating complex statements: ~(p∧q) ≡ ~p ∨ ~q and ~(p∨q) ≡ ~p ∧ ~q, and they apply directly to inequalities involving AND/OR conditions.
4. A tautology is always true (p ∨ ~p ≡ t) while a contradiction is always false (p ∧ ~p ≡ c); most everyday statements are neither, and the negation of a tautology is a contradiction.
5. The eleven laws of logic (commutative, associative, distributive, identity, negation, double negation, idempotent, De Morgan’s, universal bound, absorption, and negation of t/c) form the foundation for simplifying and proving logical equivalences without constructing truth tables.

🧠 Quick Revision Questions

1. Construct the truth table for ~p ∨ (q ∧ ~r) and determine its truth value when p = T, q = F, r = T.
2. How does exclusive OR differ from inclusive OR, and what is the symbolic representation of each?
3. Using De Morgan’s Laws, write the negation of the statement: “The temperature is below freezing and it is not snowing.”
4. Is the statement form (p ∨ q) ∧ ~p logically equivalent to q? Justify with a truth table or laws of logic.
5. Classify each of the following as a tautology, contradiction, or neither: (a) p ∧ (q ∨ ~p), (b) (p → q) ∨ (q → p), (c) p ∧ ~(p ∨ q).

📘 Lecture 3 — Laws of Logic

📖 Overview: This lecture introduces the fundamental laws of logic and demonstrates how to apply them for simplifying complex logical statements and verifying logical equivalences. It then transitions into conditional statements (implications), covering their truth tables, alternative expressions, and related concepts like inverse, converse, and contrapositive, which are essential for mathematical reasoning and proof construction.

🗂️ Topics Covered

The lecture begins with applying laws of logic (DeMorgan’s, Double Negative, Associative, Idempotent, Distributive, Negation, Identity) to simplify statement forms and verify equivalences. It then introduces conditional statements, their truth tables, alternative phrasing, and translations between English and symbolic logic. The hierarchy of operations for logical connectives is explained, followed by the implication law, negation of conditionals, and the definitions of inverse, converse, and contrapositive.

📝 Lecture Summary

APPLYING LAWS OF LOGIC

Using the laws of logic, we can simplify complex statement forms into equivalent but simpler forms. The process involves applying known logical equivalences step-by-step.

🔑 Definition — DeMorgan’s Law: ~(p ∧ q) ≡ ~p ∨ ~q and ~(p ∨ q) ≡ ~p ∧ ~q. Negation distributes and flips the connective.

📐 Formula: p ∨ [~(p ∧ q)] ≡ p ∨ [(~p) ∨ (~q)] (DeMorgan’s Law) ≡ p ∨ [p ∨ (~q)] (Double Negative Law) ≡ [p ∨ p] ∨ (~q) (Associative Law for ∨) ≡ p ∨ (~q) (Idempotent Law)

📌 Example: Simplify p ∨ [~(p ∧ q)]. Step 1: Apply DeMorgan’s Law to the inner negation: p ∨ [(~p) ∨ (~q)]. Step 2: Apply Double Negative Law: p ∨ [p ∨ (~q)]. Step 3: Apply Associative Law: [p ∨ p] ∨ (~q). Step 4: Apply Idempotent Law: p ∨ (~q). The simplified form is p ∨ (~q).

🔑 Definition — Double Negative Law: ~(~p) ≡ p. The negation of a negation returns the original statement.

🔑 Definition — Associative Law: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) and (p ∧ q) ∧ r ≡ p ∧ (q ∧ r). Grouping does not matter for conjunction or disjunction.

🔑 Definition — Idempotent Law: p ∨ p ≡ p and p ∧ p ≡ p. A statement combined with itself yields the same statement.

📌 Example: Using Laws of Logic, verify ~(p ∧ q) ∧ (p ∨ q) ≡ p. Step 1: DeMorgan’s Law gives ((~p) ∨ ~q) ∧ (p ∨ q). Step 2: Double Negative Law gives (p ∨ ~q) ∧ (p ∨ q). Step 3: Distributive Law (reverse) gives p ∨ (~q ∧ q). Step 4: Negation Law gives p ∨ c. Step 5: Identity Law gives p. So the equivalence is verified.

🔑 Definition — Distributive Law: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) and p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r).

🔑 Definition — Negation Law: p ∨ ~p ≡ t (tautology) and p ∧ ~p ≡ c (contradiction).

🔑 Definition — Identity Law: p ∨ c ≡ p and p ∧ t ≡ p.

SIMPLIFYING A STATEMENT

We can represent English sentences using logical symbols and then apply distributive law (in reverse) to simplify the condition.

📌 Example: “You will get an A if you are hardworking and the sun shines, or you are hardworking and it rains.” Let p = “You are hardworking”, q = “The sun shines”, r = “It rains”. The condition is (p ∧ q) ∨ (p ∧ r). Using distributive law in reverse: (p ∧ q) ∨ (p ∧ r) ≡ p ∧ (q ∨ r). Rephrased: “You will get an A if you are hardworking and the sun shines or it rains.”

📌 Example: Use logical equivalence to rewrite “It is not true that I am tired and you are smart.” This becomes “I am not tired or you are not smart.” (DeMorgan’s Law)

📌 Example: Use logical equivalence to rewrite “I forgot my pen or my bag and I forgot my pen or my glasses.” This simplifies to “I forgot my pen or I forgot my bag and glasses.” (Distributive Law)

CONDITIONAL STATEMENTS

A conditional statement, also called an implication, links a hypothesis to a conclusion.

🔑 Definition — Conditional Statement (Implication): If p and q are statement variables, the conditional of q by p is “If p then q” or “p implies q”, denoted p → q. p is the hypothesis (antecedent), q is the conclusion (consequent).

🔑 Definition — Truth Table for p → q: p → q is false only when p is true and q is false; in all other cases it is true.

📌 Example: Determine truth values: “If 1 = 1, then 3 = 3.” → TRUE. “If 1 = 1, then 2 = 3.” → FALSE. “If 1 = 0, then 3 = 3.” → TRUE (since hypothesis false). “If 1 = 2, then 2 = 3.” → TRUE. “If 1 = 1, then 1 = 2 and 2 = 3.” → FALSE. “If 1 = 3 or 1 = 2 then 3 = 3.” → TRUE.

ALTERNATIVE WAYS OF EXPRESSING IMPLICATIONS

The implication p → q can be expressed in many equivalent ways:

• “if p then q”
• “p implies q”
• “if p, q”
• “p only if q”
• “p is sufficient for q”
• “q is necessary for p”
• “not p unless q”
• “q follows from p”
• “q if p”
• “q whenever p”

📌 Example: “Your guarantee is good only if you bought your CD less than 90 days ago.” → “If your guarantee is good, then you must have bought your CD player less than 90 days ago.”

📌 Example: “To get tenure as a professor, it is sufficient to be world-famous.” → “If you are world-famous, then you will get tenure as a professor.”

📌 Example: “That you get the job implies that you have the best credentials.” → “If you get the job, then you have the best credentials.”

📌 Example: “It is necessary to walk 8 miles to get to the top of the Peak.” → “If you get to the top of the peak, then you must have walked 8 miles.”

TRANSLATING ENGLISH SENTENCES TO SYMBOLS

Let p = “you get an A on the final exam”, q = “you do every exercise in this book”, r = “you get an A in this class”.

📌 Example: “To get an A in this class it is necessary for you to get an A on the final.” → p → r

📌 Example: “You do every exercise in this book; You get an A on the final, implies, you get an A in the class.” → p ∧ q → r

📌 Example: “Getting an A on the final and doing every exercise in this book is sufficient for getting an A in this class.” → p ∧ q → r

TRANSLATING SYMBOLIC PROPOSITIONS TO ENGLISH

Let p = “you have the flu”, q = “you miss the final exam”, r = “you pass the course”.

📌 Example: p → q → “If you have flu, then you will miss the final exam.”

📌 Example: ~q → r → “If you don’t miss the final exam, you will pass the course.”

📌 Example: ~p ∧ ~q → r → “If you neither have flu nor miss the final exam, then you will pass the course.”

HIERARCHY OF OPERATIONS FOR LOGICAL CONNECTIVES

The order of operations for logical connectives, from highest to lowest precedence:

1. ~ (negation)
2. ∧ (conjunction), ∨ (disjunction) — equal precedence
3. → (conditional)

📌 Example: Construct a truth table for p ∨ ~q → ~p.

LOGICAL EQUIVALENCE INVOLVING IMPLICATION

Truth tables can be used to show that p → q is logically equivalent to ~q → ~p.

The two expressions have the same truth values for all combinations, so they are equivalent.

🔑 Definition — Contrapositive: The contrapositive of p → q is ~q → ~p. A conditional and its contrapositive are always logically equivalent.

🔑 Definition — Implication Law: p → q ≡ ~p ∨ q. This allows rewriting any implication as a disjunction.

NEGATION OF A CONDITIONAL STATEMENT

Since p → q ≡ ~p ∨ q, we can find the negation: ~(p → q) ≡ ~(~p ∨ q) ≡ ~(~p) ∧ ~q ≡ p ∧ ~q (by DeMorgan’s and Double Negative Laws).

Thus the negation of “if p then q” is logically equivalent to “p and not q”. The negation of an if-then statement does not start with the word “if”.

📌 Example: Negate “If Ali lives in Pakistan then he lives in Lahore.” → “Ali lives in Pakistan and he does not live in Lahore.”

📌 Example: Negate “If my car is in the repair shop, then I cannot get to class.” → “My car is in the repair shop and I can get to class.”

📌 Example: Negate “If x is prime then x is odd or x is 2.” → “x is prime but x is not odd and x is not 2.”

INVERSE OF A CONDITIONAL STATEMENT

🔑 Definition — Inverse: The inverse of p → q is ~p → ~q. A conditional and its inverse are NOT logically equivalent.

Different truth values in rows 2 and 3 confirm they are not equivalent.

📌 Example: “If today is Friday, then 2 + 3 = 5.” Inverse: “If today is not Friday, then 2 + 3 ≠ 5.”

📌 Example: “If it snows today, I will ski tomorrow.” Inverse: “If it does not snow today I will not ski tomorrow.”

CONVERSE OF A CONDITIONAL STATEMENT

🔑 Definition — Converse: The converse of p → q is q → p. A conditional and its converse are NOT logically equivalent (→ is not a commutative operator).

Different truth values show they are not equivalent.

📌 Example: “If today is Friday, then 2 + 3 = 5.” Converse: “If 2 + 3 = 5, then today is Friday.”

📌 Example: “If P is a square, then P is a rectangle.” Converse: “If P is a rectangle then P is a square.”

CONTRAPOSITIVE OF A CONDITIONAL STATEMENT

🔑 Definition — Contrapositive: The contrapositive of p → q is ~q → ~p. A conditional and its contrapositive ARE logically equivalent: p → q ≡ ~q → ~p.

📌 Example: “If today is Friday, then 2 + 3 = 5.” Contrapositive: “If 2 + 3 ≠ 5, then today is not Friday.”

📌 Example: “If it snows today, I will ski tomorrow.” Contrapositive: “I will not ski tomorrow only if it does not snow today.”

📌 Example: “If P is a square, then P is a rectangle.” Contrapositive: “If P is not a rectangle then P is not a square.”

📌 Example: “If my car is in the repair shop, then I cannot get to class.” Contrapositive: “If I can get to the class, then my car is not in the repair shop.”

⭐ Key Takeaways

The most critical concepts to remember are the fundamental laws of logic (DeMorgan’s, Double Negative, Associative, Idempotent, Distributive, Negation, Identity) for simplifying compound statements. Conditional statements (p → q) are only false when p is true and q is false, and they can be expressed in many alternative forms. The implication law (p → q ≡ ~p ∨ q) is essential for rewriting and negating conditionals, where the negation is p ∧ ~q. Crucially, a conditional is logically equivalent to its contrapositive (~q → ~p) but NOT to its inverse (~p → q) or its converse (q → p). The hierarchy of logical connectives (, then ∧/∨, then →) must be followed when constructing truth tables.

🧠 Quick Revision Questions

1. Use the laws of logic to simplify the statement form: ~(p ∨ ~q) ∨ (~p ∧ q).
2. State the Implication Law and use it to find the negation of “If it rains, then the ground is wet.”
3. Construct a truth table to verify that p → q is logically equivalent to its contrapositive.
4. Translate the following English statement into symbols: “You will succeed only if you work hard and you are lucky.” Let s = “you will succeed”, h = “you work hard”, l = “you are lucky”.
5. What is the difference between the inverse and the converse of a conditional statement? Provide an example showing they are not logically equivalent to the original statement.

📘 Lecture 4 — Biconditional

📖 Overview: This lecture introduces the biconditional logical connective “if and only if,” its truth table, notation, and meaning. It explores how to rephrase biconditional statements, demonstrates logical equivalences involving biconditional, and applies laws of logic to rewrite and simplify compound statements.

🗂️ Topics Covered

This lecture defines the biconditional operator (p ↔ q), presents its truth table, and provides examples evaluating biconditional statements as true or false. It covers ways to rephrase biconditional statements in English, shows the logical equivalence p ↔ q ≡ (p→q) ∧ (q→p), constructs truth tables for compound biconditional expressions, and logically shows equivalences like ~p ↔ q ≡ p ↔ ~q and ~(p⊕q) ≡ p↔q. Finally, it introduces key laws of logic (commutative, implication, exportation, equivalence, reductio ad absurdum) and applies them to rewrite statements without → or ↔, and to prove tautologies without truth tables.

📝 Lecture Summary

BICONDITIONAL

If p and q are statement variables, the biconditional of p and q is “p if and only if q”. It is denoted p ↔ q. “if and only if” is abbreviated as iff. The double headed arrow "↔" is the biconditional operator.

🔑 Definition — Biconditional: A compound statement of the form “p if and only if q” that is true only when p and q have the same truth value.

📐 Formula: p ↔ q → “p if and only if q” — true when p and q are both true or both false.

TRUTH TABLE FOR p ↔ q

Remark:

• p ↔ q is true only when p and q both are true or both are false.
• p ↔ q is false when either p or q is false (i.e., when they have different truth values).

EXAMPLES: Identify which of the following are True or False?

1. “1+1 = 3 if and only if earth is flat” → TRUE (both false)
2. “Sky is blue iff 1 = 0” → FALSE (one true, one false)
3. “Milk is white iff birds lay eggs” → TRUE (both true)
4. “33 is divisible by 4 if and only if horse has four legs” → FALSE (one false, one true)
5. “x > 5 iff x² > 25” → FALSE (counterexample: x = -6 makes x > 5 false but x² > 25 true)

💡 Why this matters: Biconditional statements express equivalence between conditions and are crucial for defining necessary and sufficient conditions in mathematics and logic.

REPHRASING BICONDITIONAL

p ↔ q is also expressed as:

• “p is necessary and sufficient for q”
• “If p then q, and conversely”
• “p is equivalent to q”

Example: Show that p ↔ q ≡ (p→q) ∧ (q→p)

Since the columns for p↔q and (p→q)∧(q→p) have identical truth values, they are logically equivalent.

📌 Example: Rephrase statements in “p if and only if q” form:

1. “If it is hot outside, you buy an ice cream cone, and if you buy an ice cream cone, it is hot outside.” → You buy an ice cream cone if and only if it is hot outside.
2. “For you to win the contest it is necessary and sufficient that you have the only winning ticket.” → You win the contest if and only if you hold the only winning ticket.
3. “If you read the newspaper every day, you will be informed and conversely.” → You will be informed if and only if you read the newspaper every day.
4. “It rains if it is a weekend day, and it is a weekend day if it rains.” → It rains if and only if it is a weekend day.
5. “The train runs late on exactly those days when I take it.” → The train runs late if and only if it is a day I take the train.
6. “This number is divisible by 6 precisely when it is divisible by both 2 and 3.” → This number is divisible by 6 if and only if it is divisible by both 2 and 3.

TRUTH TABLE FOR (p→q) ↔ (~q → ~p)

The columns for p→q and ~q→~p have the same truth values, showing the biconditional is always true (a tautology).

TRUTH TABLE FOR (p ↔ q) ↔ (r ↔ q)

TRUTH TABLE FOR p ∧ ~r ↔ q ∨ r

Here p ∧ ~r ↔ q ∨ r means (p ∧ (~r)) ↔ (q ∨ r)

LOGICAL EQUIVALENCE INVOLVING BICONDITIONAL

Example: Show that ~p ↔ q and p ↔ ~q are logically equivalent.

Hence ~p ↔ q ≡ p ↔ ~q (identical truth values).

EXERCISE: Show that ~(p⊕q) and p↔q are logically equivalent.

Hence ~(p⊕q) ≡ p↔q (identical truth values).

LAWS OF LOGIC:

1. Commutative Law: p ↔ q ≡ q ↔ p
2. Implication Laws: p → q ≡ ~p ∨ q ≡ ~(p ∧ ~q)
3. Exportation Law: (p ∧ q) → r ≡ p → (q → r)
4. Equivalence: p ↔ q ≡ (p→q) ∧ (q→p)
5. Reductio ad absurdum: p → q ≡ (p ∧ ~q) → c

APPLICATION:

Example: Rewrite the statement forms without using the symbols → or ↔.

1. p ∧ ~q → r
2. (p → r) ↔ (q → r)

Solution:

1. p∧~q→r ≡ (p ∧ ~q) → r (Order of operations) ≡ ~(p ∧ ~q) ∨ r (Implication law)

2. (p→r)↔(q→r) ≡ (~p ∨ r) ↔ (~q ∨ r) (Implication law) ≡ [(~p ∨ r) → (~q ∨ r)] ∧ [(~q ∨ r) → (p ∨ r)] (Equivalence of biconditional) ≡ [(~p ∨ r) ∨ (q ∨ r)] ∧ [(~q ∨ r) ∨ (~p ∨ r)] (Implication law)

Example: Rewrite the statement form ~p ∨ q → r ∨ ~q to a logically equivalent form that uses only ~ and ∧.

Solution:

Example: Show that ~(p→q) → p is a tautology without using truth tables.

Solution:

EXERCISE: Suppose that p and q are statements so that p→q is false. Find the truth values of each of the following:

1. ~p → q
2. p ∨ q
3. q ↔ p

SOLUTION Hint: (p→q is false when p is true and q is false.)

1. TRUE (p=T, q=F → ~p=F, so F→F is T)
2. TRUE (p=T ∨ q=F → T)
3. FALSE (p=T, q=F have different truth values)

⭐ Key Takeaways

The biconditional p↔q is true only when p and q share the same truth value (both true or both false), and it is logically equivalent to the conjunction of two conditionals: (p→q)∧(q→p). Biconditional statements can be rephrased as “p is necessary and sufficient for q” or “p is equivalent to q.” The negation of exclusive OR (⊕) yields the biconditional: ~(p⊕q) ≡ p↔q. Using logical equivalence laws (implication, De Morgan’s, double negation, commutative, associative, negation, and universal bound), any compound statement can be rewritten in forms using only ~ and ∧, or proven to be a tautology without constructing truth tables.

🧠 Quick Revision Questions

1. Under what truth conditions is a biconditional statement p↔q true?
2. Show that p↔q is logically equivalent to which conjunction of conditionals?
3. Express “The train runs late on exactly those days when I take it” in “if and only if” form.
4. Using logical laws (without truth tables), prove that ~(p→q) → p is a tautology.
5. If p→q is false, what are the truth values of ~p→q, p∨q, and q↔p?

📘 Lecture 5 — Argument

📖 Overview: This lecture introduces the formal concept of an argument in logic, defining premises and conclusions, and establishing the criteria for validity and invalidity. It demonstrates how to use truth tables to test argument forms and applies these methods to word problems drawn from everyday reasoning, showing that even plausible-sounding arguments can be logically invalid.

🗂️ Topics Covered

The lecture begins with a motivating example about an interesting teacher. It then formally defines an argument, premises, and conclusion, followed by definitions of valid and invalid arguments and the concept of critical rows. Several examples of argument testing with truth tables are provided, including a demonstration of a valid argument form (modus ponens) and an invalid one (converse error). The remainder of the lecture is dedicated to applying this truth table method to a series of word problems, concluding with the analysis of the initial “interesting teacher” example.

📝 Lecture Summary

ARGUMENT

An argument is a list of statements called premises (or assumptions or hypotheses) followed by a statement called the conclusion.

P₁ Premise P₂ Premise P₃ Premise . . . . .. . . . . Pₙ Premise ∴ C Conclusion

The symbol ∴ is read “therefore” and is normally placed just before the conclusion.

🔑 Definition — Argument: A list of statements (premises) followed by a statement (the conclusion).

VALID AND INVALID ARGUMENT

An argument is valid if the conclusion is true when all the premises are true. Alternatively, an argument is valid if the conjunction of its premises implies the conclusion. That is, (P₁ ∧ P₂ ∧ P₃ ∧ . . . ∧ Pₙ) → C is a tautology.

An argument is invalid if the conclusion is false when all the premises are true. Alternatively, an argument is invalid if the conjunction of its premises does not imply the conclusion.

Critical Rows: The critical rows are those rows in a truth table where the premises have truth value T.

🔑 Definition — Valid Argument: An argument form where the conclusion is true in every critical row (rows where all premises are true). 🔑 Definition — Invalid Argument: An argument form where there is at least one critical row in which the conclusion is false. 🔑 Definition — Critical Rows: The rows in a truth table where all premises are true.

EXAMPLE: Show that the following argument form is valid:

p→q p ∴ q

p q | p→q | p | q T T | T | T | T ← critical row T F | F | T | F F T | T | F | T F F | T | F | F

Since the conclusion q is true when the premises p→q and p are true, it is a valid argument.

📐 Formula: (p→q) ∧ p → q is a tautology. 📌 Example: This is the classic valid argument form known as modus ponens (affirming the antecedent).

EXAMPLE: Show that the following argument form is invalid:

p→q q ∴ p

p q | p→q | q | p T T | T | T | T T F | F | F | T F T | T | T | F ← critical row F F | T | F | F

In the second critical row, the conclusion is false when the premises p→q and q are true. Therefore, the argument is invalid.

📌 Example: This is the classic invalid argument form known as the fallacy of the converse or converse error.

EXERCISE: Use truth table to determine the argument form

p ∨ q p → ~q p → r ∴ r

p q r | p∨q | p→~q | p→r | r T T T | T | F | T | T T T F | T | F | F | F T F T | T | T | T | T T F F | T | T | F | F ← critical row F T T | T | T | T | T F T F | T | T | T | F F F T | F | T | T | T F F F | F | T | T | F

In the third critical row, the conclusion is false when all the premises are true. Therefore, the argument is invalid.

WORD PROBLEM: Tariq and Hameed

If Tariq is not on team A, then Hameed is on team B. If Hameed is not on team B, then Tariq is on team A. ∴ Tariq is not on team A or Hameed is not on team B.

Let t = Tariq is on team A, h = Hameed is on team B.

The argument is: ~t → h ~h → t ∴ ~t ∨ ~h

t h | ~t→h | ~h→t | ~t∨~h T T | T | T | F ← critical row T F | T | T | T F T | T | T | T F F | F | F | T

The argument is invalid because there are three critical rows, and in the first critical row the conclusion has truth value F.

EXERCISE: Divisibility

If at least one of these two numbers is divisible by 6, then the product of these two numbers is divisible by 6. Neither of these two numbers is divisible by 6. ∴ The product of these two numbers is not divisible by 6.

Let d = at least one of these two numbers is divisible by 6, p = product of these two numbers is divisible by 6.

d p | d→p | ~d | ~p T T | T | F | F T F | F | F | T F T | T | T | F ← critical row F F | T | T | T

In the first critical row, the conclusion is false when the premises are true. Therefore, the argument is invalid.

📌 Example: The argument commits the fallacy of denying the antecedent. Even though the product might not be divisible by 6, it is not logically guaranteed by the premises.

EXERCISE: Stereo Purchase

If I got an Eid bonus, I’ll buy a stereo. If I sell my motorcycle, I’ll buy a stereo. ∴ If I get an Eid bonus or I sell my motorcycle, then I’ll buy a stereo.

Let e = I got an Eid bonus, s = I’ll buy a stereo, m = I sell my motorcycle.

e s m | e→s | m→s | e∨m | e∨m→s T T T | T | T | T | T T T F | T | T | T | T T F T | F | F | T | F T F F | F | T | T | F F T T | T | T | T | T F T F | T | T | F | T F F T | T | F | T | F F F F | T | T | F | T

The argument is valid because in the five critical rows, the conclusion is true.

📌 Example: This is a valid argument form known as proof by cases or constructive dilemma. Since either e or m is true (the disjunction), and each individually leads to s, the conclusion that e∨m implies s holds.

EXERCISE: The Interesting Teacher

An interesting teacher keeps me awake. I stay awake in Discrete Mathematics class. Therefore, my Discrete Mathematics teacher is interesting.

Let t = My teacher is interesting, a = I stay awake, m = I am in Discrete Mathematics class.

The argument to be tested is: t → a, a ∧ m ∴ m ∧ t

t a m | t→a | a∧m | m∧t T T T | T | T | T T T F | T | F | F T F T | F | F | T T F F | F | F | F F T T | T | T | F ← critical row F T F | T | F | F F F T | T | F | F F F F | T | F | F

In the second critical row, the conclusion is false when the premises are true. Therefore, the argument is invalid.

💡 Why this matters: This example shows that a convincing-sounding argument can be logically invalid. Even if an interesting teacher keeps you awake, and you are awake in class, the teacher of that class could be boring! You might be awake for another reason (e.g., you had coffee). Understanding logical validity helps us distinguish between good reasoning and plausible-sounding fallacies.

⭐ Key Takeaways

An argument consists of premises and a conclusion, and its validity depends not on the truth of the individual statements but on the logical structure connecting them. A valid argument guarantees that if all premises are true, the conclusion must be true; this is tested by checking that in every critical row of the truth table (where all premises are true), the conclusion is also true. An invalid argument fails this test — there is at least one situation where all premises are true but the conclusion is false. Identifying critical rows and carefully checking the conclusion’s truth value in each one is the fundamental method for determining validity. Many common reasoning errors, like the converse error (fallacy of the converse) and the inverse error (denying the antecedent), create plausible but invalid argument forms.

🧠 Quick Revision Questions

1. Define an argument, a premise, and a conclusion in the context of formal logic.
2. What are critical rows, and why are they essential for determining the validity of an argument?
3. Explain the difference between a valid argument and an invalid argument. Can a valid argument have a false conclusion? Explain.
4. Use a truth table to test the validity of the argument form: p → q, ~p ∴ ~q. Is it valid or invalid? What is this fallacy called?
5. In the “Interesting Teacher” example, why is the argument invalid? Can you give a counterexample (a situation where the premises are true but the conclusion is false)?

📘 Lecture 6 — Applications of Logic

📖 Overview: This lecture explores the practical applications of logic in designing and analyzing electrical circuits, specifically focusing on switches in series and parallel, logic gates, and combinational circuits. Understanding these concepts is crucial for computer engineering, as they form the foundation of digital circuit design and Boolean algebra.

🗂️ Topics Covered

The lecture covers switches in series and parallel configurations with their corresponding truth tables, the three basic logic gates (NOT, AND, OR) with their symbolic representations and input/output tables, combinational circuits with output determination for given inputs, constructing input/output tables, finding Boolean expressions for circuits, designing circuits from Boolean expressions, and proving circuit equivalence using logical laws.

📝 Lecture Summary

SWITCHES IN SERIES

Switches connected in series require both switches to be closed for the light bulb to turn on. If either switch is open, the circuit is broken and the bulb remains off. This behavior corresponds to the logical AND operation.

| Switches | Light Bulb | | P | Q | State | | Closed | Closed | On | | Closed | Open | Off | | Open | Closed | Off | | Open | Open | Off |

🔑 Definition — Series Circuit: A circuit configuration where switches are connected one after another, so current must flow through all switches for the circuit to be complete.

📐 Formula: P ∧ Q → Light On

📌 Example: In a series circuit with switches P and Q, if P is closed (1) and Q is closed (1), the bulb is on (1). If P is closed (1) and Q is open (0), the bulb is off (0).

SWITCHES IN PARALLEL

Switches connected in parallel allow the light bulb to turn on if at least one switch is closed. Only when both switches are open does the bulb remain off. This behavior corresponds to the logical OR operation.

| Switches | Light Bulb | | P | Q | State | | Closed | Closed | On | | Closed | Open | On | | Open | Closed | On | | Open | Open | Off |

🔑 Definition — Parallel Circuit: A circuit configuration where switches are connected across the same two points, creating multiple paths for current to flow.

📐 Formula: P ∨ Q → Light On

📌 Example: In a parallel circuit with switches P and Q, if P is open (0) and Q is open (0), only then is the bulb off (0). Any other combination keeps the bulb on (1).

💡 Why this matters: Series and parallel switch configurations are the physical analogs of logical AND and OR operations, forming the basis for understanding digital logic gates.

1. NOT-gate

A NOT-gate (or inverter) is a circuit with one input and one output signal. If the input signal is 1, the output signal is 0. Conversely, if the input signal is 0, then the output signal is 1.

| Input | Output | | P | R | | 1 | 0 | | 0 | 1 |

🔑 Definition — NOT-gate: A logic gate that outputs the complement (inverse) of its input signal.

📐 Formula: R = ~P

📌 Example: Input P = 1 gives output R = 0. Input P = 0 gives output R = 1.

2. AND-gate

An AND-gate is a circuit with two input signals and one output signal. If both input signals are 1, the output signal is 1. Otherwise the output signal is 0.

Symbolic representation & Input/Output Table:

| Input | Output | | P | Q | R | | 1 | 1 | 1 | | 1 | 0 | 0 | | 0 | 1 | 0 | | 0 | 0 | 0 |

🔑 Definition — AND-gate: A logic gate that outputs 1 only when all its inputs are 1.

📐 Formula: R = P ∧ Q

📌 Example: Input P = 1, Q = 1 gives output R = 1. Input P = 1, Q = 0 gives output R = 0.

3. OR-gate

An OR-gate is a circuit with two input signals and one output signal. If both input signals are 0, then the output signal is 0. Otherwise, the output signal is 1.

Symbolic representation & Input/Output Table:

| Input | Output | | P | Q | R | | 1 | 1 | 1 | | 1 | 0 | 1 | | 0 | 1 | 1 | | 0 | 0 | 0 |

🔑 Definition — OR-gate: A logic gate that outputs 1 when at least one of its inputs is 1.

📐 Formula: R = P ∨ Q

📌 Example: Input P = 1, Q = 0 gives output R = 1. Input P = 0, Q = 0 gives output R = 0.

COMBINATIONAL CIRCUIT

A Combinational Circuit is a compound circuit consisting of the basic logic gates such as NOT, AND, OR.

🔑 Definition — Combinational Circuit: A circuit whose outputs depend only on the current inputs, with no memory elements.

DETERMINING OUTPUT FOR A GIVEN INPUT

Indicate the output of the circuit below when the input signals are P = 1, Q = 0 and R = 0

Circuit: P and Q go into AND-gate. Output of AND goes into OR-gate with R. Output of OR goes into NOT-gate to produce S.

📌 Example: Given P = 1, Q = 0, R = 0

• Step 1: P ∧ Q = 1 ∧ 0 = 0
• Step 2: (P ∧ Q) ∨ R = 0 ∨ 0 = 0
• Step 3: ~[(P ∧ Q) ∨ R] = ~0 = 1
• Output S = 1

CONSTRUCTING THE INPUT/OUTPUT TABLE FOR A CIRCUIT

Construct the input/output table for the following circuit.

Circuit: P and Q go into an AND-gate (X). P goes through a NOT-gate then into an AND-gate with R (Y). X and Y go into an OR-gate (S).

Labeling intermediate outputs:

📌 Example: For input P=1, Q=1, R=1:

• X = 1 ∧ 1 = 1
• Y = ~1 ∧ 1 = 0 ∧ 1 = 0
• S = 1 ∨ 0 = 1

FINDING A BOOLEAN EXPRESSION FOR A CIRCUIT

Circuit: P and Q go into an OR-gate (P∨Q). P and R go into an OR-gate (P∨R). Outputs of both OR-gates go into an AND-gate.

📌 Example: Trace through the circuit from left to right, writing down the output of each logic gate.

• Gate 1 (OR): P ∨ Q
• Gate 2 (OR): P ∨ R
• Gate 3 (AND): (P ∨ Q) ∧ (P ∨ R)

🔑 Definition — Boolean Expression: A mathematical expression representing the logical operation of a circuit using variables and logical operators.

📐 Formula: The Boolean expression for this circuit is (P ∨ Q) ∧ (P ∨ R)

CIRCUIT CORRESPONDING TO A BOOLEAN EXPRESSION

EXERCISE: Construct circuit for the Boolean expression (P ∧ Q) ∨ ~R

📌 Solution:

• Step 1: Place an AND-gate with inputs P and Q, producing P ∧ Q
• Step 2: Place a NOT-gate with input R, producing ~R
• Step 3: Place an OR-gate with inputs from the AND-gate and NOT-gate, producing (P ∧ Q) ∨ ~R

CIRCUIT FOR INPUT/OUTPUT TABLE

Given the input/output table:

📌 Solution: The output S is 1 in two cases:

• When P=1, Q=1, R=0 → corresponds to P ∧ Q ∧ ~R
• When P=0, Q=1, R=1 → corresponds to ~P ∧ Q ∧ R

Circuit diagram:

• AND-gate with inputs P, Q, and NOT(R) for P ∧ Q ∧ ~R
• AND-gate with inputs NOT(P), Q, and R for ~P ∧ Q ∧ R
• OR-gate combining both AND-gate outputs

EXERCISE - Proving Circuit Equivalence

Given two circuits: One with (P ∧ Q) ∨ (~P ∧ Q) ∧ (P ∧ ~Q) and another with P ∨ Q

📌 Solution: Find the Boolean expressions for the circuits and show they are logically equivalent.

Thus (P ∧ Q) ∨ (~P ∧ Q) ∨ (P ∧ ~Q) ≡ P ∨ Q

Accordingly, the two circuits are equivalent.

⭐ Key Takeaways

The most critical concepts from this lecture are: (1) Switches in series correspond to the logical AND operation while switches in parallel correspond to the logical OR operation, with their respective truth tables defining all possible input-output combinations. (2) The three fundamental logic gates—NOT, AND, OR—each have specific symbolic representations and input/output tables that form the building blocks of all digital circuits. (3) Combinational circuits can be analyzed by tracing gate outputs from left to right to determine output for given inputs, and circuits can be designed by working backwards from a Boolean expression or input/output table. (4) Boolean expressions can be derived from circuit diagrams by writing the output of each gate sequentially, and circuits can be constructed from Boolean expressions by placing corresponding gates in the correct order. (5) Circuit equivalence can be proven using logical laws (distributive, negation, identity, commutative) to show that two different circuits produce identical truth tables.

🧠 Quick Revision Questions

1. How does the behavior of switches in series differ from switches in parallel, and which logical operations do they correspond to?
2. What are the input/output tables for the NOT, AND, and OR gates, and what is the symbolic representation of each?
3. Given a combinational circuit diagram with inputs P=1, Q=0, R=0 consisting of AND, OR, and NOT gates, what steps would you follow to determine the output?
4. How would you construct the input/output table and find the Boolean expression for a circuit that has an AND-gate followed by an OR-gate, then a NOT-gate?
5. Using logical laws, how would you prove that the Boolean expression (P ∧ Q) ∨ (~P ∧ Q) ∨ (P ∧ ~Q) is equivalent to P ∨ Q?

📘 Lecture 7 — Set Theory

📖 Overview: This lecture introduces the fundamental concepts of set theory, which is the mathematical language for defining collections of objects. Understanding sets is essential because they form the foundation for all advanced mathematics, logic, and computer science topics.

🗂️ Topics Covered

The lecture covers definitions and notations for sets, three methods for representing sets (tabular, descriptive, and set-builder forms), standard sets of numbers (natural, whole, integer, rational, irrational, real, complex), subset and proper subset relationships, set equality, null set, universal set, Venn diagrams, finite and infinite sets, and membership tables.

📝 Lecture Summary

Set Definition and Notation

A set is a well-defined collection of distinct objects. The objects are called elements or members of the set. Sets are denoted by capital letters (A, B, C, ...), while elements are represented by lowercase letters (a, b, c, ...). If an object x is a member of set A, we write x ∈ A (reads "x belongs to A" or "x is in A"). If x is not a member, we write x ∉ A (reads "x does not belong to A").

🔑 Definition — Element: An object that belongs to a set is called an element or member of that set.

Tabular Form

In tabular form (also called roster form), we list all the elements of a set, separated by commas and enclosed within curly brackets {}.

📌 Examples:

• A = {1, 2, 3, 4, 5} is the set of first five Natural Numbers
• B = {2, 4, 6, 8, ..., 50} is the set of Even numbers up to 50
• C = {1, 3, 5, 7, 9, ...} is the set of positive odd numbers

💡 Why this matters: The symbol "..." is called an ellipsis and means "and so forth." It is used when the pattern of elements is clear and continuing the list is unnecessary.

Descriptive Form

In descriptive form, we state the elements of a set in words.

📌 Examples (using the same sets):

• A = set of first five Natural Numbers
• B = set of positive even integers less than or equal to fifty
• C = set of positive odd integers

Set Builder Form

In set builder form, we write the common characteristic shared by all elements of the set in symbolic form. The general structure is {x ∈ Universal Set | condition(s)}.

📌 Examples:

• A = {x ∈ N | x ≤ 5} (Set of natural numbers less than or equal to 5)
• B = {x ∈ E | 0 < x ≤ 50} (Set of even numbers greater than 0 and ≤ 50)
• C = {x ∈ O | 0 < x} (Set of positive odd numbers)

Sets of Numbers

The lecture defines 10 standard number sets:

1. Natural Numbers: N = {1, 2, 3, ...}
2. Whole Numbers: W = {0, 1, 2, 3, ...}
3. Integers: Z = {..., -3, -2, -1, 0, +1, +2, +3, ...} = {0, ±1, ±2, ±3, ...} (Z from German "Zahlen")
4. Even Integers: E = {0, ±2, ±4, ±6, ...}
5. Odd Integers: O = {±1, ±3, ±5, ...}
6. Prime Numbers: P = {2, 3, 5, 7, 11, 13, 17, 19, ...}
7. Rational Numbers: Q = {x | x = p/q, p,q ∈ Z, q ≠ 0}
8. Irrational Numbers: Q' = {x | x is not rational} (e.g., √2, √3, π, e)
9. Real Numbers: R = Q ∪ Q'
10. Complex Numbers: C = {z | z = x + iy; x,y ∈ R}, where i = √(-1)

Subset

If A and B are two sets, then A is a subset of B, written A ⊆ B, if and only if every element of A is also an element of B. Symbolically: A ⊆ B ⇔ if x ∈ A, then x ∈ B.

🔑 Definition — Subset: A ⊆ B means every element of A is also in B.

📌 Remarks:

• When A ⊆ B, B is called a superset of A
• When A is not a subset of B, there exists at least one x ∈ A such that x ∉ B
• Every set is a subset of itself

📌 Example: Let A = {1, 3, 5}, B = {1, 2, 3, 4, 5}, C = {1, 2, 3, 4}, D = {3, 1, 5}

• A ⊆ B (every element of A is in B)
• C ⊆ B (every element of C is in B)
• A ⊆ D (every element of A is in D, and D ⊆ A since every element of D is in A)
• A is NOT a subset of C (since 5 ∈ A but 5 ∉ C)

📌 Example: Z ⊆ Q because every integer n can be written as n/1 ∈ Q.

Proper Subset

A is a proper subset of B, denoted A ⊂ B, if and only if every element of A is in B but there is at least one element of B that is not in A.

📌 Example: Let A = {1, 3, 5}, B = {1, 2, 3, 5}. Then A ⊂ B because element 2 of B is not in A.

Equal Sets

Two sets A and B are equal, denoted A = B, if and only if every element of A is in B and every element of B is in A. Symbolically: A = B iff A ⊆ B and B ⊆ A.

📌 Example: Let A = {1, 2, 3, 6}, B = set of positive divisors of 6, C = {3, 1, 6, 2}, D = {1, 2, 2, 3, 6, 6, 6}. Then A, B, C, and D are all equal sets. Note that repeated elements do not change the set.

💡 Why this matters: In sets, order and repetition do not matter. {1, 2, 3} = {3, 2, 1} = {1, 1, 2, 3, 3, 3}.

Null (Empty) Set

A set containing no element is called a null set, empty set, or void set. It is denoted by Ø or { }.

📌 Examples:

• A = {x | x is a person taller than 10 feet} = Ø (no such person exists)
• B = {x | x² = 4, x is odd} = Ø (no odd number has square 4)

💡 Why this matters: Ø is regarded as a subset of every set. Every set necessarily has two subsets: Ø and the set itself. These are called improper subsets; any other subset is called a proper subset.

Exercise on Set Membership

Determine true/false:

Universal Set

The set of all elements under consideration is called the universal set, usually denoted by U.

📌 Example: If A = {2, 4, 6} and B = {1, 3, 5}, then U = {1, 2, 3, 4, 5, 6}.

Venn Diagram

A Venn diagram is a graphical representation of sets by regions in the plane. The universal set is represented by the interior of a rectangle, and other sets are represented by disks (circles) lying within the rectangle.

Finite and Infinite Sets

A set S is finite if it contains exactly m distinct elements, where m is a non-negative integer. We write |S| = m or n(S) = m. A set is infinite if it is not finite.

📌 Examples:

• S = set of letters of English alphabet: finite, |S| = 26
• Null set Ø: finite, |Ø| = 0
• Set of positive integers {1, 2, 3, ...}: infinite

📌 Exercise: Determine finite/infinite:

1. A = {months in the year}: FINITE
2. B = {even integers}: INFINITE
3. C = {positive integers less than 1}: FINITE (empty set)
4. D = {animals living on the earth}: FINITE
5. E = {lines parallel to x-axis}: INFINITE
6. F = {x ∈ R | x¹⁰⁰ + 29x⁵⁰ - 1 = 0}: FINITE (finite number of roots)
7. G = {circles through origin}: INFINITE

Membership Table

A membership table displays the membership of elements in sets. A 1 indicates an element is in a set; a 0 indicates it is not. Membership tables can be used to prove set identities.

📌 Example — Membership table for Complement of A:

If an element is a member of A (1), it cannot be a member of Aᶜ (so 0 in Aᶜ). If an element is not a member of A (0), it will be a member of Aᶜ (so 1 in Aᶜ).

⭐ Key Takeaways

The most critical concepts to remember are: (1) The three ways to represent sets — tabular (listing elements in braces), descriptive (words), and set-builder (symbolic condition) — and when to use each. (2) The precise definitions of subset (every element of A is in B) versus proper subset (subset plus at least one element in B not in A) and that set equality requires mutual subsets. (3) The null set Ø contains no elements and is a subset of every set, making it and the set itself the two improper subsets of any set. (4) The standard number sets (N ⊂ W ⊂ Z ⊂ Q ⊂ R ⊂ C) and their relationships. (5) Membership tables use 1/0 to show element membership and are tools for proving set identities.

🧠 Quick Revision Questions

1. Write the set of positive even integers less than 20 in (a) tabular form, (b) descriptive form, and (c) set-builder form.
2. If A = {1, 2, 3, 4} and B = {1, 2, 3, 4, 5, 6}, is A a subset of B? Is A a proper subset of B? Explain why or why not.
3. What is the difference between a subset and a proper subset? Give an example where one is true but the other is false.
4. Which of the following sets are equal: {a, b, c}, {c, a, b}, {a, a, b, c, c}, {a, b}? Justify your answer.
5. Is the set {x ∈ Z | x² = 9} finite or infinite? List its elements. What if x ∈ R instead of Z?

📘 Lecture 8 — Venn Diagram

📖 Overview: This lecture introduces fundamental set operations—union, intersection, difference, and complement—using both Venn diagrams and membership tables. It provides definitions, examples, and exercises to illustrate how sets interact, and it demonstrates how to prove set identities visually and algebraically. Understanding these operations is crucial for logic, probability, and database theory.

🗂️ Topics Covered

The lecture defines union, intersection, difference, and complement of sets with symbolic notation, examples, Venn diagrams, and membership tables. It remarks on properties such as commutativity, associativity, and distribution, and works through detailed exercises enumerating elements of given sets and drawing Venn diagrams. The lecture concludes by proving set identities like A – (A – B) = A ∩ B using both Venn diagrams and membership tables.

📝 Lecture Summary

UNION:

Let A and B be subsets of a universal set U. The union of sets A and B is the set of all elements in U that belong to A or to B or to both, and is denoted A ∪ B.

🔑 Definition — Union (A ∪ B): {x ∈ U | x ∈ A or x ∈ B} 📌 Example: Let U = {a, b, c, d, e, f, g}, A = {a, c, e, g}, B = {d, e, f, g}. Then A ∪ B = {a, c, d, e, f, g}.

VENN DIAGRAM FOR UNION: The region representing A ∪ B is the entire shaded area covering both circles A and B.

REMARK:

1. A ∪ B = B ∪ A (union is commutative).
2. A ⊆ A ∪ B and B ⊆ A ∪ B.

MEMBERSHIP TABLE FOR UNION:

REMARK: This membership table is similar to the truth table for logical connective disjunction (∨).

INTERSECTION:

Let A and B subsets of a universal set U. The intersection of sets A and B is the set of all elements in U that belong to both A and B and is denoted A ∩ B.

🔑 Definition — Intersection (A ∩ B): {x ∈ U | x ∈ A and x ∈ B} 📌 Example: Let U = {a, b, c, d, e, f, g}, A = {a, c, e, g}, B = {d, e, f, g}. Then A ∩ B = {e, g}.

VENN DIAGRAM FOR INTERSECTION: The region where the two circles overlap is shaded.

REMARK:

1. A ∩ B = B ∩ A.
2. A ∩ B ⊆ A and A ∩ B ⊆ B.
3. If A ∩ B = ∅, then A & B are called disjoint sets.

MEMBERSHIP TABLE FOR INTERSECTION:

REMARK: This membership table is similar to the truth table for logical connective conjunction (∧).

DIFFERENCE:

Let A and B be subsets of a universal set U. The difference of “A and B” (or relative complement of B in A) is the set of all elements in U that belong to A but not to B, and is denoted A – B or A \ B.

🔑 Definition — Set Difference (A – B): {x ∈ U | x ∈ A and x ∉ B} 📌 Example: Let U = {a, b, c, d, e, f, g}, A = {a, c, e, g}, B = {d, e, f, g}. Then A – B = {a, c}.

VENN DIAGRAM FOR SET DIFFERENCE: The part of circle A that does not overlap with circle B is shaded.

REMARK:

1. A – B ≠ B – A (Set difference is not commutative).
2. A – B ⊆ A.
3. A – B, A ∩ B and B – A are mutually disjoint sets.

MEMBERSHIP TABLE FOR SET DIFFERENCE:

REMARK: The membership table is similar to the truth table for ~ (p → q).

COMPLEMENT:

Let A be a subset of universal set U. The complement of A is the set of all element in U that do not belong to A, and is denoted Aᶜ, A̅ or Aᶜ.

🔑 Definition — Complement (Aᶜ): {x ∈ U | x ∉ A} 📌 Example: Let U = {a, b, c, d, e, f, g}, A = {a, c, e, g}. Then Aᶜ = {b, d, f}.

VENN DIAGRAM FOR COMPLEMENT: All regions of U outside the circle A are shaded.

REMARK:

1. Aᶜ = U – A
2. A ∩ Aᶜ = ∅
3. A ∪ Aᶜ = U

MEMBERSHIP TABLE FOR COMPLEMENT:

REMARK: This membership table is similar to the truth table for logical connective negation (~).

EXERCISE:

Let U = {1, 2, 3, ..., 10}, X = {1, 2, 3, 4, 5}, Y = {y | y = 2x, x ∈ X}, Z = {z | z² – 9z + 14 = 0}. Enumerate: (1) X ∩ Y (2) Y ∪ Z (3) X – Z (4) Yᶜ (5) Xᶜ – Zᶜ (6) (X – Z)ᶜ

Step 1: Enumerate given sets. U = {1, 2, 3, ..., 10} X = {1, 2, 3, 4, 5} Y = {y | y = 2x, x ∈ X} = {2, 4, 6, 8, 10} Z = {z | z² – 9z + 14 = 0} = {2, 7}

Step 2: Compute each expression. (1) X ∩ Y = {1, 2, 3, 4, 5} ∩ {2, 4, 6, 8, 10} = {2, 4} (2) Y ∪ Z = {2, 4, 6, 8, 10} ∪ {2, 7} = {2, 4, 6, 7, 8, 10} (3) X – Z = {1, 2, 3, 4, 5} – {2, 7} = {1, 3, 4, 5} (4) Yᶜ = U – Y = {1, 2, 3, ..., 10} – {2, 4, 6, 8, 10} = {1, 3, 5, 7, 9} (5) Xᶜ = {6, 7, 8, 9, 10}, Zᶜ = {1, 3, 4, 5, 6, 8, 9, 10}, Xᶜ – Zᶜ = {6, 7, 8, 9, 10} – {1, 3, 4, 5, 6, 8, 9, 10} = {7} (6) (X – Z)ᶜ = U – (X – Z) = {1, 2, 3, ..., 10} – {1, 3, 4, 5} = {2, 6, 7, 8, 9, 10}

NOTE: (X – Z)ᶜ ≠ Xᶜ – Zᶜ

EXERCISE:

Given U = {x | x ∈ Z, 0 ≤ x ≤ 10}, P = {x | x is a prime number}, Q = {x | x² < 70} (i) Draw a Venn diagram for the above (ii) List the elements in Pᶜ ∩ Q

Step 1: Write sets in tabular form. U = {0, 1, 2, 3, ..., 10} P = {x | x is a prime number} = {2, 3, 5, 7} Q = {x | x² < 70} = {0, 1, 2, 3, 4, 5, 6, 7, 8}

Step 2: Draw Venn diagram. Place elements 2, 3, 5, 7 in the P circle, 0, 1, 4, 6, 8 in the Q-only region, and 9, 10 outside both circles within U.

(ii) Pᶜ = U – P = {0, 1, 4, 6, 8, 9, 10} Pᶜ ∩ Q = {0, 1, 4, 6, 8, 9, 10} ∩ {0, 1, 2, 3, 4, 5, 6, 7, 8} = {0, 1, 4, 6, 8}

EXERCISE:

Let U = {1, 2, 3, 4, 5}, C = {1, 3}. Find A in each case: (i) A ∪ B = U, A ∩ B = ∅ and B = {1} (ii) A ⊂ B and A ∪ B = {4, 5} (iii) A ∩ B = {3}, A ∪ B = {2, 3, 4} and B ∪ C = {1, 2, 3} (iv) A and B are disjoint, B and C are disjoint, and A ∪ B = {1, 2}. (v) A ⊂ C, B ⊂ C and A ∩ B = ∅.

Solution (i): A ∪ B = U = {1, 2, 3, 4, 5} and A ∩ B = ∅, so A = Bᶜ = {1}ᶜ = {2, 3, 4, 5}.

Solution (ii): When A ⊂ B, then A ∪ B = B = {4, 5}. So A = {4} or A = {5}.

Solution (iii): Place 3 in the intersection of all three sets. 1 is not in A ∪ B so goes only in C. 4 is not in B ∪ C but is in A ∪ B (and not in A ∩ B), so 4 goes only in A. 2 is in B ∪ C and A ∪ B, but not in A ∩ B, so 2 goes only in B. Therefore A = {3, 4} and B = {2, 3}.

Solution (iv): A ∩ B = ∅ and B ∩ C = ∅, and A ∪ B = {1, 2}. Since C = {1, 3} and B ∩ C = ∅, B cannot contain 1 or 3, so B = {2}. Then A = {1}.

Solution (v): A ⊂ C, B ⊂ C, and A ∩ B = ∅. Given C = {1, 3}, the possible subsets are {1}, {3}. For A and B to be disjoint and non-empty, one must be {1} and the other {3}. So A = {1} and B = {3} or vice versa.

EXERCISE:

Use a Venn diagram to represent the following: (i) (A ∩ B) ∩ Cᶜ (ii) Aᶜ ∪ (B ∪ C) (iii) (A – B) ∩ C (iv) (A ∩ Bᶜ) ∪ Cᶜ

(i) (A ∩ B) ∩ Cᶜ is shaded: The region common to A and B, but outside C. (ii) Aᶜ ∪ (B ∪ C): The entire shaded area is everything outside A, plus everything in B or C. (iii) (A – B) ∩ C: The region where A does not overlap B, but also lies inside C. (iv) (A ∩ Bᶜ) ∪ Cᶜ: The part of A outside B, plus everything outside C.

PROVING SET IDENTITIES BY VENN DIAGRAMS:

Prove the following using Venn Diagrams: (i) A – (A – B) = A ∩ B (ii) (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ (iii) A – B = A ∩ Bᶜ

Solution (i) — A – (A – B) = A ∩ B:

• Draw two overlapping circles A and B inside U.
• Step 1: Shade A – B (the part of A not overlapping B).
• Step 2: Starting from original diagram, A – (A – B) means the part of A that is NOT in (A – B). This is exactly the overlapping region A ∩ B.
• The shaded region in the final diagram matches the shaded region for A ∩ B. Result: Proved by visual equality.

Solution (ii) — (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ:

• Draw (A ∩ B)ᶜ: All regions except the overlapping part of A and B.
• Draw Aᶜ ∪ Bᶜ: Everything outside A plus everything outside B. This covers all regions except the intersection.
• The two shaded regions are identical. Result: (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Solution (iii) — A – B = A ∩ Bᶜ:

• Draw A – B: The part of A that does not overlap B.
• Draw A ∩ Bᶜ: The part of A that lies outside B (since Bᶜ is everything not in B).
• The two shaded regions are identical. Result: A – B = A ∩ Bᶜ

PROVING SET IDENTITIES BY MEMBERSHIP TABLE:

Prove using Membership Table: (i) A – (A – B) = A ∩ B (ii) (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ (iii) A – B = A ∩ Bᶜ

Solution (i): Create columns for A, B, A – B, A – (A – B), and A ∩ B.

Since the last two columns are identical, A – (A – B) = A ∩ B.

Solution (ii): Create columns for A, B, A ∩ B, (A ∩ B)ᶜ, Aᶜ, Bᶜ, and Aᶜ ∪ Bᶜ.

Since the fourth and last columns are identical, (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ.

Solution (iii): Create columns for A, B, A – B, Bᶜ, and A ∩ Bᶜ.

Since the third and fifth columns are identical, A – B = A ∩ Bᶜ.

⭐ Key Takeaways

You must internalize the distinct definitions and notations for union, intersection, difference, and complement, as these are the fundamental building blocks of set theory. You should be able to draw Venn diagrams for any set operation and interpret membership tables, recognizing their direct analogy to logical truth tables (∨, ∧, →, ~). The exercises demonstrate how to systematically decompose set descriptions into tabular form and compute composite expressions, including complements and differences. Finally, knowing that set identities can be proven either by visual Venn diagrams or by algebraic membership tables provides dual verification and deepens your understanding.

🧠 Quick Revision Questions

1. What is the difference between A ∪ B (union) and A ∩ B (intersection) in terms of element membership?
2. For difference (A – B), explain why A – B is not necessarily equal to B – A, and give a concrete counterexample.
3. If A and B are disjoint sets, what is the value of A ∩ B? Draw the Venn diagram.
4. Using a membership table, prove that (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ (De Morgan's Law for sets).
5. Given U = {1, 2, 3, 4, 5}, A = {2, 3}, B = {3, 4}, what is (A – B)ᶜ?

📘 Lecture 9 — Set identities

📖 Overview: This lecture covers the fundamental set identities that govern operations on sets, including idempotent, commutative, associative, distributive, identity, complement, and DeMorgan's laws. It demonstrates how to prove these identities logically and through membership tables, which is essential for understanding set theory foundations and solving complex set problems.

🗂️ Topics Covered

The lecture presents twelve set identity laws with formal statements, then provides detailed proofs of subset relationships and set equalities using element arguments and logical reasoning. It demonstrates how to prove: A ⊆ A∪B, A−B ⊆ A, transitivity of subsets, and the equivalence A⊆B iff Bᶜ⊆Aᶜ. The lecture then proves key identities including alternative representation for set difference, DeMorgan's Law, associative law, distributive law, and absorption laws. It concludes with simplification examples using set identities and membership table proofs.

📝 Lecture Summary

SET IDENTITIES:

Let A, B, C be subsets of a universal set U.

1. Idempotent Laws: a. A ∪ A = A b. A ∩ A = A
2. Commutative Laws: a. A ∪ B = B ∪ A b. A ∩ B = B ∩ A
3. Associative Laws: a. A ∪ (B ∪ C) = (A ∪ B) ∪ C b. A ∩ (B ∩ C) = (A ∩ B) ∩ C
4. Distributive Laws: a. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) b. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
5. Identity Laws: a. A ∪ ∅ = A b. A ∩ ∅ = ∅ c. A ∪ U = U d. A ∩ U = A
6. Complement Laws: a. A ∪ Aᶜ = U b. A ∩ Aᶜ = ∅ c. Uᶜ = ∅ d. ∅ᶜ = U
7. Double Complement Law: (Aᶜ)ᶜ = A
8. DeMorgan's Laws: a. (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ b. (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ
9. Alternative Representation for Set Difference: A – B = A ∩ Bᶜ
10. Subset Laws: a. A ∪ B ⊆ C iff A ⊆ C and B ⊆ C b. C ⊆ A ∩ B iff C ⊆ A and C ⊆ B
11. Absorption Laws: a. A ∪ (A ∪ B) = A b. A ∩ (A ∪ B) = A

EXAMPLE 1: Subset Proofs

1. Prove that A ⊆ A ∪ B SOLUTION: Let x be an arbitrary element of A, that is x∈A. ⇒ x∈A or x∈B ⇒ x∈A ∪ B. But x is an arbitrary element of A. ∴ A ⊆ A ∪ B (proved)

2. Prove that A – B ⊆ A SOLUTION: Let x ∈ A – B ⇒ x∈A and x∉B (by definition of A – B) ⇒ x∈A (in particular). But x is an arbitrary element of A – B. ∴ A – B ⊆ A (proved)

3. Prove that if A ⊆ B and B ⊆ C, then A ⊆ C SOLUTION: Suppose that A ⊆ B and B ⊆ C. Consider x∈A ⇒ x∈B (as A ⊆ B) ⇒ x∈C (as B ⊆ C). But x is an arbitrary element of A. ∴ A ⊆ C (proved)

4. Prove that A ⊆ B iff Bᶜ ⊆ Aᶜ SOLUTION: Suppose A ⊆ B. Let x∈Bᶜ ⇒ x∉B (by definition of Bᶜ) ⇒ x∉A ⇒ x∈Aᶜ (by definition of Aᶜ). The contrapositive statement of if x∈A then x∈B is: if x∉B then x∉A, which is the definition of A⊆B. Thus if x∉B then x∉A means A⊆B. Hence Bᶜ⊆Aᶜ.

Conversely, suppose Bᶜ⊆Aᶜ. Let x∈A ⇒ x∉Aᶜ (by definition of Aᶜ) ⇒ x∉Bᶜ (∵ Bᶜ⊆Aᶜ) ⇒ x∈B (by definition of Bᶜ). But x is an arbitrary element of A. ∴ A⊆B (proved)

EXAMPLE 2: Alternative Representation for Set Difference

Let A and B be subsets of a universal set U. Prove that A – B = A ∩ Bᶜ.

SOLUTION: Let x ∈ A – B ⇒ x∈A and x∉B (definition of set difference) ⇒ x∈A and x∈Bᶜ (definition of complement) ⇒ x∈A∩Bᶜ (definition of intersection). ∴ A – B ⊆ A∩Bᶜ...(1)

Conversely, let y∈A∩Bᶜ ⇒ y∈A and y∈Bᶜ (definition of intersection) ⇒ y∈A and y∉B (definition of complement) ⇒ y∈A–B (definition of set difference). ∴ A∩Bᶜ⊆A–B...(2)

From (1) and (2): A – B = A ∩ Bᶜ (as required)

EXAMPLE 3: DeMorgan's Law

Prove DeMorgan's Law: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ

PROOF: Let x∈(A∪B)ᶜ ⇒ x∉A∪B (definition of complement) ⇒ x∉A and x∉B (DeMorgan's Law of Logic) ⇒ x∈Aᶜ and x∈Bᶜ (definition of complement) ⇒ x∈Aᶜ∩Bᶜ (definition of intersection). ∴ (A∪B)ᶜ ⊆ Aᶜ∩Bᶜ...(1)

Conversely, let y∈Aᶜ∩Bᶜ ⇒ y∈Aᶜ and y∈Bᶜ (definition of intersection) ⇒ y∉A and y∉B (definition of complement) ⇒ y∉A∪B (DeMorgan's Law of Logic) ⇒ y∈(A∪B)ᶜ (definition of complement). ∴ Aᶜ∩Bᶜ ⊆ (A∪B)ᶜ...(2)

From (1) and (2): (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ

🔑 Definition — Double Complement Law: (Aᶜ)ᶜ = A

EXAMPLE 4: Associative Law

Prove the associative law: A ∩ (B ∩ C) = (A ∩ B) ∩ C

PROOF: Consider x∈A∩(B∩C) ⇒ x∈A and x∈B∩C (definition of intersection) ⇒ x∈A and x∈B and x∈C (definition of intersection) ⇒ x∈A∩B and x∈C (definition of intersection) ⇒ x∈(A∩B)∩C (definition of intersection). ∴ A∩(B∩C) ⊆ (A∩B)∩C...(1)

Conversely, let y∈(A∩B)∩C ⇒ y∈A∩B and y∈C (definition of intersection) ⇒ y∈A and y∈B and y∈C (definition of intersection) ⇒ y∈A and y∈B∩C (definition of intersection) ⇒ y∈A∩(B∩C) (definition of intersection). ∴ (A∩B)∩C ⊆ A∩(B∩C)...(2)

From (1) & (2): A ∩ (B ∩ C) = (A ∩ B) ∩ C (proved)

EXAMPLE 5: Distributive Law

Prove the distributive law: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

PROOF: Let x∈A∪(B∩C) ⇒ x∈A or x∈B∩C (definition of union) CASE I (when x∈A): ⇒ x∈A∪B and x∈A∪C (definition of union) ⇒ x∈(A∪B)∩(A∪C) CASE II (when x∈B∩C): x∈B and x∈C (definition of intersection). x∈B ⇒ x∈A∪B and x∈C ⇒ x∈A∪C. Thus x∈A∪B and x∈A∪C ⇒ x∈(A∪B)∩(A∪C) ∴ A∪(B∩C) ⊆ (A∪B)∩(A∪C)...(1)

Conversely, suppose x∈(A∪B)∩(A∪C) ⇒ x∈(A∪B) and x∈(A∪C) (definition of intersection) CASE I (when x∈A): x∈A∪(B∩C) (definition of union) CASE II (when x∉A): Since x∈A∪B and x∉A, therefore x∈B. Also, since x∈A∪C and x∉A, therefore x∈C. Thus x∈B∩C ⇒ x∈A∪(B∩C) ∴ (A∪B)∩(A∪C) ⊆ A∪(B∩C)...(2)

From (1) and (2): A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (proved)

EXAMPLE 6: Subset Implication

For any sets A and B if A ⊆ B then: (a) A ∩ B = A (b) A ∪ B = B

SOLUTION (a): Let x∈A∩B ⇒ x∈A and x∈B ⇒ x∈A. Hence A∩B ⊆ A...(1). Conversely, let x∈A. Then x∈B (since A⊆B). x∈A and x∈B, therefore x∈A∩B. Hence A ⊆ A∩B...(2). From (1) and (2): A = A∩B (proved)

SOLUTION (b): Suppose A⊆B. Consider x∈A∪B. CASE I (x∈A): Since A⊆B, x∈A ⇒ x∈B. CASE II (x∉A): Since x∈A∪B, x∈B. Thus A∪B ⊆ B...(1). Conversely, let x∈B ⇒ x∈A∪B. Hence B ⊆ A∪B...(2). From (1) and (2): A∪B = B (proved)

USING SET IDENTITIES:

For all subsets A and B of universal set U, prove that (A – B) ∪ (A ∩ B) = A

PROOF: LHS = (A – B) ∪ (A ∩ B) = (A ∩ Bᶜ) ∪ (A ∩ B) (Alternative representation) = A ∩ (Bᶜ ∪ B) (Distributive Law) = A ∩ U (Complement Law) = A (Identity Law) = RHS (proved)

💡 Why this matters: This demonstrates how set identities can be used to simplify complex set expressions algebraically, similar to solving equations in algebra.

EXAMPLE 7:

For any two sets A and B prove that A – (A – B) = A ∩ B

SOLUTION: LHS = A – (A – B) = A – (A ∩ Bᶜ) = A ∩ (A ∩ Bᶜ)ᶜ = A ∩ (Aᶜ ∪ (Bᶜ)ᶜ) (DeMorgan's Law) = A ∩ (Aᶜ ∪ B) (Double Complement Law) = (A ∩ Aᶜ) ∪ (A ∩ B) (Distributive Law) = ∅ ∪ (A ∩ B) (Complement Law) = A ∩ B (Identity Law) = RHS (proved)

EXAMPLE 8:

For all sets A, B, and C prove that (A – B) – C = (A – C) – B

SOLUTION: LHS = (A – B) – C = (A ∩ Bᶜ) – C = (A ∩ Bᶜ) ∩ Cᶜ = A ∩ (Bᶜ ∩ Cᶜ) (Associative Law) = A ∩ (Cᶜ ∩ Bᶜ) (Commutative Law) = (A ∩ Cᶜ) ∩ Bᶜ (Associative Law) = (A – C) ∩ Bᶜ = (A – C) – B = RHS (proved)

EXAMPLE 9:

Simplify (Bᶜ ∪ (Bᶜ – A))ᶜ

SOLUTION: (Bᶜ ∪ (Bᶜ – A))ᶜ = (Bᶜ ∪ (Bᶜ ∩ Aᶜ))ᶜ (Alternative representation) = (Bᶜ)ᶜ ∩ (Bᶜ ∩ Aᶜ)ᶜ (DeMorgan's Law) = B ∩ ((Bᶜ)ᶜ ∪ (Aᶜ)ᶜ) (DeMorgan's Law) = B ∩ (B ∪ A) (Double Complement Law) = B (Absorption Law)

PROVING SET IDENTITIES BY MEMBERSHIP TABLE:

Prove the following using Membership Table: (i) A – (A – B) = A ∩ B (ii) (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ (iii) A – B = A ∩ Bᶜ

Solution (i): A – (A – B) = A ∩ B

Solution (ii): (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ

Solution (iii): A – B = A ∩ Bᶜ

⭐ Key Takeaways

The twelve set identity laws form the algebraic foundation for manipulating set expressions, analogous to laws in Boolean algebra. Proving set identities requires two-directional subset arguments using arbitrary elements and logical deductions. DeMorgan's Laws connect complement operations with union and intersection, while distributive and associative laws allow regrouping of set operations. The alternative representation of set difference (A−B = A∩Bᶜ) is a powerful tool for converting difference operations into intersection and complement operations, enabling algebraic simplification. Membership tables provide a quick verification method for set identities by exhaustively checking all cases of element membership.

🧠 Quick Revision Questions

1. State DeMorgan's Laws for sets and prove (A∪B)ᶜ = Aᶜ∩Bᶜ using element arguments.
2. Prove the distributive law A∩(B∪C) = (A∩B)∪(A∩C) using the two-directional subset method.
3. Using set identities, simplify the expression (A∩B) ∪ (A∩Bᶜ) and state which laws you used at each step.
4. Show that A−B = A∩Bᶜ by constructing a membership table.
5. Prove that if A⊆B and B⊆C then A⊆C, and also prove the equivalence A⊆B iff Bᶜ⊆Aᶜ.

📘 Lecture 10 — Applications of Venn diagram

📖 Overview: This lecture demonstrates practical applications of Venn diagrams for solving problems involving set relationships, including survey data, word problems, and testing the validity of logical arguments. It also introduces the formal concepts of set partitions and power sets, showing how sets can be broken down into subsets and how all possible subsets can be enumerated.

🗂️ Topics Covered

The lecture covers drawing Venn diagrams to represent configurations of computer users with printer, modem, and scanner; solving a typist survey problem involving manual, electronic, and word processor typewriters; solving a school software packages problem with three overlapping sets; using Venn diagrams to test the validity of logical arguments involving "all," "no," and "not" statements; the formal definition of a partition of a set; and the definition and enumeration of power sets, including nested power sets of the empty set.

📝 Lecture Summary

Exercise: Configurations of Computer Users

A number of computer users are surveyed to find out if they have a printer, modem or scanner. Let P represent the set of computer users having printer, M the set having modem, and S the set having scanner.

🔑 Definition — Configuration 1: Modem and printer but no scanner. This is represented by the region where sets M and P overlap, excluding any part that overlaps with S.

🔑 Definition — Configuration 2: Scanner but no printer and no modem. This is represented by the region inside S only, with no overlap with P or M.

🔑 Definition — Configuration 3: Scanner or printer but no modem. This is represented by the union of sets S and P (all regions inside either), with any part overlapping M excluded.

🔑 Definition — Configuration 4: No modem and no printer. This is represented by the complement of the union of sets M and P, i.e., all regions outside both M and P.

Exercise: Typists in an Office

Of 21 typists in an office, 5 use all manual typewriters (M), electronic typewriters (E) and word processors (W); 9 use E and W; 7 use M and W; 6 use M and E; but no one uses M only.

(i) Represent this information in a Venn Diagram.

The known values are placed in the Venn diagram: the intersection of all three (M∩E∩W) is 5. The number using E and W is 9, so the region for (E∩W) but not M is 9 − 5 = 4. The number using M and W is 7, so (M∩W) but not E is 7 − 5 = 2. The number using M and E is 6, so (M∩E) but not W is 6 − 5 = 1. Since no one uses M only, that region is 0.

(ii-a) How many use word processors only?

Let the number of typists using E only be x, and the number using W only be y.

We are told: "the same number of typists use electronic as use word processors." Therefore: Total using E = Total using W 1 + 5 + 4 + x = 2 + 5 + 4 + y ⇒ x − y = 1 ................................................ (Equation 1)

Also, total typists = 21: 0 + x + y + 1 + 2 + 4 + 5 = 21 ⇒ x + y = 9 ................................................ (Equation 2)

Solving (1) and (2): adding gives 2x = 10, so x = 5. Then y = 4. Number of typists using word processor only is y = 4.

📌 Example: Solving the typist equations. From x + y = 9 and x − y = 1, adding eliminates y: 2x = 10, so x = 5. Substituting: 5 + y = 9, so y = 4.

(ii-b) How many typists use electronic typewriters?

Typists using electronic typewriters = No. of elements in E = 1 + 5 + 4 + x = 1 + 5 + 4 + 5 = 15.

Exercise: School Software Packages

In a school, 100 students have access to three software packages, A, B and C. 28 did not use any software; 8 used only A; 26 used only B; 7 used only C; 10 used all three; 13 used both A and B.

(i) Draw a Venn diagram with all sets enumerated as far as possible. Label the two subsets which cannot be enumerated as x and y.

The region for A∩B is 13, which includes the triple intersection (10). So (A∩B) but not C is 13 − 10 = 3. The remaining unknowns are: (A∩C) but not B, labeled x, and (B∩C) but not A, labeled y.

(ii) If twice as many students used package B as package A, write down a pair of simultaneous equations in x and y.

Number using B = 3 + 10 + 26 + y = 39 + y. Number using A = 8 + 3 + 10 + x = 21 + x. Given: (Number using B) = 2 × (Number using A): 39 + y = 2(21 + x) = 42 + 2x ⇒ y = 2x + 3 ................. (Equation 1)

Total students = 100. So: 8 + 3 + 26 + 10 + 7 + 28 + x + y = 100 ⇒ 82 + x + y = 100 ⇒ x + y = 18 ................. (Equation 2)

(iii) Solve these equations to find x and y.

Substitute y = 2x + 3 into x + y = 18: x + (2x + 3) = 18 ⇒ 3x + 3 = 18 ⇒ 3x = 15 ⇒ x = 5 Then y = 2(5) + 3 = y = 13.

(iv) How many students used package C?

Students using package C = x + y + 10 + 7 = 5 + 13 + 10 + 7 = 35.

Example: Valid Argument (Zeus)

Use diagrams to show the validity of the following argument:

1. All human beings are mortal.
2. Zeus is not mortal.
3. ∴ Zeus is not a human being.

The premise "All human beings are mortal" is pictured by placing a disk labeled "human beings" inside a disk labeled "mortals". The second premise "Zeus is not mortal" is pictured by placing a dot labeled "Zeus" outside the disk labeled "mortals". Since Zeus is outside "mortals," and "human beings" is entirely inside "mortals," Zeus must also be outside "human beings." The argument is valid.

Example: Invalid Argument (Farhan)

Use a diagram to show the invalidity of the following argument:

1. All human beings are mortal.
2. Farhan is mortal.
3. ∴ Farhan is a human being.

The first premise is shown as before. The second premise "Farhan is mortal" is represented by a dot labeled "Farhan" inside the mortal disk. However, the dot could be either inside the "human beings" disk or inside the "mortals" disk but outside "human beings." The conclusion requires Farhan to be inside "human beings," but the premises allow the dot to be outside it. The argument is invalid.

Example: Valid Argument (Horizontal Asymptotes)

Use diagrams to test the following argument for validity:

1. No polynomial functions have horizontal asymptotes.
2. This function has a horizontal asymptote.
3. ∴ This function is not polynomial.

The premise "No polynomial functions have horizontal asymptotes" is represented by two disjoint disks: "polynomial functions" and "functions with horizontal asymptotes". The second premise places a dot in the second disk. Since the disks are disjoint, the dot cannot be in the first disk. The argument is valid.

Exercise: Argument with True Premises and False Conclusion

Use a diagram to show that the following argument can have true premises and a false conclusion:

1. All dogs are carnivorous.
2. Jack is not a dog.
3. ∴ Jack is not carnivorous.

The premise "All dogs are carnivorous" is shown by placing a "dogs" disk inside a "carnivorous" disk. The second premise "Jack is not a dog" is represented by a dot outside the "dogs" disk. However, this dot can be placed inside the "carnivorous" disk (but not in "dogs"), making the conclusion "Jack is not carnivorous" false. The premises are true, but the conclusion can be false. The argument is invalid.

Exercise: Determining Validity

Indicate by drawing diagrams, whether the argument is valid or invalid.

1. No college cafeteria food is good.
2. No good food is wasted.
3. ∴ No college cafeteria food is wasted.

The premise "No college cafeteria food is good" is represented by two disjoint disks: "college cafeteria food" and "good food". The next premise "No good food is wasted" introduces another disk labeled "wasted food" that does not overlap the "good food" disk, but it may intersect with the "college cafeteria food" disk. It is possible for "college cafeteria food" to overlap "wasted food," which would make the conclusion false while premises are true. The argument is invalid.

Partition of a Set

A set may be divided up into its disjoint subsets. Such a division is called a partition.

🔑 Definition — Partition: A partition of a set A is a collection of non-empty subsets {A₁, A₂, ..., Aₙ} of A, such that:

1. A = A₁ ∪ A₂ ∪ ... ∪ Aₙ
2. A₁, A₂, ..., Aₙ are mutually disjoint (or pairwise disjoint), i.e., for all i, j = 1, 2, ..., n, Aᵢ ∩ Aⱼ = ∅ whenever i ≠ j.

Power Set

The power set of a set A is the set of all subsets of A, denoted P(A).

🔑 Definition — Power Set: For a set A, P(A) = {x : x ⊆ A}.

📐 Formula: If A has n elements, then P(A) has 2ⁿ elements.

📌 Example: Let A = {1, 2}. Then P(A) = {∅, {1}, {2}, {1, 2}}. Since n = 2, the power set has 2² = 4 elements.

Exercise: Finding Power Sets

a. Find P(∅). b. Find P(P(∅)). c. Find P(P(P(∅))).

Solution: a. Since ∅ contains no element (n=0), P(∅) will contain 2⁰ = 1 element. P(∅) = {∅}

b. Since P(∅) contains one element (namely ∅), P(P(∅)) will contain 2¹ = 2 elements. P(P(∅)) = {∅, {∅}}

c. Since P(P(∅)) contains two elements (namely ∅ and {∅}), P(P(P(∅))) will contain 2² = 4 elements. P(P(P(∅))) = {∅, {∅}, {{∅}}, {∅, {∅}}}

💡 Why this matters: The nested power sets of the empty set demonstrate how the cardinality (number of elements) grows exponentially with each level, from 0 to 1, then to 2, then to 4 elements. This is foundational for understanding the size of different infinities and Boolean algebra.

⭐ Key Takeaways

Venn diagrams are a powerful tool for visualizing set relationships and solving problems with overlapping categories. When tackling word problems, always place known exact numbers first (like triple intersections) before calculating remaining regions. For logical arguments, an argument is valid if the conclusion must be true whenever all premises are true; if a single counterexample can be drawn where premises hold but the conclusion does not, the argument is invalid. A partition of a set requires the subsets to be non-empty, mutually disjoint, and their union must equal the original set. The power set of a set with n elements always contains exactly 2ⁿ subsets, including the empty set and the set itself.

🧠 Quick Revision Questions

1. In the typist problem, why was the region for "M only" set to 0, and how does that affect the remaining calculations?
2. In the school software problem, how was the value of 3 determined for the (A∩B but not C) region?
3. For the argument "All dogs are carnivorous. Jack is not a dog. ∴ Jack is not carnivorous," draw a diagram showing true premises and a false conclusion. What does this prove about the argument?
4. What are the three conditions a collection of subsets must satisfy to be considered a partition of a set?
5. If A = {a, b}, list all elements of P(A). Then, if B = ∅, how many elements are in P(P(B))?

📘 Lecture 11 — Relations

📖 Overview: This lecture introduces the fundamental concept of relations in discrete mathematics, beginning with ordered pairs and n-tuples before progressing to Cartesian products. It defines binary relations, their domain and range, and explores multiple methods for representing relations including coordinate diagrams, arrow diagrams, directed graphs, and matrix representations — essential tools for modeling relationships between sets.

🗂️ Topics Covered

Ordered pairs and ordered n-tuples, Cartesian products of two and more sets, binary relations from one set to another, domain and range of relations, relations on a set, and multiple representation methods including coordinate diagrams, arrow diagrams, directed graphs, and matrix representation of relations.

📝 Lecture Summary

ORDERED PAIR

An ordered pair (a, b) consists of two elements “a” and “b” in which “a” is the first element and “b” is the second element. The ordered pairs (a, b) and (c, d) are equal if, and only if, a = c and b = d. Note that (a, b) and (b, a) are not equal unless a = b.

🔑 Definition — Ordered pair: Two elements arranged with a specific order where the first and second positions matter.

📐 Formula: (a, b) = (c, d) iff a = c and b = d

📌 Example: Find x and y given (2x, x + y) = (6, 2). Solution: 2x = 6 gives x = 3, then 3 + y = 2 gives y = -1.

ORDERED n-TUPLE

The ordered n-tuple (a₁, a₂, ..., aₙ) consists of elements a₁, a₂, ..., aₙ together with the ordering: first a₁, second a₂, and so forth up to aₙ. In particular, an ordered 2-tuple is called an ordered pair, and an ordered 3-tuple is called an ordered triple. Two ordered n-tuples (a₁, a₂, ..., aₙ) and (b₁, b₂, ..., bₙ) are equal if and only if each corresponding pair of their elements is equal, i.e., aᵢ = bⱼ, for all i, j = 1, 2, ..., n.

🔑 Definition — Ordered n-tuple: A generalization of ordered pairs to sequences of n elements with fixed ordering.

CARTESIAN PRODUCT OF TWO SETS

Let A and B be sets. The Cartesian product of A and B, denoted by A × B (read as “A cross B”) is the set of all ordered pairs (a, b), where a is in A and b is in B.

🔑 Definition — Cartesian product A × B: {(a, b) | a ∈ A and b ∈ B}

📐 Formula: If |A| = m and |B| = n, then |A × B| = m × n

📌 Example: Let A = {1, 2}, B = {a, b, c}. Then A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}. B × A = {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}. A × A = {(1, 1), (1,2), (2, 1), (2, 2)}. B × B = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}.

🔑 Important remarks: 1. A × B ≠ B × A for non-empty and unequal sets A and B. 2. A × φ = φ × A = φ. 3. |A × B| = |A| × |B|.

CARTESIAN PRODUCT OF MORE THAN TWO SETS

The Cartesian product of sets A₁, A₂, ..., Aₙ, denoted A₁ × A₂ × ... × Aₙ, is the set of all ordered n-tuples (a₁, a₂, ..., aₙ) where a₁ ∈ A₁, a₂ ∈ A₂, ..., aₙ ∈ Aₙ.

🔑 Definition — Cartesian product of n sets: A₁ × A₂ × ... × Aₙ = {(a₁, a₂, ..., aₙ) | aᵢ ∈ Aᵢ, for i = 1, 2, ..., n}

BINARY RELATION

Let A and B be sets. The binary relation R from A to B is a subset of A × B. When (a, b) ∈ R, we say ‘a’ is related to ‘b’ by R, written aRb. Otherwise, if (a, b) ∉ R, we write aRb.

🔑 Definition — Binary relation from A to B: Any subset of the Cartesian product A × B.

📌 Example: Let A = {1, 2}, B = {1, 2, 3}. Then A × B = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)}. Relations from A to B include: R₁ = {(1,1), (1,3), (2,2)}, R₂ = {(1,2), (2,1), (2,2), (2,3)}, R₃ = {(1,1)}, R₄ = A × B, R₅ = ∅. All being subsets of A × B are relations from A to B.

DOMAIN OF A RELATION

The domain of a relation R from A to B is the set of all first elements of the ordered pairs which belong to R denoted by Dom(R).

🔑 Definition — Domain of R: Dom(R) = {a ∈ A | (a, b) ∈ R}

RANGE OF A RELATION

The range of a relation R from A to B is the set of all second elements of the ordered pairs which belong to R denoted Ran(R).

🔑 Definition — Range of R: Ran(R) = {b ∈ B | (a, b) ∈ R}

📌 Example: Let A = {1, 2}, B = {1, 2, 3}, define R = {(a, b) ∈ A × B | a < b}. Then R = {(1,2), (1,3), (2,3)}. Dom(R) = {1,2} and Ran(R) = {2, 3}. Since (1, 3) ∈ R so 1R3. But (2, 2) ∉ R so 2 is not related to 3 or 2R2.

📌 Example: Let A = {eggs, milk, corn} and B = {cows, goats, hens}. Define R from A to B by (a, b) ∈ R iff a is produced by b. Then R = {(eggs, hens), (milk, cows), (milk, goats)}. Thus, eggs R hens, milk R cows, etc.

📌 Example: Find all binary relations from {0,1} to {1}. Let A = {0,1} and B = {1}. Then A × B = {(0,1), (1,1)}. All binary relations from A to B are all subsets of A × B: R₁ = ∅, R₂ = {(0,1)}, R₃ = {(1,1)}, R₄ = {(0,1), (1,1)} = A × B.

🔑 Remark: If |A| = m and |B| = n, then the number of elements in A × B are m × n, and the total number of relations from A to B are 2^(m × n).

RELATION ON A SET

A relation on a set A is a relation from A to A. In other words, a relation on a set A is a subset of A × A.

🔑 Definition — Relation on a set: A subset of A × A.

📌 Example: Let A = {1, 2, 3, 4}. Define R on A as (a,b) ∈ R iff a divides b (a | b). Then R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}.

🔑 Remarks: For any set A: 1. A × A is known as the universal relation. 2. ∅ is known as the empty relation.

📌 Example: Define a binary relation E on the set of integers Z as: for all m,n ∈ Z, m E n ⇔ m – n is even. Is 0E0? Yes, since 0-0 = 0 is even. Is 5E2? No, since 5-2 = 3 is not even. Is (6,6) ∈ E? Yes, since 6-6 = 0 is even. Is (-1,7) ∈ E? Yes, since (-1)-7 = -8 is even. For any even integer n, nE0 because n – 0 = n is an even integer.

COORDINATE DIAGRAM (GRAPH) OF A RELATION

A coordinate diagram represents a relation by plotting points on a coordinate system where one axis represents set A and the other represents set B.

📌 Example: Let A = {1, 2, 3} and B = {x, y}. Let R = {(1, y), (2, x), (2, y), (3, x)}. The relation may be represented by plotting points (1,y), (2,x), (2,y), (3,x) on a coordinate grid with A on horizontal axis and B on vertical axis.

📌 Example: Draw the graph of the binary relation C from R to R defined as: for all (x, y) ∈ R × R, (x, y) ∈ C ⇔ x² + y² = 1. All ordered pairs (x, y) in relation C satisfy x² + y² = 1, which gives y = ±√(1-x²). y is real whenever -1 ≤ x ≤ 1, and x is real whenever -1 ≤ y ≤ 1. The graph is a circle with radius 1 centered at the origin, limited to the range -1 ≤ x ≤ 1 and -1 ≤ y ≤ 1. Key points include (0,1), (1,0), (0,0), (0,-1), (-1,0).

ARROW DIAGRAM OF A RELATION

An arrow diagram represents a relation by drawing arrows from elements of set A to elements of set B.

📌 Example: Let A = {1, 2, 3}, B = {x, y} and R = {(1,y), (2,x), (2,y), (3,x)}. The arrow diagram shows elements 1, 2, 3 on the left and x, y on the right, with arrows: 1→y, 2→x, 2→y, 3→x.

DIRECTED GRAPH OF A RELATION

A directed graph represents a relation on a set by drawing vertices for elements and directed edges (arrows) from a to b when (a, b) ∈ R.

📌 Example: Let A = {0, 1, 2, 3} and R = {(0,0), (1,3), (2,1), (2,2), (3,0), (3,1)}. The directed graph has vertices 0, 1, 2, 3 with directed edges: 0→0 (a loop), 1→3, 2→1, 2→2 (a loop), 3→0, 3→1.

MATRIX REPRESENTATION OF A RELATION

Let A = {a₁, a₂, ..., aₙ} and B = {b₁, b₂, ..., bₘ}. Let R be a relation from A to B. Define the n × m order matrix M by: m(i, j) = 1 if (aᵢ, bⱼ) ∈ R, and m(i, j) = 0 if (aᵢ, bⱼ) ∉ R, for i=1,2,...,n and j=1,2,...,m.

🔑 Definition — Matrix representation: An n × m binary matrix where entry (i,j) is 1 if the ordered pair is in the relation, and 0 otherwise.

📌 Example: Let A = {1, 2, 3} and B = {x, y}. Let R = {(1,y), (2,x), (2,y), (3,x)}. The matrix M is a 3×2 matrix: rows labeled 1, 2, 3 and columns labeled x, y. M = [[0, 1], [1, 1], [1, 0]] meaning (1,x)=0, (1,y)=1, (2,x)=1, (2,y)=1, (3,x)=1, (3,y)=0.

📌 Example: For matrix M = [[1, 0, 1], [1, 0, 0], [0, 1, 1]] with rows 1, 2, 3 and columns 1, 2, 3 (a relation on set A = {1,2,3}): R = {(1,1), (1,3), (2,1), (3,2), (3,3)}. Its directed graph has vertices 1, 2, 3 with edges: 1→1 (loop), 1→3, 2→1, 3→2, 3→3 (loop).

EXERCISE

Let A = {2, 4} and B = {6, 8, 10}. Define R and S from A to B as: for all (x,y) ∈ A × B, x R y ⇔ x | y and x S y ⇔ y – 4 = x.

📌 Solution: A × B = {(2,6), (2,8), (2,10), (4,6), (4,8), (4,10)}. R = {(2,6), (2,8), (2,10), (4,8)} because 2|6, 2|8, 2|10, 4|8. S = {(2,6), (4,8)} because 6-4=2 and 8-4=4. R ∪ S = {(2,6), (2,8), (2,10), (4,8)} = R. R ∩ S = {(2,6), (4,8)} = S.

⭐ Key Takeaways

A relation is fundamentally a subset of a Cartesian product, and understanding this definition is essential for all further work. The domain and range of a relation are simply the sets of first and second elements respectively from the ordered pairs. There are four important visual representation methods — coordinate diagrams, arrow diagrams, directed graphs, and matrices — each useful in different contexts. For a set A of size m and B of size n, the total number of possible relations from A to B is 2^(m×n). A relation on a set A is simply a relation from A to itself (a subset of A×A), with the two extreme cases being the universal relation (A×A) and the empty relation (∅).

🧠 Quick Revision Questions

1. What is the difference between an ordered pair (a,b) and the set {a,b}?
2. If A has 4 elements and B has 3 elements, how many elements are in A×B and how many relations can be defined from A to B?
3. For A = {1,2,3} and the relation R = {(1,2), (2,3), (3,1)} on A, what are Dom(R) and Ran(R)?
4. How would you construct the matrix representation of a relation R from A = {a₁,a₂} to B = {b₁,b₂,b₃}?
5. Given the matrix representation of a relation, how do you construct its directed graph?

📘 Lecture 12 — Types of Relations

📖 Overview: This lecture defines and explores the fundamental properties of binary relations: reflexivity, symmetry, and transitivity. Understanding these properties is essential for characterizing relations and forms the basis for more advanced concepts like equivalence relations and congruences.

🗂️ Topics Covered

The lecture covers reflexive relations with their definition, examples, directed graph representation, and matrix representation. It then covers symmetric relations similarly, followed by transitive relations. Multiple exercises test understanding of these properties on various relations including the null relation, universal relation, divides relation, and congruence modulo d. Finally, equivalence relations are introduced as relations that are reflexive, symmetric, and transitive, with congruence modulo 3 proved as an equivalence relation.

📝 Lecture Summary

REFLEXIVE RELATION

Let R be a relation on a set A. R is reflexive if and only if, for all a ∈ A, (a, a) ∈ R or equivalently aRa. That is, each element of A is related to itself.

🔑 Definition — Reflexive: A relation R on set A is reflexive iff every element of A is related to itself; i.e., (a,a) ∈ R for all a ∈ A.

🔑 Definition — Not Reflexive: R is not reflexive iff there is an element “a” in A such that (a, a) ∉ R. That is, some element “a” of A is not related to itself.

📌 Example: Let A = {1, 2, 3, 4} and define relations R₁, R₂, R₃, R₄ on A as follows: R₁ = {(1, 1), (3, 3), (2, 2), (4, 4)} — reflexive, since (a,a) ∈ R₁ for all a∈A. R₂ = {(1, 1), (1, 4), (2, 2), (3, 3), (4, 3)} — not reflexive, because (4, 4) ∉ R₂. R₃ = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)} — reflexive. R₄ = {(1, 3), (2, 2), (2, 4), (3, 1), (4, 4)} — not reflexive, because (1, 1) ∉ R₄ and (3, 3) ∉ R₄.

DIRECTED GRAPH OF A REFLEXIVE RELATION: The directed graph of every reflexive relation includes an arrow from every point to the point itself (i.e., a loop).

MATRIX REPRESENTATION OF A REFLEXIVE RELATION: Let A = {a₁, a₂, ..., aₙ}. A Relation R on A is reflexive if and only if (aᵢ, aⱼ) ∈ R ∀ i=1,2,...,n. Accordingly, R is reflexive if all the elements on the main diagonal of the matrix M representing R are equal to 1.

📌 Example: The relation R = {(1,1), (1,3), (2,2), (3,2), (3,3)} on A = {1,2,3} represented by the following matrix M, is reflexive.

M = | 1 0 1 |
    | 0 1 0 |
    | 0 1 1 |

SYMMETRIC RELATION

Let R be a relation on a set A. R is symmetric if, and only if, for all a, b ∈ A, if (a, b) ∈ R, then (b, a) ∈ R. That is, if aRb then bRa.

🔑 Definition — Symmetric: A relation R on set A is symmetric iff whenever (a,b) ∈ R, then (b,a) ∈ R for all a,b ∈ A.

🔑 Definition — Not Symmetric: R is not symmetric iff there are elements a and b in A such that (a, b) ∈ R, but (b, a) ∉ R.

📌 Example: Let A = {1, 2, 3, 4} and define relations R₁, R₂, R₃, R₄ on A as follows: R₁ = {(1, 1), (1, 3), (2, 4), (3, 1), (4,2)} — symmetric because for every ordered pair (a,b) in R₁ we also have (b,a) in R₁. R₂ = {(1, 1), (2, 2), (3, 3), (4, 4)} — symmetric (vacuously true). R₃ = {(2, 2), (2, 3), (3, 4)} — not symmetric, because (2,3) ∈ R₃ but (3,2) ∉ R₃. R₄ = {(1, 1), (2, 2), (3, 3), (4, 3), (4, 4)} — not symmetric because (4,3) ∈ R₄ but (3,4) ∉ R₄.

DIRECTED GRAPH OF A SYMMETRIC RELATION: For a symmetric directed graph, whenever there is an arrow going from one point of the graph to a second, there is an arrow going from the second point back to the first.

MATRIX REPRESENTATION OF A SYMMETRIC RELATION: Let A = {a₁, a₂, ..., aₙ}. The relation R on A is symmetric if and only if for all aᵢ, aⱼ ∈ A, if (aᵢ, aⱼ) ∈ R then (aⱼ, aᵢ) ∈ R. Accordingly, R is symmetric if the elements in the ith row are the same as the elements in the ith column of the matrix M representing R. More precisely, M is a symmetric matrix i.e. M = Mᵀ.

📌 Example: The relation R = {(1,3), (2,2), (3,1), (3,3)} on A = {1,2,3} represented by the following matrix M is symmetric.

M = | 0 0 1 |
    | 0 1 0 |
    | 1 0 1 |

TRANSITIVE RELATION

Let R be a relation on a set A. R is transitive if and only if for all a, b, c ∈ A, if (a, b) ∈ R and (b, c) ∈ R then (a, c) ∈ R. That is, if aRb and bRc then aRc. In words, if any one element is related to a second and that second element is related to a third, then the first is related to the third. Note: The “first”, “second” and “third” elements need not be distinct.

🔑 Definition — Transitive: A relation R on set A is transitive iff whenever (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R for all a,b,c ∈ A.

🔑 Definition — Not Transitive: R is not transitive iff there are elements a, b, c in A such that (a, b) ∈ R and (b, c) ∈ R but (a, c) ∉ R.

📌 Example: Let A = {1, 2, 3, 4} and define relations R₁, R₂ and R₃ on A as follows: R₁ = {(1, 1), (1, 2), (1, 3), (2, 3)} — transitive because (1,1), (1,2) are in R₁, then to be transitive (1,2) must be there and it belongs to R₁. R₂ = {(1, 2), (1, 4), (2, 3), (3, 4)} — not transitive since (1,2) and (2,3) ∈ R₂ but (1,3) ∉ R₂. R₃ = {(2, 1), (2, 4), (2, 3), (3,4)} — transitive.

DIRECTED GRAPH OF A TRANSITIVE RELATION: For a transitive directed graph, whenever there is an arrow going from one point to the second, and from the second to the third, there is an arrow going directly from the first to the third.

EXERCISE ON NULL AND UNIVERSAL RELATIONS

Let A = {1, 2, 3, 4} and define the null relation ∅ and universal relation A × A on A.

Reflexive:

• ∅ is not reflexive since (1,1), (2,2), (3,3), (4,4) ∉ ∅.
• A × A is reflexive since (a,a) ∈ A × A for all a ∈ A.

Symmetric:

• For the null relation ∅ on A to be symmetric, it must satisfy: if (a,b) ∈ ∅ then (a,b) ∈ ∅. Since (a,b) ∈ ∅ is never true, the implication is vacuously true or true by default. Hence ∅ is symmetric.
• The universal relation A × A is symmetric, for it contains all ordered pairs of elements of A. Thus, if (a,b) ∈ A × A then (b,a) ∈ A × A for all a,b in A.

Transitive:

• The null relation ∅ on A is transitive, because the implication "if (a,b) ∈ ∅ and (b,c) ∈ ∅ then (a,c) ∈ ∅" is true by default, since the condition (a,b) ∈ ∅ is always false.
• The universal relation A × A is transitive for it contains all ordered pairs of elements of A.

EXERCISE: RELATION ON POSITIVE INTEGERS

Define a relation R on the set of positive integers Z⁺ as follows: for all a, b ∈ Z⁺, a R b iff a × b is odd. Determine whether the relation is reflexive, symmetric, transitive.

Solution: Recall that the product of two positive integers is odd if and only if both of them are odd.

• Reflexive: R is not reflexive, because 2 ∈ Z⁺ but 2 R 2 for 2 × 2 = 4 which is not odd.
• Symmetric: R is symmetric, because if a R b then a × b is odd or equivalently b × a is odd (b × a = a × b) ⇒ b R a.
• Transitive: R is transitive, because if a R b then a × b is odd ⇒ both “a” and “b” are odd. Also bRc means b × c is odd ⇒ both “b” and “c” are odd. Now if aRb and bRc, then all of a, b, c are odd and so a × c is odd. Consequently aRc.

EXERCISE: DIVIDES RELATION

Let “D” be the “divides” relation on Z defined as: for all m, n ∈ Z, m D n ⇔ m|n. Determine whether D is reflexive, symmetric or transitive.

• Reflexive: Let m ∈ Z, since every integer divides itself. So m|m ∀ m ∈ Z therefore mDm ∀ m ∈ Z. Accordingly D is reflexive.
• Symmetric: Let m, n ∈ Z and suppose m D n. By definition, m|n (i.e. n/m = an integer). Clearly, then it is not necessary that m/n = an integer. Accordingly, if m D n then n D m is not true for all m,n ∈ Z. Hence D is not symmetric.
• Transitive: Let m, n, p ∈ Z and suppose m D n and n D p. Now m D n ⇒ m|n ⇒ n/m = an integer. Also n D p ⇒ n|p ⇒ p/n = an integer. We note p/m = (p/n) * (n/m) = (an int) * (an int) = an int ⇒ m|p and so mDp. Thus if mDn and nDp then mDp ∀ m,n,p ∈ Z. Hence D is transitive.

EQUIVALENCE RELATION

Let A be a non-empty set and R a binary relation on A. R is an equivalence relation if, and only if, R is reflexive, symmetric, and transitive.

🔑 Definition — Equivalence Relation: A relation R on a non-empty set A is an equivalence relation iff R is reflexive, symmetric, and transitive.

📌 Example: Let A = {1, 2, 3, 4} and R = {(1,1), (2,2), (2,4), (3,3), (4,2), (4,4)} be a binary relation on A. Note that R is reflexive, symmetric and transitive, hence an equivalence relation.

CONGRUENCES

Let m and n be integers and d be a positive integer. The notation m ≡ n (mod d) means that d | (m – n) {d divides m minus n}. There exists an integer k such that (m – n) = d·k.

📌 Example: a. Is 22 ≡ 1(mod 3)? Since 22-1 = 21 = 3×7. Hence 3|(22-1), and so 22 ≡ 1 (mod 3) b. Is –5 ≡ +10 (mod 3)? Since –5 – 10 = -15 = 3 × (-5). Hence 3|((-5)-10), and so -5 ≡ 10 (mod 3) c. Is 7 ≡ 7 (mod 3)? Since 7 – 7 = 0 = 3 × 0. Hence 3|(7-7), and so 7 ≡ 7 (mod 3) d. Is 14 ≡ 4 (mod 3)? Since 14 – 4 = 10, and 3 ∤ 10 because 10 ≠ 3·k for any integer k. Hence 14 ≡ 4 (mod 3).

EXERCISE: CONGRUENCE MODULO 3 IS AN EQUIVALENCE RELATION

Define a relation R on the set of all integers Z as follows: for all integers m and n, m R n ⇔ m ≡ n (mod 3). Prove that R is an equivalence relation.

Reflexive: R is reflexive iff for all m ∈ Z, m R m. By definition of R, this means for all m ∈ Z, m ≡ m (mod 3). Since m – m = 0 = 3×0, hence 3|(m-m), and so m ≡ m (mod 3) ⇒ mRm. Hence R is reflexive.

Symmetric: R is symmetric iff for all m, n ∈ Z, if m R n then n R m. Now mRn ⇒ m≡n (mod 3) ⇒ 3|(m-n) ⇒ m-n = 3k for some integer k ⇒ n – m = 3(-k), -k ∈ Z ⇒ 3|(n-m) ⇒ n ≡ m (mod 3) ⇒ nRm. Hence R is symmetric.

Transitive: R is transitive iff for all m, n, p ∈ Z, if mRn and nRp then mRp. Now mRn and nRp means m ≡ n (mod 3) and n ≡ p (mod 3) ⇒ 3|(m-n) and 3|(n-p) ⇒ (m-n) = 3r and (n-p) = 3s for some r,s ∈ Z. Adding: (m – n) + (n – p) = 3r + 3s ⇒ m – p = 3(r + s) where r+s ∈ Z ⇒ 3|(m – p) ⇒ m ≡ p (mod 3) ⇔ mRp. Hence R is transitive. R being reflexive, symmetric and transitive, is an equivalence relation.

⭐ Key Takeaways

A relation's properties—reflexivity, symmetry, and transitivity—are defined by logical conditions on ordered pairs and are verified by checking all applicable pairs. Reflexivity requires every element to relate to itself; symmetry demands that for every directed pair, the reverse pair also exists; transitivity requires that any two-step path implies a direct connection. These properties can be visually identified from directed graphs (loops for reflexivity, bidirectional arrows for symmetry, shortcuts for transitivity) and from matrices (diagonal ones for reflexivity, symmetry about the diagonal for symmetry). An equivalence relation is a relation that possesses all three properties, and congruence modulo d is a classic example of an equivalence relation on integers.

🧠 Quick Revision Questions

1. What condition must hold for a relation R on set A to be reflexive?
2. If a relation R is not symmetric, what specific pair(s) must exist in R?
3. Given the relation R = {(1,1), (1,2), (2,3)} on A = {1,2,3}, why is R not transitive?
4. Explain why the null relation on a non-empty set is symmetric and transitive but not reflexive.
5. Prove directly that the relation "has the same birthday as" defined on the set of all people is an equivalence relation.

📘 Lecture 13 — Matrix Representation of Relations

📖 Overview: This lecture explores matrix representations of relations and examines fundamental properties of binary relations including reflexivity, irreflexivity, symmetry, antisymmetry, and transitivity. It demonstrates how these properties appear in both matrix form and directed graphs, culminating in the definition of partial order relations with multiple examples.

🗂️ Topics Covered

The lecture covers the intersection of reflexive, symmetric, and transitive relations with proofs; irreflexive relations with matrix and directed graph representations; antisymmetric relations with matrix and directed graph representations; partial order relations defined as reflexive, antisymmetric, and transitive; and examples of partial orders including "less than or equal to" on real numbers, subset relation on power sets, divides relation on positive integers, and a relation defined by powers on integers.

📝 Lecture Summary

EXERCISE: Intersection of Relations

Suppose R and S are binary relations on a set A. We examine whether properties are preserved under intersection.

a. R ∩ S is reflexive: If R and S are reflexive, then for all a ∈ A, (a,a) ∈ R and (a,a) ∈ S. By definition of intersection, (a,a) ∈ R ∩ S for all a ∈ A. Therefore R ∩ S is reflexive.

b. R ∩ S is symmetric: If R and S are symmetric, suppose (a,b) ∈ R ∩ S. Then (a,b) ∈ R and (a,b) ∈ S. Since R is symmetric, (b,a) ∈ R. Since S is symmetric, (b,a) ∈ S. Thus (b,a) ∈ R ∩ S, proving R ∩ S is symmetric.

c. R ∩ S is transitive: If R and S are transitive, suppose (a,b) ∈ R ∩ S and (b,c) ∈ R ∩ S. Then (a,b) ∈ R, (a,b) ∈ S, (b,c) ∈ R, and (b,c) ∈ S. Since R is transitive, (a,c) ∈ R. Since S is transitive, (a,c) ∈ S. Therefore (a,c) ∈ R ∩ S, proving R ∩ S is transitive.

🔑 Definition — Intersection of Relations: The intersection of two relations R and S contains exactly those ordered pairs that belong to both R and S.

💡 Why this matters: These proofs show that the intersection of two reflexive, symmetric, or transitive relations preserves each respective property — but this is not true for all operations like union.

EXAMPLE: Let A = {1,2,3,4} with R = {(1,2), (1,3), (2,2), (3,3), (4,2), (4,3)} and S = {(2,1), (2,4), (3,3)} both transitive. R ∪ S = {(1,2), (1,3), (2,1), (2,2), (2,4), (3,3), (4,2), (4,3)}. Note (1,2) and (2,1) ∈ R∪S, but (1,1) ∉ R∪S. Hence R∪S is not transitive.

IRREFLEXIVE RELATION

Let R be a binary relation on a set A. R is irreflexive iff for all a ∈ A, (a,a) ∉ R. That is, no element in A is related to itself by R.

REMARK: R is not irreflexive iff there is an element a ∈ A such that (a,a) ∈ R.

EXAMPLE: Let A = {1,2,3,4}. R₁ = {(1,3), (1,4), (2,3), (2,4), (3,1), (3,4)} is irreflexive since no element is related to itself. R₂ = {(1,1), (1,2), (2,1), (2,2), (3,3), (4,4)} is not irreflexive since all elements are self-related. R₃ = {(1,2), (2,3), (3,3), (3,4)} is not irreflexive since (3,3) ∈ R₃. Note: R₃ is not reflexive either.

NOTE: A relation may be neither reflexive nor irreflexive.

DIRECTED GRAPH OF AN IRREFLEXIVE RELATION

In the directed graph of an irreflexive relation, there is no loop at any point of A.

EXAMPLE: Let A = {1,2,3} and R = {(1,3), (2,1), (2,3), (3,2)}. The directed graph shows arrows between distinct elements with no loops.

🔑 Definition — Irreflexive Relation: A relation R on set A is irreflexive when no element is related to itself, i.e., (a,a) ∉ R for all a ∈ A.

MATRIX REPRESENTATION OF AN IRREFLEXIVE RELATION

For an irreflexive relation R, the matrix representation will contain all 0's in its main diagonal. If any diagonal element is 1, the relation is not irreflexive.

📐 Matrix condition: A relation is irreflexive ↔ all diagonal entries in its matrix are 0.

EXAMPLE: Let A = {1,2,3} and R = {(1,3), (2,1), (2,3), (3,2)}. Matrix M =

   1 2 3
1 [0 0 1]
2 [1 0 1]
3 [0 1 0]

All main diagonal elements are 0, so R is irreflexive.

EXERCISE: Let R be the relation on Z defined as: (a,b) ∈ R ⇔ a > b. Is R irreflexive? Solution: For all a ∈ Z, (a,a) ∉ R since a > a is false. Hence R is irreflexive.

ANTISYMMETRIC RELATION

Let R be a binary relation on a set A. R is anti-symmetric iff ∀a,b ∈ A, if (a,b) ∈ R and (b,a) ∈ R then a = b.

REMARKS:

1. R is not anti-symmetric iff there exist a,b ∈ A with (a,b) ∈ R and (b,a) ∈ R but a ≠ b.
2. Being symmetric and being anti-symmetric are not negatives of each other.

EXAMPLE: Let A = {1,2,3,4}. R₁ = {(1,1), (2,2), (3,3)} is anti-symmetric and symmetric. R₂ = {(1,2), (2,2), (2,3), (3,4), (4,1)} is anti-symmetric but not symmetric because (1,2) ∈ R₂ but (2,1) ∉ R₂. R₃ = {(1,3), (2,2), (2,4), (3,1), (4,2)} is not anti-symmetric since (1,3) & (3,1) ∈ R₃ but 1 ≠ 3 (note R₃ is symmetric). R₄ = {(1,3), (2,4), (3,1), (4,3)} is neither anti-symmetric [ (1,3) & (3,1) ∈ R₄, 1≠3 ] nor symmetric [ (2,4) ∈ R₄ but (4,2) ∉ R₄ ].

🔑 Definition — Anti-symmetric Relation: A relation is anti-symmetric if the only way for both (a,b) and (b,a) to be in the relation is when a = b.

DIRECTED GRAPH OF AN ANTISYMMETRIC RELATION

In the directed graph of an anti-symmetric relation, there is no pair of arrows between two distinct elements of A.

EXAMPLE: Let A = {1,2,3} and R = {(1,1), (1,2), (2,3), (3,1)}. The directed graph shows arrows from 1→2, 2→3, 3→1 with no reverse arrows between any distinct points. R is anti-symmetric.

MATRIX REPRESENTATION OF AN ANTISYMMETRIC RELATION

Let R be an anti-symmetric relation on A = {a₁, a₂, ..., aₙ}. If (aᵢ, aⱼ) ∈ R for i ≠ j then (aⱼ, aᵢ) ∉ R. In the matrix, if the (i,j) entry is 1 (i≠j), then the (j,i) entry must be 0, and vice versa.

EXAMPLE: Let A = {1,2,3} and R = {(1,1), (1,2), (2,3), (3,1)}. Matrix M =

   1 2 3
1 [1 1 0]
2 [0 0 1]
3 [1 0 0]

R is anti-symmetric: note (1,2)=1 and (2,1)=0; (2,3)=1 and (3,2)=0; (3,1)=1 and (1,3)=0.

💡 Why this matters: Matrix representation provides a visual and computational way to verify properties — check diagonals for reflexivity/irreflexivity and symmetric pairs for antisymmetry.

PARTIAL ORDER RELATION

Let R be a binary relation defined on a set A. R is a partial order relation if and only if R is reflexive, antisymmetric, and transitive. The set A together with a partial ordering R is called a partially ordered set or poset.

🔑 Definition — Partial Order: A relation that is simultaneously reflexive, antisymmetric, and transitive.

EXAMPLE: Let R be the set of real numbers with the "less than or equal to" relation (≤). Show ≤ is a partial order.

Solution:

• Reflexive: For all x ∈ R, x ≤ x since x = x is always true.
• Anti-symmetric: If x ≤ y and y ≤ x, then by the trichotomy property (exactly one of x<y, x=y, x>y holds), we must have x = y.
• Transitive: If x ≤ y and y ≤ z, then x ≤ z follows from the transitive property of order (if x<y and y<z then x<z).

Thus ≤ is a partial order relation on R.

EXERCISE: Let A be a non-empty set and P(A) the power set of A. Define the "subset" relation ⊆ as: X ⊆ Y ⇔ ∀x, if x∈X then x∈Y. Show ⊆ is a partial order.

Solution:

1. Reflexive: Every set is a subset of itself, so X ⊆ X for all X ∈ P(A).
2. Anti-symmetric: If X ⊆ Y and Y ⊆ X, then by definition of set equality, X = Y.
3. Transitive: If X ⊆ Y and Y ⊆ Z, then by transitive property of subsets, X ⊆ Z.

Thus ⊆ is a partial order relation on P(A).

EXERCISE: Let "|" be the "divides" relation on a set A of positive integers. That is, a|b ⇔ b = k·a for some integer k. Prove | is a partial order.

Solution:

1. Reflexive: For all a ∈ A, a = 1·a, so a|a.
2. Anti-symmetric: Suppose a|b and b|a. Then b = k₁·a and a = k₂·b for integers k₁, k₂. Substituting: b = k₁·(k₂·b) = (k₁·k₂)·b. Dividing by b: 1 = k₁·k₂. Since k₁,k₂ are positive integers, k₁ = k₂ = 1. Thus a = 1·b = b.
3. Transitive: Suppose a|b and b|c. Then b = k₁·a and c = k₂·b. Substituting: c = k₂·(k₁·a) = (k₂·k₁)·a = k₃·a (where k₃ = k₂·k₁ is an integer). Thus a|c.

Therefore | is a partial order on A.

EXERCISE: Let R be the relation on Z defined as: aRb iff b = aʳ for some positive integer r. Show R is a partial order.

Solution:

1. Reflexive: For any a ∈ Z, a = a¹, so aRa.
2. Anti-symmetric: Suppose aRb and bRa. Then b = aʳ and a = bˢ for positive integers r,s. Substituting: a = (aʳ)ˢ = aʳˢ, so rs = 1. Since r,s are positive integers, r = s = 1, giving a = b¹ = b.
3. Transitive: Suppose aRb and bRc. Then b = aʳ and c = bˢ. Substituting: c = (aʳ)ˢ = aʳˢ = aᵗ where t = rs is a positive integer. Thus aRc.

Therefore R is a partial order relation on Z.

⭐ Key Takeaways

The intersection of reflexive, symmetric, or transitive relations preserves those properties, but union does not necessarily preserve transitivity. Irreflexive relations have no self-related elements, appearing as zero diagonals in matrices and no loops in directed graphs. Antisymmetric relations forbid pairs of arrows between distinct elements, appearing as matrices where (i,j)=1 with i≠j forces (j,i)=0. A partial order relation must satisfy three properties simultaneously: reflexivity, antisymmetry, and transitivity, making it a fundamental structure for ordering elements in sets, with examples including ≤ on real numbers, ⊆ on power sets, and | (divides) on positive integers.

🧠 Quick Revision Questions

1. If R and S are both reflexive relations on set A, is R ∪ S necessarily reflexive? Explain.
2. What condition must the diagonal entries of a matrix satisfy for the relation to be irreflexive?
3. Can a relation be both symmetric and anti-symmetric? If so, give an example.
4. State the three properties that a relation must satisfy to be a partial order.
5. For the divides relation on positive integers, prove that if a|b and b|a then a = b.

📘 Lecture 14 — Inverse of Relations

📖 Overview: This lecture explores the concept of inverse relations, including their definition, representation, and properties. It also introduces complementary and composite relations, providing foundational tools for understanding how relations can be manipulated and combined in discrete mathematics.

🗂️ Topics Covered

The lecture covers the definition and examples of inverse relations, their arrow diagram and matrix representations, proofs of how inverse relations preserve reflexivity, symmetry, transitivity, and antisymmetry, the condition for a relation to be symmetric (R = R⁻¹), complementary relations and their properties, and composite relations with arrow diagram and matrix representations using Boolean operations.

📝 Lecture Summary

Inverse of a Relation

Let R be a relation from A to B. The inverse relation R⁻¹ from B to A is defined as: R⁻¹ = {(b,a) ∈ B×A | (a,b) ∈ R}. More simply, the inverse relation R⁻¹ of R is obtained by interchanging the elements of all the ordered pairs in R.

🔑 Definition — Inverse Relation: R⁻¹ = {(b,a) ∈ B×A | (a,b) ∈ R}

Example: Let A = {2, 3, 4} and B = {2,6,8} and let R be the "divides" relation from A to B, i.e., for all (a,b) ∈ A×B, a R b ⇔ a | b (a divides b). Then R = {(2,2), (2,6), (2,8), (3,6), (4,8)} and R⁻¹ = {(2,2), (6,2), (8,2), (6,3), (8,4)}. In words, R⁻¹ may be defined as: for all (b,a) ∈ B×A, b R a ⇔ b is a multiple of a.

Arrow Diagram of an Inverse Relation

The relation R = {(2,2), (2,6), (2,8), (3,6), (4,8)} is represented by an arrow diagram from A to B. The inverse of this relation can be obtained simply by changing the directions of the arrows, resulting in an arrow diagram from B to A.

Matrix Representation of Inverse Relation

The relation R = {(2,2), (2,6), (2,8), (3,6), (4,8)} from A = {2,3,4} to B = {2,6,8} is defined by matrix M:

   2  6  8
2 [1  1  1]
3 [0  1  0]
4 [0  0  1]

The matrix representation of inverse relation R⁻¹ is obtained by simply taking its transpose (changing rows by columns and columns by rows):

   2  3  4
2 [1  0  0]
6 [1  1  0]
8 [1  0  1]

Thus R⁻¹ is represented by Mᵗ.

Properties of Inverse Relations

Exercise: Let R be a binary relation on a set A. Prove that:

(i) If R is reflexive, then R⁻¹ is reflexive. Suppose R on A is reflexive. By definition, ∀ a ∈ A, (a,a) ∈ R. Since R⁻¹ consists of exactly those ordered pairs obtained by interchanging the first and second element of ordered pairs in R, if (a,a) ∈ R then (a,a) ∈ R⁻¹. Accordingly, ∀ a ∈ A, (a,a) ∈ R⁻¹. Hence R⁻¹ is reflexive.

(ii) If R is symmetric, then R⁻¹ is symmetric. Suppose R on A is symmetric. Let (a,b) ∈ R⁻¹ for a,b ∈ A. By definition of R⁻¹, (b,a) ∈ R. Since R is symmetric, (a,b) ∈ R. Then by definition of R⁻¹, (b,a) ∈ R⁻¹. Thus for all a,b ∈ A, if (a,b) ∈ R⁻¹ then (b,a) ∈ R⁻¹. Accordingly R⁻¹ is symmetric.

(iii) If R is transitive, then R⁻¹ is transitive. Suppose R on A is transitive. Let (a,b) ∈ R⁻¹ and (b,c) ∈ R⁻¹. Then by definition of R⁻¹, (b,a) ∈ R and (c,b) ∈ R. Since R is transitive, if (c,b) ∈ R and (b,a) ∈ R then (c,a) ∈ R. By definition of R⁻¹, (a,c) ∈ R⁻¹. Thus for all a,b,c ∈ A, if (a,b) ∈ R⁻¹ and (b,c) ∈ R⁻¹ then (a,c) ∈ R⁻¹. Accordingly R⁻¹ is transitive.

(iv) If R is antisymmetric, then R⁻¹ is antisymmetric. Suppose R on A is antisymmetric. Let (a,b) ∈ R⁻¹ and (b,a) ∈ R⁻¹. Then by definition of R⁻¹, (b,a) ∈ R and (a,b) ∈ R. Since R is antisymmetric, if (a,b) ∈ R and (b,a) ∈ R then a = b. Thus if (a,b) ∈ R⁻¹ and (b,a) ∈ R⁻¹ then a = b. Accordingly R⁻¹ is antisymmetric.

Symmetric Relation Criterion

Exercise: Show that the relation R on a set A is symmetric if, and only if, R = R⁻¹.

Solution (Forward direction): Suppose R on A is symmetric. Let (a,b) ∈ R. Since R is symmetric, (b,a) ∈ R. By definition of R⁻¹, if (b,a) ∈ R then (a,b) ∈ R⁻¹. Since (a,b) is arbitrary, R ⊆ R⁻¹. Next, let (c,d) ∈ R⁻¹. By definition of R⁻¹, (d,c) ∈ R. Since R is symmetric, (c,d) ∈ R. Hence R⁻¹ ⊆ R. By both inclusions, R = R⁻¹.

Solution (Reverse direction): Suppose R = R⁻¹. Let (a,b) ∈ R. By definition of R⁻¹, (b,a) ∈ R⁻¹. Since R = R⁻¹, (b,a) ∈ R⁻¹ = R. Thus if (a,b) ∈ R then (b,a) ∈ R. Accordingly R is symmetric.

Complementary Relation

Let R be a relation from a set A to a set B. The complementary relation R̅ of R is the set of all those ordered pairs in A×B that do not belong to R.

🔑 Definition — Complementary Relation: R̅ = A×B - R = {(a,b) ∈ A×B | (a,b) ∉ R}

Example: Let A = {1,2,3} and R = {(1,1), (1,3), (2,2), (2,3), (3,1)} be a relation on A. Then R̅ = {(1,2), (2,1), (3,2), (3,3)}

Exercise: Let R be the relation R = {(a,b) | a < b} on the set of integers. Find: a) R̅ b) R⁻¹

a) R̅ = Z×Z - R = {(a,b) | a < b} = {(a,b) | a ≥ b} b) R⁻¹ = {(a,b) | a > b}

Exercise: Let R be a relation on a set A. Prove that R is reflexive iff R̅ is irreflexive.

Solution (Forward): Suppose R is reflexive. Then ∀ a ∈ A, (a,a) ∈ R. By definition of the complementary relation, (a,a) ∉ R̅, ∀ a ∈ A. Accordingly R̅ is irreflexive.

Solution (Reverse): If R̅ is irreflexive, then (a,a) ∉ R̅, ∀ a ∈ A. Hence by definition of R̅, (a,a) ∈ R, ∀ a ∈ A. Accordingly R is reflexive.

Exercise: Suppose R is a symmetric relation on a set A. Is R̅ also symmetric?

Solution: Let (a,b) ∈ R̅. Then by definition of R̅, (a,b) ∉ R. Since R is symmetric, if (a,b) ∉ R then (b,a) ∉ R (for (b,a) ∈ R and (a,b) ∉ R would contradict the symmetry property of R). Now (b,a) ∉ R ⇒ (b,a) ∈ R̅. Hence if (a,b) ∈ R̅ then (b,a) ∈ R̅. Thus R̅ is also symmetric.

💡 Why this matters: The complementary relation preserves symmetry, which is useful for understanding how properties transfer between a relation and its complement.

Composite Relation

Let R be a relation from a set A to a set B and S a relation from B to a set C. The composite of R and S denoted S∘R is the relation from A to C, consisting of ordered pairs (a,c) where a ∈ A, c ∈ C, and for which there exists an element b ∈ B such that (a,b) ∈ R and (b,c) ∈ S.

🔑 Definition — Composite Relation: S∘R = {(a,c) | a ∈ A, c ∈ C, ∃ b ∈ B, (a,b) ∈ R and (b,c) ∈ S}

Example: Define R = {(a,1), (a,4), (b,3), (c,1), (c,4)} as a relation from A to B and S = {(1,x), (2,x), (3,y), (3,z)} as a relation from B to C. Hence S∘R = {(a,x), (b,y), (b,z), (c,x)}

Composite Relation from Arrow Diagram

Let A = {a,b,c}, B = {1,2,3,4} and C = {x,y,z}. Define relation R from A to B and S from B to C by an arrow diagram. The composite relation S∘R can be traced by following paths from A through B to C.

Matrix Representation of Composite Relation

The matrix representation of the composite relation can be found using the Boolean product of the matrices for the relations. If Mᴿ and Mˢ are the matrices for relations R (from A to B) and S (from B to C), then Mˢ∘ᴿ = Mᴿ ○ Mˢ is the matrix for the composite relation S∘R from A to C.

Boolean Arithmetic Rules:

• Boolean Addition: 1 + 1 = 1, 1 + 0 = 1, 0 + 0 = 0
• Boolean Multiplication: 1 · 1 = 1, 1 · 0 = 0, 0 · 0 = 0

Exercise: Find the matrices representing the relations S∘R and R∘S where the matrices representing R and S are:

        [1 0 1]          [0 1 0]
M_R =   [1 1 0]    M_S = [0 0 1]
        [0 0 0]          [1 0 1]

Solution: The matrix representation for S∘R is:

Mˢ∘ᴿ = Mᴿ ○ Mˢ

[1 0 1]   [0 1 0]   [1 1 1]
[1 1 0] ○ [0 0 1] = [0 1 1]
[0 0 0]   [1 0 1]   [0 0 0]

The matrix representation for R∘S is:

Mᴿ∘ˢ = Mˢ ○ Mᴿ

[0 1 0]   [1 0 1]   [1 1 0]
[0 0 1] ○ [1 1 0] = [0 0 1]
[1 0 1]   [0 0 0]   [1 0 1]

Exercise: Let R and S be reflexive relations on a set A. Prove S∘R is reflexive.

Solution: Since R and S are reflexive relations on A, ∀ a ∈ A, (a,a) ∈ R and (a,a) ∈ S. By definition of the composite relation S∘R, (a,a) ∈ S∘R ∀ a ∈ A. Accordingly S∘R is also reflexive.

⭐ Key Takeaways

The inverse of a relation is formed by swapping the coordinates of each ordered pair, and it preserves key properties including reflexivity, symmetry, transitivity, and antisymmetry. A relation is symmetric if and only if it equals its own inverse. The complementary relation consists of all pairs not in the original relation, and it is irreflexive exactly when the original is reflexive. Composite relations combine two relations through an intermediate set, and their matrix representation uses Boolean product. The composition of reflexive relations is always reflexive.

🧠 Quick Revision Questions

1. How is the inverse relation R⁻¹ defined from a given relation R?
2. If a relation R is reflexive, what property does R⁻¹ have?
3. What is the condition for a relation R to be symmetric in terms of its inverse?
4. How is the complementary relation R̅ defined?
5. What is the Boolean product rule for 1 · 1 in matrix representation of composite relations?

📘 Lecture 15 — Functions

📖 Overview: This lecture introduces the formal definition of a function as a special type of relation, contrasting functions with non-functions through examples and arrow diagrams. It covers fundamental concepts including domain, co-domain, range, well-definedness, image and inverse image of sets, and binary operations, establishing the foundational language for discrete mathematics and computer science.

🗂️ Topics Covered

The lecture covers relations and functions, including the two formal conditions for a function; arrow diagrams and the vertical line test; range of a function; graph of a function; counting functions and binary relations between sets; well-defined functions; image and inverse image of a set; and binary operations as functions from A×A to A.

📝 Lecture Summary

RELATIONS AND FUNCTIONS

A function F from a set X to a set Y is a relation from X to Y that satisfies two properties. First, for every element x in X, there is an element y in Y such that (x,y) ∈ F — every element of X is the first element of some ordered pair of F. Second, for all elements x in X and y and z in Y, if (x,y) ∈ F and (x,z) ∈ F, then y = z — no two distinct ordered pairs in F have the same first element.

🔑 Definition — Function: A function f from a set X to a set Y is a relationship between elements of X and elements of Y such that each element of X is related to a unique element of Y, denoted f: X → Y.

Domain of f is X, co-domain of f is Y. The value f(x) is called f of x, or the image of x under f.

📌 Example: Which relations define functions from X = {2,4,5} to Y={1,2,4,6}? R₁ = {(2,4), (4,1)} → Not a function because 5 ∈ X does not appear as first element R₂ = {(2,4), (4,1), (4,2), (5,6)} → Not a function because (4,1) and (4,2) have same first element but different second elements R₃ = {(2,4), (4,1), (5,6)} → Defines a function because every element of X is first element and no pair has same first with different second

ARROW DIAGRAM OF A FUNCTION

The definition of a function implies the arrow diagram has two properties: (1) Every element of X has an arrow coming out of it. (2) No two arrows from the same element of X point to two different elements of Y.

📌 Example: Let X = {a, b, c} and Y={1,2,3,4}. A function f from X to Y by arrow diagram has f(a) = 2, f(b) = 4, and f(c) = 2. The diagram satisfies both conditions.

FUNCTIONS AND NONFUNCTIONS

Which arrow diagrams define functions from X = {2,4,5} to Y = {1,2,4,6}? Diagram (a) is Not a function because 5∈X has no arrow. Diagram (b) is Not a function because 4∈X has two arrows to different elements.

RANGE OF A FUNCTION

Let f: X→Y. The range of f consists of those elements of Y that are images of elements of X. Symbolically, Range of f = {y ∈ Y | y = f(x), for some x ∈ X}. The range is always a subset of the co-domain. The range is also called the image of X under f. When y = f(x), x is called the pre-image of y.

📌 Example: Determine range for functions from X = {2,4,5} to Y = {1,2,4,6}: f: Range = {1, 6}; g = {(2,6), (4,2), (5,1)}: Range = {1, 2, 6}; h(2)=4, h(4)=4, h(5)=1: Range = {1, 4}

GRAPH OF A FUNCTION

Let f be a real-valued function of a real variable, f:R→R. The graph of f is the set of all points (x,y) in the Cartesian coordinate plane with x in the domain and y = f(x).

📌 Example: Graph of y = x²: Points include (-3,9), (-2,4), (-1,1), (0,0), (1,1), (2,4), (3,9).

VERTICAL LINE TEST FOR THE GRAPH OF A FUNCTION

For a graph to be the graph of a function, any given vertical line in its domain intersects the graph in at most one point.

📌 Example: The relation x = y² is not a function because a vertical line intersects the graph at two points (e.g., at x=4, points (4,2) and (4,-2)).

📌 Example: Find all functions from X = {a,b} to Y = {u,v}: There are 4 functions — (1) f(a)=u, f(b)=u; (2) f(a)=u, f(b)=v; (3) f(a)=v, f(b)=u; (4) f(a)=v, f(b)=v.

📌 Example: Find four binary relations from X = {a,b} to Y = {u,v} that are not functions: (1) No arrow from a; (2) No arrow from b; (3) No arrows from either; (4) a has two arrows.

NUMBER OF FUNCTIONS

🔑 Formula: Number of functions from a set with m elements to a set with n elements = n^m

📌 Example: How many functions from a set with 3 elements to a set with 4 elements? Each of the 3 elements can map to any of 4 elements: 4 × 4 × 4 = 4³ = 64

📌 Example: Suppose A has m elements and B has n elements: Number of binary relations from A to B = 2^(m·n) Number of functions from A to B = n^m Fraction of binary relations that are functions = n^m / 2^(m·n)

FUNCTIONS NOT WELL DEFINED

A function f: X → Y is well defined iff ∀ x₁, x₂ ∈ X, if x₁ = x₂ then f(x₁) = f(x₂).

📌 Example: Determine whether f is a function from Z to R: f(n) = ±n → Not well defined: each integer has two images +n and -n f(n) = 1/(n²-4) → Not well defined: f(2) and f(-2) are undefined f(n) = √(n²+1) → Not well defined for n<0: imaginary values f(n) = √(n²+1)/2 → Well defined: each integer has unique real image

📌 Example: Student C defines h: Q→Q by h(m/n) = m/n. Student D claims h is not well defined. h(1/2) = (1/2)/2 = 1/4. h(2/4) = (2/4)/4 = 2/16 = 1/8. But 1/2 = 2/4, yet h(1/2) ≠ h(2/4). So h is not well defined.

📌 Example: Let g: R→R⁺ be defined by g(x) = x²+1. To show g is well defined: If x₁ = x₂, then x₁² = x₂², so x₁²+1 = x₂²+1, thus g(x₁) = g(x₂). Domain = R, Co-domain = R⁺. Range = all real numbers ≥ 1, i.e., [1,∞) because x² ≥ 0 implies x²+1 ≥ 1.

IMAGE OF A SET

Let f: X→Y be a function and A ⊆ X. The image of A under f is f(A) = {y ∈ Y | y = f(x), for some x in A}.

📌 Example: Let X = {1,2,3,4}, Y = {a,b,c}, A = {1,2}, B = {2,3}, with f(1)=a, f(2)=b, f(3)=b, f(4)=c. Then f(A) = {b} and f(B) = {b,c}.

INVERSE IMAGE OF A SET

Let f: X→Y be a function and C ⊆ Y. The inverse image of C under f is f⁻¹(C) = {x ∈ X | f(x) ∈ C}.

📌 Example: Let C = {a}, D = {b,c}, E = {d}. Then f⁻¹(C) = {1,2}, f⁻¹(D) = {3,4}, f⁻¹(E) = ∅.

SOME RESULTS ON IMAGES AND INVERSE IMAGES

Let f: X→Y, A,B ⊆ X, C,D ⊆ Y:

1. If A ⊆ B then f(A) ⊆ f(B)
2. f(A∪B) = f(A) ∪ f(B)
3. f(A∩B) ⊆ f(A) ∩ f(B)
4. f(A-B) ⊇ f(A) - f(B)
5. If C ⊆ D, then f⁻¹(C) ⊆ f⁻¹(D)
6. f⁻¹(C∪D) = f⁻¹(C) ∪ f⁻¹(D)
7. f⁻¹(C∩D) = f⁻¹(C) ∩ f⁻¹(D)
8. f⁻¹(C-D) = f⁻¹(C) - f⁻¹(D)

BINARY OPERATIONS

A binary operation “” defined on a set A assigns to each ordered pair (a, b) of elements of A, a uniquely determined element ab of A. A binary operation takes two elements of A and maps them to a third element of A.

A binary operation on a set A is a function from A × A to A, i.e., *: A×A → A. (a,b) is more commonly written as ab.

📌 Example: “+” and “·” are binary operations on N. “−” is not a binary operation on N but is on Z. “÷” is a binary operation on Q-{0} but not on Z.

📌 Example: Set operations union (∪), intersection (∩), and set difference (−) are binary operations on the power set P(A) of any set A. Logical connectives ∨, ∧, →, ↔ are binary operations on {T, F}. Logic gates OR and AND are binary operations on {0,1}. Logic gate NOT is a unary operation on {0,1}.

💡 Why this matters: The distinction between functions and general relations is fundamental to computer science — every program function, database query, and circuit must be well-defined and deterministic. Binary operations form the basis of arithmetic, logic gates, and algebraic structures.

⭐ Key Takeaways

A function is a relation where every element of the domain maps to exactly one unique element in the co-domain, which can be tested using arrow diagrams (every element must have exactly one outgoing arrow) or the vertical line test on graphs. The number of functions from an m-element set to an n-element set is n^m. A function is well-defined only if equal inputs always produce equal outputs — a critical property for correctness. The image and inverse image of sets extend functions from individual elements to subsets, with specific algebraic properties.

🧠 Quick Revision Questions

1. What are the two formal conditions that a relation must satisfy to be considered a function?
2. If set A has 5 elements and set B has 3 elements, how many functions exist from A to B? How many binary relations from A to B?
3. Why is h(m/n) = m/n not a well-defined function from Q to Q?
4. What is the difference between the range and the co-domain of a function?
5. What properties hold for the inverse image of a union? f⁻¹(C ∪ D) = ?

📘 Lecture 16 — Types of functions

📖 Overview: This lecture explores different types of functions based on how they map elements between sets. It defines and illustrates injective (one-to-one), surjective (onto), and bijective functions, along with identity and constant functions, providing formal definitions, proofs, examples, and counting techniques essential for understanding function properties in discrete mathematics.

🗂️ Topics Covered

The lecture covers injective (one-to-one) functions with their formal definition, contrapositive form, examples, and counting problems; graphical interpretation via the horizontal line test; surjective (onto) functions with definition, examples, and graphical interpretation; bijective functions as a combination of both properties; and finally identity and constant functions with proofs of their properties.

📝 Lecture Summary

INJECTIVE or ONE-TO-ONE FUNCTION

A function (f: X \to Y) is injective or one-to-one if, and only if, for all (x_1, x_2 \in X), if (x_1 \ne x_2) then (f(x_1) \ne f(x_2)). This means distinct points in the domain map to distinct points in the co-domain. A one-to-one function separates points.

A function (f) is not one-to-one when there exist elements (x_1) and (x_2) with (x_1 \ne x_2) but (f(x_1) = f(x_2)). Such a function collapses points together.

🔑 Definition — Injective Function: A function that maps distinct elements of the domain to distinct elements of the co-domain.

🔑 Alternative Definition: A function (f: X \to Y) is one-to-one iff for all (x_1, x_2 \in X), if (f(x_1) = f(x_2)) then (x_1 = x_2). This is the contrapositive of the original definition.

📌 Example: Determine if (f: \mathbb{R} \to \mathbb{R}) defined by (f(x) = 4x - 1) is one-to-one. Proof: Let (x_1, x_2 \in \mathbb{R}) with (f(x_1) = f(x_2)). Then (4x_1 - 1 = 4x_2 - 1). Adding 1 gives (4x_1 = 4x_2). Dividing by 4 gives (x_1 = x_2). Hence (f) is one-to-one.

📌 Example: Determine if (g: \mathbb{Z} \to \mathbb{Z}) defined by (g(n) = n^2) is one-to-one. Counter example: Let (n_1 = 2) and (n_2 = -2). Then (g(2) = 4) and (g(-2) = 4), so (g(2) = g(-2)) but (2 \ne -2). Hence (g) is not one-to-one.

📌 Example: Find all one-to-one functions from (X = {a, b}) to (Y = {u, v}). Solution: There are exactly 2 one-to-one functions. Function 1: (a \to u, b \to v). Function 2: (a \to v, b \to u).

📐 Formula — Counting One-to-One Functions: Number of one-to-one functions from a set with (m) elements to a set with (n) elements is (n \times (n-1) \times (n-2) \times \cdots \times (n-m+1)), provided (m \le n). If (m > n), there are zero one-to-one functions.

📌 Example: How many one-to-one functions from a set with 3 elements to a set with 4 elements? Solution: (4 \times 3 \times 2 = 24) functions.

📌 Example: How many one-to-one functions from a set with 3 elements to a set with 2 elements? Solution: Zero, because two elements in X map to the two in Y, but the third element of X has no distinct target left.

🔑 Graphical Interpretation — Horizontal Line Test: A graph of a function (f) is one-to-one iff every horizontal line intersects the graph in at most one point.

💡 Why this matters: The horizontal line test provides a quick visual way to check injectivity without algebraic proof.

SURJECTIVE FUNCTION or ONTO FUNCTION

A function (f: X \to Y) is surjective or onto if for every (y \in Y), there exists (x \in X) such that (f(x) = y). This means every element of the co-domain is the image of some element of the domain, i.e., co-domain of (f) = range of (f).

A function (f) is not onto if there exists (y \in Y) such that for all (x \in X), (f(x) \ne y). That is, some element of co-domain is not hit by any domain element.

🔑 Definition — Surjective Function: A function where every element of the co-domain is the image of at least one element of the domain.

📌 Example: Which arrow diagrams define onto functions? Diagram f: Not onto because 3 is not the image of any x in X. Diagram g: Onto because 1 = g(c), 2 = g(d), 3 = g(a) = g(b).

📌 Example: Define (f: \mathbb{R} \to \mathbb{R}) by (f(x) = 4x - 1). Is (f) onto? Proof: Let (y \in \mathbb{R}). Find (x = \frac{y+1}{4} \in \mathbb{R}). Then (f(x) = 4(\frac{y+1}{4}) - 1 = (y+1)-1 = y). Hence every (y) has a preimage, so (f) is onto.

📌 Example: Define (h: \mathbb{Z} \to \mathbb{Z}) by (h(n) = 4n - 1). Is (h) onto? Counter example: Let (m = 0). We need (4n - 1 = 0), so (n = \frac{1}{4} \notin \mathbb{Z}). Hence no integer (n) gives (h(n) = 0), so (h) is not onto.

🔑 Graphical Interpretation: A graph of a function (f) is onto iff every horizontal line intersects the graph in at least one point.

📌 Example: (y = |x|) from (\mathbb{R}) to (\mathbb{R}^+) is onto. (y = e^x) from (\mathbb{R}) to (\mathbb{R}) is not onto (negative values have no preimage).

📌 Example: (X = {1,5,9}), (Y = {3,4,7}), (g(1)=7, g(5)=3, g(9)=4). Is (g) one-to-one? Onto? Solution: (g) is one-to-one because all images are distinct. (g) is onto because every element of Y is an image: (3=g(5), 4=g(9), 7=g(1)).

📌 Example: (f: P({a,b,c}) \to \mathbb{Z}) where (f(A) = |A|). Is (f) one-to-one? Onto? Solution: Not one-to-one because (f({a}) = 1 = f({b})) but ({a} \ne {b}). Not onto because no set maps to (4 \in \mathbb{Z}) (max size is 3).

📌 Example: Determine injectivity/surjectivity: (a) (f: \mathbb{Z} \to \mathbb{Z}^+), (f(x) = |x|): Not injective ((f(1)=f(-1)) but (1 \ne -1)). Onto because every positive integer (a) has both (-a) and (a) as preimages. (b) (g: \mathbb{Z}^+ \to \mathbb{Z}^+ \times \mathbb{Z}^+), (g(x) = (x, x+1)): Injective (if ((x_1, x_1+1) = (x_2, x_2+1)) then (x_1=x_2)). Not onto because ((1,1)) has no preimage.

BIJECTIVE FUNCTION or ONE-TO-ONE CORRESPONDENCE

A function (f: X \to Y) that is both one-to-one (injective) and onto (surjective) is called a bijective function or a one-to-one correspondence.

🔑 Definition — Bijective Function: A function that is both injective and surjective, creating a perfect pairing between elements of the domain and co-domain.

📌 Example: The function (f: X \to Y) with (a \to 1, b \to 2, c \to 3) is bijective.

🔑 Graphical Interpretation: A graph of a function (f) is bijective iff every horizontal line intersects the graph at exactly one point.

📌 Example: Show (f: \mathbb{R} \to \mathbb{R}) defined by (f(x) = x^3) is bijective. Proof:

• One-to-one: Let (f(x_1) = f(x_2)). Then (x_1^3 = x_2^3), so (x_1^3 - x_2^3 = 0). Factor: ((x_1 - x_2)(x_1^2 + x_1x_2 + x_2^2) = 0). The second factor has no real zero (discriminant (x_2^2 - 4x_2^2 = -3x_2^2 \le 0), equality only at (x_1=x_2=0)). Hence (x_1 = x_2). So injective.
• Onto: Let (y \in \mathbb{R}). Choose (x = y^{1/3} \in \mathbb{R}). Then (f(x) = (y^{1/3})^3 = y). So surjective. Thus (f) is bijective.

IDENTITY FUNCTION ON A SET

Given a set (X), define a function (i_X: X \to X) by (i_X(x) = x) for all (x \in X). The function (i_X) is called the identity function on (X) because it sends each element to itself.

🔑 Definition — Identity Function: The function that maps every element to itself.

📌 Example: For (X = {1,2,3,4}), the identity function maps (1 \to 1, 2 \to 2, 3 \to 3, 4 \to 4).

📌 Theorem: The identity function on a non-empty set is bijective. Proof:

• Injective: Let (i_X(x_1) = i_X(x_2)). Then (x_1 = x_2), so injective.
• Surjective: Let (y \in X). Then (i_X(y) = y), so every element has a preimage. Hence (i_X) is bijective.

CONSTANT FUNCTION

A function (f: X \to Y) is a constant function if it maps all elements of (X) to a single element of (Y). That is, for all (x \in X), (f(x) = c) for some fixed (c \in Y).

🔑 Definition — Constant Function: A function that sends every element of the domain to the same value in the co-domain.

📌 Example: (f: {1,2,3,4} \to {7,8,9}) with (f(1)=7, f(2)=7, f(3)=7, f(4)=7) is constant.

🔑 Key Remark 1: A constant function is one-to-one iff its domain is a singleton (has exactly one element).

🔑 Key Remark 2: A constant function is onto iff its co-domain is a singleton (has exactly one element).

⭐ Key Takeaways

A one-to-one (injective) function maps distinct domain elements to distinct co-domain elements — use the contrapositive form (f(x_1)=f(x_2) \Rightarrow x_1=x_2) for proofs and apply the horizontal line test on graphs. An onto (surjective) function covers every co-domain element — for proofs, solve for (x) in terms of (y) and verify the solution lies in the domain. A bijective function is both one-to-one and onto, creating a perfect pairing. The identity function is always bijective, and constant functions are injective or surjective only in trivial singleton cases. Counting one-to-one functions follows a decreasing product formula, and the horizontal line test provides geometric intuition for all three function types.

🧠 Quick Revision Questions

1. State the contrapositive definition of a one-to-one function. Why is this form often easier to use in proofs?
2. Using the horizontal line test, explain why (f(x) = x^2) from (\mathbb{R}) to (\mathbb{R}) is neither injective nor surjective.
3. How many one-to-one functions exist from a 4-element set to a 5-element set? Show your calculation.
4. Prove that the function (f: \mathbb{R} \to \mathbb{R}) defined by (f(x) = 2x + 3) is bijective.
5. Give an example of a constant function that is both one-to-one and onto. What condition(s) must hold for this to be possible?

📘 Lecture 17 — Inverse Function

📖 Overview: This lecture covers the concept of inverse functions, including the conditions under which a function has an inverse and the properties of inverse functions. It also introduces function composition and explores relationships between functions and their inverses, which are fundamental concepts in discrete mathematics and calculus.

🗂️ Topics Covered

The lecture begins with equality of functions and examples demonstrating when two functions are identical. It then explores inverse functions through arrow diagrams, defining when an inverse exists and noting that only bijective functions have inverses. The lecture provides a working rule for finding inverse functions from formulas, followed by multiple examples. It concludes with composition of functions, including composition with identity functions and composing a function with its inverse.

📝 Lecture Summary

EQUALITY OF FUNCTIONS:

Suppose f and g are functions from X to Y. Then f equals g, written f = g, if, and only if, f(x)=g(x) for all x∈X.

🔑 Definition — Equality of functions: Two functions are equal if they produce identical outputs for every input in their common domain.

📌 Example: Define f: R→R and g: R→R by formulas f(x) = |x| and g(x) = √(x²) for all x∈R. Since |x| = √(x²) for all x∈R, therefore f(x) = g(x) for all x∈R. Hence f = g.

📌 Example: Define functions f and g from R to R by formulas: f(x) = 2x and g(x) = (2x³ + 2x)/(x² + 1) for all x∈R. Solution: g(x) = (2x³ + 2x)/(x² + 1) = 2x(x² + 1)/(x² + 1) = 2x = f(x) [since x² + 1 ≠ 0] for all x∈R. Hence f = g.

INVERSE OF A FUNCTION

The inverse of a function reverses the mapping from output back to input. A function f maps elements from domain X to codomain Y, and the inverse f⁻¹ maps elements from Y back to X.

🔑 Remark: Inverse of a function may not be a function. For an inverse to be a function, each output must map to exactly one input.

INJECTIVE FUNCTION INVERSE

The inverse of an injective function (one-to-one) may not be a function if the function is not also surjective.

SURJECTIVE FUNCTION INVERSE

The inverse of a surjective function (onto) may not be a function if the function is not also injective.

BIJECTIVE FUNCTION INVERSE

The inverse of a bijective function (both one-to-one and onto) is a function. Note: Inverse of a surjective function may not be a function.

INVERSE FUNCTION:

Suppose f: X→Y is a bijective function. Then the inverse function f⁻¹: Y→X is defined as: ∀ y∈Y, f⁻¹(y) = x ⇔ y = f(x) That is, f⁻¹ sends each element of Y back to the element of X that it came from under f.

🔑 Definition — Invertible function: A function whose inverse function exists is called an invertible function.

INVERSE FUNCTION FROM AN ARROW DIAGRAM:

Let the bijection f: X→Y be defined by an arrow diagram mapping elements 1,2,3,4 to elements 6,7,8,9. The inverse function f⁻¹: Y→X reverses the arrows, mapping 6,7,8,9 back to 1,2,3,4 respectively.

INVERSE FUNCTION FROM A FORMULA:

Let f: R→R be defined by the formula f(x) = 4x-1 for all x∈R. Then f is bijective, therefore f⁻¹ exists. By definition of f⁻¹, f⁻¹(y) = x ⇔ f(x)=y Now solving f(x) = y for x: 4x-1 = y → 4x = y+1 → x = (y+1)/4 Hence, f⁻¹(y) = (y+1)/4 is the inverse of f(x)=4x-1 which defines f⁻¹: R→R.

WORKING RULE TO FIND INVERSE FUNCTION:

Let f: X→Y be a one-to-one correspondence defined by the formula f(x)=y.

1. Solve the equation f(x) = y for x in terms of y.
2. f⁻¹(y) equals the right-hand side of the equation found in step 1.

📌 Example: Let a function f be defined on a set of real numbers as f(x) = (x+1)/(x-1) for all real numbers x≠1.

1. Show that f is a bijective function on R-{1}.
2. Find the inverse function f⁻¹.

Solution:

1. To show f is injective: Let x₁, x₂ ∈ R-{1} and suppose f(x₁)=f(x₂). We must show x₁=x₂. (x₁+1)/(x₁-1) = (x₂+1)/(x₂-1) (x₁+1)(x₂-1) = (x₂+1)(x₁-1) x₁x₂ - x₁ + x₂ - 1 = x₁x₂ - x₂ + x₁ - 1 -x₁ + x₂ = -x₂ + x₁ 2x₂ = 2x₁ x₂ = x₁. Hence f is injective.

b. To show f is surjective: Let y∈R-{1}. We look for x∈R-{1} such that f(x)=y. (x+1)/(x-1) = y x+1 = y(x-1) x+1 = yx-y y+1 = yx-x y+1 = x(y-1) x = (y+1)/(y-1). Thus for each y∈R-{1}, there exists x = (y+1)/(y-1) ∈ R-{1} such that f(x)=y.

2. Inverse function of f: From above, x = (y+1)/(y-1). Hence f⁻¹(y) = (y+1)/(y-1), y≠1.

📌 Example: Let f: R→R be defined by f(x) = x³ + 5. Show that f is one-to-one and onto. Find f⁻¹.

Solution:

1. f is one-to-one: Let f(x₁)=f(x₂) for x₁,x₂∈R. x₁³+5 = x₂³+5 → x₁³ = x₂³ → x₁ = x₂.

2. f is onto: Let y∈R. Find x such that f(x)=y. x³+5 = y → x³ = y-5 → x = ³√(y-5). Thus for each y∈R, x = ³√(y-5) ∈ R exists.

3. Formula for f⁻¹: x = ³√(y-5). Hence f⁻¹(y) = ³√(y-5).

COMPOSITION OF FUNCTIONS:

Let f: X→Y' and g: Y→Z be functions with the property that the range of f is a subset of the domain of g, i.e. f(X)⊆Y. Define a new function gof: X→Z as follows: (gof)(x) = g(f(x)) for all x∈X The function gof is called the composition of f and g.

🔑 Definition — Composition of functions: The composition gof first applies f to input x, then applies g to the result f(x).

COMPOSITION OF FUNCTIONS DEFINED BY ARROW DIAGRAMS:

Let X = {1,2,3}, Y'={a,b,c,d}, Y={a,b,c,d,e} and Z={x,y,z}. Define functions f:X→Y' and g:X→Z by arrow diagrams showing how elements map through the composition.

📌 Example: Let A = {1,2,3,4,5} with f,g: A→A defined as: f(1)=3, f(2)=5, f(3)=3, f(4)=1, f(5)=2 g(1)=4, g(2)=1, g(3)=1, g(4)=2, g(5)=3

Solution: (fog)(1)=f(g(1))=f(4)=1 (fog)(2)=f(g(2))=f(1)=3 (fog)(3)=f(g(3))=f(1)=3 (fog)(4)=f(g(4))=f(2)=5 (fog)(5)=f(g(5))=f(3)=3

(gof)(1)=g(f(1))=g(3)=1 (gof)(2)=g(f(2))=g(5)=3 (gof)(3)=g(f(3))=g(3)=1 (gof)(4)=g(f(4))=g(1)=4 (gof)(5)=g(f(5))=g(2)=1

🔑 Remark: The functions fog and gof are not equal.

COMPOSITION OF FUNCTIONS DEFINED BY FORMULAS:

Let f: Z→Z and g: Z→Z be defined by f(n)=n+1 and g(n)=n² for n∈Z. a. Find gof and fog. b. Is gof = fog?

Solution: a. (gof)(n)=g(f(n))=g(n+1)=(n+1)² for all n∈Z (fog)(n)=f(g(n))=f(n²)=n²+1 for all n∈Z

b. (gof)(1)=4 whereas (fog)(1)=2. Thus fog ≠ gof.

🔑 Remark: The composition of functions is not a commutative operation.

COMPOSITION WITH THE IDENTITY FUNCTION:

Let X={a,b,c,d} and Y={u,v,w} with f:X→Y defined by f(a)=u, f(b)=v, f(c)=v, f(d)=u. Find foiₓ and iᵧof, where iₓ and iᵧ are identity functions on X and Y respectively.

Solution: (foiₓ)(a)=f(iₓ(a))=f(a)=u, (foiₓ)(b)=v, (foiₓ)(c)=v, (foiₓ)(d)=u. So foiₓ = f. (iᵧof)(a)=iᵧ(f(a))=iᵧ(u)=u, (iᵧof)(b)=v, (iᵧof)(c)=v, (iᵧof)(d)=u. So iᵧof = f.

COMPOSING A FUNCTION WITH ITS INVERSE:

Let X={a,b,c} and Y={x,y,z}. Define f:X→Y with f(a)=z, f(b)=x, f(c)=y. Then f is bijective. f⁻¹ exists with f⁻¹(x)=b, f⁻¹(y)=c, f⁻¹(z)=a.

(f⁻¹of)(a)=f⁻¹(f(a))=f⁻¹(z)=a, (f⁻¹of)(b)=b, (f⁻¹of)(c)=c. Thus f⁻¹of: X→X sends each element of X to itself, so f⁻¹of = iₓ. Similarly, fof⁻¹ = iᵧ.

🔑 Remark: The function f: X→Y and g: Y→X are inverses of each other iff gof = iₓ and fog = iᵧ.

📌 Example: Let f: R→R and g: R→R be defined by f(x)=3x+2 and g(x)=(x-2)/3 for all x∈R.

Solution: (gof)(x)=g(f(x))=g(3x+2)=((3x+2)-2)/3=3x/3=x (fog)(x)=f(g(x))=f((x-2)/3)=3((x-2)/3)+2=(x-2)+2=x Thus gof and fog are identity functions. Accordingly f and g are inverse of each other.

💡 Why this matters: This example demonstrates how to verify inverse functions by showing that their compositions yield the identity function.

⭐ Key Takeaways

The most critical concepts from this lecture are that a function must be bijective (both one-to-one and onto) to have an inverse function, and the inverse function is found by solving f(x)=y for x in terms of y. Composition of functions is not commutative, meaning fog ≠ gof in general, but composing a function with its inverse always gives the identity function. Two functions are inverses of each other if and only if both gof and fog equal the identity function on their respective domains. The working rule for finding inverse functions involves solving for x and then swapping variables.

🧠 Quick Revision Questions

1. What condition must a function satisfy for its inverse to also be a function?
2. Find the inverse of f(x) = (2x-3)/5.
3. If f(x) = x² and g(x) = x+1, what is (fog)(2)?
4. What is the relationship between a function and its inverse when composed?
5. Is the composition of functions commutative? Give an example to support your answer.

📘 Lecture 18 — Composition of Functions

📖 Overview: This lecture explores the composition of functions, proving key theorems about how composition preserves one-to-one and onto properties, and establishing the associativity of composition. It also introduces real-valued functions and operations on them (sum, difference, product, quotient, scalar multiplication), and extends the discussion to finite/infinite sets, cardinality, countable sets, and image/inverse image of sets.

🗂️ Topics Covered

Theorems on composition preserving one-to-one and onto properties, associativity of composition, inverse of composition, real-valued functions and operations (sum, difference, product, quotient, scalar multiplication), counterexamples for sums of functions, zero function, characteristic functions, finite and infinite sets, cardinality, countable sets, image and inverse image of sets, and results on images/inverse images.

📝 Lecture Summary

THEOREM: If f and g are two one-to-one functions, then their composition gof is one-to-one

Proof: Let f: X → Y and g: Y → Z both be one-to-one. Suppose x₁, x₂ ∈ X such that (gof)(x₁) = (gof)(x₂). Then g(f(x₁)) = g(f(x₂)). Since g is one-to-one, f(x₁) = f(x₂). Since f is one-to-one, x₁ = x₂. Therefore, gof is one-to-one.

THEOREM: If f: X → Y and g: Y → Z are both onto functions, then gof: X → Z is onto

Proof: Let f: X → Y and g: Y → Z both be onto. Let z ∈ Z. Since g is onto, there exists y ∈ Y such that g(y) = z. Since f is onto, there exists x ∈ X such that f(x) = y. Hence, (gof)(x) = g(f(x)) = g(y) = z. Thus gof is onto.

💡 Why this matters: These theorems show that composition preserves the important properties of being one-to-one and onto, which is crucial for understanding function invertibility.

THEOREM: If f: W → X, g: X → Y, and h: Y → Z are functions, then (hog)of = ho(gof)

Proof: For every x ∈ W: ((hog)of)(x) = (hog)(f(x)) = h(g(f(x))) and (ho(gof))(x) = h((gof)(x)) = h(g(f(x))). Hence (hog)of = ho(gof).

🔑 Definition — Associativity of Composition: The composition of functions is associative.

EXERCISE: Suppose f: X → Y and g: Y → Z are both one-to-one and onto. Prove that (gof)⁻¹ exists and equals f⁻¹ o g⁻¹

Proof: Since f and g are bijective, their composition gof is bijective, so (gof)⁻¹: Z → X exists. To show (gof)⁻¹ = f⁻¹ o g⁻¹, we need (f⁻¹ o g⁻¹) o (gof) = iₓ and (gof) o (f⁻¹ o g⁻¹) = i_z.

First: (f⁻¹ o g⁻¹) o (gof) = f⁻¹ o (g⁻¹ o (gof)) = f⁻¹ o ((g⁻¹ o g) of) = f⁻¹ o (i_y of) = f⁻¹ o f = i_x

Second: (gof) o (f⁻¹ o g⁻¹) = go (f o (f⁻¹ o g⁻¹)) = go ((f o f⁻¹) o g⁻¹) = go (i_y o g⁻¹) = go g⁻¹ = i_z

Therefore, f⁻¹ o g⁻¹ = (gof)⁻¹.

REAL-VALUED FUNCTIONS

🔑 Definition — Real-valued function: Let X be any set and R be the set of real numbers. A function f: X → R that assigns to each x ∈ X a real number f(x) ∈ R is called a real-valued function.

If f: R → R, then f is called a real-valued function of a real variable.

📌 Example: f: R⁺ → R defined by f(x) = log x is a real valued function. 📌 Example: g: R → R defined by g(x) = eˣ is a real valued function of a real variable.

OPERATIONS ON FUNCTIONS

SUM OF FUNCTIONS

🔑 Definition — Sum of functions: Let f: X → R and g: X → R be real valued functions. The sum of f and g, denoted f+g, is a function f+g: X → R defined by (f+g)(x) = f(x) + g(x) for all x ∈ X.

📌 Example: Let f(x) = x² + 1 and g(x) = x + 2 from R to R. Then (f+g)(x) = (x² + 1) + (x + 2) = x² + x + 3 for all x ∈ R.

DIFFERENCE OF FUNCTIONS

🔑 Definition — Difference of functions: Let f: X → R and g: X → R be real valued functions. The difference of f and g, denoted f-g, is a function f-g: X → R defined by (f-g)(x) = f(x) - g(x) for all x ∈ X.

📌 Example: Let f(x) = x² + 1 and g(x) = x + 2. Then (f-g)(x) = (x² + 1) - (x + 2) = x² - x - 1 for all x ∈ R.

PRODUCT OF FUNCTIONS

🔑 Definition — Product of functions: Let f: X → R and g: X → R be real valued functions. The product of f and g, denoted f·g or fg, is a function f·g: X → R defined by (f·g)(x) = f(x)·g(x) for all x ∈ X.

📌 Example: Let f(x) = x² + 1 and g(x) = x + 2. Then (f·g)(x) = (x² + 1)(x + 2) = x³ + 2x² + x + 2 for all x ∈ R.

QUOTIENT OF FUNCTIONS

🔑 Definition — Quotient of functions: Let f: X → R and g: X → R be real valued functions. The quotient of f by g, denoted f/g, is a function from X to R defined by (f/g)(x) = f(x)/g(x), where g(x) ≠ 0.

📌 Example: Let f(x) = x² + 1 and g(x) = x + 2. Then (f/g)(x) = (x² + 1)/(x + 2) for all x ∈ R where x ≠ -2.

SCALAR MULTIPLICATION

🔑 Definition — Scalar multiplication: Let f: X → R be a real valued function and c be a non-zero real number. Then the scalar multiplication of f is a function c·f: R → R defined by (c·f)(x) = c·f(x) for all x ∈ X.

📌 Example: Let f(x) = x² + 1 and g(x) = x + 2. Then (3f - 2g)(x) = 3(x² + 1) - 2(x + 2) = 3x² - 2x - 1 for all x ∈ X.

EXERCISE: If f: R → R and g: R → R are both one-to-one, is f+g also one-to-one?

Counterexample: Define f(x) = x and g(x) = -x for all x ∈ R. Both f and g are one-to-one. However, (f+g)(x) = x + (-x) = 0 for all x ∈ R. Since (f+g)(1) = 0 and (f+g)(2) = 0 but 1 ≠ 2, f+g is not one-to-one.

EXERCISE: If f: R → R and g: R → R are both onto, is f+g also onto?

Counterexample: Define f(x) = x and g(x) = -x for all x ∈ R. Both f and g are onto. However, (f+g)(x) = 0 for all x ∈ R. Only 0 ∈ R has a pre-image; no non-zero element of the co-domain is the image of any element. Thus f+g is not onto.

EXERCISE: Let f: R → R be a function and c (≠ 0) ∈ R. 1. If f is one-to-one, is c·f also one-to-one? 2. If f is onto, is c·f also onto?

Solution for 1: Yes. Suppose f is one-to-one. Let (c·f)(x₁) = (c·f)(x₂). Then c·f(x₁) = c·f(x₂). Since c ≠ 0, f(x₁) = f(x₂). Since f is one-to-one, x₁ = x₂. Hence c·f is one-to-one.

Solution for 2: Yes. Suppose f is onto. Let y ∈ R. We need x ∈ R such that (c·f)(x) = y. Then c·f(x) = y, so f(x) = y/c. Since f is onto, for y/c ∈ R, there exists x ∈ R such that f(x) = y/c. Hence c·f is onto.

EXERCISE: Zero function

🔑 Definition — Zero function: The real-valued function 0ₓ: X → R defined by 0ₓ(x) = 0 for all x ∈ X is called the zero function (on X).

Proof that f + 0ₓ = f: (f + 0ₓ)(x) = f(x) + 0ₓ(x) = f(x) + 0 = f(x) for all x ∈ X.

Proof that f·0ₓ = 0ₓ: (f·0ₓ)(x) = f(x)·0ₓ(x) = f(x)·0 = 0 = 0ₓ(x) for all x ∈ X.

EXERCISE: Characteristic function

🔑 Definition — Characteristic function: Given a set S and a subset A, the characteristic function of A, denoted χₐ, is the function defined from S to the set {0,1} as:

• χₐ(x) = 1 if x ∈ A
• χₐ(x) = 0 if x ∉ A

Theorem: For all subsets A and B of S:

1. χₐₙₐ = χₐ · χₐ
2. χₐᵤₐ = χₐ + χₐ - χₐ · χₐ
3. χₐ'(x) = 1 - χₐ(x)

Proof of (1): If x ∈ A∩B, then χₐₙₐ(x) = 1, χₐ(x) = 1, χₐ(x) = 1, so χₐₙₐ(x) = 1 = (1)(1) = (χₐ·χₐ)(x). If y ∉ A∩B, then χₐₙₐ(y) = 0 and either χₐ(y) = 0 or χₐ(y) = 0, so χₐₙₐ(y) = 0 = (0)(0) = (χₐ·χₐ)(y). Hence χₐₙₐ = χₐ·χₐ.

EXERCISE: Functions from A = {1,2,3} to A

1. F is reflexive: A function F from A to A is reflexive iff every element is related to itself (aFa for all a ∈ A). Since F is a function, each element maps to a unique element. Hence F must map each element to itself, making F the identity function.

2. G is symmetric: G is symmetric iff whenever aGb then bGa. For a function from A to A, this means G must be both one-to-one and onto (bijective).

3. H is transitive onto function: H is transitive iff whenever aHb and bHc then aHc. For H to be both transitive and onto, H must be the identity function.

FINITE AND INFINITE SETS

🔑 Definition — Finite set: A set is called finite if, and only if, it is the empty set or there is a one-to-one correspondence from {1,2,3,...,n} to it, where n is a positive integer.

🔑 Definition — Infinite set: A non-empty set that cannot be put into one-to-one correspondence with {1,2,3,...,n} for any positive integer n is called infinite.

🔑 Definition — Cardinality: Let A and B be any sets. A has the same cardinality as B if, and only if, there is a one-to-one correspondence from A to B. Cardinality means "the total number of elements in a set."

🔑 Definition — Countable set: A set is countably infinite if, and only if, it has the same cardinality as the set of positive integers Z⁺. A set is called countable if, and only if, it is finite or countably infinite. A set that is not countable is called uncountable.

📌 Example: The set Z of all integers is countable.

Proof: Define f: Z⁺ → Z by:

• f(n) = n/2 if n is an even positive integer
• f(n) = -(n-1)/2 if n is an odd positive integer

f is one-to-one and onto, so Z is countably infinite.

📌 Exercise: Show that 2Z (set of all even integers) is countable.

Proof: Define h: Z → 2Z by h(n) = 2n for all n ∈ Z. h is one-to-one (if h(n₁) = h(n₂) then 2n₁ = 2n₂ so n₁ = n₂) and onto (every even integer 2n is the image of n). Since Z is countable, 2Z is countable.

IMAGE OF A SET

🔑 Definition — Image of a set: Let f: X → Y be a function and A ⊆ X. The image of A under f is denoted and defined as: f(A) = {y ∈ Y | y = f(x) for some x in A}.

📌 Example: Let f: X → Y with X = {1,2,3,4}, Y = {a,b,c}, and f(1)=a, f(2)=b, f(3)=b, f(4)=c. For A = {1,2}, f(A) = {b}. For B = {2,3}, f(B) = {b,c}.

INVERSE IMAGE OF A SET

🔑 Definition — Inverse image of a set: Let f: X → Y be a function and C ⊆ Y. The inverse image of C under f is denoted and defined as: f⁻¹(C) = {x ∈ X | f(x) ∈ C}.

📌 Example: Using the same function as above: For C = {a}, f⁻¹(C) = {1,2}. For D = {b,c}, f⁻¹(D) = {3,4}. For E = {d}, f⁻¹(E) = ∅.

SOME RESULTS ON IMAGES AND INVERSE IMAGES

Let f: X → Y be a function. Let A and B be subsets of X, and C and D be subsets of Y.

1. If A ⊆ B then f(A) ⊆ f(B)
2. f(A ∪ B) = f(A) ∪ f(B)
3. f(A ∩ B) ⊆ f(A) ∩ f(B)
4. f(A-B) ⊇ f(A) - f(B)
5. If C ⊆ D, then f⁻¹(C) ⊆ f⁻¹(D)
6. f⁻¹(C ∪ D) = f⁻¹(C) ∪ f⁻¹(D)
7. f⁻¹(C ∩ D) = f⁻¹(C) ∩ f⁻¹(D)
8. f⁻¹(C - D) = f⁻¹(C) - f⁻¹(D)

⭐ Key Takeaways

The composition of functions preserves one-to-one and onto properties — if both f and g are one-to-one, gof is one-to-one; if both are onto, gof is onto. Composition is associative, and for bijective functions, the inverse of a composition equals the composition of inverses in reverse order: (gof)⁻¹ = f⁻¹ o g⁻¹. Operations on real-valued functions (sum, difference, product, quotient, scalar multiplication) are defined pointwise, but sums of one-to-one or onto functions do not necessarily preserve those properties (counterexamples with f(x)=x and g(x)=-x). A set is countable if it is finite or has the same cardinality as Z⁺, and the image/inverse image of sets under functions obey important subset relations and distributive laws for union, intersection, and difference.

🧠 Quick Revision Questions

1. Prove that if f: X → Y and g: Y → Z are both one-to-one, then their composition gof is one-to-one.

2. Show by counterexample that the sum of two one-to-one functions from R to R is not necessarily one-to-one.

3. State and prove the formula for the inverse of the composition of two bijective functions.

4. Define the characteristic function of a subset A of S, and prove that χₐₙₐ = χₐ · χₐ.

5. Prove that the set of all even integers 2Z is countable by constructing an explicit bijection.

📘 Lecture 19 — Sequence

📖 Overview: This lecture introduces the concept of a sequence as an ordered list of elements, providing formal definitions, notation, and methods for finding terms using explicit formulas. It covers two important types of sequences—arithmetic and geometric—along with their general terms, examples, and applications, including relevance to computer programming.

🗂️ Topics Covered

The lecture begins with the informal and formal definition of a sequence, followed by notation and explicit formulas for finding terms. It includes multiple examples and exercises for computing terms and finding explicit formulas from given sequences. The second half covers arithmetic sequences (definition, common difference, general term) and geometric sequences (definition, common ratio, general term), each with solved examples and exercises. The lecture concludes with a brief discussion of sequences as one-dimensional arrays in computer programming.

📝 Lecture Summary

SEQUENCE:

A sequence is just a list of elements usually written in a row.

EXAMPLES:

1. 1, 2, 3, 4, 5, ...
2. 4, 8, 12, 16, 20,...
3. 2, 4, 8, 16, 32, ...
4. 1, 1/2, 1/3, 1/4, 1/5, ...
5. 1, 4, 9, 16, 25, ...
6. 1, -1, 1, -1, 1, -1, ... NOTE: The symbol “...” is called ellipsis, and reads “and so forth”.

FORMAL DEFINITION: A sequence is a function whose domain is the set of integers greater than or equal to a particular integer n₀. Usually this set is the set of Natural numbers {1, 2, 3, ...} or the set of whole numbers {0, 1, 2, 3, ...}.

NOTATION: We use the notation aₙ to denote the image of the integer n, and call it a term of the sequence. Thus a₁, a₂, a₃, a₄ ..., aₙ, ... represent the terms of a sequence defined on the set of natural numbers N. A sequence is described by listing the terms in order of increasing subscripts.

FINDING TERMS OF A SEQUENCE GIVEN BY AN EXPLICIT FORMULA:

An explicit formula or general formula for a sequence is a rule that shows how the values of aₖ depends on k.

🔑 Definition — Explicit Formula: A rule that shows how the value of a term aₖ depends on k.

EXAMPLE: Define a sequence a₁, a₂, a₃, ... by the explicit formula aₖ = k/(k+1) for all integers k ≥ 1. The first four terms are: a₁ = 1/(1+1) = 1/2 a₂ = 2/(2+1) = 2/3 a₃ = 3/(3+1) = 3/4 a₄ = 4/(4+1) = 4/5

EXAMPLE: Write the first four terms of the sequence defined by the formula bⱼ = 1 + 2ʲ, for all integers j ≥ 0. b₀ = 1 + 2⁰ = 1 + 1 = 2 b₁ = 1 + 2¹ = 1 + 2 = 3 b₂ = 1 + 2² = 1 + 4 = 5 b₃ = 1 + 2³ = 1 + 8 = 9 REMARK: The formula bⱼ = 1 + 2ʲ , for all integers j ≥ 0 defines an infinite sequence having infinite number of values.

EXERCISE: Compute the first six terms of the sequence defined by the formula Cₙ = 1+ (-1)ⁿ for all integers n ≥ 0. C₀ = 1 + (-1)⁰ = 1 + 1 = 2 C₁ = 1 + (-1)¹ = 1 + (-1) = 0 C₂ = 1 + (-1)² = 1 + 1 = 2 C₃ = 1 + (-1)³ = 1 + (-1) = 0 C₄ = 1 + (-1)⁴ = 1 + 1 = 2 C₅ = 1 + (-1)⁵ = 1 + (-1) = 0 REMARK:

1. If n is even, then Cₙ = 2 and if n is odd, then Cₙ = 0. Hence, the sequence oscillates endlessly between 2 and 0.
2. An infinite sequence may have only a finite number of values.

EXAMPLE: Write the first four terms of the sequence defined by Cₙ = ((-1)ⁿ n)/(n+1) for all integers n ≥ 1. C₁ = ((-1)¹(1))/(1+1) = -1/2 C₂ = ((-1)²(2))/(2+1) = 2/3 C₃ = ((-1)³(3))/(3+1) = -3/4 C₄ = ((-1)⁴(4))/(4+1) = 4/5 🔑 Definition — Alternating sequence: A sequence whose terms alternate in sign.

EXERCISE: Find explicit formulas for sequences with the initial terms given:

1. 0, 1, -2, 3, -4, 5, ... SOLUTION: aₙ = (-1)ⁿ⁺¹ n for all integers n ≥ 0

2. 1 - 1/2, 1/2 - 1/3, 1/3 - 1/4, 1/4 - 1/5, ... SOLUTION: bₖ = 1/k - 1/(k+1) for all integers k ≥ 1

3. 2, 6, 12, 20, 30, 42, 56, ... SOLUTION: Cₙ = n (n + 1) for all integers n ≥ 1

4. 1/4, 2/9, 3/16, 4/25, 5/36, 6/49, ... SOLUTION: dᵢ = i/(i+1)² for all integers i ≥ 1 OR dⱼ = (j+1)/(j+2)² for all integers j ≥ 0

ARITHMETIC SEQUENCE:

🔑 Definition — Arithmetic sequence: A sequence in which every term after the first is obtained from the preceding term by adding a constant number. Also called arithmetic progression (A.P.). The constant number is called the common difference, commonly denoted by “d”. 📌 Example: 5, 9, 13, 17, ... (common difference = 4) 📌 Example: 0, -5, -10, -15, ... (common difference = -5) 📌 Example: x + a, x + 3a, x + 5a, ... (common difference = 2a)

GENERAL TERM OF AN ARITHMETIC SEQUENCE: Let a be the first term and d be the common difference of an arithmetic sequence. Then the sequence is a, a+d, a+2d, a+3d, ... 📐 Formula: aₙ = a + (n - 1)d for all integers n ≥ 1

EXAMPLE: Find the 20th term of the arithmetic sequence 3, 9, 15, 21, ... Here a = 3, d = 9 - 3 = 6, n = 20. a₂₀ = 3 + (20 - 1)6 = 3 + 114 = 117

EXAMPLE: Which term of the arithmetic sequence 4, 1, -2, ..., is -77? Here a = 4, d = 1 - 4 = -3, aₙ = -77. -77 = 4 + (n - 1)(-3) -81 = (n - 1)(-3) n - 1 = 27 n = 28 Hence -77 is the 28th term.

EXERCISE: Find the 36th term of the arithmetic sequence whose 3rd term is 7 and 8th term is 17. Let a be the first term and d the common difference. a₃ = a + 2d = 7 ...(1) a₈ = a + 7d = 17 ...(2) Subtracting (1) from (2): 10 = 5d ⇒ d = 2 Substituting in (1): 7 = a + 2(2) ⇒ a = 3 Thus aₙ = 3 + (n - 1)2 a₃₆ = 3 + (36 - 1)2 = 3 + 70 = 73

GEOMETRIC SEQUENCE:

🔑 Definition — Geometric sequence: A sequence in which every term after the first is obtained from the preceding term by multiplying it with a constant number. Also called geometric progression (G.P.). The constant number is called the common ratio, commonly denoted by “r”. 📌 Example: 1, 2, 4, 8, 16, ... (common ratio = 2) 📌 Example: 3, -3/2, 3/4, -3/8, ... (common ratio = -1/2) 📌 Example: 0.1, 0.01, 0.001, 0.0001, ... (common ratio = 0.1)

GENERAL TERM OF A GEOMETRIC SEQUENCE: Let a be the first term and r be the common ratio of a geometric sequence. Then the sequence is a, ar, ar², ar³, ... 📐 Formula: aₙ = arⁿ⁻¹ for all integers n ≥ 1

EXAMPLE: Find the 8th term of the geometric sequence 4, 12, 36, 108, ... Here a = 4, r = 12/4 = 3, n = 8. a₈ = 4(3)⁸⁻¹ = 4(3⁷) = 4(2187) = 8748

EXAMPLE: Which term of the geometric sequence is 1/8 if the first term is 4 and common ratio 1/2? Given a = 4, r = 1/2, aₙ = 1/8. 1/8 = 4(1/2)ⁿ⁻¹ 1/32 = (1/2)ⁿ⁻¹ (1/2)⁵ = (1/2)ⁿ⁻¹ n - 1 = 5 n = 6 Hence 1/8 is the 6th term.

EXERCISE: Write the geometric sequence with positive terms whose second term is 9 and fourth term is 1. Let a be the first term and r the common ratio. a₂ = ar = 9 ...(1) a₄ = ar³ = 1 ...(2) Dividing (2) by (1): 1/9 = r² ⇒ r = 1/3 (rejecting r = -1/3 as terms are positive) Substituting in (1): 9 = a(1/3) ⇒ a = 27 Hence the geometric sequence is 27, 9, 3, 1, 1/3, 1/9, ...

SEQUENCES IN COMPUTER PROGRAMMING:

An important data type in computer programming consists of finite sequences known as one-dimensional arrays; a single variable in which a sequence of variables may be stored. EXAMPLE: The names of k students in a class may be represented by an array of k elements “name” as: name[0], name[1], name[2], ..., name[k-1]

⭐ Key Takeaways

A sequence is a function from integers (usually natural numbers) to real numbers, with each term denoted by aₙ. You must be able to compute terms from an explicit formula and find explicit formulas from given terms, recognizing patterns for alternating, arithmetic, and geometric sequences. For arithmetic sequences, the general term formula aₙ = a + (n-1)d allows finding any term when the first term and common difference are known. For geometric sequences, the formula aₙ = arⁿ⁻¹ enables finding any term using the first term and common ratio. The ability to solve for unknown terms like common difference, common ratio, or term number using these formulas is essential for problem-solving.

🧠 Quick Revision Questions

1. What is the formal definition of a sequence?
2. Write the first five terms of the sequence defined by aₙ = (-1)ⁿ/(n+1) for n ≥ 0.
3. Find the 15th term of the arithmetic sequence: 7, 11, 15, 19, ...
4. If the 2nd term of a geometric sequence is 6 and the 5th term is 162, find the first term and common ratio.
5. What is the relationship between sequences in mathematics and one-dimensional arrays in programming?

📘 Lecture 20 — Series

📖 Overview: This lecture introduces the concept of a series as the sum of terms of a sequence and covers the summation notation (sigma notation) used to represent series compactly. It explores the properties of summations, and provides detailed formulas and methods for computing the sums of arithmetic series and geometric series, including infinite geometric series, which are fundamental for many applications in mathematics and science.

🗂️ Topics Covered

The lecture begins with the definition of a series and summation notation, illustrating how to compute summations and convert between expanded form and summation notation. It then covers transforming sums by a change of variable and the basic properties of summations. The remainder of the lecture is dedicated to deriving and applying the sum formulas for arithmetic series and geometric series, including the sum of an infinite geometric series, and concludes with important sum formulas for powers of natural numbers and their application in summing more complex series.

📝 Lecture Summary

SERIES

The sum of the terms of a sequence forms a series. If (a_1, a_2, a_3, ...) represent a sequence of numbers, then the corresponding series is (a_1 + a_2 + a_3 + ... ).

SUMMATION NOTATION

The capital Greek letter sigma ((\Sigma)) is used to concisely represent a sum. The expression (\sum_{k=1}^n a_k) is a shorthand notation for the sum (a_1 + a_2 + a_3 + ... + a_n). More generally, for integers (m \le n), the summation from (k=m) to (n) of (a_k) is (\sum_{k=m}^n a_k = a_m + a_{m+1} + a_{m+2} + \cdots + a_n). Here, (k) is called the index of the summation, (m) is the lower limit, and (n) is the upper limit.

🔑 Definition — Index: The variable (k) in a summation notation is called the index of summation; it is a dummy variable that can be replaced by any other symbol (e.g., (i) or (j)) without changing the sum.

📌 Example: Let (a_0 = 2, a_1 = 3, a_2 = -2, a_3 = 1, a_4 = 0). (a) (\sum_{i=0}^4 a_i = a_0 + a_1 + a_2 + a_3 + a_4 = 2 + 3 + (-2) + 1 + 0 = 4) (b) (\sum_{j=0}^2 a_{2j} = a_0 + a_2 + a_4 = 2 + (-2) + 0 = 0) (c) (\sum_{k=1}^1 a_k = a_1 = 3)

EXERCISE (Computing Summations)

Compute the summations.

1. (\sum_{i=1}^3 (2i - 1) = [2(1)-1] + [2(2)-1] + [2(3)-1] = 1 + 3 + 5 = 9)
2. (\sum_{k=-1}^1 (k^3 + 2) = [(-1)^3 + 2] + [0^3 + 2] + [1^3 + 2] = [1] + [2] + [3] = 6)

SUMMATION NOTATION TO EXPANDED FORM

Write the summation (\sum_{i=0}^n \frac{(-1)^i}{i+1}) in expanded form. 📌 Example: (\sum_{i=0}^n \frac{(-1)^i}{i+1} = \frac{(-1)^0}{0+1} + \frac{(-1)^1}{1+1} + \frac{(-1)^2}{2+1} + \frac{(-1)^3}{3+1} + \cdots + \frac{(-1)^n}{n+1} = 1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \cdots + \frac{(-1)^n}{n+1})

EXPANDED FORM TO SUMMATION NOTATION

Write ( \frac{1}{n} + \frac{2}{n+1} + \frac{3}{n+2} + \cdots + \frac{n+1}{2n} ) using summation notation. 📌 Example: The numerators form an arithmetic sequence (1, 2, 3, ..., n+1), so the k-th term numerator is (k). The denominators form an arithmetic sequence (n, n+1, n+2, ..., 2n), so the k-th term denominator is (n + (k-1) = k + n - 1). Therefore, the k-th term of the series is (\frac{k}{(n-1) + k}). The series is (\sum_{k=1}^{n+1} \frac{k}{(n-1) + k}). A change of index ((k \rightarrow j+1)) yields (\sum_{j=0}^n \frac{j+1}{n+j}).

TRANSFORMING A SUM BY A CHANGE OF VARIABLE

The index of a summation is a dummy variable. Therefore, (\sum_{k=1}^3 k^2 = \sum_{i=1}^3 i^2). Summations can be transformed by substituting a new variable for the index. 📌 Example: Transform (\sum_{i=1}^{n-1} \frac{i}{(n-i)^2}) by making the change of variable (j = i - 1). When (i=1, j=0); when (i=n-1, j=n-2). Thus, (\sum_{i=1}^{n-1} \frac{i}{(n-i)^2} = \sum_{j=0}^{n-2} \frac{j+1}{[n-(j+1)]^2} = \sum_{j=0}^{n-2} \frac{j+1}{(n-j-1)^2}).

PROPERTIES OF SUMMATIONS

The summation operator is linear and has several important properties.

1. Sum of sums: (\sum_{k=m}^n (a_k + b_k) = \sum_{k=m}^n a_k + \sum_{k=m}^n b_k)
2. Constant multiple: (\sum_{k=m}^n c a_k = c\sum_{k=m}^n a_k), where (c) is a constant.
3. Shifting index (add i): (\sum_{k=a-i}^{b-i} (k + i) = \sum_{k=a}^{b} k)
4. Shifting index (subtract i): (\sum_{k=a+i}^{b+i} (k - i) = \sum_{k=a}^{b} k)
5. Sum of a constant: (\sum_{k=1}^n c = c + c + \cdots + c = nc)

📌 Example: Simplify (\sum_{k=1}^n 3(2k-3) + \sum_{k=1}^n (4-5k)). Using properties 1 and 2, this can be combined into a single summation: (\sum_{k=1}^n [3(2k-3) + (4-5k)] = \sum_{k=1}^n (k - 5) = \sum_{k=1}^n k - \sum_{k=1}^n 5 = \sum_{k=1}^n k - 5n).

ARITHMETIC SERIES

The sum of the terms of an arithmetic sequence forms an arithmetic series (A.S.). In general, if (a) is the first term and (d) is the common difference, the series is (a + (a+d) + (a+2d) + ... ). The (n)th term is (a_n = a + (n-1)d). The sum of the first (n) terms, (S_n), is given by formulas derived by adding the series to itself in reverse order. [ S_n = \frac{n}{2}(a + a_n) = \frac{n}{2}(a + l) ] where (l = a_n) is the last term. [ S_n = \frac{n}{2}[2a + (n-1)d] ]

📌 Example (Sum of first n natural numbers): Find (1 + 2 + 3 + ... + n). This is an A.S. with (a=1, d=1). (S_n = \frac{n}{2}[2(1) + (n-1)1] = \frac{n}{2}(n+1) = \frac{n(n+1)}{2}).

📌 Example (Sum of two-digit odd integers not divisible by 5): Find the sum of two-digit positive integers which are neither divisible by 5 nor by 2. The integers are 11, 13, 17, 19, ..., 97, 99. Grouping in sets of 4 yields a new A.S.: 60, 100, 140, ... , 380. In this A.S., (a=60, d=40, l=380). Find (n): (380 = 60 + (n-1)40 \Rightarrow n=9). (S_9 = \frac{9}{2}(60 + 380) = 1980).

GEOMETRIC SERIES

The sum of the terms of a geometric sequence forms a geometric series (G.S.). In general, if (a) is the first term and (r) is the common ratio, the series is (a + ar + ar^2 + ar^3 + ... ). The (n)th term is (a_n = ar^{n-1}). The sum of the first (n) terms, (S_n), is found by multiplying by (r) and subtracting. [ S_n = a + ar + ... + ar^{n-1}, \quad rS_n = ar + ar^2 + ... + ar^n ] [ S_n - rS_n = a - ar^n \Rightarrow S_n(1-r) = a(1-r^n) ] [ S_n = \frac{a(1-r^n)}{1-r}, \quad r \neq 1 ]

📎 Formula: (S_n = \frac{a(1-r^n)}{1-r}) for the sum of the first (n) terms of a geometric series, where (r \neq 1).

📌 Example: Find the sum of 10 terms of the G.S. (6 - 2 + \frac{2}{3} - \frac{2}{9} + \cdots). (a=6, r = \frac{-2}{6} = -\frac{1}{3}, n=10). (S_{10} = \frac{6(1-(-1/3)^{10})}{1-(-1/3)} = \frac{6(1-1/3^{10})}{1+1/3} = \frac{6(1+1/3^{10})}{4/3}).

INFINITE GEOMETRIC SERIES

For an infinite geometric series (a + ar + ar^2 + ...), if (|r| < 1), the sum of the first (n) terms approaches a finite limit as (n \to \infty). The series is convergent, and its sum (S) is: [ S = \lim_{n \to \infty} S_n = \lim_{n \to \infty} \frac{a(1-r^n)}{1-r} = \frac{a}{1-r} ] If (|r| \ge 1), the sum increases indefinitely and the series is divergent.

📌 Example: Find the sum of the infinite G.S. (\frac{9}{4} + \frac{3}{2} + 1 + \frac{2}{3} + \cdots). (a = \frac{9}{4}, r = \frac{3/2}{9/4} = \frac{2}{3}). Since (|r| < 1), the sum is (S = \frac{a}{1-r} = \frac{9/4}{1-2/3} = \frac{9/4}{1/3} = \frac{27}{4}).

📌 Example: Find a common fraction for the repeating decimal 0.81818181... = (0.\overline{81}). Write as (0.81 + 0.0081 + 0.000081 + ...), an infinite G.S. with (a=0.81, r=0.01). Sum (= \frac{a}{1-r} = \frac{0.81}{1-0.01} = \frac{0.81}{0.99} = \frac{81}{99} = \frac{9}{11}).

IMPORTANT SUMS

Several formulas for sums of powers of natural numbers are provided.

1. (\sum_{k=1}^n k = 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2})
2. (\sum_{k=1}^n k^2 = 1^2 + 2^2 + 3^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6})
3. (\sum_{k=1}^n k^3 = 1^3 + 2^3 + 3^3 + \cdots + n^3 = \left[\frac{n(n+1)}{2}\right]^2)

EXERCISE (Summing a Combined Series)

Sum to (n) terms the series (1 \cdot 5 + 5 \cdot 11 + 9 \cdot 17 + ... ). 📌 Example: Find the (k)th term: (T_k = [1 + (k-1)4] \cdot [5 + (k-1)6] = (4k-3)(6k-1) = 24k^2 - 22k + 3). The total sum is (S_n = \sum_{k=1}^n (24k^2 - 22k + 3)). Using the summation properties and the important sums: (S_n = 24\sum_{k=1}^n k^2 - 22\sum_{k=1}^n k + \sum_{k=1}^n 3) (S_n = 24\left[\frac{n(n+1)(2n+1)}{6}\right] - 22\left[\frac{n(n+1)}{2}\right] + 3n) (S_n = n[4(n+1)(2n+1) - 11(n+1) + 3]) (S_n = n[(8n^2 + 12n + 4) - (11n + 11) + 3]) (S_n = n(8n^2 + n - 4))

⭐ Key Takeaways

For the exam, you must be able to fluently translate between summation notation and expanded form. You must know the formulas for the sum of an arithmetic series, (S_n = n/2 [2a + (n-1)d]), and a geometric series, (S_n = a(1-r^n)/(1-r)), and how to identify the parameters (a, d, r), and (n). The formula (S = a/(1-r)) for the sum of a convergent infinite geometric series (where (|r| < 1)) is essential. Additionally, you should memorize and be able to apply the three important sums for (\sum k), (\sum k^2), and (\sum k^3), and use the linear properties of summation to break down and sum more complex series by finding their (k)th term.

🧠 Quick Revision Questions

1. Write the summation (\sum_{k=0}^3 (k^2 - 2)) in expanded form and compute its value.
2. Convert the series (1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \cdots) (n terms) into summation notation.
3. Find the sum of the first 15 terms of the arithmetic series where the first term is 5 and the common difference is 4.
4. Determine if the infinite geometric series (4 + 2 + 1 + 0.5 + \cdots) is convergent or divergent. If convergent, find its sum.
5. Sum to n terms the series (1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \cdots + n \cdot (n+1)).

📘 Lecture 21 — Recursion I

📖 Overview: This lecture introduces the fundamental concept of recursion, where an object is defined in terms of smaller versions of itself. It explains the structure of recursive definitions (base and recursion), demonstrates how to evaluate recursively defined functions, and explores key applications including the factorial function, Fibonacci sequence, and the Tower of Hanoi puzzle. Understanding recursion is critical for computer science as it provides elegant solutions to many algorithmic problems.

🗂️ Topics Covered

The lecture covers the definition and structure of recursion with examples like odd positive integers, evaluation of recursively defined functions using base values and recurrence relations, the factorial function defined recursively, sum of first n integers, a quotient-finding recursive function, the Fibonacci sequence, recurrence relations with initial conditions, verifying sequences satisfy recurrence relations, and the Tower of Hanoi puzzle as a classic recursive problem.

📝 Lecture Summary

Recursion

First, instead of giving the definition of Recursion, we give you an example. You already know the Set of Odd numbers. Here we give the new definition of the same set that is the set of Odd numbers.

Definition for odd positive integers may be given as:

BASE: 1 is an odd positive integer.

RECURSION: If k is an odd positive integer, then k + 2 is an odd positive integer.

Now, 1 is an odd positive integer by the definition base. With k = 1, 1 + 2 = 3, so 3 is an odd positive integer. With k = 3, 3 + 2 = 5, so 5 is an odd positive integer and so, 7, 9, 11, ... are odd positive integers.

REMARK: Recursive definitions can be used in a "generative" manner.

RECURSION: The process of defining an object in terms of smaller versions of itself is called recursion. A recursive definition has two parts:

1. BASE: An initial simple definition which cannot be expressed in terms of smaller versions of itself.
2. RECURSION: The part of definition which can be expressed in terms of smaller versions of itself.

Recursively Defined Functions

A function is said to be recursively defined if the function refers to itself such that:

1. There are certain arguments, called base values, for which the function does not refer to itself.
2. Each time the function does refer to itself, the argument of the function must be closer to a base value.

EXAMPLE: Suppose that f is defined recursively by f(0) = 3 and f(n + 1) = 2 f(n) + 3. Find f(1), f(2), f(3) and f(4).

SOLUTION: From the recursive definition it follows that f(1) = 2 f(0) + 3 = 2(3) + 3 = 6 + 3 = 9. In evaluating f(1) we use the formula given in the example and we note that it involves f(0) and we are also given the value of that which we use to find out the functional value at 1. Similarly we will use the preceding value in evaluating the next values of the functions as we did below:

• f(2) = 2 f(1) + 3 = 2(9) + 3 = 18 + 3 = 21
• f(3) = 2 f(2) + 3 = 2(21) + 3 = 42 + 3 = 45
• f(4) = 2 f(3) + 3 = 2(45) + 3 = 90 + 3 = 93

EXERCISE: Find f(2), f(3), and f(4) if f is defined recursively by f(0) = -1, f(1)=2 and for n = 1, 2, 3, ... f(n+1) = f(n) + 3 f(n - 1).

SOLUTION: From the recursive definition it follows that:

• f(2) = f(1) + 3 f(1-1) = f(1) + 3 f(0) = 2 + 3(-1) = -1
• f(3) = f(2) + 3 f(2-1) = f(2) + 3 f(1) = (-1) + 3(2) = 5
• f(4) = f(3) + 3 f(3-1) = f(2) + 3 f(2) = 5 + 3(-1) = 2

The Factorial of a Positive Integer

For each positive integer n, the factorial of n denoted n! is defined to be the product of all the integers from 1 to n: n! = n·(n-1)·(n-2)·...·3·2·1. Zero factorial is defined to be 1: 0! = 1.

EXAMPLE: 0! = 1, 1! = 1, 2! = 2·1 = 2, 3! = 3·2·1 = 6, 4! = 4·3·2·1 = 24, 5! = 5·4·3·2·1 = 120, 6! = 6·5·4·3·2·1 = 720, 7! = 7·6·5·4·3·2·1 = 5040.

REMARK: 5! = 5·4·3·2·1 = 5·(4·3·2·1) = 5·4!. In general, n! = n(n-1)! for each positive integer n.

The Factorial Function Defined Recursively

We can define the factorial function F(n) = n! recursively by specifying the initial value of this function, namely, F(0) = 1, and giving a rule for finding F(n) from F(n-1). {(n! = n(n-1)!)} Thus, the recursive definition of factorial function F(n) is:

1. F(0) = 1
2. F(n) = n F(n-1)

EXERCISE: Let S be the function such that S(n) is the sum of the first n positive integers. Give a recursive definition of S(n).

SOLUTION: The initial value of this function may be specified as S(0) = 0. Since S(n) = n + (n-1) + (n-2) + ... + 3 + 2 + 1 = n + [(n-1) + (n-2) + ... + 3 + 2 + 1] = n + S(n-1), which defines the recursive step. Accordingly S may be defined as:

1. S(0) = 0
2. S(n) = n + S(n-1) for n ≥ 1

EXERCISE: Let a and b denote positive integers. Suppose a function Q is defined recursively as follows: Q(a, b) = {0 if a < b; Q(a-b, b) + 1 if b ≤ a}. Find the value of Q(2,3) and Q(14,3). What does this function do? Find Q(3355, 7).

SOLUTION: (a) Q(2,3) = 0 since 2 < 3. For Q(14,3): Q(14,3) = Q(11,3) + 1 = [Q(8,3) + 1] + 1 = Q(8,3) + 2 = [Q(5,3) + 1] + 2 = Q(5,3) + 3 = [Q(2,3) + 1] + 3 = Q(2,3) + 4 = 0 + 4 = 4.

(b) Each time b is subtracted from a, the value of Q is increased by 1. Hence Q(a,b) finds the integer quotient when a is divided by b. Thus Q(3355, 7) = 479.

🔑 Definition — Integer Quotient: The number of times one integer (b) can be subtracted from another (a) before the remainder becomes less than b; equivalently, the result of integer division a ÷ b.

The Fibonacci Sequence

The Fibonacci sequence is defined as follows:

• F₀ = 1, F₁ = 1
• Fₖ = Fₖ₋₁ + Fₖ₋₂ for all integers k ≥ 2

F₂ = F₁ + F₀ = 1 + 1 = 2; F₃ = F₂ + F₁ = 2 + 1 = 3; F₄ = F₃ + F₂ = 3 + 2 = 5; F₅ = F₄ + F₃ = 5 + 3 = 8; and so on.

💡 Why this matters: The Fibonacci sequence appears in nature, art, and algorithm analysis, making it a fundamental recursive pattern.

Recurrence Relation

A recurrence relation for a sequence a₀, a₁, a₂, ..., is a formula that relates each term aₖ to certain of its predecessors aₖ₋₁, aₖ₋₂, ..., aₖ₋ᵢ, where i is a fixed integer and k is any integer greater than or equal to i. The initial conditions for such a recurrence relation specify the values of a₀, a₁, a₂, ..., aᵢ₋₁.

EXERCISE: Find the first four terms of the following recursively defined sequence: b₁ = 2; bₖ = bₖ₋₁ + 2·k, for all integers k ≥ 2.

SOLUTION: b₁ = 2 (given in base step); b₂ = b₁ + 2·2 = 2 + 4 = 6; b₃ = b₂ + 2·3 = 6 + 6 = 12; b₄ = b₃ + 2·4 = 12 + 8 = 20.

EXERCISE: Find the first five terms of the following recursively defined sequence: t₀ = -1, t₁ = 1; tₖ = tₖ₋₁ + 2·tₖ₋₂, for all integers k ≥ 2.

SOLUTION: t₀ = -1, t₁ = 1 (given in base step); t₂ = t₁ + 2·t₀ = 1 + 2·(-1) = 1 - 2 = -1; t₃ = t₂ + 2·t₁ = -1 + 2·1 = -1 + 2 = 1; t₄ = t₃ + 2·t₂ = 1 + 2·(-1) = 1 - 2 = -1.

EXERCISE: Define a sequence b₀, b₁, b₂, ... by the formula bₙ = 5ⁿ, for all integers n ≥ 0. Show that this sequence satisfies the recurrence relation bₖ = 5bₖ₋₁, for all integers k ≥ 1.

SOLUTION: The sequence is given by the formula bₙ = 5ⁿ. Substituting k for n we get bₖ = 5ᵏ (1). Substituting k-1 for n we get bₖ₋₁ = 5ᵏ⁻¹ (2). Multiplying both sides of (2) by 5 we obtain 5·bₖ₋₁ = 5·5ᵏ⁻¹ = 5ᵏ = bₖ using (1). Hence bₖ = 5bₖ₋₁ as required.

EXERCISE: Show that the sequence 0, 1, 3, 7, ..., 2ⁿ - 1, ..., for n ≥ 0, satisfies the recurrence relation dₖ = 3dₖ₋₁ - 2dₖ₋₂, for all integers k ≥ 2.

SOLUTION: The sequence is given by the formula dₙ = 2ⁿ - 1 for n ≥ 0. Substituting k-1 for n we get dₖ₋₁ = 2ᵏ⁻¹ - 1. Substituting k-2 for n we get dₖ₋₂ = 2ᵏ⁻² - 1. We want to prove that dₖ = 3dₖ₋₁ - 2dₖ₋₂. R.H.S. = 3(2ᵏ⁻¹ - 1) - 2(2ᵏ⁻² - 1) = 3·2ᵏ⁻¹ - 3 - 2·2ᵏ⁻² + 2 = 3·2ᵏ⁻¹ - 2ᵏ⁻¹ - 1 = (3-1)·2ᵏ⁻¹ - 1 = 2·2ᵏ⁻¹ - 1 = 2ᵏ - 1 = dₖ = L.H.S.

The Tower of Hanoi

The puzzle was invented by a French Mathematician Edouard Lucas in 1883. It is well known to students of Computer Science since it appears in virtually any introductory text on data structures or algorithms. There are three poles on first of which are stacked a number of disks that decrease in size as they rise from the base. The goal is to transfer all the disks one by one from the first pole to one of the others, but they must never place a larger disk on top of a smaller one.

Let mₙ be the minimum number of moves needed to move a tower of n disks from one pole to another. Then mₙ can be obtained recursively as follows:

• m₁ = 1
• mₖ = 2mₖ₋₁ + 1

m₂ = 2·m₁ + 1 = 2·1 + 1 = 3; m₃ = 2·m₂ + 1 = 2·3 + 1 = 7; m₄ = 2·m₃ + 1 = 2·7 + 1 = 15; m₅ = 2·m₄ + 1 = 2·15 + 1 = 31; m₆ = 2·m₅ + 1 = 2·31 + 1 = 65.

Note that mₙ = 2ⁿ - 1. For 64 disks, m₆₄ = 2⁶⁴ - 1 = 18,446,744,073,709,551,615 moves = 1.844 × 10¹⁹ moves.

Use of Recursion

At first recursion may seem hard or impossible, may be magical at best. However, recursion often provides elegant, short algorithmic solutions to many problems in computer science and mathematics.

Examples where recursion is often used:

• math functions
• number sequences
• data structure definitions
• data structure manipulations
• language definitions

📐 Formula: Tower of Hanoi — mₙ = 2ⁿ - 1 → The minimum number of moves required to transfer n disks from one pole to another, following the rule that no larger disk may ever be placed on top of a smaller disk.

📌 Example: For 5 disks, m₅ = 2⁵ - 1 = 32 - 1 = 31 moves.

⭐ Key Takeaways

A recursive definition must always have a base case (simple definition that cannot be expressed in smaller terms) and a recursive part (definition in terms of smaller versions of itself). To evaluate recursively defined functions, start from the given base values and work forward, each time substituting previous results into the recurrence formula. The factorial function is defined recursively as F(0)=1 and F(n)=nF(n-1), and the Fibonacci sequence requires two base values (F₀=1, F₁=1) with the recurrence Fₖ=Fₖ₋₁+Fₖ₋₂. A recurrence relation relates each term to its predecessors, and initial conditions provide the starting values needed to generate the sequence. The Tower of Hanoi puzzle demonstrates that the minimum number of moves for n disks follows the recurrence mₖ=2mₖ₋₁+1 with closed form mₙ=2ⁿ-1.

🧠 Quick Revision Questions

1. What are the two essential parts of any recursive definition? Provide an example from the lecture.
2. If f is defined recursively by f(0)=3 and f(n+1)=2f(n)+3, what is f(3)?
3. Write the recursive definition of the factorial function and use it to compute 4!.
4. What is the recurrence relation for the Fibonacci sequence? List the first 6 terms starting from F₀.
5. For the Tower of Hanoi puzzle with 6 disks, what is the minimum number of moves required? What is the closed-form formula for mₙ?

📘 Lecture 22 — Recursion II

📖 Overview: This lecture continues the study of recursive definitions by applying them to various mathematical structures including Boolean expressions, strings, parentheses, and arithmetic expressions. The key insight is that recursive definitions provide a systematic way to build complex objects from simpler ones using base cases and recursion rules, which is essential for understanding formal languages and computational structures.

🗂️ Topics Covered

This lecture formally defines recursive definitions with BASE, RECURSION, and RESTRICTION rules, then applies this framework to Boolean expressions, strings over an alphabet, parenthesis structures, arithmetic expressions, and recursive definitions of summation, union, and intersection of sets. Each topic includes derivations showing how specific examples can be constructed using the recursive rules.

📝 Lecture Summary

Recursive Definition Structure

A recursive definition for a set consists of three rules: I. BASE — a statement that certain objects belong to the set. II. RECURSION — a collection of rules indicating how to form new set objects from those already known to be in the set. III. RESTRICTION — a statement that no objects belong to the set other than those coming from I and II.

EXERCISE: Let S be a set defined recursively by I. BASE: 5 ∈ S. II. RECURSION: If x ∈ S and y ∈ S, then x + y ∈ S. III. RESTRICTION: S contains no elements other than those obtained from rules I and II. Show that S is the subset of all positive integers divisible by 5.

SOLUTION: Let A be the set of all positive integers divisible by 5. Then A = {5n | n ∈ N}. We need to prove that S ⊆ A. 5 is divisible by 5 since 5 = 5 × 1 ⇒ 5 ∈ A. Now consider x ∈ A and y ∈ A, we show that x + y ∈ A. x ∈ A ⇒ 5 | x so that x = 5 · p for some p ∈ N. y ∈ A ⇒ 5 | y so that y = 5 · q for some q ∈ N. Hence x + y = 5 · p + 5 · q = 5 · (p + q) ⇒ 5 | (x + y) and so (x + y) ∈ A. Thus, S is a subset of A.

RECURSIVE DEFINITION OF BOOLEAN EXPRESSIONS

I. BASE: Each symbol of the alphabet is a Boolean expression. II. RECURSION: If P and Q are Boolean Expressions, then so are (a) (P ∧ Q) (b) (P ∨ Q) and (c) ~ P. III. RESTRICTION: There are no Boolean expressions over the alphabet other than those obtained from I and II.

EXERCISE: Show that ((p ∨ q) ∨ ~ ((p ∧ ~ s) ∧ r)) is a Boolean expression over the English alphabet.

SOLUTION: (1) p, q, r, and s are Boolean expressions by I. (2) ~ s is a Boolean expression by (1) and II(c). (3) (p ∧ ~ s) is a Boolean expression by (1), (2) and II(a). (4) ((p ∧ ~ s) ∧ r) is a Boolean expression by (1), (3) and II(a). (5) ~ ((p ∧ ~ s) ∧ r) is a Boolean expression by (4) and II(c). (6) (p ∨ q) is a Boolean expression by (1) and II(b). (7) ((p ∨ q) ∨ ~ ((p ∧ ~ s) ∧ r)) is a Boolean expression by (5), (6) and II(b).

RECURSIVE DEFINITION OF THE SET OF STRINGS OVER AN ALPHABET

Consider a finite alphabet Σ = {a, b}. The set of all finite strings over Σ, denoted Σ*, is defined recursively as follows: I. BASE: ε is in Σ*, where ε is the null string. II. RECURSION: If s ∈ Σ*, then (a) sa ∈ Σ* and (b) sb ∈ Σ*, where sa and sb are concatenations of s with a and b respectively. III. RESTRICTION: Nothing is in Σ* other than objects defined in I and II above.

EXERCISE: Give derivations showing that abb is in Σ*. SOLUTION: (1) ε ∈ Σ* by I. (2) a = εa ∈ Σ* by (1) and II(a). (3) ab ∈ Σ* by (2) and II(b). (4) abb ∈ Σ* by (3) and II(b).

EXERCISE: Give a recursive definition of all strings of 0’s and 1’s for which all the 0’s precede all the 1’s. SOLUTION: Let S be the set of all strings of 0’s and 1’s for which all the 0’s precede all the 1’s. The following is a recursive definition of S. I. BASE: The null string ε ∈ S. II. RECURSION: If s ∈ S, then (a) 0s ∈ S and (b) s1 ∈ S. III. RESTRICTION: Nothing is in S other than objects defined in I and II above.

PARENTHESIS STRUCTURE

Let P be the set of grammatical configurations of parentheses. The following is a recursive definition of P. I. BASE: ( ) is in P. II. RECURSION: (a) If E is in P, so is (E). (b) If E and F are in P, so is EF. III. RESTRICTION: No configurations of parentheses are in P other than those derived from I and II above.

EXERCISE: Derive the fact that ( ( ( ) ) ( ) ) is in the set P of grammatical configuration of parentheses. SOLUTION: (1) ( ) is in P, by I. (2) ( ( ) ) is in P, by 1 and II(a). (3) ( ( ) ) ( ) is in P, by 2, I and II(b). (4) ( ( ( ) ) ( ) ) is in P, by 3, and II(a).

SET OF ARITHMETIC EXPRESSIONS

The set of arithmetic expressions over the real numbers can be defined recursively as follows. I. BASE: Each real number r is an arithmetic expression. II. RECURSION: If u and v are arithmetic expressions, then the following are also arithmetic expressions: a. (+ u) b. (− u) c. (u + v) d. (u − v) e. (u · v) f. (u/v) III. RESTRICTION: There are no arithmetic expressions other than those obtained from I and II above.

EXERCISE: Give derivations showing that ( (9·(6.1+2)) / ((4−7)·6) ) is an arithmetic expression. SOLUTION: (1) 9, 6.1, 2, 4, 7, and 6 are arithmetic expressions by I. (2) (6.1 + 2) is an arithmetic expression by (1) and II(c). (3) (9·(6.1+2)) is an arithmetic expression by (1), (2) and II(e). (4) (4 – 7) is an arithmetic expression by (1) and II(d). (5) ((4–7)·6) is an arithmetic expression by (1), (4) and II(e). (6) ( (9·(6.1+2)) / ((4−7)·6) ) is an arithmetic expression by (3), (5) and II(f).

RECURSIVE DEFINITION OF SUM

Given numbers a₁, a₂, ..., aₙ, where n is a positive integer, the summation from i = 1 to n of the aᵢ, denoted Σᵢ₌₁ⁿ aᵢ, is defined as follows: BASE: Σᵢ₌₁¹ aᵢ = a₁ RECURSION: Σᵢ₌₁ⁿ aᵢ = (Σᵢ₌₁ⁿ⁻¹ aᵢ) + aₙ

RECURSIVE DEFINITION OF UNION OF SETS

Given sets A₁, A₂, ..., Aₙ, where n is a positive integer, the union of Aᵢ from i = 1 to n, denoted ∪ᵢ₌₁ⁿ Aᵢ, is defined by: BASE: ∪ᵢ₌₁¹ Aᵢ = A₁ RECURSION: ∪ᵢ₌₁ⁿ Aᵢ = (∪ᵢ₌₁ⁿ⁻¹ Aᵢ) ∪ Aₙ

RECURSIVE DEFINITION OF INTERSECTION OF SETS

Given sets A₁, A₂, ..., Aₙ, where n is a positive integer, the intersection of Aᵢ from i = 1 to n, denoted ∩ᵢ₌₁ⁿ Aᵢ, is defined by: BASE: ∩ᵢ₌₁¹ Aᵢ = A₁ RECURSION: ∩ᵢ₌₁ⁿ Aᵢ = (∩ᵢ₌₁ⁿ⁻¹ Aᵢ) ∩ Aₙ

⭐ Key Takeaways

Every recursive definition requires three components: a base case that provides initial elements, recursion rules that build new elements from existing ones, and a restriction that excludes everything not generated by the first two rules. To verify that an expression belongs to a recursively defined set, always start with the innermost components using the base case, then apply recursion rules step by step from the inside out. The same recursive pattern — base case for the first element and recursion relating the nth case to the (n-1)th case — applies to operations like summation, union, and intersection. Recursive definitions are fundamental for specifying formal languages and mathematical structures precisely, and mastering them requires practice with derivations.

🧠 Quick Revision Questions

1. What are the three rules that must be included in any recursive definition of a set?
2. How would you derive that the string "010" belongs to the set defined by BASE: ε ∈ Σ*, RECURSION: if s ∈ Σ* then 0s ∈ Σ* and 1s ∈ Σ*?
3. If S is defined recursively by BASE: 3 ∈ S and RECURSION: if x, y ∈ S then x+y ∈ S, is 12 in S? Show your derivation.
4. Using the recursive definition of Boolean expressions, is (p ∧ (q ∨ ~r)) a valid Boolean expression? Show your steps.
5. Write the recursive definition for the union of n sets, stating both the base and recursion cases.