Csusm: Historical Readings Math 505

Front 1

Cardinals (hebrew letters)

Back 1

one, two, three...., , These numbers count sizes.

(א).

Front 2

Ordinals (greek letters)

Back 2

Definition: Given a well-ordered set M, the "order type" or "the ordinal" of M is defined to be the unique ordinal number a such that there exists a bijection f: Oa -> M preserving order.

Ordinals: first, second, third... These don't indicate size, these keep track of order/position.

Whereas there is only one countably infinite cardinal, namely itself, there are uncountably many countably infinite ordinals, namely

ω, ω + 1, ω + 2, …, ω·2, ω·2 + 1, …, ω2, …, ω3, …, ωω, …, ωωω, …, ε0, ….

Front 3

Cantor Theorems

Back 3

1. Cardinality(natural numbers) < cardinality(ℝ)

2. The real numbers (ℝ) are uncountable.

3. There is no surjection A -> P(A); that is, |A| < |P(A)|

Front 4

Cantor's Question

Back 4

is |ℝ| = |ℝ^2|??

The answer is yes. Make a bijection from ℝ^2-> ℝ.

(x, y) -> f(x,y) where f(x,y) is the number created after rotating digits in x and y, where x and y are infinite and non-repeating.

Front 5

if |A|=a and |B| = b, how big is Funct(A,B)?

Back 5

= b^a

Front 6

How big is P(A) if |A|=a?

Back 6

|P(A)| = 2 ^a

Front 7

Euclid

Back 7

"The whole is greater than its parts". If x is a proper part of y, then |x|<|y|

Front 8

How many points does a line segment have?

Back 8

Aristotles Answer: "a line is not built out of points. Rather the line is prior and you can select points as needed".

"extremity of segment"

Front 9

Cantors Transfinite Numbers

Back 9

1. Cardinals: one, two, three.... These numbers count sizes.

2. Ordinals: first, second, third... These don't indicate size, these keep track of order/position.

for finite numbers, ordinals = cardinals.

Front 10

Cantor Timeline Information

Back 10

- PHD in Number Theory

- Moved to Hallee

- Habilitation in Number Theory

- early research in uniqueness of trig series.

- 70s uniqueness

- 71 finite exceptions

- 72 countable exceptions

- 78 stated continuum hypothesis but never proved

- 1902 Russell Paradox

- 1895/7 Burelli Paradox

Front 11

proof: The real numbers (ℝ) are uncountable.

Back 11

Any subset N of a countable set M={m1, m2, m3...} is at most countable. If we can find a subset of ℝ which is not countable, then a fortune ℝ cannot be countable. Look at: subset M of ℝ where m = (0 ,1] of all positive real numbers r with 0

Proof by Contradiction:

Suppose otherwise, that M is countable.

let M = {r1, r2, r3...} be a listing of M.

Write rn as its unique infinite decimal expansion without an infinite sequence of zeros at the end.

rn = 0.an1 an2 an3...

where ani ∈ {0, 1,..9} for all n and i.

Consider now the double infinite array

r1 = 0.a11 a12 a13...

r2= 0.a21 a22 a23...

.

.

.

rn= 0.an1 an2 an3 ...

.

.

.

For every n, chose bn ∈ { 1, ..8} different from ann. Then b = 0.b1 b2 b3... is a real number in our set M and hence must have an index, say b = rk. But this cannot be since bk is different from akk. (our contradiction)

Thus, the real numbers (ℝ) are uncountable.

Front 12

Definition: Limit Points

Back 12

A point x in X is a limit point of S if every neighbourhood of x contains at least one point of S different from x itself.

Front 13

Cardinal Arithmetic Definitions ( +, *, ^)

Back 13

let K and L be finite cardinals. Choose sets A, B such that |A|=K and |B| = L.

Addition: Note that A and B must be disjoint. then K + L = |A U B|

Multiplication: K*L = |A X B|

Exponentiation: K^L = |A^B| where A^B is the set of all functions from B to A.

for infinite:

K + L = max( K, L)

K * L = max(K, L)

Front 14

Prove:

multiplication of cardinals numbers is commutative.

Back 14

Proof:

choose sets A and B such that |A| = L and |B| = M.

Consider A X B and B X A.

|A X B| = L * M

|B X A| = M * L

Choose a bijection from A X B to B X A (which essentially reverses the ordered pair).

Thus, |A X B|= |B X A|since we found a bijection.

Therefore, L*M = M *L.

Front 15

Ordinal Arithmetic definitions ( +, *)

Back 15

Let a and b be two ordinals.

Addition:

Choose 2 disjoint well-ordered sets A, B with

ordinal(A) = a and ordinal(B) = b.

a + b = ordinal( AU B)

Multiplication:

define order of A X B where (a1, b1) < (a2, b2) if and only if b1 < b2

