Discrete Mathematics Study Notes

Chapter 2 Summary

  • Main Topics Covered:
    • Sets
    • The Language of Sets
    • Set Operations
    • Set Identities
    • Functions
    • Types of Functions
    • Operations on Functions
    • Computability
    • Sequences and Summations
    • Types of Sequences
    • Summation Formulae
    • Set Cardinality
    • Countable Sets
    • Matrices
    • Matrix Arithmetic

Section 2.1: Sets

  • Definition of Sets:

    • A set is defined as an unordered collection of distinct objects (elements).
    • Examples include:
    • The students in a classroom.
    • The chairs in a room.
    • Notation:
    • An element a is in a set A is denoted as a ∈ A.
    • If a is not in A, it is denoted as a ∉ A.

  • Describing Sets:

    • Roster Method:
    • Example set: S = {a, b, c, d}.
    • Order of elements in the set doesn't matter:
      • S = {a,b,c,d} = {b,c,a,d}.
    • Repetition of elements doesn't change the set:
      • S = {a,b,c} = {a,b,c,b,c,d}.
    • Ellipses (...) can be used when there's a clear pattern:
      • S = {a, b, c, ..., z}.

  • Important Sets in Mathematics:

    • N = {0, 1, 2, 3, ...} (Natural Numbers)
    • Z = {..., -3, -2, -1, 0, 1, 2, 3, ...} (Integers)
    • Z⁺ = {1, 2, 3, ...} (Positive Integers)
    • R (Real Numbers)
    • R⁺ (Positive Real Numbers)
    • C (Complex Numbers)
    • Q (Rational Numbers)

  • Set-Builder Notation:

    • Defines a set using properties that its members must satisfy.
    • Example:, S = {x | x is a positive integer less than 100}.
    • Predicates can denote sets:
    • Example: S = {x | Prime(x)}.
    • Positive rational numbers: Q⁺ = {x ∈ R | x = p/q, p,q positive integers}.

  • Interval Notation:

    • Describes intervals using square [ ] or round ( ) brackets:
    • [a,b] = {x | a ≤ x ≤ b} (closed interval)
    • [a,b) = {x | a ≤ x < b}
    • (a,b] = {x | a < x ≤ b}
    • (a,b) = {x | a < x < b} (open interval)

  • Universal Set and Empty Set:

    • Universal Set (U): Includes all elements under consideration.
    • Empty Set (∅): Contains no elements and is different from a set containing the empty set.

  • Russell's Paradox:

    • Consider the set S of all sets that are not members of themselves; the question Is S a member of itself? leads to a paradox.
    • Similar to the barber paradox where a barber shaves all those who do not shave themselves.

  • Set Equality:

    • Two sets A and B are equal if they have the same elements;
    • Denoted as A = B. Examples:
      • {1,3,5} = {3, 5, 1}.

  • Subsets:

    • Definition: Set A is a subset of set B if every element of A is also contained in B.
    • Denoted as A ⊆ B.
    • Properties:
    • Empty set ∅ is a subset of every set: ∅ ⊆ S.
    • Every set is a subset of itself: S ⊆ S.

  • Showing Subset Relationships:

    • To show A ⊆ B: Verify if x ∈ A implies x ∈ B.
    • To show A ⊈ B: Identify an element x ∈ A such that x ∉ B.

  • Proper Subsets:

    • If A ⊆ B and A ≠ B, then A is a proper subset of B, denoted as A ⊂ B.

  • Set Cardinality:

    • Definition: The cardinality of a set A, denoted as |A|, is the number of distinct elements in A.
    • Examples of cardinality:
    • |∅| = 0
    • If S is the English alphabet, then |S| = 26.

  • Power Sets:

    • Power set of A, denoted P(A), is the set of all subsets of A.
    • If A has n elements, then |P(A)| = 2ⁿ.

  • Tuples:

    • An ordered n-tuple (a1, a2, ..., an) consists of elements where order matters;
    • Two n-tuples are equal only if all corresponding elements are equal.

  • Cartesian Product:

    • Definition: The Cartesian Product of two sets A and B, denoted A × B, is the set of ordered pairs (a, b) where a ∈ A and b ∈ B.
    • Example: For A = {a,b} and B = {1,2,3}:
    • A × B = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)}.

