Words and symbols

The number 2.5 is not an integer.

Zero is not positive.

Positive means greater than zero. The nonnegative integers are the distinct set {0,1,2,…}; state the starting index when using either set.

Epp avoids the ambiguous term natural numbers here and distinguishes positive from nonnegative integers. Do not infer the lecturer’s zero convention from the symbol alone.

They can be positive, negative or zero. Only the denominator b must be nonzero. ℚ is a special style of Q; handwritten Q on the board denotes the same set.

Real numbers include all rational numbers and irrational numbers. Negative values and zero are allowed. ℝ is a special style of R; it denotes a different set from ℚ.

Infinity is not a real endpoint to include, so ∞ always has a round bracket in this notation. Intervals contain real values, not only integers.

Equality names the relation; equals is how we read the sign.

Equality compares values; it does not update a variable. In pseudocode x:=x+1 is assignment, whereas x=x+1 is an equation.

This negates equality.

Read this as: two is less than five.

The value 2 is allowed, as is any larger value.

Distance is nonnegative. These bars mean absolute value for a number, but cardinality in |A| for a set.

Squaring a is different from multiplying a by 2.

Juxtaposition denotes an ordinary product when the surrounding notation says the factors are numbers. A×B for sets denotes a Cartesian product instead.

Here x = 3 makes the equation true.

The term 3 stays fixed while x may vary.

An expression alone does not assert an equality. The statement 2x+1=7 is an equation.

Solving it means finding all allowed values of x that make the equality true. Here x=3.

The number 3 is an element of this set.

In 3∈A, the left side is an element and A is a set. A⊆B compares two sets. Neither expression performs the assignment :=.

The number 5 is not an element of this set.

Equality is allowed: every set is a subset of itself.

B has at least one element that is not in A.

The set {∅} has one element: the empty set itself.

We list the shared element 2 only once.

The number 2 is common to both sets.

Both sets have exactly the same elements.

Here | means neither divisibility nor absolute value; its meaning depends on the notation.

The order of A and B matters.

A complement depends on the chosen universal set.

All complements in a set identity must use the same fixed universe U. A prime mark is a complement only when that convention has been declared.

Here the vertical bars mean the size of a set.

For infinite sets, cardinality is compared using bijections; it is not a finite element count. See Cardinality and countability. For a number x, |x| is absolute value instead.

The order of the entries in a pair matters.

If A has n elements, its power set has 2ⁿ elements.

If |A|=n for an integer n≥0, then |𝒫(A)|=2^n: each element is either included in a subset or not.

An element is outside the union exactly when it is outside both sets. Related laws are A∪Aᶜ=U, A∩Aᶜ=∅, and (Aᶜ)ᶜ=A.

Each equals sign needs a valid law. Alternatively, fix an arbitrary x∈U and show that membership in the left and right sides is equivalent.

In digital logic, 1 and 0 encode these values. They do not make the logical operation OR the same as ordinary integer addition: 1∨1=1.

Distinguish arithmetic addition, 1+1=(10)₂, from OR. A binary numeral’s subscript is a base marker, not a sequence index.

Read negation as: it is not the case that…

Epp commonly writes ~p for negation. In a~b the same-looking mark may instead name a relation; read the whole construction.

One false part makes the conjunction false.

Logical OR is inclusive unless stated otherwise.

Unlike inclusive OR, XOR is false when both parts are true.

An implication need not describe a causal connection.

It is false exactly when p is true and q is false. The arrow in f:A→B specifies a function’s source and target, not this truth condition.

If and only if requires both directions.

A biconditional is a formula evaluated under a valuation. P≡Q is the claim that formulas P and Q agree under every valuation. The word iff abbreviates if and only if.

The sign ≡ also has a different use in modular arithmetic.

Logical ≡ is different from a≡b (mod m), which compares integer remainders. State the context before reading the sign.

These are algebraic roles, not a claim that every set is a number. In propositional logic the analogous roles are false, true, AND, OR and NOT.

Negate the complete parenthesized expression and each component, including the strictness of inequalities. ≡ says the two formulas agree under every truth assignment.

A question such as “How many?” is not a statement.

A table with n independent propositional inputs has 2^n rows. T… is not a mathematical symbol for a truth table.

At least one of these two parts is always true.

A statement and its negation cannot both be true.

One counterexample is enough to refute a universal statement.

The domain and the predicate’s scope are part of the statement. Over an empty domain, ∀x∈D P(x) is true because there is no counterexample.

The value 3 works. Existence does not require uniqueness.

The witness must belong to the stated domain. An existential statement over an empty domain is false; more than one witness is permitted.

