MathSpeak, Proofs, and Sets

Flashcards covering common mathematics terminology, types of numbers, set definitions, set operations, logical equivalences, and proof techniques discussed in the lecture notes 'An Introduction to MathSpeak and Proofs' and 'Sets'.

Definition (mathematics)

A statement that stipulates the meaning of a new term, symbol, or object, serving as the sole authority for what that term means. Its standard form is '[Object] x is [term being defined] provided that it satisfies [specific conditions]', where 'provided that' means 'if and only if'.

Even integer

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

Odd integer

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

Divisible by b (b divides a, b is a factor of a, b is a divisor of a)

For integers a and b, a is divisible by b provided there is an integer c such that bc = a. It is written as b|a.

Prime integer

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

Composite integer

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

Theorem

A statement that follows logically from axioms, definitions, and other established statements, which must have a valid argument (proof) based on these elements.

Lemma

A theorem whose main purpose is to help prove another theorem.

Proposition

A term sometimes used to refer to a theorem that is considered less significant than other theorems.

Corollary

A theorem that follows immediately from another theorem via a very short argument.

Conjecture

A statement thought to be true that has not yet been proved.

Counterexample

A value that shows a given statement to be false.

Vacuous truth

An if-then statement (conditional statement) that is considered true because its hypothesis (the 'if part') is impossible to satisfy.

Proof

A valid argument that demonstrates a conclusion is a logical consequence of certain hypotheses, meaning the conclusion is true whenever all hypotheses are true.

Postulate (or Axiom)

A statement that is assumed true without proof, serving as a basic, fundamental starting point from which other statements can be derived.

Set

An unordered collection of distinct objects.

Elements (or members)

The objects contained within a set.

x ∈ A

Notation indicating that x is an element (or member) of set A.

x ∉ A

Notation indicating that x is not an element (or member) of set A.

Z (set)

Represents the set of integers.

R (set)

Represents the set of real numbers.

∅ (Empty set)

A set containing no elements. Also written as {}.

Roster notation

A way to express a set by explicitly listing all of its elements between braces, where the order of elements and duplicate entries do not matter (e.g., {1, 4, 5}).

Set-builder notation

A way to describe a set by stating the properties that all its elements must satisfy (e.g., {y : y ∈ Z and y ≤ 100}).

Z⁺

Represents the set of positive integers.

Z⁻

Represents the set of negative integers.

N

Represents the set of natural numbers, including zero (i.e., {n ∈ Z : n ≥ 0}).

Q

Represents the set of rational numbers ({x ∈ R : there are p, q ∈ Z such that x = p/q}).

Cardinality of a set A (|A|)

The number of elements in set A.

Finite set

A set A is finite if its cardinality, |A|, is an integer.

Infinite set

A set that is not finite.

Set equality (A = B)

Sets A and B are equal if and only if they have exactly the same elements.

Subset (A ⊆ B)

Let A and B be sets. A is a subset of B if every element of A is also an element of B.

A B

Notation indicating that A is not a subset of B.

Power set of A (2^A or P(A))

The set whose elements are all the subsets of A (i.e., {S : S ⊆ A}). For a finite set A with n elements, its power set has 2ⁿ elements.

Union of A and B (A ∪ B)

The set {x : x ∈ A or x ∈ B}, containing all elements that are in A, or in B, or in both.

Intersection of A and B (A ∩ B)

The set {x : x ∈ A and x ∈ B}, containing all elements that are common to both A and B.

Set difference of A and B (A \ B)

The set {x : x ∈ A and x ∉ B}, containing all elements that are in A but not in B.

Symmetric difference of A and B (A Δ B)

The set {x : x ∈ A \ B or x ∈ B \ A}, containing all elements that are in A or in B, but not in both (i.e., not in their intersection).

Cartesian product of A and B (A × B)

The set {(x, y) : x ∈ A and y ∈ B}, containing all possible ordered pairs where the first element is from A and the second is from B.

Ordered pair (x, y)

A pair of elements where the order matters; (x, y) is not the same as (y, x) unless x = y.

Invalidating an 'if-then' statement

To show an 'if-then' statement 'If A then B' is false, one must provide a specific counterexample where the hypothesis A is true and the conclusion B is false.

Validating an 'if-then' statement (direct proof)

To show an 'if-then' statement 'If A then B' is true using a direct proof, one must suppose A is true and then show that B is also true.

Logical equivalence (A ≡ B)

Two propositional formulas A and B are logically equivalent if, for every possible interpretation of their variables, A's truth value is the same as B's truth value. One can always safely replace one by the other.

Logical consequence (A ⇒ B)

Propositional formula B is a logical consequence of A (or A1, …, An) if B is true for every interpretation that makes A (or A1 ^ … ^ An) true. If A is true, then B must also be true.

p ∧ q

Translates to 'p and q' or 'p but q'.

p ∨ q

Translates to 'either p or q (or both)' or 'at least one of p and q is true'.

¬(p ∨ q) ≡ ¬p ∧ ¬q

Translates to 'neither p nor q', 'p and q are both false', or 'it is not the case p and it is not the case q'.

¬(p ∧ q) ≡ ¬p ∨ ¬q

Translates to 'at least one of p and q is false' or 'it is not the case that both p and q are true'.

p → q

Translates to 'If p, then q.', 'q if p', 'p only if q', 'not p unless q', 'Whenever p, it follows that q', or 'q follows from p'.

p ↔ q

Translates to 'p if and only if q' (p iff q) or 'p is true exactly when q is true'.

Proving existential statements directly

To prove a statement of the form 'There exists x ∈ U such that P(x)', one must give a specific value v ∈ U and then show that P(v) is true.

Proving a subset (W ⊆ Z)

To show that W is a subset of Z, one must consider an arbitrary element 'a' in W and then show that 'a' is also an element of Z.

Showing not a subset (W ⊈ Z)

To show that W is not a subset of Z, one must provide a specific object 'v' and show that 'v' is an element of W but not an element of Z.