Discrete Mathematics 1

Master foundational mathematical symbols and notation, including arithmetic, logic, set operations, number systems, and interval types, to build discrete mathematics literacy.

Explore the basics of sets, including notation, belonging, empty set, and descriptions, and learn to use Venn diagrams and core operations such as union, intersection, difference, and subset relations.

Explore how mathematics analyzes and abstracts structures, from concrete prototypes to algebraic structures like groups, rings, and fields. Study sets, binary operations, isomorphisms, vector spaces, and metric spaces.

Learn the cartesian coordinate system and the cartesian product of two sets, identifying points as ordered pairs on the plane via x and y axes.

Explore two important discrete sets—the natural numbers and the integers—covering zero's role, their order on the number line, and the contrast with dense, non-discrete rational numbers.

Explore the discrete metric: distance is zero for identical points and one otherwise, making every set discrete, and review the axiomatic properties of positivity, symmetry, and triangle inequality.

Explore the natural numbers as a discrete, infinite set closed under addition and multiplication, with zero and one as neutral elements, and the minimum principle guaranteeing a least element.

Learn the computational rules for adding, multiplying, and comparing natural numbers, integers, and rational numbers, including commutativity, associativity, distributivity, zero product property, cancellation property, and inverses.

Explore a visual motivation for commutativity in addition and multiplication, using natural numbers and rectangle area to show that changing order yields the same total.

Discover a visual motivation of associativity for addition and multiplication, using grouped objects and volume analogies to illustrate why order of grouping doesn't affect the result.

Explore the distributive law through visual and commercial motivations, then follow a step-by-step formal proof using the foil rule, the commutative and associative laws, and generalizations.

Explore how mathematical theories form from axioms and primitive notions, deriving theorems and definitions; learn about fields and the real numbers, with references to Euclid, Peano, Tarski, Hilbert.

Explore divisors, prime and composite numbers, and elementary divisibility rules. Master prime factorization and the greatest common divisor to simplify fractions and identify relatively prime pairs.

Explore rational numbers as fractions, including numerator and denominator, irreducible forms, proper and improper fractions, mixed numbers, and methods for adding, subtracting, multiplying, dividing, and comparing with least common denominators.

Learn to identify constants, variables, coefficients, powers and terms in algebraic expressions, and apply plus, minus, times, and division to build and evaluate expressions.

Explore the order of operations and precedence rules (Pemdas) from parentheses to exponents, then multiplication, division, and addition. Four examples illustrate distributive law and computational experience.

Plug in values for variables to evaluate algebraic expressions, apply precedence and order of operations, and compute results across cases with x and y.

Learn to simplify expressions before evaluating them by applying the square of the sum and the square of the difference, yielding 4/5 for all nonzero x and y.

Explore sigma and pi notation for sums and products, learn to use indices and bounds, and convert between explicit expressions and abbreviated sums and products in discrete mathematics.

Explore the concept of function across calculus and discrete mathematics, defining domain, codomain, and range; learn about graphs, mappings, and bijections with inverses.

Explore sequences as infinite lists with an index, where order and repetition matter, distinguish them from sets, and learn notation with parentheses, a_n, and a function from n to R.

Explore how everyday relations map to mathematical concepts like similarity, divisibility, and order. A binary relation on a non-empty set is a subset of its Cartesian product, with examples.

Explore graphs as discrete structures that model relationships, introducing vertices and edges, degree with in-degree and out-degree, loops, and directed graphs—from Euler’s bridges of Königsberg to reflexive and less-than-or-equal relations.

Explore direct proofs of formulas using the foil method, proving the square of the sum and the square of the difference in discrete mathematics.

demonstrate the difference of two squares: a^2 minus b^2 equals (a-b)(a+b) for all real numbers a and b by applying the foil method and highlighting cancellation to solve quadratic equations.

Prove the cube and fourth power formulas for sums. Explore general binomial theorem generalizations using Pascal's triangle, the foil method, and coefficient patterns.

Show that for a and b, a^n − b^n factors as (a−b) times a sum of n terms, with exponents shifting from a to b; use distributive law and cancellations.

Motivate the product rules and the power rule: multiply the same bases and add exponents, (a^k)(a^n)=a^(k+n); raise a power to a power, (a^n)^m=a^(nm); and expand (ab)^n=a^n b^n.