The value is x=2; other possible values must also be ruled out.

P(x) does not mean P multiplied by x.

P(x,y) may have several free variables. Binding every free variable produces a closed formula. Alternatively, assigning values to the free variables lets you evaluate the predicate; the same free variable keeps the same value throughout that evaluation.

The same printed variable name can have both kinds of occurrence. Parentheses delimit the quantifier’s scope; this formula still depends on the free x.

In the first statement choose y=x+1 after x is given. The second asks for one integer larger than every integer; choosing x=y disproves that possibility.

With several quantifiers, apply the rule successively without reordering variables. Negate the whole predicate: ¬(P∧Q) becomes ¬P∨¬Q, not ¬P∧¬Q.

A domain can contain numbers, people, or other objects.

For the integer example, prove that an odd n has an odd square. The converse q→p and inverse ¬p→¬q are different statements and are not generally equivalent to p→q.

Definitions justify steps in mathematical arguments.

Checking a few numbers does not replace a proof of the general statement.

Assume the hypotheses, make justified deductions, then identify the required conclusion. The conditional being proved is not itself the proof.

The number 2 is prime and even, so the statement is false.

Then N+1 is an even larger integer, contradicting the assumption.

The cases must cover every possibility.

Proof cases must cover every possibility; they need not be disjoint. Disjointness is required for adding case counts without double counting, a different use of cases.

This follows the textbook convention requiring a nonzero divisor; a ∣ b is not the fraction a/b.

The operands are integers. This negates divisibility under the stated nonzero-divisor convention; it is not a fraction or an inequality.

The number 6 divides both; no larger positive integer does.

The difference 17−2=15 is divisible by 5.

Here a,b are integers and m is a positive integer. Congruence is a relation: it says m divides a−b. In contrast, a mod m is the single remainder value.

This produces one number. The statement a≡b (mod m) instead says their remainders agree. Some programming languages use a different convention for a negative dividend.

The defining bounds are ⌊x⌋≤x<⌊x⌋+1 and ⌈x⌉−1<x≤⌈x⌉. Floor does not generally mean truncating toward zero.

The remainder restriction makes q and r unique. The integer quotient is 3; the ordinary quotient 17/5 is 3.4.

The remainder is nonnegative and less than d. For example, −17=5×(−4)+3 has remainder 3.

Board example: a and b are integers, so 3a²b is an integer that serves as k.

Board example: the integer k is 5a+4b.

The number 1 is not prime; 2 is the only even prime.

The number 1 is neither prime nor composite.

The factors 3 and 4 have product 12.

Renaming the bound index does not change the sum. ∑ is the summation operator; capital Σ can instead name an alphabet in formal-language notation.

The standard empty-product convention is 1; the corresponding empty sum is 0. ∏ denotes multiplication of terms, whereas ∑ denotes addition.

The index identifies a position in the sequence.

State the index domain and its first value, for example n=0,1,2,… . The symbol a_n denotes one term, whereas (a_n) denotes the sequence; terms may repeat.

For two distinct real roots r₁,r₂ use C r₁^n+D r₂^n. For a repeated nonzero real root r use (C+Dn)r^n. Determine C,D from two initial values; these displayed templates concern real roots.

The initial value and the range where the rule applies belong to the definition. This recurrence is an example, not a universal symbol for recurrence relations.

Check an explicit candidate against both the recurrence and the initial values. Matching a few terms alone does not prove the formulas agree for every index.

The base starts the argument and the arbitrary step propagates it. A displayed P(k)→P(k+1) alone omits the base and is not a complete induction proof.

The smaller factors need not equal n−1, so access to all earlier cases is useful. State enough base cases for the recurrence or construction actually used.

Here z and o are declared counts of zeros and ones, not global operators. The recursive definition must generate every object under discussion.

Every allowed input must have exactly one output.

The declared function determines the operation; f(x) does not mean f multiplied by x. Distinguish an input element x from an input subset S in f(S).

Different inputs may produce the same output; the image is a set, so repeated outputs are listed once. This is different from the preimage f⁻¹(T).

The result is a set and may be empty or have several elements. This use of f⁻¹ does not claim an inverse function exists.

Changing the codomain can change whether a function is onto. A/B is not notation for these two roles.

The domain and codomain restrictions make the inverse possible. f⁻¹(y) denotes inverse-function evaluation, not the reciprocal 1/f(y); a preimage f⁻¹(T) of a set remains meaningful without an inverse function.

The inside function acts first. More generally composition is defined when every output of f used here lies in the domain of g; reversing the order can change the result or be undefined.

