MATH 248 CALPOLY RETSEK

Length

The LENGTH of a word is however many letters it has

Difference

The DIFFERENCE between two words of equal length is the number of letter positions in which they disagree

Stable

A list of distinct words is called STABLE if each word on the list is the same length and the difference between consecutive words is one

Tight

A list of distinct words called TIGHT is each word is the same length and the difference or d(W, V) _< 2 for any two words on the list

Proposition

a statement that is either true or false

Equivalent

Two compound proportion forms are called EQUIVALENT if their truth tables agree (final column match)

Denial

A DENIAL of a proposition P is any proposition with the same truth value as ∼P.

Conjunction

Let P and Q represent propositions. The CONJUNCTION of P and Q is expressed symbolicallyP∧Q and is read "P andQ". The proposition P∧Q is true precisely when the component propositions P and Q are both true.

Disjunction

The DISJUNCTION of P and Q is expressed symbolicallyP∨Q and is read "P or Q". The proposition P∨Q is true precisely when at least one of the component propositions P and Q is true.

Negation

Let P represent a proposition. The negation of P is expressed symbolically∼P and is read "not P". The proposition ∼P is true precisely when the component proposition P is false.

Conditional

Let P and Q represent propositions. The CONDITIONAL sentence "If P, then Q" is expressed symbolically P⇒Q

Antecedent

In P⇒Q P is the ANTECEDENT

Consequent

In P⇒Q Q is the CONSEQUENT

Converse

The CONVERSE of the conditional sentence P⇒Q is the conditional sentence Q⇒P.

Contrapositive

The CONTRAPOSITIVE of the conditional sentence P⇒Q is the conditional sentence (∼Q)⇒(∼P).

Biconditional Sentence

Let P and Q represent propositions. The BICONDITIONAL SENTENCE "P if and only if Q" is expressed symbolically P⇔Q.

Open Sentence

An OPEN SENTENCE P (x1,x2,...,xk) is a sentence containing one or more variables that becomes a proposition only when the variables are assigned specific values.

Universe

The realm of all possible values that the variables may be assigned is called the UNIVERSE.

Truth Set

The collection of all values of the variables in the universe that make a true proposition upon substitution into the open sentence is called the TRUTH SET of the open sentence.

Universal Quantifier (∀x)P(x)

For all x,P(x)" and is true precisely whenP(x) is true for every value of x in the universe. The symbol ∀ is called the UNIVERSAL QUANTIFIER.

Existential Qualifier (∃x)P(x)

"There exists x such that P(x)" and is true precisely when P(x) is true for at least one value of x in the universe. The symbol ∃ is called the EXISTENTIAL QUALIFIERS.

Unique Existential Qualifier (∃!x)P(x)

"There exists a unique x such that P(x)" and is true precisely when P(x) is true for exactly one value of x in the universe. The symbol ∃! is called the UNIQUE EXISTENTIAL QUANTIFIER.

Direct Structure of proof

Proof:

Suppose P

Thus Q

Divides

Let Z={...,−2,−1,0,1,2,...}be the integers. We say that the integer a divides the integer b if there exists an integer k such that b=ak.

Even

An integer is even if there exists an integer k such that

a = 2k

Odd

An integer is odd if there exists an integer k such that

a = 2k + 1

Proof by Contraposition Structure

Proof.

Suppose∼Q.

•••

Therefore,∼P.

Thus,P⇒Q.

Two-part Proof of P⇔Q Structure

Proof.

(i) Show P⇒Q directly or by contraposition

.• • •

(ii) Show Q⇒P directly or by contraposition.

• • •

Therefore, (P⇒Q)∧(Q⇒P).

Thus,P⇔Q.

Proof by Contradiction Structure

Proof.

Suppose ∼P.

•••

(nonsense)

Therefore, Q.

But∼Q is true.

Therefore, P.

Rational