Generalize the power rule to any number of powers with the same base, showing that a^{n1} ... a^{nk} equals a^{sum n_i}, and provide a soft introduction to mathematical induction.

Explore two proofs of the Gauss formula for the sum of the first n natural numbers, using informal induction, the domino principle, and a counterexample contradiction via the minimum principle.

Prove the inequality a^2 + b^2 ≥ 2ab directly using (a - b)^2 ≥ 0, with equality only when a = b.

Show how to prove the inequality 2x + 5y > 19 directly from x > 2 and y > 3 by multiplying each inequality and adding results.

Apply an indirect proof to problem 11, showing that for x>2 and y>3, 2x+5y>19. Assume the opposite and derive 19>19, a contradiction, confirming the inequality.

Explore divisibility through remainders, factoring, and congruence modulo n, using visual, practical problem solving with even/odd and divisibility by two, three, and five.

Prove that if n is not divisible by three, then n^2 minus one is divisible by three, using two cases n ≡ 1 or 2 mod 3 and remainder analysis.

Determine numbers with remainders 2 mod 3 and 1 mod 4 by casework on mod 12; conclude numbers of the form 12k+5 yield the required remainders, with other cases eliminated.

Prove that six divides n^3 minus n by analyzing divisibility by two and by three with casework on n modulo two and modulo three, using their relative primeness.

Factor n to the third minus n as n(n-1)(n+1), a product of three consecutive integers, ensuring one factor is divisible by two and one by three, hence divisible by six.

Use factoring to factor n^5 - n into (n-1)n(n+1)(n^2+1), prove divisibility by 2 and 3 via consecutive numbers, and by 5 via case analysis mod 5, confirming divisibility by 30.

Prove divisibility by factoring, using problem 17 to show a large number is divisible by three. Factor pairs reveal a constant factor three, confirming divisibility and suggesting divisibility by six.

Apply the generalized a^n − b^n factorization to solve problem 18, proving 11^10 − 1 is divisible by 100 by using 11−1 and a ten-term sum ending in 0.

Learn logical thinking with a chart in discrete mathematics, solving a problem where only one friend tells the truth. Deduce that X speaks five languages from the chart.

Apply logical thinking and strategic reasoning to identify two fake coins among five with a balance scale in at most three weighings.

Divide nine coins into three groups of three and use a balance to find the single fake coin and whether it is heavier or lighter, in at most three weighings.

Apply logical thinking to problem 22 on a seven by ten board where every three by four and four by three rectangle sums to zero, yielding a total of -110.

Explore the pigeonhole principle as an easy, practical tool for reasoning; define boxes and objects to show at least one box holds more than one item.

Using the pigeonhole principle, place five points into four regions of side length three inside a six-unit equilateral triangle, ensuring two points are at distance at most three.

Apply the pigeonhole principle to modulo 3 squares; with three numbers, remainders are 0 or 1, so two share a remainder and their squared difference is divisible by three.

Apply the pigeonhole principle to modulo arithmetic to show that differences of squares, cubes, and fourth powers are divisible by 4, 9, and 16, using the binomial theorem.

Apply the pigeonhole principle to a six by six board with -1, 0, 1, showing that 14 sums (rows, columns, diagonals) cannot all be distinct because only 13 sums exist.

Two-color the hexagon’s sides and diagonals, and any coloring yields a triangle with vertices on the hexagon all in one color, by a generalized pigeonhole argument.

Explore mathematical modeling and graphs by reducing real problems to a two-color edge coloring on a hexagon, ensuring a monochromatic triangle, with applications to six people and six cities.

Count shortest A to B paths on an n by k grid with only right and up moves; preview the symmetry between n and k and the forthcoming path-count formula.

Learn how the shortest grid paths from A to B translate into binary sequences of n zeros and k ones, showing a 1-to-1 correspondence and symmetry.

Discover how to count permutations by arranging n distinct objects in a sequence, each appearing exactly once, and show that the number of arrangements equals n factorial.

Explore how bijections between two finite equinumerous sets correspond to permutations, illustrating that there are n! bijections between two n-element sets.

Explore fixed points of permutations of three elements and their vivid geometric interpretation as isometries of an equilateral triangle, including identity, rotations by 120 degrees, and mirror symmetries.

Solve the last problem: with three mislabelled boxes of black and white balls, use a two-check strategy based on permutation without fixed points to deduce all contents.

