Set Theory

Front 1

If A is necessary for B then ____ => ____

Back 1

B => A

If B holds, then A holds

Front 2

Contraposition of B => A

Back 2

-A => -B

If not A, then not B

Front 3

If A is sufficient for B then ___ => ____

Back 3

A=>B
If A holds, then B holds

Front 4

A is necessary and sufficient for B

Back 4

A <=> B
A is true if and only if B is true

Front 5

If we have the theorem "A=>B", what is the premise and what is the conclusion?

Back 5

A is the premise, B is the conclusion.

Front 6

Methods of proof of A=>B

Back 6

1. Constructive proof
-assume that A is true, and then deduce consequences of that and use them to show that B must also hold

2. Contrapositive proof

-assume that B does not hold, then use that to show that A cannot hold

-uses logical equivalence of ~B=>~A and A=>B

3. Proof by contradiction

-relies on the fact that if A=>~B is false, A=>B must be true

Front 7

Set

Back 7

a collection of objects

Front 8

A is a subset of B if

Back 8

every element of A is also an element of B

Front 9

What is a proper subset?

Back 9

A is a subset of B, but A does not equal B

Front 10

power set of A

Back 10

the set of all subsets of A - DON'T FORGET ABOUT THE EMPTY SET, OR THE SET ITSELF

Front 11

cartesian product

Back 11

if A and B are sets, the Cartesian product is the set AxB containing all the ordered pairs (a,b) where a comes from A, and b comes from B

Front 12

Binary relation

Back 12

defined by specifying some meaningful relationship that holds between the elements of the pair

Front 13

Relation on S

Back 13

when a binary relation is a subset of the product of one set S with itself

Front 14

A relation R on X is reflexive if

Back 14

xRx for all x in X

Front 15

A relation R on X is transitive if

Back 15

xRy and yRz implies xRz for any three elements x,y and z in X

Front 16

A relation R on X is complete if

Back 16

for all x and y in X, at least one of xRy or yRx holds

Front 17

A relation R on X is symmetric if

Back 17

xRy implies yRx

Front 18

A relation R on X is anti-symmetric if

Back 18

if xRy and yRx implies x=y

Front 19

Partial ordering on X

Back 19

a relation on X that is reflexive, transitive and anti-symmetric

Front 20

Linear (or total) ordering on X

Back 20

a partial ordering that is also complete

Front 21

A function is said to injective or one-to-one if

Back 21

