Exam 1 Definitions and Theorems

Statement

A sentence that can be classified as true or false

Truth value

The truth or falsity of a statement

Sentential Connectives

Logical operators that combine simple sentences to form more complex statements

Conjunction

and

Disjunction

or

Negation

Not

Consequential Implication/Conditional

If…then

Other ways to say if p, then q

p implies q, p only if q, q if p, q provided that p, q whenever p, p is a sufficient condition for q, q is a necessary condition for p

Biconditional

iff

When is p(x) a statement?

When the value of x is specified

Universal quantifier

for all

Existential quantifier

There exists

Principle of Well-Ordering

Every non-empty set S of positive integers has a least element

Theorem to prove induction

Principle of Well Ordering implies Principle of Induction (we can show that it works for the least element in the set)

Counterexample

One example where the assertion fails

Set

A mathematical model for a collection of (different) things

Elements

The objects within a set

Infinite set notation

S := {x \in (defined set) : (condition for x to be in S)}

Subset

A is a subset of B if every element of A is an element of B (also stated A is contained in B)

Proper Subset

A is a proper subset of B if there exists an element of B that is not in A

Equal sets

Two sets are equal if A is a subset of B and B is a subset of A

Theorem on the empty set

The empty set is contained in A for any set A

Union (of A and B)

{x : x \in A or x \in B}

Intersection (of A and B)

{x : x \in A and x \in B}

Complement (of B in A)

{x : x \in A and x \ not in B}

Disjoint

A and B are disjoint sets if A n B is the empty set

Universal Set

Where the elements of our mathematical system come from; denoted by U; mostly take U=R

A u (U\A) =

U

A n (U\A) =

empty set

U\(U\A)=

A

A u (B n C)=

(A u B) n (A u C)

A n (B u C)=

(A n B) u (A n C)

A\(B u C)

(A\B) n (A\C)

A\(B n C)

(A\B) u (A\C)

Indexed Family of sets for J

{Aj : j \in J} if for each element j in a nonempty set J, there exists a corresponding set Aj

Union of a set of sets

u Aj = {x: x \in Aj for some j \in J}

Intersection of a set of sets

n Aj = {x: x \in Aj for all j \in J}

Ordered Pair (a, b)

The set whose members are {a} and {a, b} ((a, b) := {{a}, {a, b}}

Theorem about (a, b) = (c, d)

iff a=c and b=d

Cartesian Product (of sets A and B)

AxB = {(a, b) : a \in A and b \in B}

Relation

A condition involving objects a and b which is either true or false

Relation (formally)

For some subset R of AxB, a \in A is related by R to b \in B if (a, b) \in R (aka aRb)

Equivalence Relation

The following properties for all x, y, z \in S hold: x~x for all x (reflexive); If x~y, then y~x for all x, y \in S (symmetric); If x~y, y~z, then x~z (transitive)

Equivalence Class with respect to R of x \in S

R is an equivalence relation, S is a set; Ex := {y \in S: y~x} = {y \in S: x~y}

Lemma on equivalence classes

For all x \in S, Ex ≠ empty set; any two different equivalence class are disjoint

Partition

A collection P of non-empty subsets of S s.t. each x \in S belongs to some A \in P and for all A, B \in P, if A ≠ B, then A n B = empty set

Theorem about partitions

1. For E equivalence relation on a set S, {Ex : x \in S} is a partition of S

2. If P is a partition, define ~ s.t. x~y iff x and y are in the same piece of the partition, then ~ is an equivalence relation

Function (from A to B)

A non-empty relation f \subset AxB that satisfies the following: existence (for all a \in A, \exists b \in B s.t. (a, b) \in f) and uniqueness (If (a, b) \in f and (a, c) \in f, then b=c

Function from A to B (domain/codomain/range)

Set A is the domain and B is the codomain, the range/image is the set of all second elements of the members of f \proper subset AxB that is: Im(f) := {b \in B : \exists a \in A : (a, b) \in f}

Surjection

For function f: A → B, if B = Im (f) (onto)

Injection

For function f: A→B, if for all a and a’ in A, f(a)=f(a’) \implies a=a’ (one-to-one)

Bijection

A function that is injective and surjective

Pre-image

If D \subset B, let f^(-1)(D)={x \in A : f(x) \in D}. The set f^(-1)(D) is the pre image.

Theorem about pre-image

f: A→B, let C1, C2 \subset A and D1, D2 \subset B. The following hold: (1) C1 \subset f^(-1)(f(C1)), (2) f(f^(-1)(D1)) \subset D1, (3) f(C1 n C2) \subset f(C1) n f(C2), (4) f(C1 u C2) = f(C1) u f(C2), (5) f^(-1)(D1 n D2) = f^(-1)(D1) n f^(-1)(D2), (6) f^(-1)(D1 u D2) = f^(-1)(D1) u f^(-1)(D2), (7) f^(-1)(B\D) = A\f^(-1)(D)

Equinumerous

There exists a bijective fcn from set S to T, then S~T

Finite set S

S=\emptyset or if \exists n\in N and a bijection from {1, 2, …, n} →S

Infinite set

A set that is not finite

In

The set {1,2,…n}

Cardinal Number

For In, it is n, if S~In, S has n elements

Transfinite

A cardinal number that is not finite

Denumerable set

\exists a bijection f:N→S

Countable set

A finite or denumerable set

Uncountable set

A set that isn’t countable

Theorem about subsets and countability

Let S be countable, and let T\subset S. Then, T is countable.

Theorem about countable sets

For set S ≠ \emptyset, the following are equivalent: (1) S is countable; (2) \exists f:S→N injection; (3) \exists g:N→S surjection

Theorem about unions of countable sets

For S, t, non-empty countable sets, SuT is countable

Theorem about products and countability

For S, T non-empty countable sets, SxT is countable

Theorem about the rational numbers

The rational numbers are countable

Theorem about countability and families

The union of a countable family of countable sets is countable

Theorem about the real numbers

The set of real numbers is uncountable