checkpoint 2 review

Common Mathematics Terminology

  • Symbolic Logic: Provides a foundation for understanding mathematical proofs and the terminology used in the discipline.

Definitions in Mathematics

  • Definition: A statement that specifies the meaning of a new term, symbol, or object.

    • Specifies what is meant by the term, serving as the sole authority on its meaning.

  • Standard Form of a Definition:

    • [Object] x is [term being defined] provided that it satisfies [specific conditions].

    • "Provided that" means "if and only if."

Examples of Definitions

  • Even Integer:

    • Definition: An integer n is even provided there is an integer k such that n = 2k.

  • Odd Integer:

    • Definition: An integer n is odd provided there is an integer k such that n = 2k + 1.

  • Divisibility:

    • Definition: Let a and b be integers. We say that a is divisible by b (also expressed as b divides a, or b is a factor of a) provided there is an integer c such that bc = a. We write b|a to indicate that b divides a.

The Limits of Definitions

  • Using the definitions above:

    • 24 is even because 24 = 2 imes 12 (12 is an integer).

    • 29 is odd because 29 = 2 imes 14 + 1 (14 is an integer).

  • Limitations of the definitions:

    • They cannot deduce that no integer is both even and odd without further properties of integers.

Your Turn: Determining Divisibility

  • Given: b|a means "b divides a."

    • 1. 24|3 - No: there is no integer c such that 24c = 3.

    • 2. 2|8 - Yes: 4 is integer and 2 imes 4 = 8.

    • 3. -3|6 - Yes: -2 is integer and -3 imes -2 = 6.

    • 4. 0|5 - No: there is no integer c such that 0 imes c = 5.

    • 5. 5|0 - Yes: 0 is integer and 5 imes 0 = 0.

    • 6. 0|0 - Yes: 37 is integer and 0 imes 37 = 0.

Two More Standard Definitions

  • Prime Integer:

    • Definition: An integer p is prime provided that p > 1 and the only positive divisors of p are 1 and p.

  • Composite Integer:

    • Definition: A positive integer a is composite provided there is an integer b such that 1 < b < a and b|a.

Examples of Prime and Composite Evaluations

  1. 21: Composite, because it has divisors 1, 3, 7, 21.

  2. 0: Not composite, as it does not meet the definition of prime.

  3. π: Not an integer, therefore not composite.

  4. 1: Not an integer, hence not composite.

  5. -2: Not greater than 1, hence not composite.

Postulates (Axioms)

  • Definition: A postulate (or axiom) is a statement that is assumed true without proof. Axioms serve as the starting points for further statements and deductions.

  • Example of an axiom about natural numbers:

    • If n is a natural number, then n + 1 is also a natural number.

Theorems and Friends

  • Theorem: A statement that follows logically from axioms, definitions, and previously established theorems, requiring proof.

  • Lemma: A theorem serving to help prove another theorem.

  • Proposition: A less significant theorem.

  • Corollary: A theorem that follows immediately from another theorem through a brief argument.

Conjectures, Counterexamples, and Vacuous Truth

  • Conjecture: A statement thought to be true but not yet proven.

    • Example: Goldbach’s Conjecture states that every even integer greater than two is the sum of two primes.

  • Counterexample: A specific case proving a statement false, e.g., 2 disproves "Every prime number is odd."

  • Vacuous Truth: An if-then statement is vacuously true if its hypothesis cannot be satisfied.

    • Example: "If an integer x is both prime and composite, then x is zero" is always true.

General Comments about Mathematical Proofs

  • Mathematical proofs often differ from formal proofs but share underlying principles. They tend to be narrative and may omit details depending on audience.

    • Example: The statement "if x + y is odd then exactly one of x or y is odd" implies universal quantification unless stated otherwise.

Overview of Proofs

  • Every proof contains:

    • A collection of hypotheses/premises H1, H2, ext{…, } H_k.

    • A desired conclusion C.

    • It must show that the conclusion is a logical consequence of the premises: H1 ext{ and } H2 ext{ and } … ext{ and } H_k ⇒ C.

Proof Process Overview

  • For direct proofs: Start by assuming all premises are true and conclude that the desired result C must also be true.

Preview: Format of Proofs for CIS 375

  1. Explicitly specify the claim you're trying to prove.

    • E.g., Proposition: If n is an even integer, then n + 1 is odd.

  2. Label and indicate the proof method.

    • E.g., Proof: (direct)

  3. State any initial assumptions/constraints clearly.

    • E.g., Suppose n is an even integer.

  4. Detail what needs to be shown, explaining the stopping condition.

    • E.g., Need to show: n + 1 is odd, meaning there exists an integer k such that n + 1 = 2k + 1.

  5. Fill the gap between assumptions and conclusions meaningfully.

  6. Conclude the proof explicitly.

    • E.g., Thus, n + 1 is odd.