Equivalently, f(a)=f(b) implies a=b.

For f:A→B, the full condition is ∀x,y∈A (f(x)=f(y)→x=y). The arrow ↣ is an optional convention in some texts, not required notation for this property.

For a target value y, the input y−1 works.

For f:A→B, onto means ∀b∈B ∃a∈A (f(a)=b). The codomain B matters. The arrow ↠ is an optional notation, not the definition.

Specify the function and its domain/codomain. A bare ↔ usually marks a logical biconditional here; it is not a sufficient notation for a bijection.

An infinite set can match a proper subset by a bijection, unlike a finite set. Uncountable means no such finite or integer-indexed enumeration covers the set.

A function is a special kind of relation.

The notation aRb means (a,b)∈R. A relation on A has R⊆A×A; reflexivity, symmetry and transitivity below concern that setting.

An entry represents a particular ordered pair. A multigraph adjacency matrix may count parallel edges and therefore have entries greater than 1; that is a different convention.

For every integer a, a≤a.

Reversing the pair preserves this relationship.

The requirement applies to every suitable triple of elements.

Antisymmetric does not mean “not symmetric.”

Antisymmetric does not mean asymmetric or “not symmetric”. Equality on a set is both symmetric and antisymmetric.

An equivalence relation partitions its underlying set into classes.

Any two classes are equal or disjoint; the union of all equivalence classes is A. The brackets here do not mean a real interval or rounding down.

Some pairs of elements may be incomparable.

A partial order need not compare every pair. Under subset inclusion, {1} and {2} are incomparable. A total order additionally compares every pair.

The strict relation is irreflexive and transitive. “Not a≺b” does not imply b≺a, because a partial order may have incomparable pairs.

There are 24 ways to order four distinct objects.

P(n,k) is the number of choices, not one choice itself. At k=n this becomes n!; at k=0 there is one empty selection.

Order is ignored and elements are not repeated. Dividing P(n,k) by k! removes the k! orders of every selected subset; C(n,0)=C(n,n)=1.

A separator construction uses r identical stars and k−1 separators; the stars in compartment i give x_i. A positive minimum or an upper bound per type changes the model.

Pascal’s identity is C(n,k)=C(n−1,k−1)+C(n−1,k) for n≥2 and 1≤k≤n−1; split subsets by whether they include a fixed element. Boundary values are C(n,0)=C(n,n)=1.

Tutor example: every shirt can be paired with either pair of trousers.

An option must not be counted twice.

If every box contained fewer than that threshold, the total capacity would be too small. The expression n+1→n is a mnemonic, not a theorem statement.

This formula applies to two finite sets.

This is a tutor example.

The current probability lessons and Epp use S; Ω is another common name. In Ω(g), the same Greek letter instead belongs to asymptotic growth notation.

An event may contain several outcomes.

Counting favorable outcomes and dividing by the total requires finitely many equally likely outcomes.

The formula P(A)=|A|/|S| requires a finite sample space with equally likely outcomes; it is not a general definition for every model.

Different outcomes can give the same value. P(X=1) sums the probabilities of HT and TH; X itself is not an event.

Here the vertical bar means “given.”

The bar reads given, not divides or set-builder such that. Independence and mutually exclusive events are different conditions.

This gives P(∅)=0, P(S)=1 and additivity for disjoint events. The counting shortcut |A|/|S| is valid only when every outcome has weight 1/|S|.

The expectation need not be an attainable value. The sum is over values of X, not over repeated copies of the same value; infinite distributions need additional convergence conditions not covered by this finite formula.

Disjoint events with positive probabilities are not independent: their intersection has probability 0 but the product is positive. Independence is a property of the probability model, not just different event names.

The denominator is the total probability of E, summed over exhaustive disjoint cases. P(E|A)=2/10 here, which differs from P(A|E)=2/11.

This example is a simple undirected graph.

For a simple undirected graph, each edge is a two-element vertex set. With loops or parallel edges, retain named edges and their endpoint information; the simple encoding alone is insufficient.

This is a tutor example.

In a directed graph, an edge has a direction.

In a graph allowing loops, a loop contributes 2 to the degree.

Every edge joins one vertex in A to one in B. The optional symbol A⊔B means disjoint union; the two equations above state that condition explicitly.

For a simple graph entries are 0 or 1. A directed graph uses a row-to-column direction and need not give a symmetric matrix. Loop-diagonal conventions must be stated separately.

The parent is the preceding vertex on that root path; children are one level farther away. Depth counts edges, not vertices, and is not a vertex’s degree.