Explore the nature of statements and logical values, distinguishing open statements from closed ones and using true/false (1/0) to ground discrete logic and proofs.

Explore unary logical connective negation, which flips a statement's truth value using a truth table. Learn to form negations of atomic statements, equalities, and inequalities.

Explore the binary conjunction of p and q, the and connective, via a truth table showing it is true only when both statements are true, with examples and exercises.

Learn the disjunction as a binary logical connective; build truth tables for p or q, true if at least one is true, false only if both are false.

Master connectives and precedence in logic by tracing negation, conjunction, and disjunction from the inside out, using truth tables and example problems with P, Q, R, and S.

Explore the if-then implication and its truth table, noting it is false only when p is true and q is false, and identify necessary conditions with examples.

Introduce the converse, inverse, and contrapositive statements for implications, showing how switching p and q affects truth and that the contrapositive is logically equivalent to the original implication using examples.

Explore the equivalence connective, or if and only if, through truth tables and necessary and sufficient conditions, with practical examples of how these concepts relate to logic.

Compare equivalence and equality for boolean expressions, using examples like the difference of squares and x^2+y^2=1 to show when statements are true or false, and explore edge cases.

Explore tautology as a logical formula and learn how to recognize, use, and prove logical formulas with truth values, negation laws, and basic proof techniques.

Learn a general truth-table method to verify tautologies, illustrated with De Morgan's laws, showing how to negate disjunction via conjunction of negations and negate conjunction via disjunction of negations.

Explore tautologies and formal fallacies in a proof-driven lesson on p implies q, its contrapositive, and why converse and inverse are not equivalent, using truth tables.

Prove one of the distributive laws, conjunction over disjunction, as a tautology using an eight-row truth table with p, q, and r. The second law is left as an exercise.

Explore how to build and analyze truth tables for expressions with p, q, and r, using negation, conjunction, and disjunction to determine tautology status.

Explore tautologies via a truth table for p implies q, q implies r, and p implies r, involving three atomic statements and confirming the expression is a tautology.

Explore existential quantifiers, including there exists and there exists exactly one, with open statements over real, natural, and integer domains, plus two-variable examples and common pitfalls.

Explore the universal quantifier for all and how order matters, with additive and multiplicative inverses and examples showing true and false statements.

Explore how universal and existential quantifiers interact with precedence rules, showing how scope and parentheses distinguish for all x (p(x) or q(x)) from for all x p(x) or q(x).

Learn how to negate statements with universal and existential quantifiers using De Morgan's laws, and apply these ideas to monotone function definitions, including f(x)=1/x not decreasing on the entire domain.

Explore expressing number properties with logical symbols, including even numbers, sums of squares, prime numbers, divisors, and universal and existential quantifiers with De Morgan's laws.

Learn to detect implied quantifiers, make the domain explicit, and rewrite the sum of two positive integers as for all positive x and y, x+y>0, using logical symbols.

Solve a delightful logical problem combining divisibility and primes. Determine n and k by testing the options, yielding (n,k) = (9,2) and (17,6) where n+7k is prime.

Solve a classic six-person truth-teller and liar puzzle, with square and round chairs forming teams, to deduce who holds the diamond by neighbor questions.

Explore a lie detector puzzle with A, B, and C, using a chart and a truth table to identify who lies and who tells the truth.

Apply truth tables to solve problem 13 using three atomic statements pA, pB, and pC, revealing that B tells the truth while A and C lie.

Apply truth tables to a three-variable logic problem: determine which of A, B, C passed based on implications and exclusions; conclude that A and B passed, C did not.

Solve the zebra puzzle, a five-house logic problem attributed to Einstein, and explore left-right interpretation while deducing who drinks water and who owns the zebra.

Explore primitive notions of set and belonging to a set, including the empty set, and translate logic and tautologies to set theory using unions, intersections, and notation.

Explore the universe and its subsets, showing how choosing a universe shapes subset relations and complements. Use natural numbers, real numbers, and Venn diagrams to illustrate these ideas.

Link logic to set theory by showing how negation becomes complement, conjunction becomes intersection, and disjunction becomes union, with De Morgan's laws illustrated by Venn diagrams.

Define the intersection of sets via conjunction: x in the intersection iff x in A and x in B. Use intervals and disjoint sets, including infinite intersection converging to {0}.

Define the union of sets through disjunction, using big union notation and logical symbols, and illustrate with intervals and Venn diagrams.

