MTH001 — Midterm Summary (Lectures 1–22)
📘 Lecture 1 — Introduction
📖 Overview: This lecture introduces the fundamental concepts of logic, which serves as the foundation for discrete mathematics. It explains what statements are, how to form compound statements using logical connectives, and how to construct truth tables to determine the truth values of compound propositions.
🗂️ Topics Covered
The lecture covers the definition of logic and discrete mathematics, the concept of simple and compound statements, logical connectives (negation, conjunction, and disjunction), symbolic representation of statements, translating between English and symbolic forms, and constructing truth tables for basic logical operations.
📝 Lecture Summary
MAIN TOPICS:
This course covers Logic, Sets & Operations on sets, Relations & Their Properties, Functions, and Sequences & Series. The set of integers includes ... -3, -2, -1, 0, 1, 2... and the set of real numbers includes all numbers on the number line. Discrete Mathematics concerns processes that consist of a sequence of individual steps.
Logic is the study of the principles and methods that distinguishes between a valid and an invalid argument.
SIMPLE STATEMENT:
A statement (also called a proposition) is a declarative sentence that is either true or false but not both. If a proposition is true, its truth value is "true"; if false, its truth value is "false". Truth values are denoted by T and F.
🔑 Definition — Statement: A declarative sentence that is either true or false but not both.
📌 Examples: "Grass is green", "4 + 2 = 6", "4 + 2 = 7", "There are four fingers in a hand" are all propositions.
Not propositions include: "Close the door" (command), "x is greater than 2" (variable not specified), "He is very rich" (pronoun reference unclear).
Rule: If the sentence is preceded by other sentences that make the pronoun or variable reference clear, then the sentence is a statement.
📌 Example: When x = 1, "x > 2" is a statement with truth-value FALSE. 📌 Example: "Bill Gates is an American" followed by "He is very rich" makes "He is very rich" a statement with truth-value TRUE.
📌 More examples: "x + 2 is positive" → Not a statement; "May I come in?" → Not a statement; "Logic is interesting" → A statement; "It is hot today" → A statement; "-1 > 0" → A statement; "x + y = 12" → Not a statement.
COMPOUND STATEMENT:
Simple statements can be used to build a compound statement using logical connectives.
📌 Examples:
- "3 + 2 = 5" and "Lahore is a city in Pakistan"
- "The grass is green" or "It is hot today"
- "Discrete Mathematics is not difficult to me"
AND, OR, NOT are called LOGICAL CONNECTIVES.
SYMBOLIC REPRESENTATION:
Statements are symbolically represented by letters such as p, q, r, ...
📌 Examples: p = "Islamabad is the capital of Pakistan" q = "17 is divisible by 3"
| Connective | Meaning | Symbol | Called |
|---|---|---|---|
| Negation | not | ~ | Tilde |
| Conjunction | and | ∧ | Hat |
| Disjunction | or | ∨ | Vel |
| Conditional | if...then... | → | Arrow |
| Biconditional | if and only if | ↔ | Double arrow |
📌 Examples using p and q above: p ∧ q = "Islamabad is the capital of Pakistan and 17 is divisible by 3" p ∨ q = "Islamabad is the capital of Pakistan or 17 is divisible by 3" ~p = "It is not the case that Islamabad is the capital of Pakistan" or simply "Islamabad is not the capital of Pakistan"
TRANSLATING FROM ENGLISH TO SYMBOLS:
Let p = "It is hot", and q = "It is sunny"
| Sentence | Symbolic Form |
|---|---|
| It is not hot | ~ p |
| It is hot and sunny | p ∧ q |
| It is hot or sunny | p ∨ q |
| It is not hot but sunny | ~ p ∧ q |
| It is neither hot nor sunny | ~ p ∧ ~ q |
📌 Example: Let h = "Zia is healthy", w = "Zia is wealthy", s = "Zia is wise"
- "Zia is healthy and wealthy but not wise" → (h ∧ w) ∧ (~s)
- "Zia is not wealthy but he is healthy and wise" → ~w ∧ (h ∧ s)
- "Zia is neither healthy, wealthy nor wise" → ~h ∧ ~w ∧ ~s
TRANSLATING FROM SYMBOLS TO ENGLISH:
Let m = "Ali is good in Mathematics", c = "Ali is a Computer Science student"
| Symbolic Form | English Translation |
|---|---|
| ~ c | Ali is not a Computer Science student |
| c ∨ m | Ali is a Computer Science student or good in Maths |
| m ∧ ~c | Ali is good in Maths but not a Computer Science student |
A convenient method for analyzing a compound statement is to make a truth table for it. 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 variable, then negation of p, "not p", is denoted as "~p". It has opposite truth value from p: if p is true, ~p is false; if p is false, ~p is true.
TRUTH TABLE FOR ~p:
| p | ~p |
|---|---|
| T | F |
| F | T |
CONJUNCTION (∧):
If p and q are statements, then the conjunction of p and q is "p and q", denoted as "p ∧ q". It is true when, and only when, both p and q are true. If either p or q is false, or if both are false, p ∧ q is false.
TRUTH TABLE FOR p ∧ q:
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Note that in the table T is only in that row where both p and q have T and all other values are F. Thus for finding out the truth values for the conjunction of two statements we will only first search out where both statements are true and write down the T in the corresponding row in the column of p ∧ q and in all other rows we will write F.
💡 Why this matters: Conjunction requires ALL components to be true for the compound statement to be true.
DISJUNCTION (∨) or INCLUSIVE OR:
If p and q are statements, then the disjunction of p and q is "p or q", denoted as "p ∨ q". It is true when at least one of p or q is true and is false only when both p and q are false.
TRUTH TABLE FOR p ∨ q:
| p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Note that in the table F is only in that row where both p and q have F and all other values are T. Thus for finding out the truth values for the disjunction of two statements we will only first search out where both statements are false and write down the F in the corresponding row in the column of p ∨ q and in all other rows we will write T.
💡 Why this matters: Disjunction requires only ONE component to be true for the compound statement to be true.
Remark: For conjunction of two statements we find the T in both the statements. But in disjunction we find F in both the statements. In other words, we fill T first in the column of conjunction and F in the column of disjunction.
⭐ Key Takeaways
A statement must be a declarative sentence with a definite truth value (true or false), and sentences with unclear references or variables are not statements. Compound statements are built from simple statements using logical connectives: negation (~), conjunction (∧), and disjunction (∨), each with specific truth table rules. Negation flips the truth value, conjunction is true only when both parts are true, and disjunction is false only when both parts are false. Translating between English and symbolic notation requires careful attention to connectives and the structure of the sentence. Truth tables provide a systematic method for determining the truth value of any compound proposition for all possible combinations of its components.
🧠 Quick Revision Questions
- Why is "He is very rich" not always considered a statement? When can it become a statement?
- What is the difference between the truth table pattern for conjunction (∧) and disjunction (∨)?
- Translate into symbolic form: "It is not hot but it is sunny" using p = "It is hot" and q = "It is sunny".
- If p is false and q is true, what is the truth value of ~p ∧ q?
- What is the only condition under which a disjunction (p ∨ q) is false?
📘 Lecture 2 — Truth Tables
📖 Overview: This lecture introduces the construction and interpretation of truth tables for compound statements involving multiple logical operators. It demonstrates how to systematically evaluate truth values for expressions with negation, conjunction, disjunction, and their combinations, and covers foundational logical equivalences including De Morgan’s Laws, the double negative property, and the concept of tautology.
🗂️ Topics Covered
The lecture covers truth tables for three statement forms: ~p ∧ q, ~p ∧ (q ∨ ~r), and (p∨q) ∧ ~(p∧q). It then explains the double negative property ~(~p) ≡ p through an example, demonstrates that ~(p∧q) and ~p ∧ ~q are not logically equivalent, introduces De Morgan’s Laws for negating conjunctions and disjunctions, applies them to inequalities and real-world statements, and concludes with the definition of tautology and the example p ∨ ~p.
📝 Lecture Summary
Truth table for the statement form ~ p q
A truth table for the expression ~p ∧ q is constructed by listing all possible truth values for p and q, then determining ~p, and finally the conjunction of ~p with q. The result is true only when p is false and q is true.
🔑 Truth table: A table that shows all possible truth values for statement variables and the resulting truth value of a compound statement.
| p | q | ~p | ~p ∧ q |
|---|---|---|---|
| T | T | F | F |
| T | F | F | F |
| F | T | T | T |
| F | F | T | F |
📌 Example: For row 3, p = F, q = T, so ~p = T, and T ∧ T = T.
Truth table for ~ p (q ~ r)
This truth table involves three variables (p, q, r), requiring 8 rows. The intermediate columns compute ~r, then q ∨ ~r, then ~p, and finally the conjunction of ~p with (q ∨ ~r).
🔑 ~r: Negation of r.
| p | q | r | ~r | q ∨ ~r | ~p | ~p ∧ (q ∨ ~r) |
|---|---|---|---|---|---|---|
| T | T | T | F | T | F | F |
| T | T | F | T | T | F | F |
| T | F | T | F | F | F | F |
| T | F | F | T | T | F | F |
| F | T | T | F | T | T | T |
| F | T | F | T | T | T | T |
| F | F | T | F | F | T | F |
| F | F | F | T | T | T | T |
📌 Example: In row 6 (p=F, q=T, r=F), ~r = T, so q ∨ ~r = T ∨ T = T, ~p = T, so final result is T ∧ T = T.
Truth table for (pq) ~ (pq)
This table computes p∨q, p∧q, its negation ~(p∧q), and then the conjunction of p∨q with ~(p∧q). This expression is true when p and q have different truth values.
| p | q | p∨q | p∧q | ~(p∧q) | (p∨q) ∧ ~(p∧q) |
|---|---|---|---|---|---|
| T | T | T | T | F | F |
| T | F | T | F | T | T |
| F | T | T | F | T | T |
| F | F | F | F | T | F |
📌 Example: For p=T, q=F, p∨q = T, p∧q = F, ~(p∧q) = T, final result: T ∧ T = T.
Double Negative Property ~(~p) º p
The double negative property states that negating a negation returns the original proposition. The truth table confirms ~(~p) has the same truth value as p.
| p | ~p | ~(~p) |
|---|---|---|
| T | F | T |
| F | T | F |
📌 Example: “It is not true that I am not happy” is equivalent to “I am happy.” Let p = “I am happy”, then ~p = “I am not happy”, and ~(~p) = “It is not true that I am not happy”. Since ~(~p) ≡ p, the given statement means “I am happy”.
💡 Why this matters: The double negative property confirms that two negations cancel each other logically, which is essential for simplifying statements.
~(pq) and ~p ~q are not logically equivalent
The truth table shows that ~(p∧q) and ~p ∧ ~q have different truth values in rows 2 and 3, proving they are not logically equivalent.
| p | q | ~p | ~q | p∧q | ~(p∧q) | ~p ∧ ~q |
|---|---|---|---|---|---|---|
| T | T | F | F | T | F | F |
| T | F | F | T | F | T | F |
| F | T | T | F | F | T | F |
| F | F | T | T | F | T | T |
🔑 Logically equivalent: Two statement forms that have identical truth values for all possible truth values of their variables.
📌 Example: In row 2 (p=T, q=F), ~(p∧q) = T but ~p ∧ ~q = F, so they differ.
De Morgan’s Laws
De Morgan’s Laws provide rules for negating compound statements:
- ~(p ∧ q) ≡ ~p ∨ ~q — the negation of an “and” statement is an “or” of the negations.
- ~(p ∨ q) ≡ ~p ∧ ~q — the negation of an “or” statement is an “and” of the negations.
Truth table for ~(p ∨ q) ≡ ~p ∧ ~q confirms the equivalence:
| p | q | ~p | ~q | p ∨ q | ~(p ∨ q) | ~p ∧ ~q |
|---|---|---|---|---|---|---|
| T | T | F | F | T | F | F |
| T | F | F | T | T | F | F |
| F | T | T | F | T | F | F |
| F | F | T | T | F | T | T |
All truth values match, confirming the equivalence.
📌 Application: Negate the statement “The fan is slow or it is very hot.” Using De Morgan’s Law: ~(p ∨ q) ≡ ~p ∧ ~q, so the negation is “The fan is not slow and it is not very hot.”
📌 Application: Negate “Akram is unfit and Saleem is injured.” Using De Morgan’s Law: ~(p ∧ q) ≡ ~p ∨ ~q, so the negation is “Akram is not unfit or Saleem is not injured.”
Inequalities and De Morgan’s Laws
De Morgan’s Laws apply to inequalities. For the compound inequality -1 < x ≤ 4, which means x > -1 and x ≤ 4, the negation using De Morgan’s Law is: x > -1 or x ≤ 4 is false. Equivalently: x ≤ -1 or x > 4.
📌 Example: For the inequality -1 < x ≤ 4, write as (x > -1) ∧ (x ≤ 4). Negation: ~(x > -1) ∨ ~(x ≤ 4) = (x ≤ -1) ∨ (x > 4).
Exercise
- (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) — This is the associative law for conjunction, which is logically equivalent.
- Are (p∧q)∨r and p ∧ (q ∨ r) logically equivalent? — They are not logically equivalent because the parentheses change the grouping; (p∧q)∨r is a disjunction, while p∧(q∨r) is a conjunction.
🔑 Associative law: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r), meaning grouping does not affect the truth value.
Tautology
A tautology is a statement form that is always true regardless of the truth values of the statement variables. It is represented by the symbol t.
📌 Example: The statement form p ∨ ~p is a tautology because:
| p | ~p | p ∨ ~p |
|---|---|---|
| T | F | T |
| F | T | T |
Both rows yield T, so p ∨ ~p ≡ t.
💡 Why this matters: Tautologies are always true statements, forming the basis of logical reasoning and valid arguments.
⭐ Key Takeaways
The most critical concepts from this lecture are the systematic construction of truth tables for compound statements with up to three variables, the double negative property which allows cancellation of two negations, and De Morgan’s Laws which provide a method for negating conjunctions and disjunctions by distributing negation and flipping the operator. It is essential to remember that ~(p∧q) is not equivalent to ~p∧~q; instead it is ~p∨~q. The concept of tautology identifies statements that are always true, such as p ∨ ~p. Understanding truth tables is fundamental for verifying logical equivalences and analyzing logical arguments.
🧠 Quick Revision Questions
- Construct the truth table for ~p ∧ q and identify in which row(s) the result is true.
- Using De Morgan’s Laws, what is the negation of the statement “The fan is slow or it is very hot”?
- Are the statements ~(p ∧ q) and ~p ∧ ~q logically equivalent? Explain why or why not.
- What is a tautology? Give one example from this lecture.
- Write the negation of the inequality -1 < x ≤ 4 using De Morgan’s Laws.
📘 Lecture 3 — Applying Laws of Logic
📖 Overview: This lecture introduces the application of logical laws to simplify statement forms and verify logical equivalences. It then transitions to conditional statements (implications), covering their truth tables, alternative expressions, translations between English and symbolic form, and related concepts like negation, inverse, converse, and contrapositive.
🗂️ Topics Covered
The lecture begins by applying DeMorgan’s, Double Negative, Associative, Idempotent, Distributive, Negation, and Identity laws to simplify logical expressions and verify equivalences. It then defines conditional statements, provides their truth table, and explores alternative phrasings. The lecture continues with exercises on translating English sentences to symbolic propositions and vice versa, establishing a hierarchy of logical operations, and constructing truth tables for complex statements. Finally, it covers the logical equivalence involving implication (including Implication Law), the negation of a conditional statement, and the definitions and distinctions between the inverse, converse, and contrapositive of a conditional statement.
📝 Lecture Summary
Laws of Logic
Using law of logic, simplify the statement form p ∨ [~(~p ∧ q)]. The solution begins with DeMorgan’s Law to get p ∨ [~(~p) ∨ (~q)], then applies the Double Negative Law to become p ∨ [p ∨ (~q)], uses the Associative Law for ∨ to get [p ∨ p] ∨ (~q), and finally applies the Idempotent Law to arrive at the simplified form p ∨ (~q).
🔑 Definition — DeMorgan’s Law: ~(p ∧ q) ≡ ~p ∨ ~q and ~(p ∨ q) ≡ ~p ∧ ~q.
🔑 Definition — Double Negative Law: ~(~p) ≡ p.
🔑 Definition — Associative Law: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) and (p ∧ q) ∧ r ≡ p ∧ (q ∧ r).
🔑 Definition — Idempotent Law: p ∨ p ≡ p and p ∧ p ≡ p.
📌 Example: Using Laws of Logic, verify the logical equivalence ~ (~ p ∧ q) ∧ (p ∨ q) ≡ p. The steps are: ~(p ∧ q) ∧ (p ∨ q) ≡ ((~p) ∨ ~q) ∧ (p ∨ q) (DeMorgan’s) ≡ (p ∨ ~q) ∧ (p ∨ q) (Double Negative) ≡ p ∨ (~q ∧ q) (Distributive Law) ≡ p ∨ c (Negation Law) ≡ p (Identity Law). This verifies the equivalence. 💡 Why this matters: These laws provide a systematic method for simplifying complex logical statements without constructing extensive truth tables.
Simplifying a Statement
The lecture shows how to rephrase a complex condition more simply using logical equivalences. The statement is: “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 the Distributive Law in reverse, (p ∧ q) ∨ (p ∧ r) ≡ p ∧ (q ∨ r). Translating back to English gives: “You will get an A if you are hardworking and the sun shines or it rains.”
Conditional Statements or Implications
If p and q are statement variables, the conditional of q by p is “If p then q” or “p implies q” and is denoted p → q. It is false when p is true and q is false; otherwise it is true. In p → q, p is called the hypothesis (or antecedent) and q is called the conclusion (or consequent).
🔑 Definition — Conditional Statement (p → q): A logical statement that is false only when the hypothesis (p) is true and the conclusion (q) is false; it is true in all other cases. 📐 Truth Table for p → q:
| p | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
📌 Example: Determine the truth value of “If 1 = 1, then 3 = 3.” Since both p (1=1) is true and q (3=3) is true, the conditional is TRUE.
Alternative Ways of Expressing Implications
The implication p → q can be expressed in many alternative ways: “if p then q”, “p implies q”, “if p, q”, “p only if q”, “p is sufficient for q”, “not p unless q”, “q follows from p”, “q if p”, “q whenever p”, and “q is necessary for p”.
📌 Example: Write “Your guarantee is good only if you bought your CD less than 90 days ago” in the form “if p, then q”. Let p = “your guarantee is good” and q = “you bought your CD less than 90 days ago”. The rephrased statement is: If your guarantee is good, then you must have bought your CD player less than 90 days ago.
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”. The translation uses the logical connectives: → for implication, ∧ for conjunction, and ∨ for disjunction.
📌 Example: “Getting an A on the final and doing every exercise in this book is sufficient for getting an A in this class.” The symbolic translation is p ∧ q → r.
Hierarchy of Operations for Logical Connectives
The order of precedence for logical connectives is: ~ (negation) has highest priority, then ∧ (conjunction) and ∨ (disjunction) have equal priority, and finally → (conditional) has the lowest priority.
📌 Example: Construct a truth table for the statement form p ∨ ~ q → ~ p. According to the hierarchy, the negation (~) is evaluated first, then disjunction (∨), and finally conditional (→). The result shows that the statement is false when p is true and q is either true or false, and true when p is false.
Logical Equivalence Involving Implication
A conditional statement and its contrapositive are logically equivalent. Symbolically, p → q ≡ ~q → ~p.
🔑 Definition — Implication Law: p → q ≡ ~p ∨ q. This law expresses a conditional as a disjunction.
📌 Example: Use truth table to show p → q ≡ ~q → ~p. The truth tables for both expressions have the same truth values for all combinations of p and q (T, F, T, T), confirming their logical equivalence.
Negation of a Conditional Statement
Since p → q ≡ p ∨ q, the negation is ~ (p → q) ≡ ~ ( p ∨ q) ≡ ~(~p) ∧ (~q) (by De Morgan’s law) ≡ p ∧ ~q (by Double Negative law). Thus, the negation of “if p then q” is logically equivalent to “p and not q”.
📌 Example: Write the negation of “If Ali lives in Pakistan then he lives in Lahore.” The negation is: Ali lives in Pakistan and he does not live in Lahore.
Inverse, Converse, and Contrapositive of a Conditional Statement
The inverse of p → q is ~p → ~q. A conditional and its inverse are not logically equivalent. The converse of p → q is q → p. A conditional and its converse are not equivalent. The contrapositive of p → q is ~q → ~p. A conditional and its contrapositive are logically equivalent.
🔑 Definition — Inverse: The statement formed by negating both the hypothesis and conclusion of a conditional statement. 🔑 Definition — Converse: The statement formed by swapping the hypothesis and conclusion of a conditional statement. 🔑 Definition — Contrapositive: The statement formed by both swapping and negating the hypothesis and conclusion of a conditional statement; it is logically equivalent to the original conditional.
📌 Example: For “If today is Friday, then 2 + 3 = 5”: Inverse: “If today is not Friday, then 2 + 3 ≠ 5.” Converse: “If 2 + 3 = 5, then today is Friday.” Contrapositive: “If 2 + 3 ≠ 5, then today is not Friday.”
⭐ Key Takeaways
The most critical concepts from this lecture are: (1) logical laws like DeMorgan’s, Double Negative, Distributive, and Imputation laws are powerful tools for simplifying complex logical statements and verifying equivalences without constructing full truth tables. (2) A conditional statement (p → q) is false only when the hypothesis is true and the conclusion is false, and it can be expressed in many equivalent English phrases. (3) The negation of a conditional is logically equivalent to “p and not q” (p ∧ ~q), not another “if-then” statement. (4) A conditional statement is logically equivalent to its contrapositive (~q → ~p) but not to its inverse (~p → ~q) or its converse (q → p). (5) The hierarchy of logical operations (negation first, then conjunction/disjunction, then conditional) is essential for correctly interpreting and constructing truth tables for compound statements.
🧠 Quick Revision Questions
- Using the laws of logic, simplify the statement form: ~(~p ∧ q) ∧ (p ∨ q). What is the final simplified form?
- What is the truth value of the conditional statement “If 1 = 0, then 3 = 3”?
- Write the statement “It is necessary to walk 8 miles to get to the top of the Peak” in the form “if p, then q”.
- State the negation of the conditional statement: “If n is divisible by 6, then n is divisible by 2 and n is divisible by 3.”
- Identify whether each of the following is logically equivalent to the original conditional statement p → q: (a) its inverse, (b) its converse, (c) its contrapositive, (d) ~p ∨ q.
📘 Lecture 4 — Biconditional operator
📖 Overview: This lecture introduces the biconditional operator (iff) as a logical connective that combines two conditional statements. It covers truth tables, logical equivalences involving biconditionals, and several laws of logic used to simplify or rewrite statement forms, with applications for rewriting without implication or biconditional symbols.
🗂️ Topics Covered
The lecture begins with the definition and truth table of the biconditional operator pq, including examples of true/false statements. It then rephrases biconditional in English and covers truth tables for complex statements like (pq)(qp) and (pq)(rq). Logical equivalence involving biconditional is demonstrated, followed by several laws of logic (commutative, implication, exportation, equivalence, reductio ad absurdum). Applications show how to rewrite statements without or using only ~ and , and how to prove a tautology without truth tables.
📝 Lecture Summary
Biconditional operator
If p and q are statement variables, the biconditional of p and q is “p if, and only if, q” and is denoted pq. “if and only if” abbreviated iff. The double headed arrow "" is the biconditional operator.
🔑 Definition — Biconditional: pq is true when p and q have the same truth value (both true or both false), and false otherwise.
📐 Truth Table: pq is true only when p and q are both T or both F; false otherwise.
| p | q | pq |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
📌 Example: True or false?
- “1+1 = 3 if and only if earth is flat” → TRUE (both false)
- “Sky is blue iff 1 = 0” → FALSE (one true, one false)
- “Milk is white iff birds lay eggs” → TRUE (both true)
- “33 is divisible by 4 if and only if horse has four legs” → FALSE (one false, one true)
- “x > 5 iff x² > 25” → FALSE (e.g., x = -5 gives x² > 25 true but x > 5 false)
Equivalence: pq ≡ (pq) ∧ (qp)
The biconditional is logically equivalent to the conjunction of two conditionals.
📐 Truth table showing same truth values:
| p | q | pq | pq | qp | (pq)∧(qp) |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | F | F | T | F |
| F | T | F | T | F | F |
| F | F | T | T | T | T |
Rephrasing Biconditional
pq is also expressed as:
- “p is necessary and sufficient for q”
- “if p then q, and conversely”
- “p is equivalent to q”
📌 Example: “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.”
Truth Table for (pq) (qp)
| p | q | pq | ~q | ~p | (pq)( | |
|---|---|---|---|---|---|---|
| T | T | T | F | F | T | T |
| T | F | F | T | F | F | T |
| F | T | T | F | T | T | T |
| F | F | T | T | T | T | T |
This is always true — a tautology.
Truth Table for (pq)(rq)
| p | q | r | pq | rq | (pq)(rq) |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | T | F | T | F | F |
| T | F | T | F | F | T |
| T | F | F | F | T | F |
| F | T | T | F | T | F |
| F | T | F | F | F | T |
| F | F | T | T | F | F |
| F | F | F | T | T | T |
Truth Table for p ∧ ~r q ∨ r (where p∧~r q∨r means (p ∧ (~r)) (q ∨ r))
| p | q | r | ~r | p∧~r | q∨r | p∧~r q∨r |
|---|---|---|---|---|---|---|
| T | T | T | F | F | T | F |
| T | T | F | T | T | T | T |
| T | F | T | F | F | T | F |
| T | F | F | T | T | F | F |
| F | T | T | F | F | T | F |
| F | T | F | T | F | T | F |
| F | F | T | F | F | T | F |
| F | F | F | T | F | F | T |
Logical Equivalence Involving Biconditional
Show that ~p q and p ~q are logically equivalent.
| p | q | ~p | ~q | ~pq | p~q |
|---|---|---|---|---|---|
| T | T | F | F | F | F |
| T | F | F | T | T | T |
| F | T | T | F | T | T |
| F | F | T | T | F | F |
Same truth values → logically equivalent.
Show ~(p ⊕ q) and p q are logically equivalent
| p | q | p⊕q | ~(p⊕q) | pq |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | T | F | F |
| F | T | T | F | F |
| F | F | F | T | T |
Same truth values → logically equivalent.
Laws of Logic
- Commutative Law: p q ≡ q p
- Implication Laws: p q ≡ ~p ∨ q ; also ≡ ~(p ∧ ~q)
- Exportation Law: (p ∧ q) r ≡ p (q r)
- Equivalence: p q ≡ (p q) ∧ (q p)
- Reductio ad absurdum: p q ≡ (p ∧ ~q) c (where c is a contradiction)
Application: Rewrite without or
- p ∧ ~q r → Using order of operations: (p ∧ ~q) r ≡ ~(p ∧ ~q) ∨ r (implication law)
- (p r) (q r) → ≡ (~p ∨ r) (~q ∨ r) (implication law) → then ≡ [(~p ∨ r) (~q ∨ r)] ∧ [(~q ∨ r) (
p ∨ r)] → then ≡ [(~p ∨ r) ∨ (q ∨ r)] ∧ [(~q ∨ r) ∨ (~p ∨ r)]
Application: Rewrite using only ~ and ∧
Rewrite ~p ∨ q r ∨ ~q to a logically equivalent form using only ~ and ∧.
- Given: ~p ∨ q r ∨ ~q
- ≡ (~p ∨ q) (r ∨ ~q) [order of operations]
- ≡ ~[(~p ∨ q) ∧ ~(r ∨ ~q)] [implication law pq ≡ ~(p∧~q)]
- ≡
[(p ∧ ~q) ∧ (~r ∧ q)] [De Morgan’s law]
Show ~(pq) p is a tautology without truth tables
| Statement | Reason |
|---|---|
| ~(pq) p | Given |
| ≡ | Implication law pq ≡ ~(p∧~q) |
| ≡ (p ∧ ~q) p | Double negation law |
| ≡ ~(p ∧ ~q) ∨ p | Implication law pq ≡ ~p∨q |
| ≡ (~p ∨ q) ∨ p | De Morgan’s law |
| ≡ (q ∨ ~p) ∨ p | Commutative law of ∨ |
| ≡ q ∨ (~p ∨ p) | Associative law of ∨ |
| ≡ q ∨ t | Negation law |
| ≡ t | Universal bound law |
Thus, it is a tautology (always true).
Exercise: Find truth values when pq is false
Given: pq is false. This happens only when p is true and q is false.
- ~p q: ~p is false, so false q (false) → TRUE (conditional with false antecedent is true)
- p ∨ q: true ∨ false → TRUE
- q p: false true → FALSE (different truth values)
⭐ Key Takeaways
The biconditional pq is true only when both statements have the same truth value. It is logically equivalent to (pq) ∧ (qp), which connects it to the conditional operator. The key laws to remember for manipulating biconditionals include the equivalence law, implication laws (pq ≡ ~p∨q ≡ ~(p∧~q)), and De Morgan’s laws. You must also know the rephrasing “necessary and sufficient” and “if and only if”. For test preparation, be comfortable building truth tables for compound statements with biconditionals and applying the laws to rewrite or simplify logical statements without using or .
🧠 Quick Revision Questions
- What is the truth value of pq when p is true and q is false?
- Show that pq is logically equivalent to which conjunction of conditionals?
- Rewrite p q using only ~ and ∧.
- If pq is false, what are the truth values of p and q?
- What does the phrase “p is necessary and sufficient for q” mean in terms of the biconditional operator?
📘 Lecture 5 — Arguments
📖 Overview: This lecture introduces the fundamental concept of logical arguments, distinguishing between valid and invalid forms. It explains how to determine argument validity using truth tables, which is crucial for constructing and evaluating logical reasoning in mathematics and computer science.
🗂️ Topics Covered
The lecture defines what constitutes an argument, including premises and conclusion. It then establishes the criteria for valid versus invalid arguments, using truth tables as the primary tool for evaluation. Two detailed examples demonstrate the process of testing argument forms for validity, followed by an exercise applying these methods.
📝 Lecture Summary
Argument
An argument is a list of statements called premises (or assumptions or hypotheses) followed by a statement called the conclusion. The symbol "∴", read "therefore," is normally placed just before the conclusion.
🔑 Definition — Argument: A list of statements (premises) followed by a conclusion. 📐 Structure: P₁, P₂, P₃, ..., Pₙ ∴ C (where P are premises and C is conclusion) 📌 Example: "An interesting teacher keeps me awake. I stay awake in Discrete Mathematics class. Therefore, my Discrete Mathematics teacher is interesting." Here, the first two statements are premises, and the last statement is 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, meaning (P₁ ∧ P₂ ∧ P₃ ∧ ... ∧ Pₙ) → C is a tautology. An argument is invalid if the conclusion is false when all the premises are true, or if the conjunction of its premises does not imply the conclusion.
🔑 Definition — Valid Argument: An argument where the conclusion must be true whenever all premises are true. 🔑 Definition — Invalid Argument: An argument where it is possible for all premises to be true while the conclusion is false. 📐 Formula for validity: (P₁ ∧ P₂ ∧ ... ∧ Pₙ) → C must be a tautology. 💡 Why this matters: Validity ensures that if you accept the premises, you logically must accept the conclusion. Invalid arguments represent logical fallacies.
Example: Valid Argument Form
Show that the argument form p → q, p ∴ q is valid.
| p | q | p → q | p | q |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | F |
| F | T | T | F | T |
| F | F | T | F | F |
📌 Example: The critical rows are those where all premises (p → q and p) are true. Only the first row has both premises true (T, T), and in that row the conclusion (q) is also true (T). Therefore, the argument form is valid.
Example: Invalid Argument Form
Show that the argument form p → q, q ∴ p is invalid.
| p | q | p → q | q | p |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | F | T |
| F | T | T | T | F |
| F | F | T | F | F |
📌 Example: The critical rows are those where all premises (p → q and q) are true: row 1 and row 3. In row 3, both premises are true (T, T), but the conclusion (p) is false (F). Therefore, the argument form is invalid.
Exercise: Determining Validity
Use a truth table to determine if the argument form p ∨ q, p → ~q, p → r ∴ r is valid or invalid.
| 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 | | 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 |
📌 Example: Critical rows are those where all three premises (p ∨ q, p → ~q, p → r) are true. These are rows 3, 5, 6, 7, and 8. In row 6, all premises are true (T, T, T), but the conclusion (r) is false (F). Therefore, the argument form is invalid.
⭐ Key Takeaways
The most critical concept is understanding that argument validity depends entirely on the logical structure, not the truth of individual statements. A valid argument guarantees the conclusion is true whenever all premises are true, while an invalid argument has at least one scenario where premises are true but the conclusion is false. The truth table method systematically tests this by identifying critical rows where all premises are true and checking if the conclusion is always true in those rows. Students must remember that the argument form p → q, p ∴ q is valid (modus ponens), while p → q, q ∴ p is invalid (fallacy of affirming the consequent). Always look for at least one critical row with a false conclusion to prove invalidity.
🧠 Quick Revision Questions
- What is the formal definition of a valid argument in terms of propositional logic?
- For the argument form p → q, ~q ∴ ~p, use a truth table to determine if it is valid or invalid.
- What distinguishes a critical row in a truth table used for testing argument validity?
- Why is the argument "If it rains, the ground gets wet. The ground is wet. Therefore, it rained" considered invalid?
- How many premises must be true for a row to be considered critical when testing argument validity?
📘 Lecture 6 — Sets
📖 Overview: This lecture introduces the fundamental concept of sets, which are well-defined collections of distinct objects. It covers the core definitions of set membership, various ways to represent sets, important number sets, and the foundational relationships between sets such as subset, proper subset, equality, and the null set. These concepts are essential for all of mathematics and logic.
🗂️ Topics Covered
The lecture begins by defining a set and its elements, then explains the three standard forms for representing sets: Tabular, Descriptive, and Set Builder Form. It lists the common sets of numbers (Natural, Whole, Integer, etc.), defines the critical concepts of Subset and Proper Subset, and covers Equal Sets, the Null Set, the Universal Set, and Venn Diagrams. Finally, it distinguishes between Finite and Infinite Sets and introduces the Membership Table.
📝 Lecture Summary
Sets
A set is defined as a well defined collection of {distinct} objects. The objects are called the elements or members of the set. Sets are denoted by capital letters (A, B, C…), while their elements are represented by lower case letters (a, b, c…). If an object x is a member of a set A, we write x ∈ A, which reads “x belongs to A”. Otherwise, we write x ∉ A, which reads “x does not belong to A”.
Tabular Form
This form lists all the elements of a set, separated by commas and enclosed within braces or curly brackets {}. The symbol “...” called an ellipsis, is a short for “and so forth.”
📌 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.
Descriptive Form
This form states the elements of a set in words.
📌 Examples:
- A = set of first five Natural Numbers.
- B = set of positive even integers less or equal to fifty.
- C = set of positive odd integers.
Set Builder Form
This form writes the common characteristics shared by all the elements of the set in symbolic form.
📌 Examples:
- A = {x ∈ N / x ≤ 5}
- B = {x ∈ E / 0 < x ≤ 50}
- C = {x ∈ O / 0 < x}
Where N, E, O represent the sets of natural, even, and odd numbers respectively.
Sets of Numbers
The lecture defines the following common sets of numbers:
- Set of Natural Numbers (N): N = {1, 2, 3, ...}
- Set of Whole Numbers (W): W = {0, 1, 2, 3, ...}
- Set of Integers (Z): Z = {..., -3, -2, -1, 0, +1, +2, +3, ...}. “Z” stands for the first letter of the German word for integer: Zahlen.
- Set of Even Integers (E): E = {0, ± 2, ± 4, ± 6, ...}
- Set of Odd Integers (O): O = {± 1, ± 3, ± 5, ...}
- Set of Prime Numbers (P): P = {2, 3, 5, 7, 11, 13, 17, 19, ...}
- Set of Rational Numbers (Q): Q = {x | x = p/q; p, q ∈ Z, q ≠ 0}
- Set of Irrational Numbers (Q̅): Q̅ = Qᶜ = { x | x is not rational}. For example, √2, √3, π, e, etc.
- Set of Real Numbers (R): R = Q ∪ Q̅
- Set of Complex Numbers (C): C = {z | z = x + iy; x, y ∈ R}
Subset
If A and B are two sets, A is called a subset of B, written A ⊆ B, if, and only if, any element of A is also an element of B. Symbolically: A ⊆ B ⇔ if x ∈ A then x ∈ B.
- Remark: When A ⊆ B, B is called a superset of A.
- Remark: When A is not a subset of B, then there exists at least one x ∈ A such that x ∉ B.
- Remark: 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 also an element of B)
- A ⊆ D (every element of A is also an element of D, and also note that every element of D is in A so D ⊆ A)
- A is not a subset of C (because element 5 of A is not in C).
📌 Example: The set of integers “Z” is a subset of the set of Rational Number “Q”, since every integer ‘n’ could be written as: n = n/1 ∈ Q. Hence Z ⊆ Q.
Proper Subset
Let A and B be sets. A is a proper subset of 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, and is denoted as A ⊂ B.
📌 Example: Let A = {1, 3, 5}, B = {1, 2, 3, 5}. Then A ⊂ B (because there is an element 2 of B which is not in A).
Equal Sets
Two sets A and B are equal if, and only if, every element of A is in B and every element of B is in A, and is denoted A = B. Symbolically: A = B iff A ⊆ B and B ⊆ A.
📌 Example: Let A = {1, 2, 3, 6}, B = the 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.
Null Set
A set which contains no element is called a null set, or an empty set or a void set. It is denoted by the Greek letter ∅ (phi) or { }.
📌 Example: A = {x | x is a person taller than 10 feet} = ∅ 📌 Example: B = {x | x² = 4, x is odd} = ∅
🔑 Definition — Null Set: A set with no elements. Remark: ∅ is regarded as a subset of every set.
Exercise: Determining Truth of Statements
Determine whether each of the following statements is true or false.
- x ∈ {x} → TRUE (x is the member of the singleton set {x})
- {x} ⊆ {x} → TRUE (Every set is the subset of itself. Note that every set has necessarily two subsets: ∅ and the set itself. These are known as Improper subsets; any other subset is called a Proper Subset.)
- {x} ∈ {x} → FALSE ( {x} is not the member of {x} because the only member is x)
- {x} ∈ {{x}} → TRUE
- ∅ ⊆ {x} → TRUE
- ∅ ∈ {x} → FALSE
Universal Set
The set of all elements under consideration is called the Universal Set. The Universal Set is usually denoted by U.
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 the other sets are represented by disks lying within the rectangle.
Finite and Infinite Sets
A set S is said to be finite if it contains exactly m distinct elements where m denotes some non-negative integer. In such case we write |S| = m or n(S) = m. A set is said to be infinite if it is not finite.
📌 Examples:
- The set S of letters of English alphabets is finite and |S| = 26
- The null set ∅ has no elements, is finite and |∅| = 0
- The set of positive integers {1, 2, 3,...} is infinite.
Membership Table
A membership table is a table displaying the membership of elements in sets. To indicate that an element is in a set, a 1 is used; to indicate that an element is not in a set, a 0 is used. Membership tables can be used to prove set identities.
The table below is the Membership table for the Complement of A (Aᶜ).
| A | Aᶜ |
|---|---|
| 1 | 0 |
| 0 | 1 |
If an element is the member of A, then it cannot be the member of Aᶜ; thus where the table has 1 for A, in that row it has 0 in Aᶜ.
⭐ Key Takeaways
A set is a well-defined collection of distinct objects, and its elements can be described using Tabular, Descriptive, or Set Builder forms. A subset (A⊆B) means every element of A is in B, while a proper subset (A⊂B) requires at least one extra element in B. For two sets to be equal, each must be a subset of the other (A=B iff A⊆B and B⊆A). The null set (∅) is a universal subset, contained within every set, and the Universal Set (U) contains all elements under consideration.
🧠 Quick Revision Questions
- What are the three forms used to represent a set, and how do they differ?
- Give the formal definition and symbolic representation of a subset.
- How do you determine if two sets A and B are equal?
- Why is the Empty Set (∅) considered a subset of every set?
- What is the difference between a finite set and an infinite set? Provide one example of each.
📘 Lecture 7 — Sets Continued
📖 Overview: This lecture continues the study of set theory, introducing fundamental set operations: union, intersection, difference, and complement. It explains how to represent these operations using Venn diagrams and membership tables, and demonstrates how to prove set identities through both visual and tabular methods, which are essential for logical reasoning in mathematics.
🗂️ Topics Covered
The lecture covers the definitions, symbolic representations, Venn diagrams, and membership tables for union, intersection, difference, and complement of sets. It includes detailed worked examples solving exercises involving enumeration of sets and set operations, and concludes with proving set identities using 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): A ∪ B = {x ∈ U | x ∈ A or x ∈ B}
📐 Formula: A ∪ B = {x ∈ U | x ∈ A or x ∈ B} → The set of elements that are in A, in B, or in both.
📌 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: The union A ∪ B is the shaded area covering all of set A, all of set B, and their overlap.
Remarks:
- A ∪ B = B ∪ A (union is commutative).
- A ⊆ A ∪ B and B ⊆ A ∪ B.
Membership Table for Union: This table (1 = element present, 0 = absent) shows that the union is 1 if either A or B is 1, and 0 only if both are 0. It is similar to the truth table for the 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): 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: The intersection A ∩ B is the shaded area where sets A and B overlap.
Remarks:
- A ∩ B = B ∩ A (intersection is commutative).
- A ∩ B ⊆ A and A ∩ B ⊆ B.
- If A ∩ B = ∅, then A and B are called disjoint sets.
Membership Table for Intersection: The intersection is 1 only when both A and B are 1. This table is similar to the truth table for the 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): 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: The set difference A – B is the part of set A that does not overlap with set B.
Remarks:
- A – B ≠ B – A (set difference is not commutative).
- A – B ⊆ A.
- A – B, A ∩ B, and B – A are mutually disjoint sets.
Membership Table for Set Difference: The set difference A – B is 1 only when A is 1 and B is 0. This table is similar to the truth table for ~(p → q). 💡 Why this matters: Understanding the membership table for set difference helps connect set operations to logical implications.
COMPLEMENT:
Let A be a subset of universal set U. The complement of A is the set of all elements in U that do not belong to A, and is denoted A̅, A' or Aᶜ.
🔑 Definition — Complement (Aᶜ): 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: The complement Aᶜ is the area of the universal set U outside of set A.
Remarks:
- Aᶜ = U – A.
- A ∩ Aᶜ = ∅.
- A ∪ Aᶜ = U.
Membership Table for Complement: The complement is 1 when A is 0, and 0 when A is 1. This table is similar to the truth table for the logical connective negation (~).
EXERCISE (Enumerating Sets and Operations):
Let U = {1, 2, 3, ..., 10}, X = {1, 2, 3, 4, 5}, Y = {y | y = 2x, x ∈ X}, Z = {z | z² – 9z + 14 = 0}
First, enumerate the sets: Y = {2, 4, 6, 8, 10}, Z = {2, 7} (since the equation z² – 9z + 14 = 0 factors to (z-2)(z-7)=0).
- X ∩ Y = {1, 2, 3, 4, 5} ∩ {2, 4, 6, 8, 10} = {2, 4}
- Y ∪ Z = {2, 4, 6, 8, 10} ∪ {2, 7} = {2, 4, 6, 7, 8, 10}
- X – Z = {1, 2, 3, 4, 5} – {2, 7} = {1, 3, 4, 5}
- Yᶜ = U – Y = {1, 2, 3, ..., 10} – {2, 4, 6, 8, 10} = {1, 3, 5, 7, 9}
- Xᶜ – Zᶜ: First, Xᶜ = {6, 7, 8, 9, 10}. Zᶜ = {1, 3, 4, 5, 6, 8, 9, 10}. So Xᶜ – Zᶜ = {7}.
- (X – Z)ᶜ = U – (X – Z) = {1, 2, ..., 10} – {1, 3, 4, 5} = {2, 6, 7, 8, 9, 10}
Note: (X – Z)ᶜ ≠ Xᶜ – Zᶜ.
EXERCISE (Venn Diagram and Set Operations):
Given U = {x | x ∈ Z, 0 ≤ x ≤ 10}, P = {x | x is a prime number}, Q = {x | x² < 70}.
First, write sets in tabular form: U = {0, 1, 2, 3, ..., 10}, P = {2, 3, 5, 7}, Q = {0, 1, 2, 3, 4, 5, 6, 7, 8}.
(i) Venn Diagram: P is placed as a subset within Q, with elements {2, 3, 5, 7}. Q contains additional elements {0, 1, 4, 6, 8}. Elements {9, 10} are outside both P and Q but inside U.
(ii) Pᶜ ∩ Q = {0, 1, 4, 6, 8, 9, 10} ∩ {0, 1, 2, 3, 4, 5, 6, 7, 8} = {0, 1, 4, 6, 8}
EXERCISE (Finding Set A):
Let U = {1, 2, 3, 4, 5}, C = {1, 3}, and A and B are non-empty sets.
(i) A ∪ B = U, A ∩ B = ∅, and B = {1} Solution: Since A and B are disjoint and their union is U, A = Bᶜ. A = {1}ᶜ = {2, 3, 4, 5}.
(ii) A ⊂ B and A ∪ B = {4, 5} Solution: When A ⊂ B, then A ∪ B = B = {4, 5}. Since A is a proper subset of B, A = {4} or A = {5}.
(iii) A ∩ B = {3}, A ∪ B = {2, 3, 4} and B ∪ C = {1, 2, 3} Solution: Using a Venn diagram analysis, 3 is in the intersection. 1 is in C but not in A ∪ B, so it is only in C. 4 is in A ∪ B but not in B ∪ C, so it is only in A. 2 is in B ∪ C and A ∪ B but not in A ∩ B nor in C, so 2 is only in B. Therefore, A = {3, 4} and B = {2, 3}.
(iv) A ∩ B = ∅, B ∩ C = ∅, A ∪ B = {1, 2}. Also C = {1, 3} Solution: Since B and C are disjoint and C contains 1 and 3, A ∪ B = {1, 2}. So A = {1} and B = {2}.
PROVING SET IDENTITIES BY VENN DIAGRAMS:
Three identities are proven using Venn diagrams with numbered regions.
(i) A – (A – B) = A ∩ B: Diagrams show that the region for A – (A – B) (the part of A not in A – B) is identical to the region A ∩ B.
(ii) (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ: The complement of the intersection (all regions outside A ∩ B) matches the union of the complements (all regions not in A combined with all regions not in B).
(iii) A – B = A ∩ Bᶜ: The region of A outside B (set difference) is the same as the intersection of A with the complement of B.
PROVING SET IDENTITIES BY MEMBERSHIP TABLE:
The same three identities are proven using membership tables (1 = in set, 0 = not in set).
(i) A – (A – B) = A ∩ B:
| A | B | A-B | A-(A-B) | A∩B |
|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| The last two columns are identical, proving the identity. |
(ii) (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ:
| A | B | A∩B | (A∩B)ᶜ | Aᶜ | Bᶜ | Aᶜ∪Bᶜ |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| The fourth and last columns are identical, proving the identity. |
(iii) A – B = A ∩ Bᶜ:
| A | B | A-B | Bᶜ | A∩Bᶜ |
|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| The third and fifth columns are identical, proving the identity. |
⭐ Key Takeaways
The four fundamental set operations—union (∪), intersection (∩), difference (-), and complement (ᶜ)—each have precise definitions, symbolic notations, and visual representations in Venn diagrams. Membership tables provide a systematic way to verify set relationships, directly analogous to truth tables in logic. Key properties to remember include: union and intersection are commutative; set difference is not commutative; and De Morgan's Law (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ. Set identities can be proven either visually through Venn diagrams or rigorously through membership tables, and both methods are valid.
🧠 Quick Revision Questions
- What is the union of A = {1, 3, 5} and B = {2, 4, 6}? Draw its Venn diagram.
- If A and B are disjoint sets, what is A ∩ B? Give an example.
- What is the difference between A – B and B – A? Give an example to show they are not equal.
- State and prove De Morgan's Law (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ using a membership table.
- If U = {1, 2, 3, 4, 5, 6}, A = {2, 4, 6}, and B = {3, 4, 5}, find: (a) Aᶜ, (b) A – B, (c) (A ∪ B)ᶜ.
📘 Lecture 8 — Sets Continued
📖 Overview: This lecture extends the study of sets to ordered pairs and n-tuples, introduces the Cartesian product of sets, and defines binary relations along with their representations. These concepts are fundamental for understanding functions, relations, and discrete structures in mathematics and computer science.
🗂️ Topics Covered
The lecture covers ordered pairs and ordered n-tuples with equality conditions, Cartesian products of two and more sets, binary relations from one set to another, domain and range of relations, and multiple ways to represent relations including coordinate diagrams, arrow diagrams, directed graphs, and matrix representation.
📝 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: A pair of elements where the order matters; (a, b) = (c, d) iff a = c and b = d.
📌 Example: Find x and y given (2x, x + y) = (6, 2)
- Two ordered pairs are equal if corresponding components are equal
- Hence: 2x = 6 and x + y = 2
- Solving: x = 3, 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ₙ. 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 = 1, 2, ..., n.
🔑 Definition — Ordered n-tuple: A sequence of n elements where order matters; equality requires matching elements at each position.
CARTESIAN PRODUCT OF TWO SETS:
Let A and B be sets. The Cartesian product of A and B, denoted A × B (read "A cross B"), is the set of all ordered pairs (a, b), where a is in A and b is in B.
📐 Formula: A × B = {(a, b) | a ∈ A and b ∈ B}
- If set A has m elements and set B has n elements, then A × B has m × n elements.
📌 Example: Let A = {1, 2}, B = {a, b, c}
- 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:
- A × B ≠ B × A for non-empty and unequal sets A and B
- A × ∅ = ∅ × A = ∅
- |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ₙ.
📐 Formula: A₁ × A₂ × ... × Aₙ = {(a₁, a₂, ..., aₙ) | aᵢ ∈ Aᵢ, for i = 1, 2, ..., n}
BINARY RELATION:
Let A and B be sets. A (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 a R b. Otherwise if (a, b) ∉ R, we write a R̸ b.
🔑 Definition — Binary Relation: Any subset of the Cartesian product A × B; elements (a,b) in the subset indicate that a is related to b.
📌 Example: Let A = {1, 2}, B = {1, 2, 3}
- A × B = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)}
- 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 Dom(R).
🔑 Definition — Domain of a Relation: 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 a Relation: Ran(R) = {b ∈ B | (a,b) ∈ R}
📌 Exercise: Let A = {1, 2}, B = {1, 2, 3}, define R = {(a, b) ∈ A × B | a < b}
- 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.
📌 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. 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}
- A = {0,1}, B = {1}, A × B = {(0,1), (1,1)}
- All subsets: R₁ = ∅, R₂ = {(0,1)}, R₃ = {(1,1)}, R₄ = {(0,1), (1,1)} = A × B
- If |A| = m and |B| = n, the total number of relations from A to B is 2^(m×n)
RELATION ON A SET:
A relation on the set A is a relation from A to A. In other words, a relation on a set A is a subset of A × A.
📌 Example: Let A = {1, 2, 3, 4} Define R on A as (a,b) ∈ R iff a divides b (written a|b) R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)}
Remarks:
- A × A is known as the universal relation
- ∅ is known as the empty relation
📌 Exercise: Define E on Z as m E n ⇔ m – n is even
- 0E0? Yes (0-0=0 is even)
- 5E2? No (5-2=3 is not even)
- (6,6) ∈ E? Yes (6-6=0 is even)
- (-1,7) ∈ E? Yes (-1-7=-8 is even)
- For any even integer n, nE0 since n-0=n is even
COORDINATE DIAGRAM (GRAPH) OF A RELATION:
Let A = {1, 2, 3} and B = {x, y} with R = {(1,y), (2,x), (2,y), (3,x)}. The relation can be represented in a coordinate diagram using x-axis for A and y-axis for B, plotting each ordered pair as a point.
📌 Example: Draw the graph of C from R to R defined as (x,y) ∈ C ⇔ x² + y² = 1 All ordered pairs satisfy x² + y² = 1, which is the equation of a unit circle centered at the origin. The graph is a circle with radius 1, limited to -1 ≤ x ≤ 1 and -1 ≤ y ≤ 1.
ARROW DIAGRAM OF A RELATION:
Let A = {1, 2, 3}, B = {x, y} and R = {(1,y), (2,x), (2,y), (3,x)}. The arrow diagram shows elements of A on the left, elements of B on the right, with arrows connecting related elements.
DIRECTED GRAPH OF A RELATION:
Let A = {0, 1, 2, 3} and R = {(0,0), (1,3), (2,1), (2,2), (3,0), (3,1)} be a relation on A. The directed graph shows elements as vertices (circles labeled with elements) and ordered pairs as directed arrows from the first to the second element. A loop at a vertex represents a pair (a,a).
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 matrix M by:
- m(i,j) = 1 if (aᵢ, bⱼ) ∈ R
- m(i,j) = 0 if (aᵢ, bⱼ) ∉ R for i = 1, 2, ..., n and j = 1, 2, ..., m
📐 Formula: Relation Matrix M with entries m(i,j) = 1 if related, 0 otherwise.
📌 Example: A = {1, 2, 3}, B = {x, y}, R = {(1,y), (2,x), (2,y), (3,x)} M = [ [0, 1], [1, 1], [1, 0] ] (3×2 matrix where rows represent A elements and columns represent B elements)
📌 Example: For matrix M = [ [1, 0, 1], [1, 0, 0], [0, 1, 1] ]
- Ordered pairs: R = {(1,1), (1,3), (2,1), (3,2), (3,3)}
- Directed graph has vertices 1, 2, 3 with arrows: 1→1, 1→3, 2→1, 3→2, 3→3
📌 Exercise: Let A = {2, 4} and B = {6, 8, 10}, define R and S from A to B:
- x R y ⇔ x | y (x divides y)
- x S y ⇔ y – 4 = x
- A × B = {(2,6), (2,8), (2,10), (4,6), (4,8), (4,10)}
- R = {(2,6), (2,8), (2,10), (4,8)}
- S = {(2,6), (4,8)}
- R ∪ S = {(2,6), (2,8), (2,10), (4,8)} = R
- R ∩ S = {(2,6), (4,8)} = S
💡 Why this matters: Relations formalize connections between elements of sets and are the foundation for functions, databases, graph theory, and many computer science applications like social networks and search engines.
⭐ Key Takeaways
You must master ordered pairs and their equality conditions, as they form the basis for Cartesian products and relations. The Cartesian product A × B has |A| × |B| elements, and any subset of it is a binary relation. Every relation has a domain (first elements) and range (second elements), and can be represented in five ways: as a set of ordered pairs, coordinate diagram, arrow diagram, directed graph, or matrix. The total number of relations from A to B equals 2^(|A|×|B|). Understanding these representations is essential for visualizing and computing with relations in discrete mathematics.
🧠 Quick Revision Questions
- Given (3x, x + 2y) = (9, 5), find the values of x and y.
- If A = {a, b} and B = {1, 2}, list all elements of A × B and B × A. Are they equal? Why or why not?
- How many distinct binary relations can be defined from a set with 2 elements to a set with 3 elements?
- For the relation R = {(1,2), (2,3), (3,1), (1,1)} on A = {1, 2, 3}, find Dom(R), Ran(R), and draw the directed graph.
- Write the matrix representation for the relation R = {(a,x), (b,y), (c,x)} from A = {a, b, c} to B = {x, y}.
📘 Lecture 9 — Sets Continued
📖 Overview: This lecture covers the fundamental properties of binary relations: reflexivity, symmetry, and transitivity. These properties are essential for understanding equivalence relations and congruence, which have applications in mathematics, computer science, and logic.
🗂️ Topics Covered
The lecture defines and illustrates reflexive relations (every element related to itself), symmetric relations (if a is related to b then b is related to a), and transitive relations (if a is related to b and b is related to c then a is related to c). Each property is explained with set notation, directed graphs, and matrix representations. Several worked examples test these properties on specific relations including the null/universal relations, the "less than" relation on real numbers, the "odd product" relation on positive integers, the "divides" relation on integers, and the "same first name" relation. The lecture concludes by combining all three properties to define an equivalence relation and introduces congruence modulo d as a key example, proving it forms an equivalence relation on the integers.
📝 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. Equivalently, aRa. That is, each element of A is related to itself.
🔑 Definition — Reflexive Relation: A relation R on a set A is reflexive if every element of A is related to itself, meaning (a,a) ∈ R for all a ∈ A.
REMARK: 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)} R₂ = {(1, 1), (1, 4), (2, 2), (3, 3), (4, 3)} R₃ = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)} R₄ = {(1, 3), (2, 2), (2, 4), (3, 1), (4, 4)}
- R₁ is reflexive, since (a, a) ∈ R₁ for all a ∈ A.
- R₂ is not reflexive, because (4, 4) ∉ R₂.
- R₃ is reflexive, since (a, a) ∈ R₃ for all a ∈ A.
- R₄ is not reflexive, because (1, 1) ∉ R₄, (3, 3) ∉ R₄.
DIRECTED GRAPH OF A REFLEXIVE RELATION
The directed graph of every reflexive relation includes an arrow (loop) from every point to the point itself.
📌 Example: Using the same relations R₁-R₄ from above:
- R₁ is reflexive because at every point of the set A we have a loop in the graph.
- R₂ is not reflexive, as there is no loop at 4.
- R₃ is reflexive.
- R₄ is not reflexive, as there are no loops at 1 and 3.
💡 Why this matters: The directed graph provides a visual way to instantly check if a relation is reflexive — just look for a loop at every vertex.
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} is represented by the following matrix M and is reflexive:
M = 1 2 3 1 [1 0 1] 2 [0 1 0] 3 [0 1 1]
Since the main diagonal has 1, 1, 1 (all 1s), the relation is reflexive.
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 Relation: A relation R on a set A is symmetric if whenever a is related to b, then b is also related to a.
REMARK: 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)} R₂ = {(1, 1), (2, 2), (3, 3), (4, 4)} R₃ = {(2, 2), (2, 3), (3, 4)} R₄ = {(1, 1), (2, 2), (3, 3), (4, 3), (4, 4)}
- R₁ is symmetric because for every ordered pair (a,b) in R₁, we have (b,a) in R₁. For example, we have (1,3) in R₁ and we have (3,1) in R₁.
- R₂ is also symmetric (vacuously true — no pairs break the condition).
- R₃ is not symmetric, because (2,3) ∈ R₃ but (3,2) ∉ R₃.
- R₄ is 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.
📌 Example: Using the same relations:
- R₁ is symmetric, R₂ is symmetric.
- R₃ is not symmetric since there are arrows from 2 to 3 and from 3 to 4 but not conversely.
- R₄ is not symmetric since there is an arrow from 4 to 3 but no arrow from 3 to 4.
MATRIX REPRESENTATION OF A SYMMETRIC RELATION
Let A = {a₁, a₂, ..., aₙ}. A 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 i-th row are the same as the elements in the i-th 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 = 1 2 3 1 [0 0 1] 2 [0 1 0] 3 [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.
🔑 Definition — Transitive Relation: A relation R on a set A is transitive if whenever a is related to b and b is related to c, then a is related to c.
REMARK: 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)} R₂ = {(1, 2), (1, 4), (2, 3), (3, 4)} R₃ = {(2, 1), (2, 4), (2, 3), (3,4)}
- R₁ is transitive because (1, 1), (1, 2) are in R and then (1,2) is also there (satisfying the condition). Similarly checked for other ordered pairs.
- R₂ is not transitive since (1,2) and (2,3) ∈ R₂ but (1,3) ∉ R₂.
- R₃ is 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.
📌 Example: Using the same relations:
- R₁ is transitive.
- R₂ is not transitive since there is an arrow from 1 to 2 and from 2 to 3 but no arrow from 1 to 3 directly.
- R₃ is transitive.
EXERCISE: Null and Universal Relations
Let A = {1, 2, 3, 4} and define the null relation ∅ and universal relation A × A on A. Test these relations for reflexive, symmetric and transitive properties.
Reflexive: (i) ∅ is not reflexive since (1,1), (2,2), (3,3), (4,4) ∉ ∅. (ii) A × A is reflexive since (a,a) ∈ A × A for all a ∈ A.
Symmetric: (i) 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. (ii) 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: (i) 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. (ii) The universal relation A × A is transitive for it contains all ordered pairs of elements of A. Accordingly, if (a,b) ∈ A × A and (b,c) ∈ A × A then (a,c) ∈ A × A as well.
EXERCISE: Relation on {0,1,2}
Let A = {0, 1, 2} and R = {(0,2), (1,1), (2,0)} be a relation on A.
- Is R reflexive? Symmetric? Transitive?
- Which ordered pairs are needed in R to make it a reflexive and transitive relation?
Solution:
-
R is not reflexive, since 0 ∈ A but (0,0) ∉ R and also 2 ∈ A but (2,2) ∉ R. R is clearly symmetric. R is not transitive, since (0,2) & (2,0) ∈ R but (0,0) ∉ R.
-
For R to be reflexive, it must contain ordered pairs (0,0) and (2,2). For R to be transitive, we note (0,2) and (2,0) ∈ but (0,0) ∉ R. Also (2,0) and (0,2) ∈ R but (2,2) ∉ R. Hence (0,0) and (2,2) are needed in R to make it a transitive relation.
EXERCISE: "Less Than" Relation
Define a relation L on the set of real numbers ℝ as follows: for all x, y ∈ ℝ, x L y ⇔ x < y.
a. Is L reflexive? No, because x < x is false for any real number x. b. Is L symmetric? No, because if x < y then y < x is false (e.g., 0 < 1 but 1 < 0 is false). c. Is L transitive? Yes, because if x < y and y < z, then x < z (by transitive law of order of real numbers).
EXERCISE: "Odd Product" Relation
Define a relation R on the set of positive integers ℤ⁺ as follows: for all a, b ∈ ℤ⁺, a R b iff a × b is odd.
Solution: Recall that the product of two positive integers is odd if and only if both of them are odd.
a. Reflexive: R is not reflexive, because 2 ∈ ℤ⁺ but 2 R 2 is false since 2 × 2 = 4 which is not odd. b. Symmetric: R is symmetric, because if a R b then a × b is odd or equivalently b × a is odd (since b × a = a × b) ⇒ b R a. c. 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 ℤ defined as: for all m, n ∈ ℤ, m D n ⇔ m|n. Determine whether D is reflexive, symmetric or transitive.
Reflexive: Let m ∈ ℤ. Since every integer divides itself, m|m ∀ m ∈ ℤ, therefore m D m ∀ m ∈ ℤ. Accordingly, D is reflexive.
Symmetric: Let m, n ∈ ℤ and suppose m D n. By definition, this means m|n. Clearly, it is not necessary that n|m. For example, 2|4 but 4 does not divide 2. Accordingly, if m D n then n D m is not true ∀ m, n ∈ ℤ. Hence D is not symmetric.
Transitive: Let m, n, p ∈ ℤ and suppose m D n and n D p. Now m D n ⇒ m|n ⇒ n/m is an integer. Also n D p ⇒ n|p ⇒ p/n is an integer. We note p/m = (p/n) × (n/m) = (an integer) × (an integer) = an integer. This implies m|p and so m D p. Thus if m D n and n D p then m D p ∀ m, n, p ∈ ℤ. Hence D is transitive.
EXERCISE: "Same First Name" Relation
Let A be the set of people living in the world today. A binary relation R is defined on A as follows: for all p, q ∈ A, p R q ⇔ p has the same first name as q.
a. Reflexive: Since every person has the same first name as his/her self, for all p ∈ A, pRp. Thus, R is reflexive. b. Symmetric: Let p, q ∈ A and suppose pRq. This means p has the same first name as q ⇔ q has the same first name as p ⇔ q R p. Thus if pRq then qRp ∀ p,q ∈ A. Hence R is symmetric. c. Transitive: Let p, q, r ∈ A and suppose p R q and q R r. Now pRq ⇔ p has the same first name as q and qRr ⇔ q has the same first name as r. Consequently, p has the same first name as r ⇔ p R r. Thus, if pRq and qRs then pRr ∀ p, q, r ∈ A. Hence R 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 that 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.
🔑 Definition — Congruence Modulo d: m is congruent to n modulo d if d divides (m - n).
📌 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 is NOT congruent to 4 (mod 3).
EXERCISE: Congruence Mod 3 is an Equivalence Relation
Define a relation R on the set of all integers ℤ as follows: for all integers m and n, m R n ⇔ m ≡ n (mod 3). Prove that R is an equivalence relation.
-
R is reflexive: For all m ∈ ℤ, m R m means m ≡ m (mod 3). Since m - m = 0 = 3×0, 3|(m-m), and so m ≡ m (mod 3) ⇔ mRm. Hence R is reflexive.
-
R is symmetric: For all m, n ∈ ℤ, 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 ∈ ℤ ⇒ 3|(n-m) ⇒ n ≡ m (mod 3) ⇒ nRm. Hence R is symmetric.
-
R is transitive: For all m, n, p ∈ ℤ, 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 ∈ ℤ. Adding: (m-n) + (n-p) = 3r + 3s ⇒ m - p = 3(r + s), where r + s ∈ ℤ ⇒ 3|(m-p) ⇒ m ≡ p (mod 3) ⇔ mRp. Hence R is transitive.
R being reflexive, symmetric and transitive, is an equivalence relation.
⭐ Key Takeaways
For the exam, you must remember that a reflexive relation requires EVERY element of the set to have a loop (on itself), as shown by all 1s on the main diagonal of its matrix. A symmetric relation requires that for every arrow from a to b, there is also an arrow back from b to a, making the matrix symmetric across the diagonal. A transitive relation requires that if there is a path from a to b and from b to c, then there must be a direct arrow from a to c. The null relation (empty set) is trivially symmetric and transitive but never reflexive, while the universal relation (all possible pairs) is always reflexive, symmetric, and transitive. Finally, an equivalence relation combines all three properties, and congruence modulo d (m ≡ n mod d if d divides m-n) is the classic example of an equivalence relation, as proven by checking reflexivity (m-m=0), symmetry (if d|(m-n) then d|(n-m)), and transitivity (if d|(m-n) and d|(n-p) then d|(m-p)).
🧠 Quick Revision Questions
- If a relation's matrix has 1,0,0 in the first column and 0,1,0 in the second column and 0,0,1 in the third column, is the relation reflexive? Why or why not?
- What does it mean for a relation to be "vacuously symmetric"? Give an example.
- For the relation R = {(1,2), (2,3), (1,3)} on set A = {1,2,3}, is R transitive? What if we remove (1,3)?
- What three conditions must a relation satisfy to be an equivalence relation? Prove that the "same age" relation on a group of people is an equivalence relation.
- Is 47 ≡ 11 mod 4? Show your work.
📘 Lecture 10 — Sets Continued
📖 Overview: This lecture explores the properties of binary relations on sets—reflexivity, symmetry, and transitivity—and examines how these properties are preserved under set operations like intersection and union. It also introduces irreflexive and antisymmetric relations, and culminates in the definition of a partial order relation, a fundamental concept in discrete mathematics.
🗂️ Topics Covered
The lecture begins by proving that the intersection of two reflexive, symmetric, or transitive relations retains those properties, and shows via counterexample that union does not preserve transitivity. It then defines irreflexive relations with directed graph and matrix representations, defines antisymmetric relations with graph and matrix representations, and finally defines and illustrates partial order relations through multiple examples including “less than or equal to,” the subset relation, the divisibility relation, and the relation defined by b = a^r.
📝 Lecture Summary
EXERCISE
Suppose R and S are binary relations on a set A. The lecture asks whether R ∩ S is reflexive, symmetric, or transitive if R and S individually possess those properties.
a. R ∩ S is reflexive: Suppose R and S are reflexive. Then ∀ a ∈ A, (a,a) ∈ R and (a,a) ∈ S. By definition of intersection, ∀ a ∈ A, (a,a) ∈ R ∩ S. Accordingly, R ∩ S is reflexive.
b. R ∩ S is symmetric: Suppose R and S are symmetric. To prove R ∩ S is symmetric, show that ∀ a,b ∈ A, if (a,b) ∈ R ∩ S then (b,a) ∈ R ∩ S. Suppose (a,b) ∈ R ∩ S ⇒ (a,b) ∈ R and (a,b) ∈ S. Since R is symmetric, (b,a) ∈ R. Similarly, since S is symmetric, (b,a) ∈ S. Thus (b,a) ∈ R and (b,a) ∈ S ⇒ (b,a) ∈ R ∩ S. Accordingly, R ∩ S is symmetric.
c. R ∩ S is transitive: Suppose R and S are transitive. To prove R ∩ S is transitive, show that ∀ a,b,c ∈ A, if (a,b) ∈ R ∩ S and (b,c) ∈ R ∩ S then (a,c) ∈ R ∩ S. Suppose (a,b) ∈ R ∩ S and (b,c) ∈ R ∩ S ⇒ (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. Hence (a,c) ∈ R and (a,c) ∈ S ⇒ (a,c) ∈ R ∩ S. Accordingly, R ∩ S is transitive.
EXAMPLE:
Let A = {1,2,3,4} and let R and S be transitive binary relations on A defined as: R = {(1,2), (1,3), (2,2), (3,3), (4,2), (4,3)} and S = {(2,1), (2,4), (3,3)} Then R ∪ S = {(1,2), (1,3), (2,1), (2,2), (2,4), (3,3), (4,2), (4,3)}. We 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, R is irreflexive if no element in A is related to itself by R.
🔑 Definition — Irreflexive Relation: A relation R on a set A is irreflexive if and only if for every element a in A, the pair (a,a) is NOT in R.
💡 Why this matters: Irreflexivity is the opposite of reflexivity—while reflexive means every element relates to itself, irreflexive means NO element relates to itself.
REMARK: R is not irreflexive iff there is an element a ∈ A such that (a,a) ∈ R.
EXAMPLE: Let A = {1,2,3,4} and define the following relations on A: R₁ = {(1,3), (1,4), (2,3), (2,4), (3,1), (3,4)} R₂ = {(1,1), (1,2), (2,1), (2,2), (3,3), (4,4)} R₃ = {(1,2), (2,3), (3,3), (3,4)} Then R₁ is irreflexive since no element of A is related to itself in R₁, i.e., (1,1)∉R₁, (2,2)∉R₁, (3,3)∉R₁, (4,4)∉R₁. R₂ is not irreflexive since all elements of A are related to themselves in R₂. R₃ is not irreflexive since (3,3) ∈ R₃. Note that R₃ is not reflexive. A relation may be neither reflexive nor irreflexive.
DIRECTED GRAPH OF AN IRREFLEXIVE RELATION
Let R be an irreflexive relation on a set A. Then by definition, no element of A is related to itself by R. Accordingly, there is no loop at each point of A in the directed graph of R.
EXAMPLE: Let A = {1,2,3} and R = {(1,3), (2,1), (2,3), (3,2)} be represented by the directed graph. [No loops at any vertex.]
MATRIX REPRESENTATION OF AN IRREFLEXIVE RELATION
Let R be an irreflexive relation on a set A. Then by definition, no element of A is related to itself by R. Since the self-related elements are represented by 1's on the main diagonal of the matrix representation of the relation, for irreflexive relation R, the matrix will contain all 0's in its main diagonal.
EXAMPLE: Let A = {1,2,3} and R = {(1,3), (2,1), (2,3), (3,2)} be represented by the matrix: M = 1 2 3 1 [0 0 1] 2 [1 0 1] 3 [0 1 0] Then R is irreflexive, since all elements in the main diagonal are 0's.
EXERCISE
Let R be the relation on the set of integers Z defined as: for all a,b ∈ Z, (a,b) ∈ R ⇔ a > b. Is R irreflexive?
SOLUTION: R is irreflexive if for all a ∈ Z, (a,a) ∉ R. Now by the definition of given relation R, 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.
🔑 Definition — Antisymmetric Relation: A relation R on a set A is antisymmetric if whenever (a,b) and (b,a) are both in R, then a and b must be the same element.
REMARK:
- R is not anti-symmetric iff there are elements a and b in A such that (a,b) ∈ R and (b,a) ∈ R but a ≠ b.
- The properties of being symmetric and being anti-symmetric are not negatives of each other. A relation can be both, neither, or one but not the other.
💡 Why this matters: A relation can be both symmetric and antisymmetric (like equality) or neither (like the example with (1,3) and (3,1) but 1≠3).
EXAMPLE: Let A = {1,2,3,4} and define the following relations on A: R₁ = {(1,1), (2,2), (3,3)} R₂ = {(1,2), (2,2), (2,3), (3,4), (4,1)} R₃ = {(1,3), (2,2), (2,4), (3,1), (4,2)} R₄ = {(1,3), (2,4), (3,1), (4,3)}
R₁ is anti-symmetric and symmetric (only pairs are same elements). R₂ is anti-symmetric but not symmetric because (1,2) ∈ R₂ but (2,1) ∉ R₂. R₃ is not anti-symmetric since (1,3) and (3,1) ∈ R₃ but 1 ≠ 3. Note that R₃ is symmetric. R₄ is neither anti-symmetric because (1,3) and (3,1) ∈ R₄ but 1 ≠ 3, nor symmetric because (2,4) ∈ R₄ but (4,2) ∉ R₄.
DIRECTED GRAPH OF AN ANTISYMMETRIC RELATION
Let R be an anti-symmetric relation on a set A. Then by definition, no two distinct elements of A are related to each other in both directions. Accordingly, there is no pair of arrows between two distinct elements of A in the directed graph of R.
EXAMPLE: Let A = {1,2,3} and R = {(1,1), (1,2), (2,3), (3,1)}. R is anti-symmetric, since there is no pair of arrows between two distinct points in A. (Any two distinct points have at most one arrow between them.)
MATRIX REPRESENTATION OF AN ANTISYMMETRIC RELATION
Let R be an anti-symmetric relation on a set A = {a₁, a₂, ..., aₙ}. Then if (aᵢ, aⱼ) ∈ R for i ≠ j, then (aⱼ, aᵢ) ∉ R. Thus in the matrix representation of R, there is a 1 in the iᵗʰ row and jᵗʰ column iff the jᵗʰ row and iᵗʰ column contains 0, and vice versa.
EXAMPLE: Let A = {1,2,3} and R = {(1,1), (1,2), (2,3), (3,1)} on A be represented by the matrix: M = 1 2 3 1 [1 1 0] 2 [0 0 1] 3 [1 0 0] Then R is anti-symmetric as shown by the form of matrix M.
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 Relation: A relation that is reflexive, antisymmetric, and transitive. The set with this relation is called a partially ordered set (poset).
EXAMPLE
Let R be the set of real numbers and define the "less than or equal to" on R as follows: for all real numbers x and y in R, x ≤ y ⇔ x < y or x = y. Show that ≤ is a partial order relation.
SOLUTION: ≤ is reflexive: For ≤ to be reflexive means that x ≤ x for all x ∈ R. But x ≤ x means that x < x or x = x, and x = x is always true. Hence under this relation every element is related to itself.
≤ is anti-symmetric: For ≤ to be anti-symmetric means that ∀ x,y ∈ R, if x ≤ y and y ≤ x, then x = y. This follows from the definition of ≤ and the trichotomy property, which says that "given any real numbers x and y, exactly one of the following holds: x < y or x = y or x > y."
≤ is transitive: For ≤ to be transitive means that ∀ x,y,z ∈ R, if x ≤ y and y ≤ z then x ≤ z. This follows from the definition of ≤ and the transitive property of order of real numbers.
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 follows: for all X,Y ∈ P(A), X ⊆ Y ⇔ ∀ x, if x ∈ X then x ∈ Y. Show that ⊆ is a partial order relation.
SOLUTION:
- ⊆ is reflexive: Let X ∈ P(A). Since every set is a subset of itself, X ⊆ X for all X ∈ P(A).
- ⊆ is anti-symmetric: Let X,Y ∈ P(A) and suppose X ⊆ Y and Y ⊆ X. Then by definition of equality of two sets, X = Y.
- ⊆ is transitive: Let X,Y,Z ∈ P(A) and suppose X ⊆ Y and Y ⊆ Z. Then by the transitive property of subsets, X ⊆ Z.
EXERCISE
Let "|" be the "divides" relation on a set A of positive integers. That is, for all a,b ∈ A, a|b ⇔ b = k·a for some integer k. Prove that | is a partial order relation on A.
SOLUTION:
-
"|" is reflexive: [Show ∀ a ∈ A, a|a] Suppose a ∈ A. Then a = 1·a, so a|a by definition of divisibility.
-
"|" is anti-symmetric: [Show ∀ a,b ∈ A, if a|b and b|a then a=b] Suppose a|b and b|a. By definition of divisibility, there are integers k₁ and k₂ such that b = k₁·a and a = k₂·b. Now b = k₁·a = k₁·(k₂·b) = (k₁·k₂)·b. Dividing both sides by b gives 1 = k₁·k₂. Since a,b are positive integers, k₁ and k₂ are both positive integers. The equation k₁·k₂ = 1 can hold only when k₁ = k₂ = 1. Thus a = k₂·b = 1·b = b.
-
"|" is transitive: [Show ∀ a,b,c ∈ A, if a|b and b|c then a|c] Suppose a|b and b|c. By definition of divisibility, there are integers k₁ and k₂ such that b = k₁·a and c = k₂·b. Now c = k₂·b = k₂·(k₁·a) = (k₂·k₁)·a = k₃·a where k₃ = k₂·k₁ is an integer ⇒ a|c.
Thus "|" is a partial order relation on A.
EXERCISE
Let R be the relation defined on the set of integers Z as follows: for all a,b ∈ Z, aRb iff b = aʳ for some positive integer r. Show that R is a partial order on Z.
SOLUTION: [R is reflexive]: For any a ∈ Z, a = a¹, so aRa.
[R is anti-symmetric]: Let a,b ∈ Z and suppose aRb and bRa. Then there are positive integers r and s such that b = aʳ and a = bˢ. Now a = bˢ = (aʳ)ˢ = aʳˢ ⇒ rs = 1. Since r and s are positive integers, this equation holds iff r = 1 and s = 1, and then a = b¹ = b.
[R is transitive]: Let a,b,c ∈ Z and suppose aRb and bRc. Then there are positive integers r and s such that b = aʳ and c = bˢ. Now c = bˢ = (aʳ)ˢ = aʳˢ = aᵗ (where t = rs is also a positive integer). Hence aRc.
Accordingly, R is a partial order relation on Z.
⭐ Key Takeaways
The intersection of two reflexive, symmetric, or transitive relations preserves those properties, but union does not necessarily preserve transitivity. An irreflexive relation has no self-related elements, shown by the absence of loops in its directed graph and all zeros on the main diagonal of its matrix. An antisymmetric relation prohibits bidirectional arrows between distinct elements, meaning its matrix cannot have 1's in mirror positions (i,j) and (j,i) for i≠j. A partial order relation requires reflexivity, antisymmetry, and transitivity simultaneously—key examples include ≤ on real numbers, ⊆ on power sets, and | (divisibility) on positive integers. Understanding these properties is essential for analyzing ordered structures in mathematics.
🧠 Quick Revision Questions
- If R and S are both reflexive relations on a set A, is R ∪ S necessarily reflexive? Explain why or why not.
- What condition must be met for a relation to be classified as irreflexive? How does this differ from not being reflexive?
- Give an example of a relation that is both symmetric and antisymmetric. What type of relation must this be?
- What three properties must a relation satisfy to be considered a partial order relation? Name one example from the lecture and one from real life.
- In the matrix representation of an antisymmetric relation, what pattern of 1's is forbidden?
📘 Lecture 11 — Relations and Functions
📖 Overview: This lecture formally defines functions as a special type of relation, distinguishing them from general binary relations through two essential properties. It covers how to identify functions from arrow diagrams, ordered pairs, and graphs, and introduces fundamental concepts like domain, co-domain, range, image, and inverse image, along with binary operations as a special type of function.
🗂️ Topics Covered
The lecture begins by defining a function as a relation with two specific conditions, then works through exercises identifying functions from various representations including ordered pairs and arrow diagrams. It then introduces the range of a function, the graph of a function and the vertical line test, followed by counting functions between finite sets and the concept of well-defined functions. The lecture concludes with the definition of image and inverse image of sets, several results about these operations, and an introduction to 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: (1) 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. (2) 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. X is the domain and Y is the co-domain of f. The unique element y of Y related to x by f is denoted f(x), called "f of x", the value of f at 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)} is NOT a function because 5 ∈ X does not appear as the first element in any ordered pair.
- R₂ = {(2,4), (4,1), (4,2), (5,6)} is NOT a function because (4,1) and (4,2) have the same first element but different second elements.
- R₃ = {(2,4), (4,1), (5,6)} defines a function because it satisfies both conditions.
📌 Example: Let A = {4,5,6} and B = {5,6}. Define R and S from A to B: (x,y)∈R ⇔ x≥y; xSy ⇔ 2|(x-y).
- R = {(5,5), (6,5), (6,6)} — NOT a function because 4∈A is not related to any element of B.
- S = {(4,6), (5,5), (6,6)} — defines a function since each element of A is related to a unique element of B.
ARROW DIAGRAM OF A FUNCTION
The arrow diagram for a function f has two properties: (1) Every element of X has an arrow coming out of it. (2) No element of X has two arrows coming out pointing to two different elements of Y.
📌 Example: X = {a,b,c}, Y = {1,2,3,4}. A function f from X to Y defined by arrow diagram shows f(a)=2, f(b)=4, f(c)=2. This satisfies both conditions.
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}.
Key notes: (1) The range is always a subset of the co-domain. (2) The range is also called the image of X under f. (3) When y = f(x), x is called the pre-image of y. (4) The set of all elements of X related to some y∈Y is called the inverse image of y.
📌 Example: Determine the range of functions f, g, h 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).
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 graph of y = x² on R defines a function (vertical line test passes). The graph of x = y² does NOT define a function (a vertical line intersects at two points).
COUNTING FUNCTIONS
📌 Example: How many functions are there from a set with three elements to a set with four elements? Each of the 3 elements can map to any of the 4 elements in Y. Total functions = 4 × 4 × 4 = 4³ = 64.
📌 Example: A has m elements, B has n elements.
- Number of binary relations from A to B = 2^(mn)
- Number of functions from A to B = n^m
- Fraction of binary relations that are functions = n^m / 2^(mn)
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 if f: Z→R defined below is well defined:
- f(n) = ±n: NOT well defined (each integer has two images)
- f(n) = 1/(n²-4): NOT well defined (f(2) and f(-2) undefined)
- f(n) = √n: NOT well defined (imaginary values for n<0)
- f(n) = n²+1: Well defined (each integer has unique image)
📌 Example: h: Q→Q defined by h(m/n) = m/n. Claim: Not well defined. Since 1/2 = 2/4, h(1/2) = (1/2)/(1/2) = 1 but h(2/4) = (2/4)/(2/4) = 1 ≠ 1/2? Wait — proper evaluation: h(1/2) = 1/2 divided by 2 = 1, but h(2/4) = 2/4 divided by 4 = 1/8? Actually re-evaluating: h(m/n) = m/n where the denominator is n? For 1/2: h(1/2) = 1/2 = 0.5; for 2/4: h(2/4) = 2/4 = 0.5. But this gives same value? The lecture shows different results — the key point is that the rule is ambiguous for different representations of the same rational number, so h is NOT well defined.
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}.
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}.
SOME RESULTS
Let f: X→Y be a function. Let A,B ⊆ X and C,D ⊆ Y:
- If A⊆B then f(A) ⊆ f(B)
- f(A∪B) = f(A) ∪ f(B)
- f(A∩B) ⊆ f(A) ∩ f(B)
- f(A-B) ⊇ f(A) - f(B)
- If C⊆D then f⁻¹(C) ⊆ f⁻¹(D)
- f⁻¹(C∪D) = f⁻¹(C) ∪ f⁻¹(D)
- f⁻¹(C∩D) = f⁻¹(C) ∩ f⁻¹(D)
- 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.
🔑 Definition: A binary operation "*" on a set A is a function from A×A to A, i.e., : A×A → A. Usually written ab rather than *(a,b).
📌 Examples:
- "+" 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
- Union (∪), intersection (∩), set difference (−) are binary operations on P(A)
- Logical connectives ∨, ∧, →, ↔ are binary operations on {T,F}
- OR and AND gates are binary operations on {0,1}; NOT is a unary operation
💡 Why this matters: Binary operations are the foundation of algebraic structures like groups, rings, and fields, and are fundamental in computer arithmetic and logic circuit design.
⭐ Key Takeaways
A function is a special type of relation where every element of the domain maps to exactly one element of the co-domain — it must satisfy both the "every element maps" condition and the "unique image" condition. The vertical line test provides a quick graphical way to check if a relation is a function, while the well-defined condition ensures that equal inputs always produce equal outputs. The number of functions from an m-element set to an n-element set is n^m, which is a small fraction of all possible binary relations (2^(mn)). Binary operations are simply functions from A×A to A, unifying the concepts of functions and operations in mathematics.
🧠 Quick Revision Questions
- What are the two properties that a relation must satisfy to be called a function?
- If f: {1,2,3} → {a,b,c,d} and f(1)=a, f(2)=b, what condition is violated that makes this NOT a function?
- How many functions exist from a set with 5 elements to a set with 3 elements?
- What does it mean for a function to be "well defined," and give an example of a rule that is not well defined.
- State the vertical line test and apply it to determine whether the graph of x = y² defines a function.
📘 Lecture 12 — Functions
📖 Overview: This lecture defines and explores three fundamental properties of functions: injectivity (one-to-one), surjectivity (onto), and bijectivity (both). Understanding these classifications is crucial for analyzing how functions map elements between sets and forms the foundation for advanced topics like invertibility and cardinality.
🗂️ Topics Covered
The lecture covers injective (one-to-one) functions with formal definitions, examples, and the horizontal line test; surjective (onto) functions with similar treatment; bijective functions as a combination of both properties; and special function types including the identity function and constant function.
📝 Lecture Summary
INJECTIVE FUNCTION or ONE-TO-ONE FUNCTION
Let f: X → Y be a function. f is injective or one-to-one if, and only if, ∀ x₁, x₂ ∈ X, if x₁ ≠ x₂ then f(x₁) ≠ f(x₂). That is, f is one-to-one if it maps distinct points of the domain into distinct points of the co-domain. A one-to-one function separates points.
🔑 Definition — One-to-One Function: A function f: X → Y is one-to-one iff ∀ x₁, x₂ ∈ X, if x₁ ≠ x₂ then f(x₁) ≠ f(x₂) (i.e., distinct elements of the first set have their distinct images in the second set). The equivalent contra-positive statement is: ∀ x₁, x₂ ∈ X, if f(x₁) = f(x₂), then x₁ = x₂.
FUNCTION NOT ONE-TO-ONE
A function f: X → Y is not one-to-one iff there exist elements x₁ and x₂ in X such that x₁ ≠ x₂ but f(x₁) = f(x₂). That is, if distinct elements x₁ and x₂ can be found in the domain of f that have the same function value. A function that is not one-to-one collapses points together.
📌 Example: In arrow diagrams, function f maps {a,b,c} to {1,2,3,4} with a→1, b→2, c→3 — this is one-to-one because no two different elements map to the same element. Function g maps a→2, b→1, c→2 — this is NOT one-to-one because a and c both map to 2.
📌 Example: Define f: R → R by f(x) = 4x - 1. Is f one-to-one? Let x₁, x₂ ∈ R such that f(x₁) = f(x₂) ⇒ 4x₁ - 1 = 4x₂ - 1 ⇒ 4x₁ = 4x₂ ⇒ x₁ = x₂ Since f(x₁) = f(x₂) implies x₁ = x₂, f is one-to-one.
📌 Example: Define g: Z → Z by g(n) = n². Is g one-to-one? Let n₁, n₂ ∈ Z and suppose g(n₁) = g(n₂) ⇒ n₁² = n₂² ⇒ either n₁ = n₂ or n₁ = -n₂ Counter example: n₁ = 2 and n₂ = -2. Then g(2) = 4 and g(-2) = 4, but 2 ≠ -2. Hence g is NOT one-to-one.
📌 Example: Find all one-to-one functions from X = {a,b} to Y = {u,v}. There are two one-to-one functions: one maps a→u, b→v; the other maps a→v, b→u.
📌 Example: How many one-to-one functions are there from a set with three elements to a set with four elements? Let X = {x₁, x₂, x₃} and Y = {y₁, y₂, y₃, y₄}. x₁ may be mapped to any of 4 elements. Then x₂ may be mapped to any of the remaining 3 elements. Finally x₃ may be mapped to any of the remaining 2 elements. Total = 4 × 3 × 2 = 24 one-to-one functions.
📌 Example: How many one-to-one functions are there from a set with three elements to a set with two elements? Let X = {x₁, x₂, x₃} and Y = {y₁, y₂}. Two elements in X could be mapped to the two elements in Y separately, but there is no element in Y for the third element of X. Accordingly, there is no one-to-one function from a set with three elements to a set with two elements.
GRAPH OF ONE-TO-ONE FUNCTION
A graph of a function f is one-to-one iff every horizontal line intersects the graph in at most one point. (Horizontal Line Test)
📌 Example: y = x² is NOT one-to-one from R to R⁺ because the horizontal line y=4 intersects at (-2,4) and (2,4).
SURJECTIVE FUNCTION or ONTO FUNCTION
Let f: X → Y be a function. f is surjective or onto if, and only if, ∀ y ∈ Y, ∃ x ∈ X such that f(x) = y. That is, f is onto if every element of its co-domain is the image of some element(s) of its domain. Co-domain of f = range of f.
🔑 Definition — Onto Function: A function f: X → Y is onto iff every element y in Y equals f(x) for at least one x in X.
FUNCTION NOT ONTO
A function f: X → Y is not onto iff there exists y ∈ Y such that ∀ x ∈ X, f(x) ≠ y. That is, there is some element in Y that is not the image of any element in X.
📌 Example: In arrow diagrams, function f maps {a,b,c} to {1,2,3} with a→1, b→2 — f is NOT onto because 3 ≠ f(x) for any x. Function g maps {a,b,c,d} to {1,2,3} with a→3, b→3, c→1, d→2 — g IS onto because 1=g(c), 2=g(d), 3=g(a)=g(b).
📌 Example: Define f: R → R by f(x) = 4x - 1. Is f onto? Let y ∈ R. We search for x ∈ R such that f(x) = y, or 4x-1 = y. Solving: x = (y+1)/4 ∈ R. For every y ∈ R, there exists x = (y+1)/4 ∈ R such that f(x) = 4((y+1)/4) - 1 = (y+1) - 1 = y. Hence f is onto.
📌 Example: Define h: Z → Z by h(n) = 4n - 1. Is h onto? Let m ∈ Z. We search for n ∈ Z such that h(n) = m, or 4n-1 = m. Solving: n = (m+1)/4. But n = (m+1)/4 is not always an integer for all m ∈ Z. Counter example: Let m = 0. Then h(n) = 0 ⇒ 4n-1=0 ⇒ 4n=1 ⇒ n=1/4 ∉ Z. Hence h is not onto.
GRAPH OF ONTO FUNCTION
A graph of a function f is onto iff every horizontal line intersects the graph in at least one point.
📌 Example: y = |x| is onto from R to R⁺, but NOT onto from R to R.
📌 Example: Let X = {1,5,9} and Y = {3,4,7}. Define g: X → Y by g(1)=7, g(5)=3, g(9)=4. Is g one-to-one? Is g onto? g is one-to-one because each element of X maps to a different element of Y: g(1)≠g(5), g(1)≠g(9), g(5)≠g(9). g is onto because each element of Y is the image of some element of X: 3=g(5), 4=g(9), 7=g(1).
📌 Example: Define f: P({a,b,c}) → Z as follows: for all A ∈ P({a,b,c}), f(A) = the number of elements in A. a. Is f one-to-one? f is not one-to-one because f({a}) = 1 and f({b}) = 1 but {a} ≠ {b}. b. Is f onto? f is not onto because there is no element of P({a,b,c}) mapped to 4 ∈ Z.
📌 Example: Determine if each function is injective or surjective. a. f: Z → Z⁺ defined as f(x) = |x| f is not injective because f(1)=1 and f(-1)=1 but 1≠-1. f is onto because for every a∈Z⁺, there exist -a and +a in Z such that f(-a)=a and f(a)=a.
b. g: Z⁺ → Z⁺ × Z⁺ defined as g(x) = (x, x+1) Let g(x₁)=g(x₂) for x₁,x₂∈Z⁺ ⇒ (x₁,x₁+1) = (x₂,x₂+1) ⇒ x₁=x₂ and x₁+1=x₂+1 ⇒ x₁=x₂. Hence g is one-to-one. g is not onto because (1,1)∈Z⁺×Z⁺ is not the image of any element of Z⁺.
BIJECTIVE FUNCTION or ONE-TO-ONE CORRESPONDENCE
A function f: X → 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.
📌 Example: The function f: X → Y defined by the arrow diagram mapping a→1, b→2, c→3 is both one-to-one and onto, hence bijective.
📌 Example: Let f: R → R be defined by f(x) = x³. Show f is bijective. One-to-one: Let f(x₁)=f(x₂) for x₁,x₂∈R ⇒ x₁³=x₂³ ⇒ (x₁-x₂)(x₁²+x₁x₂+x₂²)=0 ⇒ x₁=x₂ (second factor has no real solution). Hence f is one-to-one. Onto: Let y∈R. We search for x∈R such that f(x)=y ⇒ x³=y ⇒ x=y^(1/3)∈R. Hence for y∈R, there exists x=y^(1/3)∈R such that f(x)=f(y^(1/3))=(y^(1/3))³=y. Hence f is onto. Thus, f is bijective.
GRAPH OF BIJECTIVE FUNCTION
A graph of a function f is bijective iff every horizontal line intersects the graph at exactly one point.
IDENTITY FUNCTION ON A SET
Given a set X, define a function iₓ from X to X by iₓ(x) = x for all x ∈ X. The function iₓ is called the identity function on X because it sends each element of X to itself.
🔑 Definition — Identity Function: iₓ: X → X defined by iₓ(x) = x.
📌 Example: Let X = {1,2,3,4}. The identity function iₓ maps 1→1, 2→2, 3→3, 4→4.
📌 Example: Let X be a non-empty set. Prove that the identity function on X is bijective. Let iₓ: X → X be defined as iₓ(x) = x ∀ x∈X. Injective: Let iₓ(x₁)=iₓ(x₂) for x₁,x₂∈X ⇒ x₁=x₂. Hence iₓ is one-to-one. Surjective: Let y∈X (co-domain). Then there exists y∈X (domain) such that iₓ(y)=y. Hence iₓ is onto. Thus, iₓ is bijective.
CONSTANT FUNCTION
A function f: X → Y is a constant function if it maps (sends) all elements of X to one element of Y, i.e., ∀ x ∈ X, f(x) = c, for some c ∈ Y.
🔑 Definition — Constant Function: A function where all elements of the domain map to the same element of the co-domain.
Remark:
- A constant function is one-to-one iff its domain is a singleton (has exactly one element).
- A constant function is onto iff its co-domain is a singleton (has exactly one element).
⭐ Key Takeaways
A student must understand the precise definitions of injective, surjective, and bijective functions and be able to prove or disprove each property using algebraic methods and counterexamples. The horizontal line test provides a quick graphical way to determine injectivity, surjectivity, and bijectivity. Counting one-to-one functions from a set of m elements to a set of n elements requires n ≥ m, with the number being the falling factorial P(n,m). Special functions like the identity function (always bijective) and constant functions (injective only for singleton domains, surjective only for singleton co-domains) serve as important boundary cases.
🧠 Quick Revision Questions
- State the contra-positive definition of a one-to-one function. How is this version used in proofs?
- Is the function f: Z → Z defined by f(n) = 2n + 3 one-to-one? Onto? Prove your answers.
- How many one-to-one functions exist from a set with 4 elements to a set with 5 elements? Show your calculation.
- Explain why a function whose graph passes the horizontal line test at exactly one point for every horizontal line must be bijective.
- Under what conditions is a constant function bijective? Explain using the definitions of injectivity and surjectivity.
📘 Lecture 13 — Sequences
📖 Overview: This lecture introduces the concept of sequences as ordered lists of elements, provides formal definitions and notations, and explores methods for finding terms using explicit formulas. It covers two important special types of sequences—arithmetic and geometric—along with their general term formulas, making it foundational for understanding patterns in mathematics and computer programming.
🗂️ Topics Covered
The lecture begins with the basic definition of a sequence and its notation, then proceeds to finding terms of a sequence given by an explicit formula with multiple examples. It introduces arithmetic sequences (AP) with their general term formula and worked examples, followed by geometric sequences (GP) with their general term and examples. The lecture concludes with a brief discussion of sequences in computer programming as one-dimensional arrays.
📝 Lecture Summary
SEQUENCE
A sequence is just a list of elements usually written in a row. The symbol “...” is called ellipsis, and reads “and so forth”.
🔑 Definition — Sequence: 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.
📐 Formula: aₖ = [expression in k] → plug in integer values of k to find terms
📌 Example 1: Define sequence a₁, a₂, a₃, ... by the explicit formula aₖ = k/(k+1) for all integers k ≥ 1.
- 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 2: Write the first four terms of sequence 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ʲ defines an infinite sequence having infinite number of values.
📌 Example 3: Compute first six terms of Cₙ = 1 + (-1)ⁿ for all integers n ≥ 0.
- C₀ = 1 + (-1)⁰ = 2
- C₁ = 1 + (-1)¹ = 0
- C₂ = 1 + (-1)² = 2
- C₃ = 1 + (-1)³ = 0
- C₄ = 1 + (-1)⁴ = 2
- C₅ = 1 + (-1)⁵ = 0
Remarks: (1) If n is even, Cₙ = 2; if n is odd, Cₙ = 0. The sequence oscillates endlessly between 2 and 0. (2) An infinite sequence may have only a finite number of values.
📌 Example 4: Write first four terms of 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
Remark: A sequence whose terms alternate in sign is called an alternating sequence.
📌 Exercise: Find explicit formulas for sequences with initial terms given:
- 0, 1, -2, 3, -4, 5, ... → aₙ = (-1)ⁿ⁺¹ n for all integers n ≥ 0
- 1-1/2, 1/2-1/3, 1/3-1/4, 1/4-1/5, ... → bₖ = 1/k - 1/(k+1) for all integers n ≥ 1
- 2, 6, 12, 20, 30, 42, 56, ... → Cₙ = n(n+1) for all integers n ≥ 1
- 1/4, 2/9, 3/16, 4/25, 5/36, 6/49, ... → dᵢ = i/(i+1)² for all integers i ≥ 1 OR dⱼ = (j+1)/(j+2)² for all integers j ≥ 0
ARITHMETIC SEQUENCE
A sequence in which every term after the first is obtained from the preceding term by adding a constant number is called an arithmetic sequence or arithmetic progression (A.P.). The constant number, being the difference of any two consecutive terms, is called the common difference of A.P., commonly denoted by “d”.
📌 Examples:
- 5, 9, 13, 17, ... (common difference = 4)
- 0, -5, -10, -15, ... (common difference = -5)
- 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. Then the sequence is a, a+d, a+2d, a+3d, ...
🔑 Definition — nth term of AP: aₙ = a + (n-1)d for all integers n ≥ 1, where a = first term, d = common difference.
📌 Example: Find the 20th term of the arithmetic sequence 3, 9, 15, 21, ...
- Given: 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?
- Given: a = 4, d = 1-4 = -3, aₙ = -77
- -77 = 4 + (n-1)(-3)
- -77-4 = (n-1)(-3)
- -81/(-3) = n-1
- 27 = n-1
- n = 28 → -77 is the 28th term.
📌 Example: Find the 36th term of the arithmetic sequence whose 3rd term is 7 and 8th term is 17.
- Let a = first term, d = common difference
- a₃ = a + 2d = 7 ...(1)
- a₈ = a + 7d = 17 ...(2)
- Subtracting (1) from (2): 10 = 5d → d = 2
- Substituting d=2 in (1): 7 = a + 4 → a = 3
- aₙ = 3 + (n-1)2
- a₃₆ = 3 + (36-1)2 = 3 + 70 = 73
GEOMETRIC SEQUENCE
A sequence in which every term after the first is obtained from the preceding term by multiplying it with a constant number is called a geometric sequence or geometric progression (G.P.). The constant number, being the ratio of any two consecutive terms, is called the common ratio of the G.P., commonly denoted by “r”.
📌 Examples:
- 1, 2, 4, 8, 16, ... (common ratio = 2)
- 3, -3/2, 3/4, -3/8, ... (common ratio = -1/2)
- 0.1, 0.01, 0.001, 0.0001, ... (common ratio = 0.1 = 1/10)
GENERAL TERM OF A GEOMETRIC SEQUENCE: Let a be the first term and r be the common ratio. Then the sequence is a, ar, ar², ar³, ...
🔑 Definition — nth term of GP: aₙ = arⁿ⁻¹ for all integers n ≥ 1, where a = first term, r = common ratio.
📌 Example: Find the 8th term of the geometric sequence 4, 12, 36, 108, ...
- Given: 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 is 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 → 1/8 is the 6th term.
📌 Example: Write the geometric sequence with positive terms whose second term is 9 and fourth term is 1.
- Let a = first term, r = 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 must be positive)
- Substituting r = 1/3 in (1): 9 = a(1/3) → a = 27
- Sequence: 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].
💡 Why this matters: Understanding sequences is essential for working with arrays and indexed data structures in programming.
⭐ Key Takeaways
This lecture establishes that a sequence is a function from integers to terms, defined by explicit formulas or by recursive patterns. The two most important special sequences are arithmetic sequences, where consecutive terms differ by a constant d (formula: aₙ = a + (n-1)d), and geometric sequences, where consecutive terms have a constant ratio r (formula: aₙ = arⁿ⁻¹). You must be able to find specific terms from formulas, derive formulas from given terms, and solve for unknown parameters like a, d, r, or n using given conditions. Alternating sequences arise when terms change sign, and sequences in computing correspond to one-dimensional arrays. For exam success, practice converting between sequence descriptions and explicit formulas.
🧠 Quick Revision Questions
- Write the first four terms of the sequence defined by aₙ = n/(2n+1) for n ≥ 1.
- State the formula for the nth term of an arithmetic progression, defining all symbols.
- Find the 15th term of the arithmetic sequence 7, 11, 15, 19, ...
- Find the 6th term of the geometric sequence 2, -6, 18, -54, ...
- Which term of the geometric sequence with first term 5 and common ratio 2 equals 160?
📘 Lecture 14 — Series
📖 Overview: This lecture introduces the concept of series as the sum of terms of a sequence, along with summation notation using the Greek letter sigma (Σ). It covers computing sums, transforming sums, properties of summations, and delves into arithmetic and geometric series, including formulas for finite and infinite sums, culminating in important summation formulas and practical problem-solving.
🗂️ Topics Covered
This lecture covers defining series and summation notation, computing summations from given sequences, converting between expanded form and summation notation, transforming sums by change of variable, and properties of summations. It then introduces arithmetic series and derives the sum formula, solves problems including the sum of natural numbers and sums with divisibility constraints. Finally, it covers geometric series for both finite and infinite sums, and presents important standard summation formulas for powers of integers.
📝 Lecture Summary
Series
A series is the sum of the terms of a sequence. If a₁, a₂, a₃, ... represent a sequence of numbers, then the corresponding series is a₁ + a₂ + a₃ + ... which can be written as Σ aₖ (from k=1 to ∞).
Summation Notation
The capital Greek letter sigma (Σ) is used to write a sum in shorthand notation. For example, Σ aₖ (from k=1 to n) = a₁ + a₂ + a₃ + ... + aₙ. More generally, if m and n are integers and m ≤ n, then Σ aₖ (from k=m to n) = aₘ + aₘ₊₁ + aₘ₊₂ + ... + aₙ. Here, k is called the index of the summation, m is the lower limit, and n is the upper limit.
🔑 Definition — Summation Notation: A compact way to represent the sum of a sequence of terms using the Greek letter sigma (Σ).
Computing Summations
Given a₀ = 2, a₁ = 3, a₂ = -2, a₃ = 1, and a₄ = 0, compute:
- Σ aᵢ (from i=0 to 4): = a₀ + a₁ + a₂ + a₃ + a₄ = 2 + 3 + (-2) + 1 + 0 = 4
- Σ a₂ⱼ (from j=0 to 2): = a₀ + a₂ + a₄ = 2 + (-2) + 0 = 0
- Σ aₖ (from k=1 to 1): = a₁ = 3
📐 Example: Compute Σ (2i - 1) (from i=1 to 3) = [2(1) - 1] + [2(2) - 1] + [2(3) - 1] = 1 + 3 + 5 = 9.
📐 Example: Compute Σ (k³ + 2) (from k=-1 to 1) = [(-1)³ + 2] + [(0)³ + 2] + [(1)³ + 2] = [-1+2] + [0+2] + [1+2] = 1 + 2 + 3 = 6.
Summation Notation to Expanded Form
Write the summation Σ (-1)ⁱ / (i + 1) (from i=0 to n) in expanded form: The expanded form is (-1)⁰/(0+1) + (-1)¹/(1+1) + (-1)²/(2+1) + (-1)³/(3+1) + ... + (-1)ⁿ/(n+1) = 1/1 + (-1)/2 + 1/3 + (-1)/4 + ... + (-1)ⁿ/(n+1) = 1 - 1/2 + 1/3 - 1/4 + ... + (-1)ⁿ/(n+1).
Expanded Form to Summation Notation
Write the series 1/n + 2/(n+1) + 3/(n+2) + ... + (n+1)/(2n) using summation notation. Solution: Find the kth term of the series. The numerators form an arithmetic sequence 1, 2, 3, ..., n+1. First term a=1, common difference d=1, so the kth numerator aₖ = a + (k-1)d = 1 + (k-1)(1) = k. The denominators form an arithmetic sequence n, n+1, n+2, ..., 2n. First term a=n, common difference d=1, so the kth denominator aₖ = a + (k-1)d = n + (k-1)(1) = k + n - 1. Hence the kth term of the series is k / [(n-1) + k]. The series is Σ k / [(n-1) + k] (from k=1 to n+1) or equivalently Σ (k+1) / (n+k) (from k=0 to n).
Transforming a Sum by a Change of Variable
The index of a summation is a dummy variable because it can be replaced by any other symbol. For example, Σ k² (from k=1 to 3) = Σ i² (from i=1 to 3).
📐 Example: For the sum Σ k / [(n-1) + k] (from k=1 to n+1), substitute k = j + 1 so j = k - 1. When k=1, j=0. When k=n+1, j=n. The sum becomes Σ (j+1) / [(n-1) + (j+1)] (from j=0 to n) = Σ (j+1)/(n+j) (from j=0 to n) = Σ (k+1)/(n+k) (from k=0 to n).
Properties of Summations
- Σ (aₖ + bₖ) (from k=m to n) = Σ aₖ (from k=m to n) + Σ bₖ (from k=m to n)
- Σ c·aₖ (from k=m to n) = c·Σ aₖ (from k=m to n), c ∈ ℝ
- Σ (k + i) (from k=a-i to b-i) = Σ k (from k=a to b)
- Σ (k - i) (from k=a+i to b+i) = Σ k (from k=a to b)
- Σ c (from k=1 to n) = c + c + ... + c (n times) = nc
📐 Example: Express Σ (2k - 3) (from k=1 to 3) + Σ (4 - 5k) (from k=1 to n) more simply. Solution: The first sum is a constant, so Σ (2k-3) (from k=1 to 3) = 3. Using property (2) to combine, 3 + Σ (4 - 5k) (from k=1 to n) = Σ [3 + (4 - 5k)] (from k=1 to n) is incorrect as the first sum is a constant, not a summation over n. Wait: 3 · Σ (2k-3) (from k=1 to n) means multiply the sum by 3? No, the first sum is from 1 to 3, a fixed number. Let's recompute: The original sum is Σ (2k-3) (from k=1 to 3) + Σ (4-5k) (from k=1 to n). First sum = (2-3)+(4-3)+(6-3) = (-1)+(1)+(3) = 3. So the expression is 3 + Σ (4-5k) (from k=1 to n) = 3 + [Σ 4 (from k=1 to n) - Σ 5k (from k=1 to n)] = 3 + [4n - 5Σ k (from k=1 to n)].
💡 Why this matters: These properties allow us to break complicated sums into simpler parts and handle constant terms efficiently.
Arithmetic Series
The sum of the terms of an arithmetic sequence forms an arithmetic series (A.S.). For example, 1 + 3 + 5 + 7 + ... If a is the first term and d the common difference, the series is a + (a+d) + (a+2d) + ...
Sum of n Terms of an Arithmetic Series: Let a be the first term and d the common difference. The nth term is aₙ = a + (n-1)d. The sum Sₙ = n(a + l)/2, where l = aₙ = a + (n-1)d. Also, Sₙ = n/2 [2a + (n-1)d].
📐 Formula — Sum of Arithmetic Series: Sₙ = n/2 (a + l) = n/2 [2a + (n-1)d]
📐 Example: Find the sum of first n natural numbers. Let Sₙ = 1 + 2 + 3 + ... + n. This is an arithmetic series with a=1, d=1. Sₙ = n/2 [2(1) + (n-1)(1)] = n/2 [2 + n - 1] = n(n+1)/2.
📐 Example: Find the sum of all two-digit positive integers which are neither divisible by 5 nor by 2. The numbers are odd and not ending in 5: 11, 13, 17, 19, 21, 23, 27, 29, ..., 97, 99. This is not a simple arithmetic series. Group in sets of four: (11+13+17+19) + (21+23+27+29) + ... + (91+93+97+99) = 60 + 100 + 140 + ... + 380. This is an arithmetic series with a=60, d=40, l=380. Find n: 380 = 60 + (n-1)(40) ⇒ 320 = (n-1)(40) ⇒ n-1 = 8 ⇒ n=9. S₉ = 9/2 (60 + 380) = 9/2 (440) = 1980.
Geometric Series
The sum of the terms of a geometric sequence forms a geometric series (G.S.). For example, 1 + 2 + 4 + 8 + 16 + ... If a is the first term and r the common ratio, the series is a + ar + ar² + ar³ + ...
Sum of n Terms of a Geometric Series: Let a be the first term and r the common ratio. The nth term is aₙ = arⁿ⁻¹. The sum Sₙ = a(1 - rⁿ)/(1 - r) for r ≠ 1.
📐 Formula — Sum of Finite Geometric Series: Sₙ = a(1 - rⁿ)/(1 - r), r ≠ 1.
📐 Example: Find the sum of the geometric series 6 - 2 + 2/3 - 2/9 + ... to 10 terms. Here a=6, r = -2/6 = -1/3, n=10. S₁₀ = 6[1 - (-1/3)¹⁰] / [1 - (-1/3)] = 6[1 - (1/3¹⁰)] / (4/3) = 6(3/4)[1 - 1/59049] = (18/4)[59048/59049] = (9/2)(59048/59049).
Infinite Geometric Series: For an infinite geometric series a + ar + ar² + ..., if |r| < 1, then as n → ∞, rⁿ → 0, so the sum S = a/(1 - r). If the sum increases indefinitely, the series is divergent. If it approaches a finite limit, it is convergent.
📐 Formula — Sum of Infinite Geometric Series: S = a/(1 - r), for |r| < 1.
📐 Example: Find the sum of the infinite geometric series 9/4 + 3/2 + 1 + 2/3 + ... Here a=9/4, r = (3/2)/(9/4) = (3/2)(4/9) = 2/3. Since |r| < 1, S = a/(1 - r) = (9/4)/(1 - 2/3) = (9/4)/(1/3) = (9/4)(3/1) = 27/4.
📐 Example: Find a common fraction for the recurring decimal 0.818181... 0.81 = 0.81 + 0.0081 + 0.000081 + ... This is an infinite geometric series with a=0.81, r=0.0081/0.81=0.01. S = a/(1 - r) = 0.81/(1 - 0.01) = 0.81/0.99 = 81/99 = 9/11.
Important Sums
- Σ k (from k=1 to n) = 1 + 2 + 3 + ... + n = n(n+1)/2
- Σ k² (from k=1 to n) = 1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6
- Σ k³ (from k=1 to n) = 1³ + 2³ + 3³ + ... + n³ = [n(n+1)/2]²
📐 Example: Sum to n terms the series 1·5 + 5·11 + 9·17 + ... The series is formed from two arithmetic sequences: (i) 1, 5, 9, ... with kth term 4k-3; (ii) 5, 11, 17, ... with kth term 6k-1. The kth term of the series Tₖ = (4k-3)(6k-1) = 24k² - 22k + 3. Sₙ = Σ Tₖ (from k=1 to n) = Σ (24k² - 22k + 3) = 24Σ k² - 22Σ k + 3Σ 1 = 24[n(n+1)(2n+1)/6] - 22[n(n+1)/2] + 3n = 4n(n+1)(2n+1) - 11n(n+1) + 3n = 8n³ + n² - 4n.
⭐ Key Takeaways
You must master the definitions of a series and summation notation, including identifying the index, lower, and upper limits. The five properties of summations are essential for simplifying and combining sums. The formulas for arithmetic series (Sₙ = n/2[a + l]) and geometric series (Sₙ = a(1-rⁿ)/(1-r) for finite and S = a/(1-r) for infinite with |r|<1) are fundamental tools. You should be able to convert between expanded form and summation notation, perform change of variable transformations, and apply the three important sums (Σk, Σk², Σk³) to solve complex series problems.
🧠 Quick Revision Questions
- What is the value of Σ (3k - 1) from k=1 to 4?
- Express the series 1/2 + 2/3 + 3/4 + ... + n/(n+1) using summation notation.
- Find the sum of the first 20 terms of the arithmetic series with a=5 and d=3.
- Find the sum of the infinite geometric series 8 + 4 + 2 + 1 + ...
- Find the sum of the series Σ (2k² - k + 1) from k=1 to n.
📘 Lecture 15 — Applications of Basic Mathematics
📖 Overview: This lecture introduces the five basic arithmetic operations that form the foundation of all mathematics and demonstrates how to perform these operations using Microsoft Excel. It covers starting Excel, understanding its interface, and writing formulas for addition, subtraction, multiplication, division, percentages, and exponents.
🗂️ Topics Covered
The lecture covers the five basic arithmetic operations of addition, subtraction, multiplication, division, and exponents with examples, followed by a comprehensive introduction to Microsoft Excel 2002 XP including starting the software, understanding the workbook interface with cells and ranges, entering and editing data, and creating formulas for each arithmetic operation using cell references and Excel operators.
📝 Lecture Summary
OBJECTIVES
The objectives of this lecture are to learn about different course modules, basic arithmetic operations, starting Microsoft (MS) Excel, and using MS Excel to carry out arithmetic operations.
BASIC ARITHMETIC OPERATIONS
Five arithmetic operations provide the foundation for all mathematical operations: Addition, Subtraction, Multiplication, Division, and Exponents.
🔑 Definition — Arithmetic Operations: The five fundamental operations that form the basis for all mathematical calculations.
📌 Example — Addition: 12 + 5 = 17 📌 Example — Subtraction: 12 - 5 = 7 📌 Example — Multiplication: 12 x 5 = 60 📌 Example — Division: 12 ÷ 5 = 2.4 📌 Example — Exponent: (4)^2 = 16, (4)^1/2 = 2, (4)^-1/2 = 1/(4)^1/2 = ½ = 0.5
MICROSOFT EXCEL IN BUSINESS MATHEMATICS & STATISTICS
Microsoft Corporation's Spreadsheet software Excel is widely used in business mathematics and statistical applications. The latest version covered is EXCEL 2002 XP, though earlier versions like EXCEL 2000 and EXCEL 97 can also be used for the applications in this course.
Starting EXCEL 2000 XP
EXCEL 2000 XP can be started by going through the following steps:
- Click Start on your computer
- Click All Programs
- Click Microsoft Excel
The EXCEL window opens and a blank worksheet becomes available. A Workbook by the name book1 is shown with three sheets: Sheet1, Sheet2 and Sheet3. The Excel Window has Column numbers starting from A and row numbers starting from 1. The intersection of a row and column is called a Cell. The first cell is A1 which is the intersection of column A and row 1. All cells in a Sheet are referenced by a combination of Column name and row number.
🔑 Definition — Cell: The intersection of a row and column in an Excel worksheet, referenced by a combination of column letter and row number. 📌 Example — Cell Reference: B15 means cell in column B and row 15. A cell in row 12 and column C has reference C12.
🔑 Definition — Range: All cells starting from the leftmost corner where the range starts to the rightmost corner in the last row, specified by the starting cell, a colon, and the ending cell. 📌 Example — Range: A Range which starts from A1 and ends at D15 is referenced by A1:D15 and has all the cells in columns A to D up to and including row 15.
A value can be entered into a cell by clicking that cell. The mouse pointer moves to the selected cell. Enter the value followed by the Enter key and the mouse pointer moves to the cell below. To replace a value, select the cell again and enter the new value. To change individual digits, double-click the cell to see the blinking cursor, then use arrow keys or mouse to move to the digit to be changed.
About calculation operators in Excel
In Excel there are four different types of operators:
- Arithmetic operators
- Comparison operators
- Text concatenation operator
- Reference operators
The Excel arithmetic operators are as follows:
- Addition: Symbol: + (Example: =5+4 Result: 9)
- Subtraction: Symbol: - (Example: =5-4 Result: 1)
- Multiplication: Symbol: * (Example: =5*4 Result: 20)
- Division: Symbol: / (Example: =12/4 Result: 3)
- Percent: Symbol: % (Example: =20% Result: 0.2)
- Exponentiation: Symbol: ^ (Example: =5^2 Result: 25)
Excel Formulas for Addition
All calculations in Excel are made through formulas which are written in cells where the result is required.
To add two numbers 10 and 5 in Excel:
- Open a blank worksheet
- Click on cell A15 and enter 10
- Click on cell B15 and enter 5
- Click on cell C15 (where the sum will appear)
- Enter equal sign = in cell C15
- Write "(" (left bracket) in cell C15
- Click on cell A15 (value 10) — the cell reference A15 is written
- Write "+" after A15
- Click on cell B15 (value 5) — the cell reference B15 is written
- Write ")" (right bracket)
- Press Enter key
The answer 15 is shown in cell C15. The formula "=A15+B15" is displayed in the formula bar.
📌 Example — Adding multiple numbers: To add 5, 10, 15, 20, 30 and 40, enter values in cells A34 through F34. Write formula =5+10+15+20+30+40 in cell G34. The answer is 120.
Alternatively, use the SUM function: Enter =SUM(A34:F34) by typing "=" followed by SUM, followed by "(", clicking on cell A34 (value 5), dragging to cell F34 (value 40), entering ")", and pressing Enter.
Excel Formula for Subtraction
Excel formulas for subtraction use the minus sign (-). To subtract 15 from 25:
- Enter 25 in cell A50 and 15 in cell B50
- Write formula =A50-B50 in cell C50
The answer 10 is displayed in cell C50. If you enter 15 first and 25 later, the result would be 15-25 = -10.
Excel Formula for Multiplication
The Excel multiplication operator is * (asterisk). To multiply 25 by 15:
- Enter 25 in cell A60 and 15 in cell B60
- Write formula =A60*B60 in cell C60
The answer 375 is displayed in cell C60.
Excel Formula for Division
The division sign is / (forward slash). To divide 240 by 15:
- Enter 240 in cell A75 and 15 in cell B75
- Write formula =A75/B75 in cell C75
The answer 16 is displayed in cell C75.
Excel Formula for Percent
The formula for converting percent to fraction uses the symbol %. To convert 20% to fraction:
- Write =20% — the result is 0.2
If you enter 20 in cell A99, write =A99% in cell B99 to get the result 0.2.
Excel Formula for Exponentiation
The symbol for exponentiation is ^ (caret). To calculate 16 raised to the power 2:
- Enter 16 in cell A85 and 2 in cell B85
- Write formula =A85^B85 in cell C85
The answer 256 is displayed in cell C85.
⭐ Key Takeaways
The five fundamental arithmetic operations—addition, subtraction, multiplication, division, and exponents—are performed in Excel by writing formulas that begin with an equals sign (=) and use cell references and arithmetic operators (+, -, *, /, %, ^). Every formula in Excel must start with =, and it is best practice to reference cells by their coordinates (like A15) rather than typing numbers directly, so that results update automatically when values change. The SUM function provides an efficient way to add multiple values in a range. Understanding cell references, ranges, and the formula bar is essential for all spreadsheet work in business mathematics and statistics.
🧠 Quick Revision Questions
- What are the five basic arithmetic operations, and what symbols does Excel use for each?
- How do you reference a range of cells from column B row 3 to column F row 20 in Excel?
- What must every Excel formula begin with, and why is it better to use cell references instead of actual numbers in formulas?
- What is the result of the Excel formula =16^2, and what operator is used for exponentiation?
- How would you write an Excel formula to convert 45% into a decimal fraction?
📘 Lecture 16 — Applications of Basic Mathematics (Continued)
📖 Overview: This lecture continues the application of basic mathematics, focusing on percentage change calculations and their use in real-world scenarios like salary increases and investment returns. The lecture demonstrates how to perform these calculations both manually and using Microsoft Excel, making the concepts practical for business and financial planning.
🗂️ Topics Covered
The lecture covers calculating percentage change between two values, including increases and decreases, with multiple examples such as sales growth, fruit drying, and cotton weight change. It then applies these concepts to multi-year salary increases with varying annual percentages, and finally to investment returns over multiple years with both positive and negative rates of return. All calculations are demonstrated step-by-step in Microsoft Excel.
📝 Lecture Summary
Percentage Change
To find the percent change between an initial and final value, first compute the change by subtracting the initial value from the final value. Then, divide this change by the initial value and multiply by 100%. The formula works for both increases (positive change) and decreases (negative change). In Excel, the formula for change is =Final_Cell - Initial_Cell, and for percentage change it is =Change_Cell / Initial_Cell * 100.
🔑 Definition — Percentage Change: (Final value – Initial value) / Initial value × 100%
📐 Formula: Percentage change = (Change / Initial value) × 100%
📌 Example: Monday’s Sales were Rs.1000 and grew to Rs.2500 the next day. Initial = 1000, Final = 2500, Change = 2500-1000 = 1500, % Change = (1500/1000) × 100 = 150%. In Excel, cell C4=1000, C5=2500, formula in C6 = =C5-C4 (result 1500), formula in C7 = =C6/C4*100 (result 150).
Example 1: Next Day’s Sale as Percentage of Monday’s Sale
This example finds what percent the next day’s sale represents compared to Monday’s sale. This is a ratio calculation, not a change calculation. Monday’s sale = 1000, Next day’s sale = 2500. Next day’s sale as % = 2500/1000 × 100 = 250%, meaning the next day’s sale was two and a half times Monday’s sale.
Example 2: Dried Fruit – Percentage Decrease
In making dried fruit, 15 kg of fresh fruit shrinks to 3 kg of dried fruit. This is a decrease. Original = 15 kg, Final = 3 kg, Change = 3-15 = -12, % change = -12/15 × 100 = -80%. The size was reduced by 80%. In Excel, cell D19=15, D20=3, formula in D21 = =D20-D19 (result -12 kg), formula in D22 = =D21/D19*100 (result -80%).
Example 3: Cotton Weight – Percentage Increase
After mixing with water, cotton weight increased from 3 kg to 15 kg. Original = 3 kg, Final = 15 kg, Change = 15-3 = 12, % change = 12/3 × 100 = 400%. Weight increased by 400%. In Excel, cell D26=3, D27=15, formula in D28 = =D27-D26 (result 12 kg), formula in D29 = =D28/D26*100 (result 400%).
Example 4: Multi-Year Salary Increase
A union signed a three-year contract with wage increases of 3%, 2%, and 1% in successive years. An employee currently earns Rs. 5000 per month. The salary at the end of the contract is calculated by applying each percentage increase sequentially: 5000 × (1 + 3%) × (1 + 2%) × (1 + 1%) = 5000 × 1.03 × 1.02 × 1.01 = Rs. 5306. In Excel, the ROUND function is used to round to zero decimal places. Data: cell C35=5000, C36=3, C38=2, C40=1. Formulas: C37 = =ROUND(C35*(1+C36/100);0) (result 5150), C39 = =ROUND(C37*(1+C38/100);0) (result 5253), C41 = =ROUND(C39*(1+C40/100);0) (result 5306).
Example 5: Multi-Year Investment Return
An investment of Rs. 100,000 is made for 4 years with annual rates of return: 4%, 8%, -10%, and 9%. The value at the end of each year is calculated by applying the return to the previous year’s value. Data: cell C46=100000, C47=4, C49=8, C51=-10, C53=9. Formulas: C48 = =ROUND(C46*(1+C47/100);0) (result 104000), C50 = =ROUND(C48*(1+C49/100);0) (result 112320), C52 = =ROUND(C50*(1+C51/100);0) (result 101088), C54 = =ROUND(C52*(1+C53/100);0) (result 110186). 💡 Why this matters: This demonstrates how a negative return in one year can significantly reduce the overall investment value, and how compounding works over multiple periods.
⭐ Key Takeaways
The formula for percentage change is always (Final – Initial) / Initial × 100%, where a negative result indicates a decrease. When calculating cumulative effects like salary increases or investment returns over multiple years, each year’s percentage change is applied sequentially to the previous year’s result, using the formula Previous_Value × (1 + Rate/100). The Excel ROUND function is useful for displaying whole numbers (no decimals). For percentage change, the initial value is always the denominator, while for finding what percent one value is of another, you use that value divided by the reference value.
🧠 Quick Revision Questions
- What is the formula for calculating percentage change, and how do you interpret a negative result?
- In Example 4, if the wage increases were applied in reverse order (1%, 2%, 3%), would the final salary be the same? Why or why not?
- In Example 5, calculate the value after year 2 if the rates were 5% and 10% instead of 4% and 8%, starting from Rs. 100,000.
- If Monday’s sales are Rs. 500 and Tuesday’s are Rs. 750, what is the percentage change from Monday to Tuesday?
- An investment of Rs. 50,000 loses 20% in year 1 and gains 25% in year 2. What is the final value after year 2?
📘 Lecture 17 — Applications of Basic Mathematics (Continued)
📖 Overview: This lecture continues the application of basic mathematical concepts to real-world financial scenarios. It covers the fundamental principles of stock market investments, including definitions and calculations of stock yield, earnings per share, and the price-earnings ratio. The lecture then details the practical mathematics of buying and selling shares, calculating return on investment, and understanding discounts, concluding with the essential formulas and examples for simple and compound interest.
🗂️ Topics Covered
The lecture begins with a revision of percentage increase and decrease calculations using a loan interest rate example. It then introduces the definition of a stock and key stock market metrics: stock yield, earnings per share (EPS), price-earnings (P/E) ratio, outstanding shares, net current asset value per share (NCAVPS), and definitions of market value, face value, and dividend. Following this, practical examples are provided for calculating the total cost of buying shares and the return on investment (including dividends and commissions). The lecture concludes with sections on discount and net cost price, simple interest, and compound interest, with detailed Excel calculations for each example.
📝 Lecture Summary
Revision Lecture
The lecture begins by revisiting percentage change with a loan interest rate example. When an interest rate decreases from 9% to 7%, the calculation is: Decrease = 7 - 9 = -2. The percent decrease = (Decrease / Original) * 100 = (-2/9) * 100 = -22.2%. Conversely, for a rate increase from 7% to 9%, the percent increase = (Increase / Original) * 100 = (2/7) * 100 = 28.6%. The lecture shows how to perform these calculations in Excel by entering the original and new rates, using formulas for the difference and the percentage change.
The Definition of a Stock
A stock is a share in the ownership of a company, representing a claim on the company's assets and earnings. As you acquire more stock, your ownership stake in the company becomes greater. Shares, equity, or stock all mean the same thing.
Stock yield can refer to the rate of income generated from a stock in the form of regular dividends. It is represented in percentage form, calculated as the annual dividend payments divided by the stock's current share price.
Earnings per share (EPS) is the total profits of a company divided by the number of shares. For example, a company with $1 billion in earnings and 200 million shares would have earnings of $5 per share.
Price-earnings ratio (P/E) is a valuation ratio of a company's current share price compared to its per-share earnings.
📐 Formula: P/E Ratio = Market Price per Share / Earnings per Share 📌 Example: If a company is trading at $43 a share and earnings were $1.95 per share, the P/E ratio is 22.05 ($43 / $1.95).
Outstanding shares are stock currently held by investors, including restricted shares owned by officers and insiders, as well as those held by the public. Shares repurchased by the company are not considered outstanding.
Net Current Asset Value Per Share (NCAVPS) is calculated by taking a company's current assets and subtracting total liabilities, then dividing by the total number of outstanding shares.
📐 Formula: NCAVPS = (Current Assets - Total Liabilities) / Total Shares Outstanding
Current Assets are all assets expected to be converted into cash within one year, including cash, accounts receivable, inventory, and marketable securities. Liabilities are a company's legal debts or obligations that arise during business operations.
Market value is the price at which investors buy or sell a share at a given time. Face value (or "par value") is the original cost of a share shown on the certificate, usually a small amount with no relationship to its market price.
A dividend is a distribution of a part of a company's profit to its shareholders. For example, a company earning Rs 1 crore might keep half for reinvestment and distribute the other half (Rs 50 lakh) as dividends. If the capital is divided into 10,000 shares, each share earns Rs 500. If you own 100 shares, you get Rs 50,000 (100 shares x Rs 500). Sometimes the dividend is given as a percentage of the share's face value. If the face value is Rs 10, a 50% dividend means Rs 5 per share.
Buying Shares
To calculate the total cost of buying shares: multiply the number of shares by the price per share, then add the commission (a percentage of the total price).
📌 Example: If you buy 100 shares at Rs. 62.50 per share with a 2% commission, the calculation is:
- Total Value of Shares = 100 * Rs. 62.50 = Rs. 6,250
- Commission = 0.02 * Rs. 6,250 = Rs. 125
- Total Cost = Rs. 6,375
Return on Investment
Return on Investment (ROI) is calculated by dividing the total gain (including dividends) by the total cost of the investment.
📌 Example: You bought 100 shares at Rs. 52.25 and sold them after 1 year at Rs. 68. The commission rate is 1% for both buying and selling. The 10% dividend is based on the face value of each share, which is Rs. 10.
- Bought: Cost of shares = 100 * 52.25 = 5,225.00. Commission = 5,225.00 * 0.01 = 52.25. Total Cost = 5,225 + 52.25 = 5,277.25.
- Sold: Sale of shares = 100 * 68 = 6,800.00. Commission = 6,800.00 * 0.01 = 68.00. Net Receipts = 6,800 - 68 = 6,732.00.
- Gain: Net Receipts - Total Cost = 6,732 - 5,277.25 = 1,454.75.
- Dividends: Since the dividend is 10% of the face value (Rs. 10), the dividend per share is Rs. 1. Total Dividends = 100 shares * Rs. 1 = 100.00.
- Total Gain = Net Gain + Dividends = 1,454.75 + 100 = 1,554.75.
- Return on Investment = (Total Gain / Total Cost) * 100 = (1,554.75 / 5,277.25) * 100 = 29.46%.
The lecture provides detailed Excel formulas to perform these calculations step-by-step for the "Bought", "Sold", and "Gain" components.
Discount
Discount is a rebate or reduction in price, expressed as a percentage of the list price.
📐 Formula: Discount = List Price * Discount Rate 📌 Example: List price = 2200, Discount Rate = 15% (0.15). Discount = 2200 * 0.15 = 330.
Net Cost Price
Net Cost Price is the price after the discount is subtracted from the list price.
📐 Formula: Net Cost Price = List Price - Discount 📌 Example: List price = 4,500 Rs., Discount = 20%.
- Discount = 0.2 * 4,500 = 900 Rs.
- Net Cost Price = 4,500 - 900 = 3,600 Rs.
Simple Interest
For simple interest, where P = Principal, R = Rate of interest per annum, and T = Time in years, the formula is:
📐 Formula: Simple Interest (I) = (P * R * T) / 100 💡 Why this matters: The total amount (A) to be paid at the end of T years is the principal plus the simple interest: A = P + I. 📌 Example: P = Rs. 500, T = 4 years, R = 11%. I = (500 * 4 * 11) / 100 = 22,000 / 100 = Rs. 220.
Compound Interest
Compound interest is interest that is calculated on the initial principal and also on the accumulated interest from previous periods. It "attracts interest."
📌 Example: P = 800, Interest rate = 10% per year.
- Year 1 Interest = 0.1 * 800 = 80. New Principal = 800 + 80 = 880.
- Year 2 Interest = 0.1 * 880 = 88. New Principal = 880 + 88 = 968.
📐 Formula: Compound Amount (S) = P(1 + r/100)^n, where n is the number of periods. Compound Interest = S - P. 📌 Example: Calculate compound interest on Rs. 750 invested at 12% per annum for 8 years.
- S = 750 * (1 + 12/100)^8 = 750 * (1.12)^8 = 750 * 2.47596 = 1857 Rs. (approximately)
- Compound Interest = 1857 - 750 = 1107 Rs.
⭐ Key Takeaways
For the exam, you must be able to calculate a percent increase or decrease in a rate. You should know the key stock market definitions: EPS (profit per share) and P/E ratio (price per share divided by EPS). Most importantly, master the Return on Investment calculation, which involves computing the total cost of buying shares (including commission), the net receipts from selling shares (subtracting commission), the net gain, and adding any dividend income. Finally, you must be able to apply the standard formulas for Simple Interest (I = PRT/100) and Compound Interest (S = P(1+r/100)^n) to solve for interest earned over a given time period.
🧠 Quick Revision Questions
- Calculate the net cost price of an item with a list price of Rs. 8,000 and a discount rate of 15%.
- What is the Earnings Per Share (EPS) for a company with total profits of $5 million and 2 million shares outstanding?
- You buy 200 shares at Rs. 30.00 per share with a 2% commission and sell them at Rs. 40.00 per share with a 1% commission. If the dividend is 5% on a face value of Rs. 10, what is your return on investment?
- Calculate the simple interest on a principal of Rs. 2,500 at a rate of 8% per annum for 5 years.
- A principal of Rs. 1,000 is invested at a compound interest rate of 5% per annum for 3 years. What is the final compound amount (to the nearest Rupee)?
📘 Lecture 18 — Applications of Basic Mathematics (Continued)
📖 Overview: This lecture explores the practical applications of basic mathematics in financial contexts, focusing on annuities as a tool for savings and investments. It covers how to calculate the accumulated (future) and discounted (present) values of a series of payments, introduces essential algebraic operations for simplifying expressions, and explains how to solve linear equations. Understanding these concepts is crucial for making informed financial decisions about loans, retirement income, and investments.
🗂️ Topics Covered
The lecture begins by defining an annuity and its common payment frequencies. It then details the calculations for the accumulated value (future value) of an annuity using an accumulation factor, followed by the discounted value (present value) using a discount factor, with step-by-step examples. The discussion shifts to an introduction of algebraic operations, covering types of expressions (monomial, binomial, etc.) and how to factor, multiply, and divide them. Finally, the lecture explains the process for solving linear equations by collecting like terms and isolating the variable.
📝 Lecture Summary
OBJECTIVES
This lecture aims to teach students about annuity, accumulated value, accumulation factor, discount factor, discounted value, basic algebraic operations, investments, exponents, and solving linear equations.
Annuity
An annuity is a series of fixed payments made over a period of time, such as rent, car payments, or bond coupons. It is a type of investment providing a steady income stream, often used for retirement. The most common payment frequencies are yearly, semi-annually, quarterly, and monthly.
Calculating the Future Value or accumulated value of an Annuity
The future value (accumulated value) of an annuity tells you how much you will have in the future by investing a fixed amount per period. To find this, you can calculate the future value of each payment and sum them. A mathematical shortcut is the formula for the accumulated value of an ordinary annuity.
🔑 Definition — Annuity: A series of fixed payments required from you or paid to you at a specified frequency over a fixed period of time.
📐 Formula: Accumulated Value (S) = C × [((1 + i)^n – 1) / i] Where:
- C = Payment per period (amount of annuity)
- i = Interest rate per period
- n = Number of payments
- The term [((1 + i)^n – 1) / i] is the accumulation factor for n periods.
📌 Example 1: Consider receiving $1,000 every year for 5 years, invested at 5%. C = $1000, i = 0.05, n = 5.
- Accumulation Factor = ((1 + 0.05)^5 – 1) / 0.05 = 5.53
- Accumulated Value S = $1000 × 5.53 = $5525.63
Calculating the Present Value or discounted value of an Annuity
The present value (discounted value) of an annuity determines today’s worth of a series of future payments. You can calculate the present value of each future payment and add them. A mathematical shortcut is the formula for the present value of an ordinary annuity.
📐 Formula: Discounted Value (A) = C × [(1 – (1 + i)^(-n)) / i] Where:
- C = Cash flow per period
- i = Interest rate
- n = Number of payments
- The term [(1 – (1 + i)^(-n)) / i] is the discount factor for n periods.
📌 Example 2: Using the same cash flow as Example 1 ($1,000 every year for 5 years, discounted at 5%). C = $1000, i = 0.05, n = 5.
- Discount Factor = (1 – (1 + 0.05)^(-5)) / 0.05 = 4.33
- Discounted Value A = $1000 × 4.33 = $4329.48
NOTATIONS
In annuity calculations:
- R = Amount of annuity
- n = Number of payments
- i = Interest rate per conversion period
- S = Accumulated value
- A = Discounted or present worth of an annuity
ACCUMULATED VALUE
The accumulated value (S) of an annuity is the total payments made including the interest.
- Formula: S = R[((1 + i)^n – 1) / i]
- 💡 Why this matters: This formula is a short cut for finding the total value of all payments and interest earned at the end of the term, giving a more accurate result than summing individual rounded values.
DISCOUNT FACTOR AND DISCOUNTED VALUE
When a future value is converted into its present worth, the rate used is the discount rate. The present worth of future payments is called the discounted value.
📌 Example 1: Accumulation Factor (AF) for n payments. Rate of interest i = 4.25%, Number of periods n = 18, Amount of Annuity R = 10,000 Rs. AF = ((1 + 0.0425)^18 – 1) / 0.0425 = 26.24 Accumulated Value S = 10,000 × 26.24 = 260,240 Rs.
📌 Example 2: Discounted Value (DV). Using the same values as Example 1 (i=4.25%, n=18, R=10,000 Rs.). Discount Factor (DF) = (1 – 1/(1 + 0.0425)^18) / 0.0425 = 12.4059 Discounted Value = 10,000 × 12.4059 = 124,059 Rs.
📌 Example 3: Discounted Value (DV). How much money deposited now will provide payments of Rs. 2000 at the end of each half-year for 10 years if interest is 11% compounded six-monthly?
- Amount of annuity (R) = 2000 Rs.
- Rate of interest per period (i) = 11% / 2 = 0.055
- Number of periods (n) = 10 × 2 = 20
- Discounted Value = 2000 × [(1 – 1 / (1 + 0.055)^20) / 0.055] = 2000 × 11.95 = 23,900.77 Rs.
ALGEBRAIC OPERATIONS
An algebraic expression indicates mathematical operations on a combination of numbers and variables. The components of an expression are separated by addition and subtraction. There are four types of terms: monomial (1 term), binomial (2 terms), trinomial (3 terms), and polynomial (more than 1 term).
Division by a monomial involves two steps:
- Identify factors in the numerator and denominator.
- Cancel common factors.
📌 Example: Simplify 36x²y / 60xy²
- Factor: [3 × 12 × (x)(x)(y)] / [5 × 12 × (x)(y)(y)]
- Cancel common factors 12, x, and y. Result: 3x / 5y
📌 Example: Simplify (48a² – 32ab) / 8a
- Divide each term in the numerator by the denominator: (48a²/8a) – (32ab/8a)
- Cancel factors: 6a – 4b
Multiplying polynomials involves multiplying each term in one expression by each term in the other. The product of two negatives is positive.
📌 Example: Multiply –x(2x² – 3x – 1) = (-x)(2x²) + (-x)(-3x) + (-x)(-1) = -2x³ + 3x² + x
Exponents of a term mean calculating a power of that term.
📌 Example: Simplify (3x⁶y³ / x²z³)²
- Simplify inside the brackets first: (3x⁴y³ / z³)
- Square each factor: (3²)(x⁴²)(y³²) / z³*² Result: 9x⁸y⁶ / z⁶
LINEAR EQUATION
A linear equation is solved by isolating the variable.
📌 Example: Solve x = 341.25 + 0.025x
- Collect like terms: x – 0.025x = 341.25 → 0.975x = 341.25
- Divide both sides by the numerical coefficient: x = 341.25 / 0.975 Result: x = 350
⭐ Key Takeaways
For the exam, you must master the ability to differentiate between accumulated and discounted value problems and apply their respective formulas correctly. Remember that the accumulation factor is [((1 + i)^n – 1) / i] and the discount factor is [(1 – (1 + i)^(-n)) / i], and both are multiplied by the payment per period. You should be comfortable performing basic algebraic operations, including factoring, canceling common terms, and applying exponents. Finally, solving linear equations requires a two-step process: collect like terms on one side and then divide both sides by the coefficient of the variable. The definitions of annuity, monomial, binomial, and polynomial are also essential.
🧠 Quick Revision Questions
- What is an annuity and what is it typically used for?
- Write the formula for calculating the accumulated value of an annuity and identify the accumulation factor.
- What is the discount factor formula, and how is it used to find the discounted value of an annuity?
- Simplify the algebraic expression: (75x³y²) / (25x²y⁵).
- Solve the linear equation: 2x + 5 = 3x – 10.
📘 Lecture 19 — Matrices
📖 Overview: This lecture introduces the concept of matrices, their dimensions, and basic types. It explains why matrices are essential tools in business, economics, and computer graphics for processing large datasets. The lecture also covers the identity matrix and its property as a multiplicative identity for matrices.
🗂️ Topics Covered
The lecture begins by discussing objectives and practical applications of matrices in fields like econometrics, network analysis, and linear programming. It then defines what a matrix is, explains its dimension or order, and distinguishes between row, column, and square matrices. Finally, it introduces the identity matrix and demonstrates its unique property as a multiplicative identity through a worked example.
📝 Lecture Summary
OBJECTIVES
The objectives of this lecture are to learn about matrices—what they are, their operations, typical applications, and how they are used in Excel. Students often wonder why they should study matrices, as there are many important practical applications in business and industry where large amounts of data are processed daily.
TYPICAL APPLICATIONS
Practical questions in modern business and economic management can be answered with the help of matrix representation in fields such as:
- Econometrics
- Network Analysis
- Decision Networks
- Optimization
- Linear Programming
- Analysis of data
- Computer graphics
WHAT IS A MATRIX?
A Matrix is a rectangular array of numbers. The plural of matrix is matrices. Matrices are usually represented with capital letters such as Matrix A, B, C. For example, the order for school clothing in September can be illustrated in a table and then represented as a matrix. The data from the table below:
| Size | Youth S | M | L | XL |
|---|---|---|---|---|
| Sweat Pants | 0 | 10 | 34 | 40 |
| Sweat Shirts | 18 | 25 | 29 | 21 |
| Shorts | 19 | 13 | 48 | 36 |
| T-shirts | 27 | 7 | 10 | 24 |
...can be entered in the shape of a matrix as follows:
[0 10 34 40 12]
[18 25 29 21 7 ]
[19 13 48 36 9 ]
[27 7 10 24 14]
💡 Why this matters: This shows how real-world tabular data can be converted into a matrix format for mathematical operations.
DIMENSION
Dimension or Order of a Matrix = Number of Rows × Number of Columns. The ‘×’ is just notation; it does not mean to multiply both numbers.
🔑 Definition — Dimension of a Matrix: The size of a matrix, expressed as rows × columns.
📌 Example: Matrix T has dimensions of 2×3, meaning it has 2 rows and 3 columns. The order of matrix T is 2×3.
ROW, COLUMN AND SQUARE MATRIX
Suppose n = 1,2,3,4,...
- A matrix with dimensions 1×n is referred to as a row matrix.
- A matrix with dimensions n×1 is referred to as a column matrix.
- A matrix with dimensions n×n is referred to as a square matrix.
📌 Example: Matrix A (right) is a 1×4 row matrix. Matrix B (middle) is a 2×1 column matrix. Matrix C is a 3×3 square matrix.
IDENTITY MATRIX
An identity matrix is a square matrix with 1's on the main diagonal (from the upper left to the lower right) and 0's off the main diagonal. An identity matrix is denoted as I. The subscript indicates the size of the identity matrix. For example, Iₙ represents an identity matrix with dimensions n × n.
MULTIPLICATIVE IDENTITY
With real numbers, the number 1 is referred to as a multiplicative identity because the product of any real number and 1 is that real number. With matrices, the identity matrix shares the same unique property as the number 1. In other words, for any 2×2 matrix A, the product I × A = A and A × I = A.
🔑 Definition — Multiplicative Identity for Matrices: The identity matrix I such that for any matrix A of compatible dimensions, I × A = A and A × I = A.
📐 Formula: I × A = A and A × I = A
📌 Example: Given the 2×2 matrix A = [2, -1; -3, 4]:
-
Compute I × A:
- r1c1 = 1(2) + 0(-3) = 2
- r1c2 = 1(-1) + 0(4) = -1
- r2c1 = 0(2) + 1(-3) = -3
- r2c2 = 0(-1) + 1(4) = 4 Result: [2, -1; -3, 4] = A
-
Compute A × I:
- r1c1 = 2(1) + (-1)(0) = 2
- r1c2 = 2(0) + (-1)(1) = -1
- r2c1 = -3(1) + 4(0) = -3
- r2c2 = -3(0) + 4(1) = 4 Result: [2, -1; -3, 4] = A
where 'r' is for row and 'c' is for column. This verifies that I × A = A and A × I = A.
⭐ Key Takeaways
A matrix is a rectangular array of numbers used extensively in business, economics, and computer science for processing large datasets. The dimension or order of a matrix is given as rows × columns, and three basic types are row matrix (1×n), column matrix (n×1), and square matrix (n×n). The identity matrix is a special square matrix with 1's on the main diagonal and 0's elsewhere, denoted as I, and it serves as the multiplicative identity for matrices—multiplying any compatible matrix by the identity yields the original matrix. Understanding these foundational concepts is essential for performing matrix operations and applying them to real-world problems.
🧠 Quick Revision Questions
- What is a matrix, and what is the plural form of matrix?
- What does the dimension or order of a matrix represent?
- What are the three types of matrices based on dimensions, and how do they differ?
- What is an identity matrix, and what are its characteristics?
- Why is the identity matrix called a multiplicative identity for matrices? Provide a simple example.
📘 Lecture 20 — Operation on Matrices
📖 Overview: This lecture introduces fundamental matrix operations used to organize and interpret data in business contexts. It covers addition, subtraction, scalar multiplication, and multiplication of matrices, along with the concept of matrix inverses, using real-world examples like clothing orders and juice sales to illustrate applications.
🗂️ Topics Covered
The lecture covers organizing data using matrices for business applications, matrix addition and subtraction with corresponding elements, scalar multiplication, matrix multiplication rules including row-column product definition and dimension compatibility checks, and finally the concept of multiplicative inverses for both real numbers and 2×2 matrices. Examples include athletic clothing orders for universities and juice sales revenue calculations for competing companies.
📝 Lecture Summary
OBJECTIVES
The objectives of the lecture are to learn about organizing and interpreting data using matrices, using matrices in business applications, adding and subtracting matrices, multiplying a matrix by a scalar, multiplying matrices, and interpreting the meaning of elements within a product matrix.
EXAMPLE 1
An athletic clothing company manufactures T-shirts and sweat shirts in four sizes: small, medium, large, and x-large. The company supplies two universities: U of R and U of S. The tables below show September's clothing orders.
University of S's September Clothing Order:
| S | M | L | XL | |
|---|---|---|---|---|
| T-shirts | 100 | 300 | 500 | 300 |
| sweat shirts | 150 | 400 | 450 | 250 |
University of R's September Clothing Order:
| S | M | L | XL | |
|---|---|---|---|---|
| T-shirts | 60 | 250 | 400 | 250 |
| sweat shirts | 100 | 200 | 350 | 200 |
Matrix Representation
The above information can be given by two matrices S and R:
S =
[100 300 500 300]
[150 400 450 250]
R =
[60 250 400 250]
[100 200 350 200]
MATRIX OPERATIONS
The matrix operations are summarized as: organize and interpret data using matrices, use matrices in business applications, add and subtract two matrices, multiply a matrix by a scalar, multiply two matrices, and interpret the meaning of the elements within a product matrix.
PRODUCTION
The clothing company's production in preparation for September orders is shown below:
| S | M | L | XL | |
|---|---|---|---|---|
| T-shirts | 300 | 700 | 900 | 500 |
| sweat shirts | 300 | 700 | 900 | 500 |
P =
[300 700 900 500]
[300 700 900 500]
ADDITION AND SUBTRACTION OF MATRICES
The sum or difference of two matrices is calculated by adding or subtracting the corresponding elements of the matrices. To add or subtract matrices, they must have the same dimensions.
PRODUCTION REQUIREMENT
Since U of S ordered 100 small T-shirts and U of R ordered 60, together 160 small T-shirts are required to supply both universities. To calculate the total number of T-shirts and sweat shirts required to supply both universities, add the corresponding elements of the two order matrices:
[100 300 500 300] + [60 250 400 250] = [160 550 900 550]
[150 400 450 250] [100 200 350 200] [250 600 800 450]
OVERPRODUCTION
The company produced 300 small T-shirts but received orders for only 160, meaning 140 small T-shirts too many were produced. To determine over-production, subtract the total order matrix from the production matrix:
[300 700 900 500] - [160 550 900 550] = [140 150 0 -50]
[300 700 900 500] [250 600 800 450] [ 50 100 100 50]
MULTIPLY A MATRIX BY A SCALAR
Given a matrix A and a number c, scalar multiplication cA is computed by multiplying the scalar c by every element of A. For example:
Let A =
[2 3]
[4 5]
Then 2A =
[4 6]
[8 10]
🔑 Definition — Scalar Multiplication: Multiplying a matrix by a scalar (a single number) by multiplying every element of the matrix by that scalar. 📐 Formula: If A = [aᵢⱼ] and c is a scalar, then cA = [c × aᵢⱼ] 📌 Example: If A = [[2,3],[4,5]] and c=2, then 2A = [[4,6],[8,10]]
MULTIPLICATION OF MATRICES
To understand matrix multiplication, consider this example: Competing companies A and B sell juice in 591 mL, 1 L, and 2 L plastic bottles at prices of Rs.1.60, Rs.2.30, and Rs.3.10 respectively. The sales for July:
| 591mL | 1L | 2L | |
|---|---|---|---|
| Company A | 20,000 | 5,500 | 10,600 |
| Company B | 18,250 | 7,000 | 11,000 |
What is total revenue of Company A? Company B?
Matrices illustrate this: Sales as a 2×3 matrix S, selling prices as a column matrix P, and total revenue as a column matrix R.
S =
[20000 5500 10600]
[18250 7000 11000]
P =
[1.60]
[2.30]
[3.10]
R =
[?]
[?]
Since revenue = number of sales × selling price, total revenue for each company is the product of the sales matrix and the price matrix. The product of a row and a column is the number obtained by multiplying corresponding entries (first by first, second by second, etc.) and adding the results.
MULTIPLICATION RULES
If matrix A is an m × n matrix and matrix B is an n × p matrix, then the product AB is the m × p matrix whose entry in the i-th row and j-th column is the product of the i-th row of A and the j-th column of B. The product of a row and a column is the number obtained by multiplying corresponding elements (first by first, second by second, etc.). To multiply matrices, the number of columns of A must equal the number of rows of B.
🔑 Definition — Matrix Multiplication: AB exists only when the number of columns of A equals the number of rows of B. The resulting matrix has dimensions equal to the rows of A by the columns of B. 📐 Formula: (AB)ᵢⱼ = Σₖ Aᵢₖ × Bₖⱼ (sum of products of corresponding elements from row i of A and column j of B) 📌 Example: For sales matrix S (2×3) and price matrix P (3×1): Company A revenue = (20000×1.60) + (5500×2.30) + (10600×3.10) = 32000 + 12650 + 32860 = Rs. 77,510 Company B revenue = (18250×1.60) + (7000×2.30) + (11000×3.10) = 29200 + 16100 + 34100 = Rs. 79,400
💡 Why this matters: Matrix multiplication allows us to compute combined results (like total revenue) by pairing rows of one matrix with columns of another.
EXAMPLE
Given matrices below, decide if the product exists and determine its dimensions:
A (3×3), B (3×2)
Product AB: Exists because inner dimensions match (3 columns of A = 3 rows of B). Result dimensions: 3×2.
Product BA: Does NOT exist because inner dimensions do not match (2 columns of B ≠ 3 rows of A).
MULTIPLICATION CHECKS
The table summarizes when multiplication is possible:
| Product | Dimensions of Matrices | Does product exist? | Dimensions of Product |
|---|---|---|---|
| AB | A = 3×3, B = 3×2 | Yes (inner dimensions match) | 3×2 |
| BA | B = 3×2, A = 3×3 | No (inner dimensions do not match) | n/a |
INVERSES
Real Numbers: Two non-zero real numbers are multiplicative inverses of each other if their product (in both orders) is 1. The multiplicative inverse of x is 1/x, since x × (1/x) = 1 and (1/x) × x = 1.
📌 Example: The multiplicative inverse of 5 is 1/5, since 5 × (1/5) = 1 and (1/5) × 5 = 1.
Matrices: Two 2×2 matrices are inverses of each other if their products (in both orders) is a 2×2 identity matrix. The multiplicative inverse of a 2×2 matrix A is denoted A⁻¹, such that A A⁻¹ = I and A⁻¹ A = I, where I is the identity matrix.
🔑 Definition — Identity Matrix: A square matrix with 1s on the main diagonal and 0s elsewhere. For 2×2: I = [[1,0],[0,1]]
📌 Example: The multiplicative inverse of matrix [[3,-1],[-5,2]] is [[2,1],[5,3]] since:
[3 -1] × [2 1] = [(3×2 + -1×5) (3×1 + -1×3)] = [6-5 3-3] = [1 0]
[-5 2] [5 3] [(-5×2 + 2×5) (-5×1 + 2×3)] [-10+10 -5+6] [0 1]
⭐ Key Takeaways
Matrix addition and subtraction require matrices of identical dimensions and involve adding or subtracting corresponding elements. Scalar multiplication multiplies every element of a matrix by the scalar. Matrix multiplication requires the number of columns of the first matrix to equal the number of rows of the second; the result has dimensions equal to the rows of the first by columns of the second. The product of a row and column is the sum of products of corresponding entries. A matrix's inverse (if it exists) produces the identity matrix when multiplied in either order. Always check dimension compatibility (inner dimensions match) before attempting matrix multiplication.
🧠 Quick Revision Questions
- What condition must two matrices satisfy to be added or subtracted?
- How is scalar multiplication performed on a matrix?
- What are the dimension requirements for matrix multiplication AB, and what are the dimensions of the product?
- In the juice company example, calculate Company A's total revenue step by step using matrix multiplication.
- What is the multiplicative inverse of a 2×2 matrix, and what property must it satisfy?
📘 Lecture 21 — Ratios and Proportions
📖 Overview: This lecture introduces the concepts of ratios and proportions, demonstrating how ratios can be used to estimate unknown quantities when only one quantity is known. It then transitions into merchandising, covering trade discounts, net price calculations, and the stakeholders involved in the pricing chain.
🗂️ Topics Covered
The lecture begins with estimating using ratios through two examples involving punch recipes, then solves a class grade ratio problem. It formally defines proportion and the property that the product of means equals the product of extremes, with examples solving for unknowns. The latter half introduces merchandising, covering stakeholders like the middleman, list price, and trade discount calculations.
📝 Lecture Summary
ESTIMATING USING RATIOS-EXAMPLE 1
In the previous lecture, we studied how ratios can be used to determine unknowns. Here is another example with a slightly different approach. Here, ratios between the quantities and data of only one quantity is known. We will estimate the total quantity that can be made. It is the quantity of orange juice that will determine the total quantity that can be made. Again the method is to use the ratio of the unknown to the known.
In a punch the ratio of mango juice, apple juice and orange juice is 3:2:1. If you have 1.5 liters of orange juice, how much punch can you make?
Calculation:
- Mango juice : Apple juice : Orange juice = 3 : 2 : 1
- Total = 3+2+1 = 6
- Mango juice (X) = (3/1)×1.5 = 4.5 litres
- Apple juice (Y) = (2/1)×1.5 = 3.0 litres
- Orange juice (Z) = 1.5 litres
- Punch = 4.5 + 3.0 + 1.5 = 9 litres
EXCEL Calculation: The method used is the same as in previous examples.
ESTIMATING USING RATIOS-EXAMPLE 2
In a punch ratio of mango juice, apple juice and orange juice is 3 : 2 : 1.5. If you have 500 litres of orange juice find how much mango and apple juices are required to make the punch.
The ratio of mango juice, apple juice and orange juice is 3 : 2 : 1.5 If you have 500 milliliters of orange juice, how much mango juice and apple juice is needed?
- Mango juice : Apple juice : Orange juice = 3 : 2 : 1.5
- Total = 6.5
- Mango juice (X) = (3/1.5)*500 = 1000 litres
- Apple juice (Y) = (2/1.5)*500 = 667 litres
- Orange juice (Z) = 500 litres
- Punch = 1000 + 667 + 500 = 2167 litres
EXCEL Calculation: Here also ratios were used.
- Mango juice = B45/B47*D47
- Apple juice = B46/B47*D47
- Orange juice = D47
EXAMPLE
In a certain class, the ratio of passing grades to failing grades is 7 to 5. How many of the 36 students failed the course?
The ratio, "7 to 5" (or 7 : 5 or 7/5), tells you that, of every 7 + 5 = 12 students, five failed. That is, 5/12 of the class failed.
Then (5/12)(36) = 15 students failed.
PROPORTION
a/b = c/d
...the values in the "b" and "c" positions are called the "means" of the proportion, while the values in the "a" and "d" positions are called the "extremes" of the proportion. A basic defining property of a proportion is that the product of the means is equal to the product of the extremes. In other words, given:
a/b = c/d
...it is a fact that ad = bc.
🔑 Definition — Proportion: An equation stating that two ratios are equal.
📐 Formula: ad = bc → In a proportion a/b = c/d, the product of the extremes (a and d) equals the product of the means (b and c).
PROPORTION-EXAMPLES
Is 24/140 proportional to 30/176?
Check: 140 × 30 = 4200, 24 × 176 = 4224
So the answer is that given ratios are not proportional.
PROPORTION EXAMPLE 1
Find the unknown value in the proportion: 2 : x = 3 : 9.
First, convert the colon-notation ratios to fractions: 2/x = 3/9
Then: 18 = 3x, x = 6
PROPORTION EXAMPLE 2
Find the unknown value in the proportion: (2x + 1) : 2 = (x + 2) : 5
First, convert the colon-notation ratios to fractions: (2x + 1)/2 = (x + 2)/5
Then solve: 5(2x + 1) = 2(x + 2) 10x + 5 = 2x + 4 8x = 1 x = –1/8
MERCHANDISING
What does merchandising cover?
- Understand the ordinary dating notation for the terms of payment of an invoice.
- Solve merchandise pricing problems involving mark ups and markdowns.
- Calculate the net price of an item after single or multiple trade discounts.
- Calculate a single discount rate that is equivalent to a series of multiple discounts.
- Calculate the amount of the cash discount for which a payment qualifies.
STAKEHOLDERS IN Merchandising
Who are the stakeholders in merchandising? The main players are:
- Manufacturer
- Middleman
- Retailer
- Consumer
There are discounts at all levels in the above chain.
MIDDLEMAN
A middle man is a person who buys a product directly from the manufacturer, and then either sells the product at retail prices to the public, or sells the product at wholesale prices to a distributor. There can often be more than one middle man when the latter practice is adopted. A middle man can purchase from the manufacturer and then work with another middle man who buys for the distributor. The manufacturer often views the middle man as the alternative to direct distribution.
List price or Retail price
List price refers to the manufacturer's suggested retail pricing. It may or may not be the price asked of the consumer. Much depends on:
- the product itself,
- the built-in profit margin,
- Supply and demand.
A product that is in high demand with low availability will sometimes sell higher than the list price, though this is less common than the reverse. Virtually all products have a suggested retail or list price. Resellers (middleman, retailer) buy products in bulk and get a substantial discount in order to be able to get profit from selling the product at or below list price.
Trade Discount
Let L is the list price, then amount of trade discount is some percentage of this price. List price less amount of discount is the net price. In mathematical terms, we can write:
Amount of discount = d × L
Where, d = Percentage of Discount, L = List Price
Net Price = L – Ld = L(1 – d)
Net Price = List Price – Amount of Discount
💡 Why this matters: Understanding trade discounts is crucial for calculating the actual cost to a reseller and determining the profit margin at each stage of the supply chain.
⭐ Key Takeaways
Ratios can be used to estimate unknown quantities in a mixture by multiplying the known quantity by the ratio of the unknown component to the known component. A proportion is an equality of two ratios, and its fundamental property is that the product of the means equals the product of the extremes (ad = bc). In merchandising, the net price is the list price minus the trade discount, calculated as L(1 – d). The middleman, retailer, and consumer are key stakeholders in the pricing chain, where discounts are applied at each level.
🧠 Quick Revision Questions
- In a punch with a ratio of mango:apple:orange = 3:2:1, if you have 2 liters of mango juice, how much orange juice and total punch can you make?
- Is the ratio 15:25 proportional to 9:15? Justify your answer using the means-extremes property.
- Solve for x in the proportion: 4:x = 5:20.
- A manufacturer offers a 20% trade discount on a list price of $500. What is the net price?
- In a class of 48 students, if the ratio of passing to failing grades is 5:3, how many students failed?
📘 Lecture 22 — Introduction to Statistics
📖 Overview: This lecture introduces the field of statistics, its meaning, and its scope as a science for drawing conclusions from numerical data. It covers the fundamental characteristics of statistics, differentiates between data and variables, and explains measurement scales and errors, providing a foundation for understanding how statistical methods are applied across various disciplines.
🗂️ Topics Covered
The lecture begins by defining what statistics is and its various meanings, including as numerical data, as a scientific discipline, and as sample quantities. It then outlines the key characteristics of the science of statistics, explains how statistics works, and highlights its importance in diverse fields. The lecture moves on to define data, observations, and variables, classifying them as quantitative vs. qualitative and discrete vs. continuous. Finally, it details the four measurement scales (nominal, ordinal, interval, ratio) and discusses errors of measurement, including biased and random errors.
📝 Lecture Summary
WHAT IS STATISTICS?
Statistics is the science that enables us to draw conclusions about various phenomena based on real data collected on a sample basis. It serves as a tool for data-based research, also known as quantitative analysis, and has applications in virtually every field from Anthropology to Zoology. Modern developed countries promote Statistical Literacy as an essential skill for interpreting real-life data and making informed decisions.
MEANINGS OF ‘STATISTICS’
The word "Statistics" has three distinct meanings:
- Plural form: Refers to numerical facts systematically arranged, such as statistics of prices or crimes. This is the common, everyday meaning.
- Singular form: Denotes a discipline or science that includes procedures for collecting, processing, and analyzing numerical data to make inferences and decisions in the face of uncertainty (the incompleteness of data).
- Plural form (quantities): Refers to numerical quantities calculated from sample observations; a single such quantity is a statistic (e.g., the mean of a sample).
CHARACTERISTICS OF THE SCIENCE OF STATISTICS
Key characteristics of statistics include:
- It deals with the behaviour of aggregates or large groups of data, not individual items.
- It deals with aggregates of observations of the same kind.
- It deals with variability that obscures underlying patterns.
- It deals with uncertainty, leading to conclusions in terms of probability.
- It deals with characteristics that can be described numerically.
- It deals with aggregates subject to a number of random causes.
- Statistical laws are valid on the average or in the long run, not guaranteed for all cases.
- Statistical results can be misleading if data collection or interpretation is flawed.
THE WAY IN WHICH STATISTICS WORKS
Statistics has several main functions:
- It summarizes large sets of data into an understandable form.
- It assists in the efficient design of experiments and surveys.
- It aids in sound and effective planning in any field.
- It helps in drawing general conclusions and making predictions under given conditions.
IMPORTANCE OF STATISTICS IN VARIOUS FIELDS
Statistical techniques are powerful tools for analyzing numerical data across all branches of learning. A modern administrator, politician, businessman, social scientist, and research worker all use statistics. Banks, insurance companies, and governments have statistics departments. The lecture notes that "a social scientist without an adequate understanding of statistics, is often like the blind man groping in a dark room for a black cat that is not there."
The Meaning of Data
Data, from the Latin for "those that are given," are the results of observations. Examples include statements in an interview, exam answers, athletic event results (e.g., marathon time), and scientific measurements (e.g., spectral composition of light).
OBSERVATIONS AND VARIABLES
An observation is any sort of numerical recording of information, whether a measurement (height), a classification (heads/tails), or an answer (yes/no). A variable is a characteristic that varies with an individual or object (e.g., age). The set of all possible values a variable can take is its domain. If the domain contains only one value, the variable is a constant.
QUANTITATIVE AND QUALITATIVE VARIABLES
Variables are classified by their form:
- Quantitative variable: A characteristic expressed numerically (e.g., age, weight, income).
- Qualitative variable (or attribute): A non-numerical characteristic (e.g., sex, eye-colour, quality). Individuals with such a characteristic can be counted or enumerated into categories.
Discrete and Continuous Variables
A quantitative variable is further classified:
- Discrete variable: Can only take a discrete set of integers (count data), such as the number of persons in a family. Values are taken by jumps.
- Continuous variable: Can take on any value (fractional or integral) within a given interval (measurement data), such as the height of a plant. Its domain is an interval with no gaps.
Measurement Scales
Measurement is assigning numbers to observations. The four scales are:
- NOMINAL SCALE: Classifies observations into mutually exclusive qualitative categories. Numbers (e.g., 1 for male, 2 for female) carry no numerical significance or order.
- ORDINAL OR RANKING SCALE: Has the property of ordering or ranking (e.g., excellent, good, fair, poor). The relation between categories is "greater than" (or more preferred).
- INTERVAL SCALE: Has a constant interval size but no true zero point. Temperature in Celsius or Fahrenheit is an example (e.g., 40°C is not twice as hot as 20°C). Addition and subtraction are meaningful.
- RATIO SCALE: A special interval scale with a meaningful true zero point as its origin (e.g., weight, volume, distance). This allows for meaningful ratios (e.g., 40 kg is twice as heavy as 20 kg).
🔑 Definition — [True Zero Point]: A point on a measurement scale where the value zero indicates the complete absence of the quantity being measured.
📐 Formula: [Ratio Scale] → always has a true zero point; [Interval Scale] → does not have a true zero point. 📌 Example: Temperature: 20°C and 40°C (Interval scale because 40/20 is not meaningful). Weight: 20 kg and 40 kg (Ratio scale because 40 kg is twice as heavy as 20 kg).
ERRORS OF MEASUREMENT
A continuous variable can never be measured perfectly, so measurements are recorded correct to the nearest unit. The difference between the observed value (x) and the true value (x+ε) is the error (ε). This is technically known as the error of measurement.
- Absolute error: The error ε, which involves the unit of measurement.
- Relative error: Absolute error divided by the true value: ε / (x+ε).
- Percentage error: Relative error multiplied by 100.
💡 Why this matters: In statistics, "error" does not mean a "mistake," but rather an inevitable departure from a true, unmeasurable value. Understanding error is fundamental to assessing the accuracy and reliability of any measurement.
BIASED AND RANDOM ERRORS
Errors are classified by their behavior:
- Biased error (or cumulative/systematic error): The observed value is consistently and constantly higher or lower than the true value. It arises from observer limitations or imperfect instruments. It is not revealed by repeating measurements and is cumulative (more measurements = larger error).
- Unbiased error (or random/accidental error): Deviations from the true value tend to occur equally often. It is revealed when measurements are repeated and tends to cancel out in the long run, making it compensating.
⭐ Key Takeaways
A student must understand that "Statistics" has three distinct meanings: as plural data, a singular science, and a sample quantity. The key characteristic of statistics is that it deals with aggregates of data that exhibit variability and uncertainty, leading to conclusions based on probability. It is crucial to differentiate between a qualitative variable (an attribute) and a quantitative variable, and within quantitative, between a discrete variable (counts) and a continuous variable (measurements). The four measurement scales (nominal, ordinal, interval, ratio) are fundamental for determining what arithmetic operations are permissible with data; the key difference between interval and ratio scales is the presence of a true zero point. Finally, statistical errors are not mistakes but inherent inaccuracies in measurement, classified as either biased (systematic) or unbiased (random).
🧠 Quick Revision Questions
- State the three different meanings of the word "statistics" as explained in the lecture.
- What is the fundamental difference between a qualitative variable and a quantitative variable?
- Give an example of a discrete variable and a continuous variable.
- What is the key property that distinguishes a ratio scale from an interval scale?
- Explain the difference between a biased error and an unbiased (random) error.