Section 2.2: Set Operations

  • Boolean Algebra:

    • Set theory and propositional calculus are both examples of Boolean algebra.
    • A universal set U exists for all set operations.

  • Union:

    • Definition: The union of sets A and B, denoted A ∪ B, is the set of all elements in A, B, or both.
    • Example: A ∪ B = {1, 2, 3} ∪ {3, 4, 5} = {1, 2, 3, 4, 5}.

  • Intersection:

    • Definition: The intersection of sets A and B, denoted A ∩ B, is the set of elements that are both in A and B.
    • Example: A ∩ B = {1, 2, 3} ∩ {3, 4, 5} = {3}.

  • Complement:

    • Definition: If A is a set, the complement of A (with respect to U), denoted Ā, is defined by:
    • Ā = {x ∈ U | x ∉ A}.
    • Example: If U is the integers less than or equal to 10, Ā for A = {6,7,8} would be {1, 2, 3, 4, 5, 9, 10}.

  • Difference:

    • Definition: The difference of sets A and B, denoted A - B, includes elements of A not in B.
    • A - B = {x ∈ A ∧ x ∉ B}.

  • Cardinality of Union:

    • Inclusion-Exclusion Principle:
    • The formula is:
      ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A ∪ B| = |A| + |B| - |A ∩ B|
    • Used to count the number of elements in the union of two sets,
    • Example: If A has 5 elements and B has 6 elements, and they share 2 elements,
    • Then |A ∪ B| = 5 + 6 - 2 = 9.

  • Review Questions Example tally for student sets:

    • Given:
      • U = {0,1,2,3,4,5,6,7,8,9,10}
      • A = {1,2,3,4,5}
      • B = {4,5,6,7,8}
    • Solutions:
      1. A ∪ B = {1,2,3,4,5,6,7,8}
      2. A ∩ B = {4,5}
      3. Ā = {0,6,7,8,9,10}
      4. B - A = {6,7,8}

  • Symmetric Difference (Optional):

    • The symmetric difference of sets A and B, denoted A Δ B, is defined as:
    • A Δ B = (A - B) ∪ (B - A).

  • Set Identities:

    • Laws include:
    • Identity Law: A ∪ Ø = A and A ∩ U = A.
    • Idempotent Law: A ∪ A = A and A ∩ A = A.
    • Commutative Laws: A ∪ B = B ∪ A and A ∩ B = B ∩ A.
    • Associative Laws: A ∪ (B ∪ C) = (A ∪ B) ∪ C etc.
    • Distributive Laws: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) etc.

  • De Morgan's Laws:

    • Ā ∪ B = U if and only if A ∩ B = Ø.
    • Ā ∩ B = Ø if and only if A ∪ B = U.

Section 2.3: Functions

  • Definition of a Function:

    • A function f from set A to set B, denoted f: A → B, is a rule that assigns to each element in A exactly one element in B:
    • If f(a) = b, then b is unique to a within B.

  • Domain and Codomain:

    • Domain: Set A, Codomain: Set B.
    • Image: An element in B related to an element in A.
    • Preimage: An element in A related to an element in B.
    • Range: The set of all images f(A).

  • Types of Functions:

    • Injective (One-to-One):
    • f(a) = f(b) implies a = b. No two different inputs can produce the same output.
    • Surjective (Onto):
    • Every element in B has a preimage in A i.e., f covers the entire codomain.
    • Bijective (One-to-one Correspondence):
    • A function that is both injective and surjective.

  • Inverse Functions:

    • If f is a bijection, then its inverse, denoted f⁻¹, can be defined.
    • Example: If f(a) = b, then f⁻¹(b) = a.

  • Function Composition:

    • Let f: B → C and g: A → B, then composition f∘g is defined as:
    • f∘g(x) = f(g(x)).

  • Representing Functions:

    • Functions can be specified using explicit statements, formulas, or even programming languages.

Section 2.4: Sequences and Summations

  • Definition of Sequences:

    • A sequence is an ordered list of elements, typically defined as a function from a subset of integers to a set S.
    • Notation: the term of the sequence is denoted as a_n.

  • Geometric Progression:

    • A geometric progression is a sequence defined by a starting element a and a common ratio r:
    • Example: With a = 1 and r = 2, sequence is {1, 2, 4, 8, ...}.

  • Arithmetic Progression:

    • An arithmetic progression has a starting element a and a common difference d:
    • Example: With a = 1 and d = 2, sequence is {1, 3, 5, 7, ...}.

  • Recurrence Relations:

    • A recurrence relation defines a sequence based on previous terms. An example is the Fibonacci sequence.

  • Summation:

    • Summation notation is used to denote the sum of a sequence:
    • Σ_{j=m}^{n} a_j, where j is the index of summation.

Section 2.5: Countability and Cardinality

  • Cardinality:

    • The cardinality of a set is the measure of the 'number of elements' in the set.
    • Sets that can be put in one-to-one correspondence with natural numbers are countable; otherwise, they are uncountable.

  • Countable Sets Existence:

    • Example of a countable set: Positive integers, rational numbers.
    • Uncountable Sets: Example, the real numbers cannot be listed in a sequence, demonstrating uncountability.

  • Hilbert's Grand Hotel:

    • A thought experiment illustrating that even an infinite number of guests can accommodate new ones by shifting existing guests to the next room, maintaining countability.

  • Real Numbers as Uncountable:

    • Proved by Cantor's diagonal argument which shows a constructed number differing from any listed real number.

Section 2.6: Matrices

  • Definition of a Matrix:

    • A matrix is a rectangular array of numbers. Denoted as an m × n matrix.
    • An example:
      A=[a<em>11a</em>12 a<em>21a</em>22]A = \begin{bmatrix} a<em>{11} & a</em>{12} \ a<em>{21} & a</em>{22} \end{bmatrix}

  • Matrix Operations:

    • Addition: Two matrices can be added only if their dimensions match.
    • If A and B are both m × n, then A + B results in a new m × n matrix with each element being the sum of the corresponding entries.
    • Multiplication: For matrix multiplication, the number of columns in the first matrix must equal the number of rows in the second matrix.
    • Example: If A is m × k, and B is k × n, then their product AB is an m × n matrix.

  • Identity & Transpose:

    • The Identity Matrix: For any matrix A, operations involving $I_n$ (identity matrix of order n) leave A unchanged when multiplied.
    • The Transpose of a Matrix: The transpose of matrix A, denoted A^T, is obtained by switching its rows and columns.

Conclusion

  • This study guide covers fundamental concepts in discrete mathematics focusing particularly on sets, functions, sequences, summation, cardinality, and matrices as outlined in the course material for CMSC 56. Students are encouraged to review examples for clarification on complex concepts.