A Sample Proof Format

  • Proposition: If n is an even integer, then n + 1 is odd.

  • Proof: (direct) Assume n is an even integer.

  • Need to show: n + 1 is odd (i.e., there exists k such that n + 1 = 2k + 1).

  • Since: n is even, there exists an integer m such that n = 2m. Thus, n + 1 = 2m + 1. Therefore, there is an integer k (namely m) such that n + 1 = 2k + 1, confirming it is odd.

Partitions and Equivalence Relations

Definition of a Partition

  • A partition of a set A is a collection of nonempty, pairwise disjoint sets whose union is A.

  • Each part (block) must be nonempty and distinct.

  • Example: { {V, Z}, {W, Y}, {X} } is a partition of {V, W, X, Y, Z}.

Equivalence Relations Definition

  • A relation R on the set A is an equivalence relation if it is reflexive, symmetric, and transitive.

  • Reflexive: For all x ∈ A, (x, x) ∈ R.

  • Symmetric: For all x, y ∈ A, if (x, y) ∈ R, then (y, x) ∈ R.

  • Transitive: For all x, y, z ∈ A, if (x, y) ∈ R and (y, z) ∈ R, then (x, z) ∈ R.

Example of Equivalence Relation

  • Consider the equality relation on the set of real numbers R. It satisfies all conditions for an equivalence relation.

Equivalence Classes

  • For equivalence relation R on set A, the equivalence class of an element w is defined as the set of elements related to w.

  • Denoted as [w]_R = {z ext{ in } A : (w, z) ext{ in } R}.

Extended Example with Student Roster

  • Consider the set of students (Vanna, Waldo, Xena, etc.) with various equivalence relations based on major, class standing, or grades.

Functions

Definition of a Function

  • A relation f is a function if for all a, b, c, if (a, b) in f and (a, c) in f, then b = c.

    • Ensures no two pairs have the same first component.

Examples of Function Definitions

  • Valid functions: f1 = {(1, 2), (2, 5), (4, 5), (10, −37)}

  • Invalid functions: f2 = {(1, 2), (2, 5), (4, 5), (2, −37)} (2 has two mappings).

Domains and Images

  • Domain of f: Set of all first elements x for which there exists y in f (dom f).

  • Image of f: Set of all second elements y for which there exists x in f (im f).

Functions from A to B

  • A function is from A to B if the domain of f equals A and the image of f is a subset of B.

Injective Functions

Definition

  • A function f : A → B is injective if, for all x1, x2 in A, if f(x1) = f(x2), then x1 = x2.

    • An alternative way: If x1 ≠ x2, then f(x1) ≠ f(x2).

Examples of Injective Functions

  • f1 is not injective, for example, if f1(2) = f1(4).

  • Function h(x) = x^2 is not injective over Z as example, but may be over non-negative integers.

Surjective Functions

Definition

  • A function f : A → B is surjective (onto) if for all y in B, there exists an x in A such that f(x) = y.

Bijective Functions

Definition

  • A function f : A → B is a bijection if it is both injective and surjective.

Proofs by Induction

Overview

  • Mathematical Induction: A method for proving statements that are asserted about positive integers.

    • Basis Step: Show the statement is true for the first positive integer (usually 1).

    • Inductive Step: Assume it is true for some arbitrary positive integer k and then show it is true for k + 1.

Example of Induction Proof

Claim: orall m, rac{m(m + 1)}{2} is the sum of the first m integers.

  1. Base Case: For m = 1, both sides are equal to 1.

  2. Inductive Step: Assuming it holds for k, show for k + 1.

Conclusion of Induction

Induction proves that the sum formula holds for all positive integers m.

Additional Properties of Relations

Definitions and Examples

  • Reflexive: Relation includes (a, a) for all a in A.

  • Irreflexive: Relation does not include (a, a) for any a in A.

  • Symmetric: If (x, y) is in R, implies (y, x) is in R.

  • Antisymmetric: If (x, y) and (y, x) are in R, then x must equal y.

  • Transitive: If (x, y) and (y, z) are in R, then (x, z) must also be in R.

Examples of Relation Properties

  • Consider various defined relations over different elements and categorize them according to the above properties.

Key Concepts in Set Theory

Definitions and Characteristics

  • Sets are collections of objects, defined via membership or subsets.

    • Cardinality indicates the number of elements in a set.

    • Equality of sets based on the identical elements.

Operations on Sets

  • Union, intersection, set difference, symmetric difference, and Cartesian products are standard operations delineated with specific notations and examples.

Power Sets

  • The power set of a set A, denoted as 2A, includes all possible subsets of A.

Summary of Set Operations

  • Various set operations summarize and describe common operations performed on sets with respective definitions and examples.

Conclusion

  • The notes cover essential mathematics terminology, foundational definitions, proof strategies, introductory concepts of functions and relations, set theories, and detailed operations on sets, aimed to provide comprehensive guidance for learners.