Explore how two sets are equal exactly when they have the same elements, via the equivalence x in A iff x in B and the axiom of extensionality.

Define subset by implication: A ⊆ B iff every x in A is in B. Equality from mutual inclusion; negate with a counterexample x in A, not in B.

Learn how the empty set corresponds to a false statement and why it is a subset of every set via implication.

Define the universe as the largest set we work in, often N or Z, where belonging to the universe is the counterpart of a true statement in logic.

Define A minus B as elements in A that are not in B, illustrated with Venn diagrams and logical symbols; show the difference is not commutative.

Learn the symmetric difference of sets, defined as (A minus B) union (B minus A), and explore its commutativity and logical symbol formulation.

Define the complement of a set relative to a universe, denote it as A^c, and illustrate how different universes yield different complements.

Explore the laws of set theory and logic by translating sets into logical expressions, proving tautologies with truth tables, and applying De Morgan's and distributive laws.

Illustrates De Morgan's laws with Venn diagrams and truth-table proofs, using set theory concepts of complement, union, and intersection.

Illustrate and prove the distributive law of intersection over union using Venn diagrams and a tautology, linking to prior De Morgan and conjunction disjunction results.

Derive set difference and symmetric difference using set laws rather than tautologies, and prove identities with complements, De Morgan's laws, and the distributive and foil methods.

Explore the Cartesian product of two finite sets with practical exercises, using ordered pairs, coordinate representations, and visualizations to determine products and verify cardinalities.

Define the power set of a set X as all its subsets, denoted P(X) or 2^X, and illustrate with two, three, and four element sets, linking to boolean algebra.

Define the cardinality of a set as the number of its elements, with multiple notations, and distinguish counting finite sets from the challenges of infinite sets in discrete mathematics.

Show that the power set of a finite set X with |X|=n has cardinality 2^n by a one-to-one correspondence with sequences of zeros and ones of length n.

Equinumerous, or equipotent, sets share the same cardinality via bijections. The video links bijections to n! for n-element sets and introduces aleph zero and the continuum as cardinalities.

Explore the inclusion-exclusion principle for finite sets, learning how to compute union cardinalities by subtracting intersections for two and three sets, with visual intuition from Venn diagrams.

Explore the inclusion-exclusion principle with a three-language problem, using a Venn diagram and step-by-step calculations to determine all-three and single-language speakers.

Examine the transposition law and contrapositive, showing A subset of B iff the complement of B is subset of the complement of A, with Venn diagram illustration.

Explore two solved problems from the discrete mathematics book (problems 5 and 6) to illustrate set operations, including unions, intersections, Cartesian products, and power sets, with graphical reasoning.

Explore three Venn diagram problems in Boolean algebras, describing colored regions using union, intersection, and complement; relate set difference and symmetric difference to primary operations.

Define functions in discrete mathematics as having a unique output for each input, with every element of X as an input. Note no domain departure distinction in this context.

Explore core function concepts in discrete mathematics: domain, co-domain, and range; graphs; surjections, injections, bijections, inverse functions, and composition; plus related topics like monotonicity within ordered, discrete sets.

Identify topics left out of discrete mathematics and why they are less relevant, and show where to find them in precalculus and calculus resources.

Explore ways to define and depict functions, including verbal descriptions, value tables, two-line notation, Venn diagrams, and Cartesian graphs, with examples like Sweden's social security numbers and modulo five remainders.

Identify whether a rule defines a function by testing tables, arrows, Venn diagrams, graphs, and the vertical line test, ensuring one output per input and full domain coverage.

Explore recursively defined functions from natural numbers with an initial condition and a recurrence relation, revealing sequences and explicit formulas like f(n)=n^2 and f(n)=2^n.

Understand injections, surjections, and bijections, examine onto and 1-to-1 mappings, and analyze how different functions can be injective, surjective, both, or neither.

Examine how to detect injections across formula, graph, table, and verbal descriptions using the horizontal line test and value-argument equality. Distinguish injective from surjective cases, with examples and 1-to-1 reasoning.

Explore functions on positive natural numbers by examining divisors, sigma zero, and sigma one, including injections, surjections, and power-of-two cases.

Write and negate the definitions of injection and surjection using logical symbols, apply De Morgan’s laws for universal and existential quantifiers, and identify not injective and not surjective cases.