f(x)=/=f(x') if x=/=x'

Front 22

A function is said to be surjective or onto if

Back 22

for every y in Y, there is an x in X s.t. f(x)=y

Front 23

Bijective

Back 23

-a function that is one-to-one and onto

-implies that an inverse exists f^(-1): Y-->X

Front 24

A set X of real numbers is bounded above if

Back 24

there exists a real number b such that b>=x for all x in X

Note: b is called an upper bound for x

Front 25

A least upper bound for the set X is a number b* that is

Back 25

an upper bound for X and is such that b*<=b for every upper bound b

Front 26

Least Upper Bound Principle

Back 26

any non-empty set of real numbers that is bounded above has a least upper bound

Front 27

How many least upper bounds can have a set X have?

Back 27

One. If b1* and b2* were both least upper bounds, the b1*<=b2* and b2*<=b1* which implies that b1*=b2*

Front 28

Supremum of X

Back 28

the least upper bound b* of X (b*=supX)

Front 29

A set X is bounded below if

Back 29

there exists a real number a such that x>=a for all x in X

Front 30

A set that is bounded below has greatest lower bound a* with the properties

Back 30

a*<=x for all x in X and a*>=a for all lower bounds a

Front 31

Infimum of X

Back 31

the greatest lower bound of X (a*=infX)

Front 32

Theorem 1

Let X be a set of real numbers a b* a real number. Then supX=b* if and only if:

Back 32

(i) x<=b* for all x in X

(ii) for each e>0 there exists an x in X s.t. x>b*-e

Front 33

A monotone sequence is one that is

Back 33

increasing or decreasing

Front 34

A convergent sequence is one that

Back 34

converges to some number (see def 6, p. 6)

Front 35

Every convergent sequence is bounded. True or false? Why or why not?

Back 35

True. Only finitely many terms of the sequence can lie outside the interval I=(x-1,x+1). The set I is bounded and the finite set of points from the sequence that are not in I is bounded, so the sequence must be bounded.

Front 36

Is every bounded sequence convergent?

Back 36

No. Example: {(-1)^k} oscillates within bounds.

Front 37

Every bounded monotone sequence is convergent. True or false?

Back 37

True. See proof on p. 7.

Front 38

Every subsequence of a convergent sequence is itself convergent but it does not have the same limit as the original sequence.

Back 38

False. Every subsequence of a convergent sequence is itself convergent AND it has the same limit as the original sequence.

Front 39

If a sequence is bounded, does it contain a convergent subsequence?

Back 39

Yes.

Front 40

Cauchy Sequence

Back 40

-alternative necessary and sufficient condition for convergence

-a sequence of real number is called a Cauchy sequence if for every e>0, there exists a natural number N such that any two terms in the sequence past this point are closer together than e

-all convergent sequences are Cauchy sequences

-all Cauchy sequences are convergent

-this extends to R^n

Front 41

A sequence is convergent if and only if it is a

Back 41

cauchy sequence (see proof on page 9)

Front 42

If the sequence is convergent, what can we say about the lower and upper limits?

Back 42

They are equal to the limit of the sequence

Front 43

What is a metric on a set X? What four properties must it satisfy?

Back 43

a measure of distance and it is a function d

1) Positivity

2) Discrimination

3) Symmetry

4) The Triangle Inequality

Front 44

Is every convergent sequence in Rn bounded?

Back 44

Yes.

Front 45

A set S in Rn is bounded if

Back 45

there exists a number M such that the distance between x and the origin is less than or equal to M for all x in S

Front 46

What does every bounded sequence in Rn have?

Back 46

a convergent subsequence

Front 47

a subset S of Rn is bounded if and only if

Back 47

every sequence of points in S has a convergent subsequence

Front 48

a subset S of Rn is compact if

Back 48

it is closed and bounded

Front 49

a subset S of Rn is compact if and only if every sequence of points in S has what?

Back 49

a subsequence that converges to a point in S

Front 50

a function f is continuous at a point a in S if

Back 50

for every e>0 there exists a d>0 s.t.

|f(x)-f(a)|<e whenever ||x-a||<d

if f is continuous at every point in S, then f is continuous on S

Front 51

A vector valued function is continuous at a point x^o if and only if

*two options - one using components and the other using sequences*

Back 51

1) each component is continuous at x^o

2) f(xk) --> f(xo) for every sequence (xk) of points in S that converges to xo

Front 52

If f is a continuous function and we take any compact subset K of the domain of the function, what can we say about f(K)={f(x):x comes from K}

Back 52

it is compact (see theorem 19)

Front 53

f is continuous if and only if

(related to open and closed sets and inverse functions)

Back 53

1. f-1(U) is open for each open set U in Rm

2. f-1(F) is closed for each closed set F in Rm

Front 54

Let S be a compact set in R and let xL be the GLB of S and xU be the LUB of S, then

Back 54

both xL and xU are in S

(see theorem 21)

Front 55

Weierstrass Existence of Extreme Values

Back 55

Let f:S->R be a continuous function where S is a non-empty compact subset of Rn. Then there exists a vector xU and a vector xL such that:

f(xL)<=f(x)<=f(xU) for all x in S

(see theorem 22)

Front 56

Brouwer Fixed-Point Theorem

Back 56

if you have a continuous function with a non-empty compact and convex domain then there exists at least one fixed point of f in S (a fixed point is a point where f(x)=x. (see theorem 23)