A tentative estimate is not automatically the final shortest distance. Dijkstra’s algorithm requires nonnegative edge weights. ∞ is an extended sentinel here, not an ordinary real weight.

These are walks, not necessarily paths: returning to a previous vertex is allowed. More generally (M^r)_ij counts length-r walks for nonnegative integer r; M⁰ is the identity matrix.

Pᵀ swaps P’s row and column indices. Right multiplication reorders columns and left multiplication by Pᵀ reorders rows. Reversing the convention for P changes the displayed identity; the matrix does not name an edge bijection.

A simple undirected graph excludes both loops and parallel edges. The degree convention does not by itself specify how a matrix should record loops; state the matrix convention explicitly.

Adjacency means one edge; connectedness permits a longer path. In this simple graph deg(v)=|N(v)|; parallel edges and loops require separate degree conventions.

This is the convention in Epp, 5th Metric edition, printed pages 679–680. A walk may repeat vertices and edges.

Epp calls this a simple circuit. Its first and last vertices coincide; a path cannot repeat that vertex.

The at-least-three-edges restriction belongs to this simple-graph setting. Use the separate walk/trail/circuit entry for the source’s general multigraph convention.

A path has no repeated vertex. A single vertex is a length-zero walk. Under Epp’s general convention a loop is a one-edge circuit; the at-least-three-edges cycle rule applies only to simple graphs.

A finite tree has |E|=|V|−1 and a unique path between every two vertices. Loops and parallel pairs would create circuits and are therefore excluded.

Matching vertex counts or degree lists is necessary but not sufficient in general. Distinct parallel edges must have distinct images even when their endpoint pairs coincide.

A finite spanning tree has |V|−1 edges. A minimum spanning tree minimizes total edge weight among spanning trees; it need not minimize the route from one fixed source to every vertex.

The right-hand x is read before the replacement. Assignment is an action; x=4 is a statement about a state, and 4∈A is set membership.

This is an exact count under that model; Θ(n²) describes its growth. It is not automatically a time in seconds or the count of every machine instruction.

Changing between fixed bases greater than 1 multiplies the logarithm by a positive constant. Actual algorithms may round sizes; include that rounding in an exact operation count.

The output change depends on the function and starting point. Δx is one quantity, not multiplication by an independently defined variable Δ.

Big O alone is an upper bound, not necessarily a tight order. The common shorthand f=O(g) means membership in a class of bounds, not equality with one function. Ω(g) is unrelated to the sample-space name Ω.

At an exit with i=n, this gives the required sum. Proving an invariant alone does not prove termination; that requires a separate argument.

Σ names a set here, whereas ∑ denotes summation. The bars in |w| denote string length, not absolute value or divisibility. A word’s order matters.

Zero concatenated words give ε, so ε belongs to every L*, even ∅*={ε}. The star applies to the preceding language or grouped regular expression; concatenation need not commute.

A word is accepted if and only if the state after its entire input lies in F. ε is accepted exactly when q₀∈F. An accepting state is not necessarily a halt state.

Include the empty continuation: an accepting state and a nonaccepting state are already distinguished by ε. The sign ∼ here is state equivalence, not propositional negation.

The inputs are supplied and the requested result is a value. Solving instead asks which inputs satisfy a stated condition.

Substitution checks the value: 3+2=5.

In this course solve can also mean finding an explicit sequence satisfying a recurrence and its initial values; read the object named after the verb.

Distribute A∩ over the union and use B∪Bᶜ=U. The rewritten expression has the same value under the stated universe; this is not solving for A.

A few successful numerical examples do not prove a statement about all integers.

Prove is the instruction; proof is the completed argument. A proof-end square □ marks completion in some notation, not the command itself.

A counterexample must satisfy the hypotheses and violate the conclusion.

Disprove is the instruction; disproof is the argument. The negation sign ¬ is not a universal abbreviation of that instruction.

Identify its role: a hypothesis, a case assumption, or an assumption in a proof by contradiction.

The sentence tells you whether an object is fixed, arbitrary or defined. Assume/suppose instead explicitly introduces a hypothesis to reason from.

There exists an integer x such that x is greater than 2.

Replacing x with 3 gives the true equality 3+2=5.

The word therefore does not itself prove the conclusion; the step needs justification.

This is a conclusion marker, not a logical connective and not a guarantee that the preceding reasoning is valid.

Equality names the relation, equation names an equality involving variables, and equals is the verb.

Include the domain when reading: integer says which objects are being considered.

The value k=3 works. The phrase for some does not mean exactly one.

If gives one direction. Iff includes both, so proving equivalence requires both directions.