Explore injections and surjections on finite and infinite sets, identifying when a function is injective or surjective. Use examples like f(n)=2n and a surjective but not injective map on naturals.

Explore two simple function classes: constant functions map any input to one value, while identity functions map each element to itself, shown as a horizontal line and a diagonal.

Explore inverse functions in discrete math, determine when they exist for bijections, and construct f inverse from a table while observing the graph symmetry across the diagonal.

Explore the composition of functions, where f is applied first and g second, from x to z via y, noting inner and outer functions and the domain and image.

Explore how the order of composing functions matters using f(x)=2x+1 and g(x)=x^2−2. Show that g∘f and f∘g differ, illustrating noncommutativity.

See how composing f with the identity on x or the identity on y leaves f unchanged, illustrating that identity behaves like one in multiplication.

Explore compositions of permutations on a six-element set, compute sigma composed with tau and its inverse using table and diagram methods, and verify with two-line notation.

Explore the associativity of function composition, showing grouping does not affect the result. Note that composition is not commutative, and relates to identity functions, linear transformations, and geometry.

Explore how permutations of three elements map to equilateral triangle isometries, forming a non-commutative group under composition with inverses, identity, and symmetry-rotation relations.

Explore inverse functions and compositions using Cartesian products, surjective and injective mappings, and bijections, illustrating a function that is its own inverse and yields the identity under composition.

Explore the uniqueness of inverse functions through compositions. The lecture proves that if an inverse exists, it is unique, and shows identity, injective versus non-injective, and constant-function counterexamples.

Explore the theorem that a function has an inverse if and only if it is a bijection, and see how surjection and injection underpin this equivalence, yielding a unique inverse.

Examine surjections, injections, and compositions of functions; prove that if both f and g are surjective, then g∘f is surjective, and if both are injective, then g∘f is injective.

Explore surjections, injections, and compositions in problem 8, presenting a counterexample with surjective g and h but non-surjective f, and prove f is injective when g and h are injective.

Explore finite, countable, and uncountable sets, define equinumerous via bijections, and examine cardinalities such as aleph-zero and the continuum, including surjections from natural numbers.

Prove that natural numbers starting at four, even naturals, and all integers are countable by constructing surjections from the naturals, showing they have aleph0 cardinality and are equipotent with N.

Demonstrates that the set of rational numbers is countable by constructing surjections from natural numbers to pairs and to rationals via Cartesian products and bijections.

Explore images and inverse images of elements and subsets under a function, and the distinction between inverse image and inverse function. Learn how injections, surjections, and bijections relate to concepts.

Illustrate the difference between inverse function and inverse image using two mappings from X={1,2,3} to Y={a,b,c}, show when inverse function exists, and compute inverse images of all subsets.

examine images and inverse images of elements and subsets for the sum function f(a,b)=a+b on n×n, and describe inverse images of k as lattice points a+b=k in the first quadrant.

Explore images and inverse images in discrete mathematics, focusing on problem 13. Learn when A ⊆ f^{-1}(f(A)) holds with equality under injectivity, and when f(f^{-1}(B)) equals B under surjectivity.

Explore images, unions, and intersections under a function. The image of a union equals the union of images always; the image of the intersection equals the intersection only for injective functions.

Explore inverse images of unions and intersections and prove their equality for subsets of the codomain, using the definition of inverse image via f.

Explore monotone functions between finite, ordered sets, analyze increasing, decreasing, non-decreasing, and non-increasing mappings, and connect cardinalities to function counts and combinatorics.

Explore monotone functions through two celebrities, floor and ceiling, defined for all real numbers with integer outputs, non-decreasing, where floor is the greatest integer function and ceiling the least integer.

Explore periodic functions in discrete mathematics with definitions and basic period, featuring a mod-5 remainder function and the fractional part function as primary examples.

Explores even and odd functions in a discrete setting with integers, and shows y-axis and origin symmetry. Uses a mod five function to make explicit even and odd variants.

Explore compositions of f and g with f(n)=n^4 and g(n)=n mod 16. Find that f∘g has 16 outputs and g∘f has only 2 outputs, 0 or 1.

Explore binary relations on a non-empty set, including reflexive, symmetric, and transitive relations, equivalence classes, and order and partial order relations, with Cartesian product representations and graph depictions.

Learn how relations appear in the DM book, on page nine and in section 2.6, connected to graph theory; use PDF search or ask questions, with video 27 covering basics.