a X b = ordinal ( A X B)

** addition is associative but not commutative.

Front 16

ω + 2 =

Back 16

Let A = { a0, a1, a2...} and B ={ b0, b1}

|A| = ω and |B| = 2

ω + 2 = ordinal( A U B)

A U B = { a0, a1, a2, ....., b0, b1}

which can be correlated with

C ={ 0, 1, 2, 3, 4, ....ω, ω+1}

and ordinal(C) = ω+2

Front 17

2+ ω =

Back 17

Let A = { a0, a1, a2...} and B ={ b0, b1}

|A| = ω and |B| = 2

2+ ω = ordinal( B U A)

B U A = { bo, b1, a0, a1, a2...}

which can be correlated with

C = { 0, 1, 2, 3, 4....}

and ordinal(C) = ω

Front 18

2* ω =

Back 18

Let A = { a0, a1} and B ={ b0, b1, ...}

|A| = 2 and |B| = ω

define A X B listed in order

(a0, b0) (a1, b0) (a0, b1) (a1, b1) (a0, b2) (a1, b2)...

which can be correlated with

C = { 0, 1, 2, 3, 4, 5...}

and ordinal(C) = ω

Front 19

ω * 2 =

Back 19

Let A = { a0, a1, ...} and B ={ b0, b1}

|A| = ω and |B| = 2

define A X B listed in order

(a0, b0) (a1, b0) (a2, b0)...

(a0, b1) (a1, b1) (a2, b1)...

.

.

.

which can be correlated with

C = { 0, 1, 2, 3, 4, 5...ω, ω+1, ω+2.... ω+ω}

and ordinal(C) = ω+ω

Front 20

Order in which number sets were defined in math

Back 20

1. Complex Numbers in early 1800 as ordered pairs of real numbers ℝ

2. ℝ in 1872. Several who cleaned these up but the most notable were Cantor(defined with sequences) and Dedekind(defined with cuts).

3. , ℕ, ℤ: 1888 Peano Axiomd and Dedekind

4. Sets and sequences.

Front 21

When are ordinals countable?

Back 21

a, an ordinal number, is countable if and only if there is a countable set of order type a.

Front 22

Peano Axiom Notation

Back 22

Propositions:

U = or

∩ = and

∨ = true

∧ = False

classes:

U = Union

∩ = Intersection

∨ = Universe

∧ = Empty class

* dots tell us where to put parentheses

⊃ means implies

= means if and only if

Front 23

Definition: Closed Set

Back 23

A set is closed if it contains its' limit points.

Front 24

Definition: well-ordered

Back 24

each subset has a least element.

a well-order relation (or well-ordering) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering.

well-ordered sets have an ordinal order type. if the set is not well-ordered, then it doesn't have an ordinal.

Front 25

Strict Finitism

Back 25

Only a finite number of natural number exist

Front 26

Classical Finitism

Back 26

potential infinity exists but not actual infinity. The claim is that you can do math with this.

Front 27

Continuum Hypothesis

Back 27

there are no cardinals between aleph_1(size of the real numbers) and aleph_0 (size of the natural numbers). That

aleph_1 = 2^ aleph_0

This cannot be proved or disproved but <= can be proved.

Front 28

Schroder-Bernstein Theorem (Cantors Version)

Back 28

If |A| <= |B| and |B| <= |A| then |A| = |B|

Front 29

Schroder-Bernstein Theorem

Back 29

If A and B are sets, and if there are 2 injections f: A -> B and g: B -> A, then there exists a bijective function h: A->B.

Front 30

Burali-Forti (1897) Paradox

Back 30

The set of all ordinals is well-ordered. Or alternatively, the size of the set of all ordinals does not exists (causes a paradox).

Proof:

let Ω be the collection of all ordinals.

claim: Ω is well-ordered

let γ be the order type of Ω.

But γ ∈ Ω, so γ is also the order type of he segment Ω sub γ.

so γ < γ (which is a contradiction).

Front 31

Russell's Paradox

Back 31

The set of all set that which do not contain themselves.

Front 32

Cantors Paradox (1899)

Back 32

If S is a set, then |P(S)| > |S|

Proof:

let V be the universe

so every set is a subset of V.

so P(V) ⊆ V

so |P(V)|≤ |V|

But |P(V)|> |V|by Cantors theorem (which is our contradiction).

Front 33

Axiom of Extensional

(ZF set theory)

Back 33

Two sets are equal if and only if they have the same elements.

∀ x, y [ x = y ↔ ∀u (u ∈ x ↔ u ∈y)]

Front 34

Axiom of Separation

Back 34

(Zermelo) Whenever the propositional function F(x) is definite for all elements of a set M, M possesses a subset M_F containing as elements precisely those elements x of M for which F(x) is true.

Front 35

Axiom of Choice (AOC)

(ZF set theory)

Back 35

