CS173 UIUC Mathematics Terminology

Sets and Numbers

• Z: Represents all integers; includes {..., -3, -2, -1, 0, 1, 2, 3}.
• N: Denotes non-negative integers; considered natural numbers including 0.
• Z+: Indicates positive integers, excluding 0.
• R: Denotes real numbers; includes all rational and irrational numbers.
• Q: Represents rational numbers; designed as fractions p/q, with q ≠ 0, and includes operations for addition and multiplication.
• C: Refers to complex numbers; represented in the form a + bi.

Strings and Propositions

• ε in strings: Symbolizes the empty string, having a length of 0.
• Concatenation of strings: Combines two strings, e.g., "blue" + "cat" equals "bluecat".
• Proposition: A declarative statement that is either true or false; it cannot be a question or include variables.

Logical Operators

• p ∧ q (And): Truth table shows that both statements must be true for the conjunction to be true.
• p ∨ q (Or): Truth table indicates the disjunction is true if at least one statement is true.
• Exclusive or: True if only one of p or q is true; false if both are true.
• p → q (Implies): Truth table specifies that the implication is false only when p is true and q is false.
• Converse: The converse of p → q is q → p; they are not equivalent.
• Biconditional (p ↔ q): States p if and only if q; both must be true or both false.
• Contrapositive: ¬q → ¬p; logically equivalent to the original statement.
• De Morgan's Laws:
  • ¬(p ∧ q) = ¬p ∨ ¬q
  • ¬(p ∨ q) = ¬p ∧ ¬q
• Negation of implications: ¬(p → q) rewrites to p ∧ ¬q.

Quantifiers

• Universal Quantifier: Symbolized as ∀x; means "for all".
• Existential Quantifier: Symbolized as ∃y; means "there exists".
• Negation of universal statements: ¬(∀x, P(x)) is equivalent to ∃x, ¬P(x).

Proof Techniques

• Universal proof methods: General arguments can be proved or disproved with specific counter-examples.
• Existential proof methods: Specific examples can affirm existence, while general arguments can refute it.

Number Theory

• Divisibility: a | b signifies that a divides b; b can be expressed as an = b for some integer n.
• gcd (Greatest Common Divisor): Found by inspecting prime factors and identifying shared ones.
• lcm (Least Common Multiple): Calculated as lcm(a,b) = ab/gcd(a,b).
• GCD property: For any integers a and b, if a = bq + r, then gcd(a, b) = gcd(b, r).

Relations and Order

• a ≡ b mod k: Indicates that k divides (a - b).
• Reflexive Relation: Every element is related to itself, satisfied when for all x ∈ A, xRx holds.
• Irreflexive Relation: No element is related to itself.
• Symmetric Relation: Mutual relation where if xRy, then yRx.
• Antisymmetric Relation: Distinct elements are never related in both directions; if xRy and yRx, then x must equal y.
• Transitive Relation: If aRb and bRc, then a must relate to c.
• Partial Order: A relation that is reflexive, antisymmetric, and transitive.
• Linear Order: A partial order where every pair of elements is comparable.
• Strict Partial Order: Characterized by being irreflexive, antisymmetric, and transitive.
• Equivalence Relation: Defined as being reflexive, symmetric, and transitive.

Functions

• Basic Function: Defined as f: A → B, where A is the domain and B is the co-domain. The number of possible functions is P^N, where P is elements in B.
• Onto Function: For every y in B, there exists an x in A such that f(x) = y.