Examine the formal definition of binary relations as subsets of Cartesian products, define domain and range, and illustrate with a students-and-courses example and a bipartite graph.

Describe relations using verbal, roster, and graphical methods; illustrate with n divides k, real numbers with x ≤ y, and congruence modulo five as subsets of Cartesian products.

Learn to plot relations as subsets of Cartesian products, using real and integer coordinates, and distinguish equal, strict, and non-strict inequalities on the plane for discrete mathematics 1.

Depict relations on finite sets with a table of zeros and ones, equivalent to the Cartesian product. Explore four relations: less than, divisibility, x squared, and parity modulo two.

Translate relations on finite sets into directed graphs with vertices, edges, and loops, using tables or Cartesian products, and apply to divisibility and x is in relation with y.

Examine equivalence relations defined by reflexivity, symmetry, and transitivity, with examples like parallelity of lines and similarity of triangles, and identify non equivalence relations such as divisors and subset relations.

Learn to recognize equivalence relations from plots and tables by testing reflexivity, symmetry, and transitivity, with examples like diagonal reflexivity and modulo two congruence.

Apply a graph-based method to recognize reflexive, symmetric, and transitive relations on finite sets, using loops, double arrows, and closed triangles; e.g., modulo two is the only equivalence relation.

Explore relation congruence modulo n and prove it forms an equivalence relation by verifying reflexive, symmetric, and transitive properties.

Explore how equivalence relations partition sets into disjoint equivalence classes, illustrated by congruence modulo n and geometric examples, defining quotient sets.

Explore properties of relations in discrete mathematics 1, including irreflexive, antisymmetric, and strongly connected, and apply them to relations such as less than, greater than, and divisor relation n plus.

Define three types of ordered relations using reflexivity, antisymmetry, and transitivity, and show how non-strict and strict partial orders become total orders when every pair is comparable.

Explore partial orders and hasse diagrams in discrete mathematics 1 by examining proper subset and proper divisor relations, using the power set and the divisors of 60.

In discrete mathematics 1, evaluate three relations on a four-element set using tables and graphs to determine reflexive, symmetric, transitive, irreflexive, antisymmetric, asymmetric, connected, and strongly connected properties.

Examine a two-part relation on natural numbers: x=y for x,y ≤5, and x+y even for x,y>5; analyze reflexive, symmetric, and transitive properties.

Define integers from natural numbers using an equivalence relation on pairs of naturals. Represent each integer by an equivalence class and define addition and multiplication coordinate-wise.

Let E be the even numbers; X,Y in P(N) relate iff X ∩ E = Y ∩ E. The relation is reflexive, symmetric, and transitive.

Explore how functions and relations use the Cartesian product, show domain and range on graphs, and note that a relation can connect two different sets, not always a function.

See that every function is a relation, but not every relation is a function, since a function assigns one value per input, shown by the domain, graph, and ordered pairs.

Relate a relation's inverse by swapping pair positions, and state that a function's inverse exists only for bijections, illustrated by diagonal symmetry.

Analyze a relation from a four-element x to a three-element y. Determine departure set, domain, range, and inverse, then verify it is not a function using the vertical line test.

Examine four relations between sets x and y, apply the vertical line test to determine functions, and analyze inverses, injectivity, and domain considerations for the last case.

Explain the equality of functions through three conditions: same departure and target sets, same domain, and identical values on that domain, with A→B and C→D examples.

Explore compositions of relations by linking students to professors through courses, using a two-step relation from students to courses and from courses to professors to obtain student–professor pairs.

Explore compositions of relations with example 2 on natural numbers. Demonstrate that R composed with R relates x to x+2, and illustrate with two graph representations.

Explains the cancellation law for injective functions. If f is injective and f∘g1 = f∘g2, then g1 = g2, illustrating left cancelable property used to solve equations with logarithmic example.

Learn three theorems about compositions and inverses of functions: the associativity of composition, the invertibility of composed bijections, and the inverse of a composition equals the composition of inverses.

Translate three theorems from the previous video to relations, proving associativity of composition, the inverse of a composition, and the inverse of an inverse for relations.

Explore sequences as functions defined on the set of natural numbers. Learn to scale and add sequences, and contrast finite and infinite cases for proofs in discrete mathematics.

Explore explicit and recursive formulas for defining sequences, including deriving that the sum of odd numbers equals n squared via Gauss formula and a geometric illustration.