If x is a set of nonempty, pairwise disjoint sets, then there is a set y that consists of exactly one member of every set in x. Such a y is called a choice set for x.

Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin.

Front 36

Axiom of Pairing

(ZF set theory)

Back 36

For any x and y, the set {x, y} exists.

∀ x,y ∃ z ∀ u ( u ∈z ↔ u = x or u = y)

Front 37

Axiom of Infinity

(ZF set theory)

Back 37

Version 1:(Zermelo)

There is a set Z such that

1). the empty set is an element of Z

2). if a is in Z then {a} is also in Z.

Version 2: (Von Neumann)

There exists a set Z such that

1). the empty set is an element of Z

2). if a is in Z then a union {a} is also in Z.

Version 3: (Dedekind)

There exists a set Z and an injective non-surjective function S: Z-> Z

Front 38

Axiom of Replacement

(ZF set theory)

Back 38

Asserts that the image of any set under any definable mapping is also a set.

∀ x ∈ A ∃! y F(x, y) → ∃ B ∀ y ( y∈ B ↔ ∃ x∈ A F(x, y))

axiom of replacement implies axiom of separation.

Front 39

Axiom of Union

(ZF set theory)

Back 39

For any x, the union of all the sets in x exists. This union is denoted ∪x

Front 40

Axiom: Power set

(ZF set theory)

Back 40

For any set x, its power set P(x) exists.

Front 41

Axiom: Empty Set

(ZF set theory)

Back 41

The empty set exists

Front 42

Axiom of Regularity

(ZF set theory)

Back 42

states that every non-empty set A contains an element that is disjoint from A.

∀ x ( x ≠ ∅ → ∃ y ∈ x ( y ∩ x = ∅ ) )

This does not generate new sets but prevents weird things from happening such as y ∈ x and x ∈ y.

This prevents: cycles and infinitely descending chains

Front 43

Definition: Perfect

Back 43

A subset of R is called perfect if it is non-empty and equal to its set of limit points.

* every perfect set is uncountable.

Front 44

Definition of Ordinal

Cantor, von Neumann, ZF

Back 44

Cantors Def: order types of well-ordered sets (abstraction)

Von Neumann: any ordinal is the set of all ordinals before it.

Zermelo-Frankel ST: An ordinal is a transitive set, all of whose members are also transitive. A set is Transitive if every member of it is a subset of it.

ex: {0, {0}} is an ordinal but {{0}} is not an ordinal

Front 45

Cantors Definition: sets

Back 45

|A| < |B| is there exists an injection, but not a bijection f: A -> B.

Front 46

Cantors Definition: sets <=

Back 46

|A| <= |B| is there exists an injection f: A -> B

Front 47

Different Philosophers' definition of 3.

Frege

Russell

Zermelo

von Neumann

Peano

Back 47

1). It is a symbol.

2). Frege: 3 is the class of all triples.

3). Russell: set of all triples of base types.

4). Zermelo:

∅, {∅}, {{∅}}, {{{∅}}}, .... so it is the number of parentheses.

5). von Neumann: 3 is defined as the segment of all cardinals less than 3.

3:= { 0, 1, 2}

= { 0, 1, {0, 1} }

= { 0, {0}, {0, {0}} }

6). Peano: 3 = S( S( S(0) ) )

Philosophers like Freges' definition because it is somewhat canonical. Set theoreticians like von Neumann. Mainstream math like Peano.

Front 48

What does ZF, ZFC, and VBG stand for?

Back 48

Zermelo-Fraenkl Set Theory

Zermelo-Fraenkl plus the axiom of choice.

von Neumann, Bearneys, and Godel.

Front 49

Axiom of Reducability

Back 49

Any function is coextensive with what he calls a predicate function (a function in which the types of apparent variables run no higher than the types of the arguments).

Front 50

Axiom of Determinacy

Back 50

States that this game is determined for every choice of x.

Front 51

Axiom of Projective Determinacy

Back 51

Asserts that our game is determined whenever x is a projective set.

Front 52

Projective

Back 52

A subset of R is called protective if it can be obtained in finitely many steps from a Borel subset of some R^n by applying the basic operations of taking complements and projections.

Front 53

(FOL) Metavariables

Back 53

Not part of the official syntax but these are used to describe the syntax.

Front 54

(FOL) Expression

Back 54

strings of symbols

Front 55

(FOL) Term

Back 55

is an expression that names something.

ex: 4+5 or x + 5

Definition: We define terms recursively as follows:

- Any declared variable symbol is a term

- Any declared constant symbol is a term

- if f is a declared function symbol of arity k, and if t1, t2, ..., tk are terms, then f(t1, t2, ..., tk) is a term

- if γ is a formula and if x is a variable symbol, then ix.γ is a term.

Front 56

(FOL) Atomic Formula

Back 56

Definition: We define atomic formula as follows.