A real number r is called RATIONAL if there exist integers p and q (with q can't = 0) such that r = p / q.

Irrational

A real number that is not rational is called IRRATIONAL.

Existence Proof Structure (Constructive Proof of (∃x)P(x))

Proof.

Consider the object*

.•••

Therefore,P(*) is true.

Thus, (∃x)P(x).

Universal (for all) Proof Structure (Proof of (∀x)P(x))

Proof.

Let x be an arbitrary member of the universeU.

•••

Therefore,P(x) is true.

Thus, (∀x)P(x).

Unique Existence Proof Structure (Two-part Proof of (∃!x)P(x))

Proof.

(i) Show (∃x)P(x) by some method.

• • •

(ii) Show [P(x1)∧P(x2)] ⇒ [x1 = x2].

• • •

Thus, (∃!x)P(x).

Queen

A QUEEN is a chess piece that can attack along rows, columns and diagonals.

Truce

A TRUCE is an arrangement of mutually non-attacking queens.

Set / Elements

A SET is a collection of objects called its ELEMENTS. If A is a set and x is an element of A, we write x ∈ A. Otherwise, we write x not∈ A.

Set of Rational Numbers

Q={r∈R: r =p/q for some p∈Z and q∈Z with q not= 0}.

Empty Set

The set having no elements is called the EMPTY SET and is denoted by the Danish letter∅.

Open Interval

Closed Interval

Open Ray (from a to infinity)

Closed Ray (from a to infinity)

Open Ray (from minus infinity to b)

Closed Ray (from minus infinity to b)

(a, b) = {x∈R:a < x < b}

[a, b] = {x∈R:a ≤ x≤ b}

(a, ∞) = {x∈R:a < x}

[a, ∞) = {x∈R:a ≤ x}

(-∞, b) = {x∈R:x < b}

(-∞, b] = {x∈R:x ≤ b}

Subset

We say that A is a SUBSET of B and write A⊆B provided each element of the set A is also an element of the set B. That is, A⊆B⇔[x∈A⇒x∈B]. We say A equals B and write A=B provided A⊆B and B⊆A. That is, A=B⇔[A⊆B∧B⊆A].

Ordinary

A set A is called ORDINARY if it does not contain itself as an element ,i.e. if A not ∈ A.

Union

The UNION of A and B is the set A∪B = {x∈U: x∈A∨x∈B}.

Intersection

The INTERSECTION of A and B is the set A ∩ B= {x∈U:x∈A∧x∈B}.

Difference

The DIFFERENCE A\B is the set A\B={x∈U:x∈A∧x not∈B}.

Complement

Let A be a set with elements in some universe U. The COMPLEMENT of A is the set ̃A given by ̃A=U\A.

Disjoint

WhenA∩B=∅, we say that A and B are DISJOINT

Family

FAMILY of sets or script A

Union of script A

Big U A∈ script A= {x∈U: x∈A for at least one set A∈ script A}

Intersection of script A

Big ∩ A∈ script A= {x∈U: x∈A for every set A∈ script A}

Power Set

Let A be a set. The POWER SET of A is denoted by P(A) and consists of every subset ofA.

Index

Let ∆ be a nonempty set. Suppose for each α∈∆ there is a corresponding set Aα. The family of setsA={Aα: α∈∆} is called an INDEXED FAMILY OF SETS. Each α∈∆ is a particular INDEX and the set ∆ is called the INDEXING SET

Cartesian Product

Let A and B be sets. The CARTESIAN PRODUCT of A and B is the set A × B= {(a, b) : a∈A and b∈B}.

Relation

Let A and B be sets. A RELATION from A to B is simply a subset of A×B. If R is a relation from A to B and (a,b)∈R, then we write aRb and say "a is related to b."Subsets ofA×A are called relations on A(rather than "relations from A to A").

Domain

The DOMAIN of the relation R from A to B is the set Dom(R) ={x∈A: (∃y)(y∈B∧(x,y)∈R)} consisting of the "first entries" of ordered pairs in R. "The x values"

Range

The RANGE of the relation R from A to B is the set Ran(R) ={y∈B: (∃x)(x∈A∧(x,y)∈R)} consisting of the "second entries" of ordered pairs in R. "The y values"

Identity Relation

Let A be a set. The relation IA={(x,x)∈A×A:x∈A} is called the IDENTITY RELATION on A. Note that by definition Dom(IA) = Ran(IA) = A

Inverse Relation

Let R be a relation from A to B. The INVERSE of R is the relation R^−1={(y, x)∈B×A: (x, y)∈R}. Note that R^−1 is a relation from B to A.

Composition

LetRbe a relation from A to B and let Sbe a relation from B to C. The COMPOSITION of R and S is the relation S◦R={(a, c)∈A×C: (∃b∈B)((a,b)∈R∧(b, c)∈S)}.Note that S◦R is a relation from A to C.

Equivalence Relation

Let R be a relation on the set A. We call R an EQUIVALENCE RELATION on A if R has the following three properties:

(i) Ifa∈A, then (a,a)∈R.(Reflexivity)

(ii) If (x,y)∈R, then (y,x)∈R(Symmetry)(iii) If (x,y)∈R and (y,z)∈R, then (x,z)∈R. (Transitivity)

Equivalence Class

Let R be an equivalence relation on the set A. For each x∈A, the EQUIVALENCE CLASS of x determined by R is the set x/ R ={y∈A: (x, y)∈R}. The set of all the different equivalence classes is called A modulo Rand is writtenA/R={x/R:x∈A}. Note that A/R is a set of sets.

Modulo

Let m∈Z with m != 0. Define the relation ≡m on Z by ≡m ={(x, y) ∈ Z×Z: m divides (x−y)}.

In our shorthand, we might write x≡my iff m divides (x−y).

Another common notation for x≡my is x≡y(mod m).

Either way, the statement x≡my is read "x is congruent to y modulo m."

Partition

Let A be a set and script A a family of subsets of A. We call script A a PARTITION of A if :

(a) Every member of A is nonempty.(b) If X and Y in A are distinct, then X ∩ Y = ∅.

(c) A = ⋃ X∈ script A == X

Function, Codomain

Let f be a relation from A to B. We call f a FUNCTION from A to B and write f: A→B iff has the following two properties:

(i) Dom(f) =A.

(ii) [ (x, y) ∈ f ∧ (x, z) ∈ f] ⇒ y = z.

The set B is called the CODOMAIN of the function.

Image

Let f:A→B. If (a, b) ∈ f, we write f(a) = b and say that "b is the IMAGE of a under f" or that "b is the value of f at a."

One to One (injective) function

Let f:A→B. The function f is called ONE TO ONE if

[f(x) =y and f(z) = y]⇒ x = z

The phrase "one-to-one" is often shortened to "1-1". One-to-one functions are also called INJECTIONS.

Onto (surjective) function

Let f:A→B. The function f is called ONTO if

Ran(f) = B. Onto functions are also called SURJECTIONS.

Bijection Function

A function f:A→B is called a BIJECTION if it is 1-1 and onto. A bijection and its inverse function interact naturally.

Natural Numbers and Integers

N={1,2,3,...} (the natural numbers)

Z={...,−3,−2,−1,0,1,2,3,...}(the integers).

Image

Let f:A→B and X⊆A. The IMAGE of the subset X is the set f(X) ={f(x)∈B:x∈X}.

Preimage

Let f:A→B and Y⊆B. The PREIMAGE of the subset Y is the set f^−1(Y) = {x∈A: f(x)∈Y}.

Natural Number Characteristics

1) 1 ∈ N.