Explore monotone number sequences, defining increasing, decreasing, non-decreasing, and non-increasing sequences on natural numbers, with stepwise criteria a_n < a_{n+1}, and note finite sequences and counted repetitions.

Survey the proofs section of discrete mathematics 1, learning axioms, theorems, lemmas, and corollaries, plus various proof types. Find reading resources and methods, including direct, indirect, contrapositive, induction, and counterexamples.

Explore how axioms, primitive notions, and definitions shape mathematical theories, from sets and natural numbers to geometry, using betweenness, containment, and congruence to define line segments, angles, and triangles.

Defines axioms, motivates their selection, and uses real numbers as an ordered field to illustrate addition and multiplication axioms, inverses, and concepts of consistency, independence, completeness, and axiom of choice.

Explore the roles of theorems, propositions, lemmas, and corollaries within a chosen context, detailing assumptions, conclusions, and how lemmas support proofs, while corollaries follow from main theorems.

Master direct proofs in discrete mathematics by starting from assumptions, using axioms and modus ponens, and recognizing element chasing and the role of definitions.

Tackle two element-chasing proofs from the discrete mathematics book (pages 93–94), applying set and function concepts, including inverse image, to establish subset relations.

Explore direct proofs by deduction and reduction with three examples, covering even numbers, divisibility, and the arithmetic mean versus the geometric mean, with counterexamples and equivalences.

Apply De Morgan's laws to prove or disprove statements containing universal or existential quantifiers. The lecture uses n squared modulo three to illustrate counterexamples and handling negation.

Prove and disprove statements with quantifiers by exploring primes and a quadratic prime sequence, including a counterexample with p(n)=n^2+n+41 showing not all outputs are prime.

Show whether the cartesian product distributes over union: A × (B ∪ C) equals (A × B) ∪ (A × C).

Disprove the formula for all A, B, C by a counterexample: A={1}, B={2}, C={3}; left side is {1}, right side is {(1,1)}.

Prove that for sets A, B, and C, the formula with Cartesian product and set minus holds, using definitions, De Morgan's law, and distributive and associative properties to show equality.

Explore existence theorems with concrete calculus examples, including the Darboux property for continuous functions. Demonstrate Rolle’s theorem and the mean value theorem, and discuss derivatives and proofs.

Learn to prove statements directly from axioms in discrete mathematics, with examples like the cancellation law and order axioms, and see when uniqueness proofs arise.

Explore existence and uniqueness theorems by solving linear, exponential, and power equations with inverse operations, using logarithms and careful equation construction.

Explore proving uniqueness by showing exactly two of three statements hold, using last digits of squares and a^2 - b^2 = 89 with a+b=89 and a-b=1 to find n=1974.

Explore proofs by cases: learn how tautologies and divisibility problems reveal hidden cases in proofs, including De Morgan's laws and divisibility by three.

Dive into proofs by cases with geometry examples, including the inscribed angle theorem and cosine rule, and learn how corollaries follow from case-based proofs.

Explore how a cycle of implications establishes equivalence among statements, as shown by P→Q→R→P and transitivity. Then apply it to a square matrix: nonzero determinant implies all conditions hold.

Explore two main types of indirect proofs, contrapositive and contradiction, and learn to apply logical rules like modus tollens to prove theorems in discrete mathematics.

Explore direct and indirect proofs, including modus ponens, contrapositive, and proof by contradiction, with guided exercises and clear textbook examples from the DM book.

Explore proof by contrapositive in indirect proofs with example 18. Show that if a product of two integers is even, then at least one is even.

Prepare to understand the contrapositive-proof statement: for n positive natural numbers k1..kn, if the sum of reciprocals exceeds n/2, then some ki equals 1.

Use contrapositive to prove the inequality implies some ki equals one. Negate Q to all i; deduce ki is at least two, yielding a contradiction with reciprocals.

Explore the extended cancellation law for injective functions and its if-and-only-if characterization, using proof by contrapositive to show left cancelability on function compositions.

This lecture demonstrates the pigeonhole principle by contradiction and notes that contrapositive can be used; it discusses indirect proof strategies.

Use a proof by contradiction to show that if a is not equal to zero, a divides b, and a does not divide c, then a does not divide b+c.