-all declared boolean variables are atomic formulas

-both T and ┴ are atomic formulas

- if R is a declared relation symbol of arity k, and if t1, ...tk are terms, then R(t1,...tk) is an atomic formula.

- In particular, if t1 and t2 are terms then =(t1, t2) is an atomic formula

Front 57

(FOL) Formula

Back 57

is an expression that asserts something about certain terms. Formulas are either true or false.

ex: 4 + 5 = 9 or 7 < 4

Definition: We define formula recursively as follows.

- Any atomic formula is a formula

- if γ is formula, then (¬γ) is a formula

- if γ and ψ are formulas, then the following are also formulas:

(γ ∨ ψ) (γ ∧ ψ) (γ → ψ)

-if γ is a formula, and if x is a variable symbol, then (∀x.γ) is a formula, and (∃x.γ) is a formula.

Front 58

(FOL) Context

Back 58

is a description of all the constants, variables, and definitions in use, along with all axioms and other (temporary) assumptions that are made.

components:

1). symbol declarations: variables, constants, function symbols

2). definitions

3). Abbreviations and conventions

4). what variables are fixed

5). assumptions

Front 59

(FOL) Sequent

Back 59

is a formula together with a context.

Some of these will be axioms.

Front 60

(FOL) Formal Rule of Inference

Back 60

is a rule that takes as inputs zero or more sequents, and returns as an output another sequent.

Front 61

(FOL) Proof

Back 61

is a sequence of sequents, where each is either an axiom, a previously established theorem, or follows from previous sequents in the sequence by formal rules of inference.

Front 62

(FOL) What are the 2 levels of syntax and what do they differ by?

Back 62

2 levels: basic and extended syntax. Extended syntax uses abbreviations where basic does not. The user normally enters the extended version into the computer and then the computer converts it into the basic version and stores it.

ex: 3 + 4 + 5 this is the extended version since there are no ()

( (3+4) +5) this is the basic version since it is what the computer would interpret it as.

Front 63

(FOL) what are the 5 types of symbols that can be declared?

Back 63

1). Variable symbols. These are sometimes called individual variables, to distinguish them from boolean variables.

2). Constant symbols. These are sometimes called individual constants, to distinguish them from boolean constants.

3). function symbols.

4). Relation symbols.

5). Boolean variables.

Front 64

Cantors Definition: Countably Infinite

Back 64

a set A is countably infinite if

|A| = |natural numbers|

Front 65

Prove

Cantors Theorem: |A| < |P(A)|

Back 65

Proof:

1). first we show injective.

This is easy to see since we can make a function from A to P(A) such that a -> {a}. It is injective since by definition, P(A) contains all the elements of A and its subsets.

2). Now we show there is no surjection A-> P(A)

suppose f: A -> P(A).

We must show that f is not surjective (AKA there is something in the image not mapped to something in the domain).

Let B ∈ P(A) or B ⊆ A be defined by

B := { x ∈ A | x ∉ f(x) }

Claim: B is not in the image of f.

Case 1: Let x ∈ B, then x ∉ f(x) by definition of B.

Since x ∈ B and x ∉ f(x) we conclude f(x) ≠ B. This means that B is not in the image of any x ∈ B.

Case 2: Let x ∉ B. Then ¬(x ∉ f(x)) by definition of B.

so x ∈ f(x).

Since x ∉ B and x ∈ f(x), we conclude that f(x) ≠ B.

So for all x ∈ A, f(x) ≠ B.

Therefore, f is not surjective.

Front 66

Prove

Theorem (one of Cantors): The set ℝ^2 of all ordered pairs of real numbers has the same size as ℝ.

Back 66

Proof:

This will be proved by showing that there is a bijection from 1 set to the other.

It suffices to prove that the set of all pairs (x,y) 0< x, y, <= 1 can be mapped bijectively onto (0, 1].

Consider the pair (x,y).

Write x, y in their unique non-terminating decimal expansion.

ex: x = 0.3 01 2 007 08...

y = 0.009 2 05 1 0008...

(1-1) Separate the digits of x and y into groups by always going to the next nonzero digit, inclusive.

Now, we associate to (x,y) the number z ∈ (0,1] by writing down the first x-group, after that the first y-group, then the second x-group, and so on...

ex: z = 0.30090122050071080008...

Since neither x nor y exhibits only zeros from a certain point on, we find that the expression for z is again a non-terminating decimal expansion.

(onto) Conversely, from the expansion of z, we can immediately read off the premiere (x,y) and the map is bijective.

Front 67

Dedekind Cuts`

Back 67

Took the rational numbers and made a "cut". But every time you make a cut, there is always a number where you sliced.

Front 68

Transitive Set

Back 68

Assume S is a set of sets. S is transitive means that ∀ x, y if y ∈ x and x ∈ S then y ∈ S.