(2) If x∈N, then x has a unique successor x+ 1∈N.

(3) 1 is not the successor of any natural number.

(4) If x and y have the same successor, then x=y.

(5) If S⊆N satisfies

(i) 1 ∈ S;

(ii)∀k∈N, k∈S ⇒ k+ 1 ∈ S,

then S=N

Principle of Mathematic Induction (PMI)

If S⊆N satisfies

(i) 1 ∈ S;

(ii)∀ k ∈ N, k∈S ⇒ k+ 1 ∈ S,

then S = N

PMI Proof Structure

Proof.

LetS={n∈N:P(n) is true}.

•••

ThereforeSmeets condition (i) of the PMI.

•••

ThereforeSmeets condition (ii) of the PMI.

Thus, S=N by the PMI.

Generalized PMI

Suppose S ⊆ N satisfies

k ∈ S

[ n >= k ∧ n ∈ S ] ⇒ n + 1 ∈ S

THEN { k, k + 1, k + 2 ...} ⊆ S

The Principle of Complete Induction

If S ⊆ N satisfies

∀ n ∈ N, [{k ∈ N: k < n} ⊆ S] ⇒ n∈S ,then S=N

Prime

An integer p > 1 is called PRIME if the only positive integers that divide p are 1 and p itself.

Cardinality

Sets A and B have the same CARDINALITY, written

|A| =|B|, if there exists a bijection f:A→B.

Infinite / Finite

The set A is INFINITE if there exists a one-to-one function f: N→A. Otherwise, A is called FINITE.

Countable

The set A is called COUNTABLE if there exists a one-to-one function f:A→N.

Still learning (1)

You've started learning these terms. Keep it up!