Explore a proof by contradiction that the intersection of the intervals (-1/n, 1/n) for all n≥1 contains only zero, using the unbounded naturals lemma and the sigma notation for intersection.

Learn how to prove that the square root of two is irrational using proof by contradiction, leveraging irreducible fractions and a key lemma about even numbers.

prove by contradiction that there are infinitely many prime numbers. assume finite primes, form product of primes plus one, get a number with a new prime factor, contradicting finiteness.

Explore how equivalence relations partition a set into disjoint equivalence classes, forming a quotient set. The lecture emphasizes reflexivity, symmetry, and transitivity.

Demonstrates two proofs of uniqueness by contradiction in a group: the neutral element and each element's inverse, using group axioms and illustrative examples.

Explore the principle of mathematical induction and proofs by induction, connected across three courses, with material on the minimum principle and extra articles to derive and verify formulas.

Explore which statements induction can prove—formulas, inequalities, divisibility, and recursive sequences for all natural numbers or from a starting point n0—illustrated by Gauss's sum and the domino effect.

Learn how mathematical induction proves statements about natural numbers, starting from a base case and using an induction step, illustrated by the domino effect.

Explore proofs by induction of two formulas: the sum of squares from 1 to n and a sum of fractions equal to n/(n+1), with base cases and induction steps.

In induction proofs, both the base case and the induction step are essential. The domino analogy and examples show that missing either one invalidates the proof.

Learn to prove by induction that the sum of the first n odd numbers equals n squared, using recursively defined functions and the base case, induction step, and explicit formula.

Explores three recursively defined functions, derives explicit formulas f(n)=3×2^n, g(n)=7+2n, and h(n)=n!, and sketches induction proofs.

Explore strong induction with two base cases. Use a two-step recurrence to prove a closed form for the sequence a1=1, a2=8, where a_n = a_{n-1} + 2 a_{n-2}.

Explore induction with two base cases for linear recurrences, guessing and proving explicit formulas, with examples producing a_n = 2^{n+1}-1 and x_n = 2^n or 3^n.

Apply strong induction to prove that every integer n≥2 can be factored into primes, using a single base case n=2 and a case distinction between primes and composites.

Master induction to prove divisibility by nine for expressions like 2^(2n+1) + 3n + 7, using base case, induction step, and a completing-then-compensating technique.

This lecture, building on examples 43 and 44, proves by induction that 2^{6n+1} + 3^{2n+2} is divisible by 11 for all natural numbers n.

Examine induction proofs of inequalities not true for all naturals, using 2^n > 2n with base n=3 and a stepwise induction justification.

Prove that n! is greater than or equal to 2^n for n >= 4 using induction, starting with the base case n = 4 and the induction step to n+1.

Explore the inequality for all natural numbers n ≥ 2, where the left-hand side sum of 1/√k grows without bound, proven by induction from base case n=2.

Generalize formulas from two terms to any number of factors using induction, highlighting the base case, the induction step, and associativity of the operations (multiplication and addition).

Explore generalizing the logarithm product rule from two factors to any number, using base case and induction, with associativity guiding the proof.

The lecture discusses generalizing formulas through induction, extending De Morgan's laws to any number of statements, using base case n=2 and associativity, with examples from logic and set theory.

Demonstrate a more difficult induction proof for a^n − b^n, showing how a zero-operation trick lets you apply the induction hypothesis and extend to n+1.

This lecture demonstrates a proof by induction of a product formula for the first n factors, detailing base case and the induction step, with algebraic cancellation and factoring.

Review induction fundamentals as a domino-style process from base case to induction step. Apply to natural numbers, matrices, and polynomials, discuss strong induction, division with remainder, and direct deduction contrasts.

Compare induction with the well-ordering principle and see how a least counterexample leads to a contradiction, proving the sum of the first n natural numbers equals n(n+1)/2.

Offer practical advice for advanced theorem provers, covering direct and indirect proofs (contrapositives, contradictions), induction, and pigeonhole principles, with linked resources and the expert text by William Gunther.

Color the 15 by 15 board with red, yellow, and green, and prove by contradiction that two rows have the same number of squares colored with a color.

Analyze the 12 consecutive integers and show that at least one cannot be expressed as a sum of ten fourth powers, since such sums have remainders 0–10 modulo 16.

Use the pigeonhole principle and a contradiction to show that any sequence of distinct n^2+1 real numbers contains a subsequence of length n+1 that is strictly increasing or decreasing.