Yi Lin. General Systems Theory: A Mathematical Approach

Подождите немного. Документ загружается.

Chapter 3

We use natural numbers to count finite sets. The Axiom of Choice tells that

every set can be counted by an ordinal. Therefore, we use natural numbers to

indicate finite ordinals.

Let

α be an arbitrary ordinal. The successor S(α) of the ordinal is defined by

S (

α)=α ∪

{

α}. Then S

(

α) is also an ordinal, and we have

0 = Ø

1 = S(

Ø)

2 = S

(

)

3=S

(

2),

...

(3.17)

Intuitively, natural numbers are those ordinals obtained by applying

to Ø a finite

number of times.

An ordinal

α is a successor ordinal (or isolated ordinal) if ∃ β( α = S(β)). It is

a limit ordinal if

α ≠ 0 and α is not a successor ordinal. For example, let ω be the

set of all natural numbers and 0. Then

ω is an ordinal and all smaller ordinals are

successor ordinals or 0. So

ω is a limit ordinal, since if not it would be a natural

number, and hence

ω is the least limit ordinal. Actually, the Axiom of Infinity is

equivalent to postulating the existence of a limit ordinal.

The following theorem shows that the elements of

ω are the real natural

numbers.

Theorem 3.2.5. The Peano postulates are

(1)

∈

(2)

(3)

(4)

(Induction)

Proof: For (4), if X

≠ ω, let γ be the least element of ω

X, and show that γ

is a limit ordinal < ω, contradiction.

Let α and β be two ordinals.

Define

α + β

type (

{0}

∪

{1},

where

Theorem 3.2.6. For any

α, β, γ:

(1)

(2)

(3)

Axiomatic Set Theory

(4)

(5) If

is a limit ordinal,

Proof: The results are straightforward from the definition of addition.



Recall that the addition of ordinals is not commutative. Let α and β be two

ordinals. We define the multiplication

α · β = type (β × α, H ), where H is the

lexicographic order on

α:

(3.18)

Again, we get directly from the definition the basic properties of the multiplication

of ordinals.

Theorem 3.2.7. For any

α, β, γ::

(1)

(2)

(3)

(4)

(5) If

β is a limit ordinal,

(6)

We, again, need to remember that the multiplication of ordinals is not commu-

tative and the distributive law (6) fails for multiplication on the right.

Let A be a set. We define A

to be the set of all functions from n to A,

and is the function s with domain n such

that

Under these definitions, A² and

A × A

are not the same, but there is an obvious 1–1 correspondence between them.

In general, if s is a function with domain(s) = I, we may think of I as an index

set and s as a sequence indexed by I. In this case, we write s

for s

(

). When D

(

)

is an ordinal α, we may think of s as a sequence of length α. If D

(

) = β, we

may concatenate the sequences s and t to form a sequence of length

α + β as

follows: the function with domain

α + β is defined by for each

and

for all

We have seen that there need not exist a set of the form {

x : φ (x

) }. But there is

nothing wrong with thinking about such collections, and they sometimes provide

useful motivation. Informally, we call any collection of the form {x :

(

x)} a

Chapter 3

class. A proper class is a class which is not a set (because it is too “big”). We use

V and ON to indicate the following two classes

V = {x : x = x

}

(3.19)

= {

x : x is an ordinal}

(3.20)

Theorem 3.2.8

[Transfinite Induction on ON]. If C ⊂ ON and C ≠ Ø, then C

has a least element.

Proof:

Fix α ∈ C. If α is not the least element of C, let β be the least element

∩

Then

is the least element of



Theorem 3.2.9 [Transfinite Recursion on ON].

If F : V → V, then there exists

a unique G : ON

→ V such that

Proof:

For uniqueness, if

and

both satisfy Eq. (3.21), we can show that

by transfinite induction on

(3.21)

To establish existence, we call g a δ-approximation if g is a function with

domain

and

(3.22)

As in the proof of uniqueness, if g is a

δ approximation and g' is a δ

approximation, then

Next, by transfinite induction on

, we can show that for each δ there is a δ

-approximation (which then is unique).

Now, let

(

) be the value g

(

), where g is the δ

-approximation for some



A useful application of recursion is in defining ordinal exponentiation: Let α

and

be two ordinals. Then

is defined by recursion on β by

(1)

(2)

(3)

If β is a limit,

As in Chapter 2, 1–1 functions are used to compare the size of sets. Generally,

if A can be well-ordered, then A

for some α (Theorem 3.2.4), and there is

then a least such

α, which we will call the cardinality of the set A, denoted by

⏐A

⏐.

In any statement involving

⏐

⏐,

we imply that

can be well-ordered. Under

the Axiom of Choice,

⏐

A⏐ is defined for every set A. Regardless of the Axiom of

Choice,

⏐

α⏐

is defined and is ≤ α for every ordinal α.

Axiomatic Set Theory

Theorem 3.2.10.

⏐

⏐ ≤ β ≤ α, then ⏐

⏐ = ⏐

⏐.

Proof:

β ⊂ α

implies

⏐β⏐ ≤ ⏐α⏐

, and

⏐α⏐ ⊂ β

, so ⏐α⏐ ≤ ⏐β⏐

. Thus, by

Bernstein’s equipollent theorem in the previous chapter, we have

⏐α⏐

⏐β⏐



Theorem 3.2.11. If n ∈ ω, then

(1)

+ 1.

(2)

∀α ( α ~ n → α = n).

Proof:

Statement (1) can be proved by induction on

and (2) follows by using

Theorem 3.2.6.



Corollary 3.2.1.

is a cardinal and each n

∈ ω

is a cardinal.

A set

is finite if

⏐

and to be countable if

⏐

A⏐ ≤ ω. Infinite means not

finite. Uncountable means not countable.

Cardinal multiplication and addition are defined in the following. They must

be distinguished from ordinal multiplication and addition. Let

κ and λ be two

cardinals we define

Theorem 3.2.12.

For

Proof:

First show n + m < ω by induction on m. Then show n · m < ω by

induction on m. The rest follows from Theorem 3.2.11 (2).



Theorem 3.2.13.

Every infinite cardinal is a limit ordinal.

Proof: If κ is an infinite cardinal and κ = α + 1, then since 1 + α = α,

κ = ⏐κ⏐ = ⏐

1 +

⏐

This contradicts the definition of



Theorem 3.2.14. If

κ is an infinite cardinal, κ × κ = κ

Proof: We prove the theorem by transfinite induction on κ. Assume this

holds for smaller cardinals. Then for

α < κ

⏐α × α⏐

⏐α⏐ ⊗ ⏐α⏐

. Define a

well-ordering on

κ × κ by (α

)

(γ,

)

if and only if

precedes

lexicographically]

(3.23)

Each has no more than

predecessors under the ordering

, so type

whence



Chapter 3

Corollary 3.2.2. Let κ and λ be infinite cardinals then

(1)

(2)

Proof:

For (2), use the proof of Theorem 3.2.13 to define a 1–1 mapping

This gives a 1–1 mapping

Therefore,



Theorem 3.2.15.

∀α∃κ

(κ

and

is a cardinal).

Proof:

Assume α ≥ ω. Let W =

{H : H

∈ P(

α × α

) and H well-orders α }.

Let S = {type(

) : H ∈ W}. Then

∪

S is a cardinal > α.



Let α be an ordinal and α

the least cardinal > α. A cardinal number κ is a

successor cardinal if there exists some ordinal

α such that κ = α

. The cardinal

κ is a limit cardinal if κ > ω and is not a successor cardinal. Now, the sequence

of transfinite cardinals

ℵ

is defined by transfinite recursion on

(1)

= ω.

(2)

= (ω

)

(3) For any limit ordinal

Theorem 3.2.16.

(1)

Every infinite cardinal is equal to ω

for some α .

(2)

β →ωα < ωβ.

(3)

is a limit cardinal if and only if α is a limit ordinal.

(4)

is a successor cardinal if and only if α is a successor ordinal.

We now turn to cardinal exponentiation. Let

A = {ƒ : ƒ is a function ∧

(ƒ) = B ∧ R

(ƒ)

⊂

We define

Theorem 3.2.17. If λ ≥ ω and 2 ≤ κ ≤ λ

then

Proof:

2 ~ P(λ) follows by identifying sets with their characteristic func-

tions. Then

where XY implies that there exists a 1–1 function from X into Y.

(3.24)



Cardinal exponentiation is not the same as ordinal exponentiation. For exam-

ple, the ordinal 2

is ω

, but the cardinal 2

= ⏐P(ω)⏐> ω .

Axiomatic Set Theory

Theorem 3.2.18. If κ , λ , and σ are any cardinals, then

and

Proof:

We can check that

and



The Continuum Hypothesis (CH) is the conjecture that 2

= ω

. The Gener-

alized Continuum Hypothesis is the conjecture that

If α and β are ordinals and ƒ : α → β is a mapping. The mapping ƒ maps α

cofinally if D

(ƒ) is unbounded in

; i.e.,

∀

b ∈ β∃

∈

(ƒ)(

≤

). The cofinality

, denoted by cf(

), is the least α such that there is a mapping from α cofinally

into

. Therefore, cf(

) ≤ β; if β is a successor, cf(

) = 1.

Theorem 3.2.19. There is a cofinal mapping ƒ : cf(

β) → β which is strictly in-

creasing

Proof: Let g : cf(β) → β be any cofinal mapping, and define a mapping ƒ

recursively by



Theorem 3.2.20. If α is a limit ordinal and ƒ : α → β is a strictly increasing

cofinal mapping, then cf(

α) = cf(

Proof:

cf(

) ≤ cf(α) follows by composing a cofinal mapping from cf(

)

into α with the mapping ƒ. To show cf(α) ≤ cf(

), let g : cf(β

)

→ β

be a cofinal

mapping, and let h(ξ) be the least η such that ƒ(η) > g (ξ ); then h : cf(β) → α is

a cofinal mapping.



Corollary 3.2.3. cf(cf(β)) = cf(β).

An ordinal

β is regular if β is a limit ordinal and cf(

) = β

. Thus, Corollary

3.2.3 implies that cf(

)

is regular for all limit ordinals

Chapter 3

Theorem 3.2.21.

If an ordinal

is regular, then

is a cardinal.

Theorem 3.2.22. κ

is regular.

Proof:

If ƒ mapped

cofinally into

for some α < κ

, then

(3.25)

but the union of

≤ κ

sets each of cardinality

≤ κ

must have cardinality

≤ κ ⊗ κ

by Theorem 3.2.14.



Theorem 3.2.23

[König’s Theorem].

If κ is infinite and cf(κ

)

≤ λ

, then κ

κ .

Proof:

Fix a cofinal mapping ƒ : λ → κ

. Let

κ→

. We show that G

cannot be an onto mapping. Define h :

λ → κ so that h(α) is the least element of

(3.26)

Then h

∉ R

(



Theorem 3.2.24. Assume AC and GCH. Let κ and λ ≥ 2 and at least one of them

be infinite. Then

(1)

(2)

(3)

Proof:

(1) follows from Theorem 3.2.17. For (2),

> κ by Theorem 3.2.23,

but

≤ κ

. For (3), λ < cf(κ) implies that

each

and



We conclude this section by showing that all of classical mathematics can be

built upon ZFC.

Let

be the ring of integers,

the field of rational numbers, the field of real

numbers, and the field of complex numbers. It suffices to show that there is a

way, based on ZFC, to construct the sets of

and

Any reasonable way

of defining these sets from the natural numbers will do, but for definiteness we

take =

ω × ω/ ~, where (n,

) is intended to represent n – m the equivalence

relation ~ is defined by the following: (

a,b

) ~ (

c,d

) if and only if a + d = c + b

Axiomatic Set Theory

is the set of equivalence classes of the relation ~, and operations + and · are

defined as follows:

(3.27)

(3.28)

where [(

b)] is the equivalence class of the relation ~ containing (

b).

Let y

where (

) is intended to represent x/

, and

So is the

set of left sides of all Dedekind cuts. with field operations defined in

the usual way.

We will need the following definitions.

(a)

(b)

3.3. Families of Sets

For an infinite cardinal κ we say that two sets X and Y are k -disjoint if

Theorem 3.3.1.

If κ

≥

and

⏐

κ,

then there exists S

⊂

)

of power

consisting of m-disjoint sets and such that A

Proof: It will be sufficient to find just one set A which can be decomposed as

in the theorem and has power

κ. A 1–1 mapping of A onto A

will then enable us

to obtain the desired decomposition of A

Let

ℵ

and

. Two functions

ƒ, g

(conceived as sets of ordered

pairs) are

ℵ

-disjoint if

We will construct a sequence of type ω

α+1

ℵ

disjoint functions. To carry

out this construction we need the following lemma.

Lemma 3.3.1.

is a transfinite sequence of type

γ < ω

α+1

with range contained

in F, then there exists a function ƒ ∈ F which is ℵ

-disjoint from each term ϕ

the sequence.

Proof of lemma:

To see this we notice that the range of

ϕ has power

≤ ℵ

and thus can be represented as the range of a function Φ : ω

→ F. If ξ <

Let ƒ (

) be the first ordinal in

Then ƒ

∈

which is

ℵ

-disjoint from every

, because

can hold

only if

η ≥ ξ



Chapter 3

Let Γ : p(

)

→

∪

{

}, where ρ ∉ F, such that

For each transfinite sequence

ϕ denote by B(ϕ

) the

set of all functions in F which are ℵ

-disjoint from all terms of ϕ. By transfinite

induction, we obtain a function

: satisfying the equation

(3.29)

for each

ξ <

Thus, and is

ℵ

-disjoint from all

, η < ξ, which belong

to F, provided that such functions exist; otherwise g

= ρ.

We claim that g

≠ ρ for each ρ < ω

. Otherwise there would be a smallest

γ < ω

(

= ρ

) and g

⏐γ would be a sequence satisfying the assumptions of

Lemma 3.3.1. This contradicts the assumption that

∉

F. Thus, ⏐

(

)

⏐ =

+1.

Let

R (

). Since each element of A is an ordered pair of ordinals <

, we

infer that

⏐

≤ ω

; on the other hand,

Thus,

⏐

⏐ = ω



For an infinite cardinal κ two sets x, y ⊂ κ are almost disjoint if ⏐

∩

⏐ < κ.

An almost disjoint family

⊂

(κ)such that

and any two distinct

elements of

are almost disjoint. A maximal almost disjoint family is an almost

disjoint family with no almost disjoint family

properly containing it.

Theorem 3.3.2. Let κ ≥ ω

then

(a)

⊂

(

κ) is an almost disjoint family and

⏐

= κ

, then

is not

maximal.

(b)

There is a maximal almost disjoint family

⊂

(

κ) of cardinality ≥ κ

The proof follows from that of Theorem 3.3.1.

Theorem 3.3.3. If κ ≥ ω and 2

<κ

= κ, then there exists an almost disjoint family

⊂

(κ

)

with

⏐

= 2

Proof: Let I = { x

⊂ κ : x < κ}. Since If X ⊂ κ, let

⏐X

⏐

κ,

then

⏐

also. If

≠

then

since if we fix

such that

then

(3.30)

Let then

⏐

= 2

and is an almost disjoint family

of subsets of I. If we let ƒ be a 1–1 function from I onto

κ,{ƒ(A): A ∈ } is an

almost disjoint family of 2

subsets of κ.

A family

of sets is called a ∆

-system, or a quasi-disjoint family, if there is a

fixed set r, called the root of the ∆

-system, such that a

b = r whenever a and b

are disjoint members of

Axiomatic Set Theory

Theorem 3.3.4.

(

∆-System Lemma). Let κ be an infinite cardinal. Let θ > κ be

regular and satisfy

∀α

(

⏐α

<κ

⏐ < θ

Assume ⏐ ⏐≥θ

and

∀

∈

(

⏐

)

then

there is a

⊂

such that

⏐

⏐ = θ

and

forms a ∆

-system.

Proof:

By shrinking

if necessary, we may assume

⏐

θ.

Then

Since what the elements of

are as individuals is irrelevant, we may assume

Then each x

∈ has some order type < κ as a subset of θ. Since θ is

regular and

θ > κ, there is some ρ < κ such that

= {x

∈

: x has type ρ

} has

cardinality θ. We now fix such a ρ and deal with

For each

θ, ⏐α

<κ

⏐

implies that fewer than

elements of are subsets

α.

Thus,

is unbounded in θ. If x ∈ and ξ < ρ, let x (

) be the ξ

element of x. Since θ is regular, there is some ξ such that

unbounded in θ. Now fix ξ

to be the least such ξ (

may be 0). Let

(3.31)

Then α

< θ and x(

) < α

for all x ∈ and all η < ξ

By transfinite recursion on µ < θ, pick x

∈

so that

(

) >

and

(ξ

)

is above all elements of earlier x

; i.e.,

(3.32)

Let = {x

: µ < θ}. Then ⏐⏐ = θ and x

∩

y ⊂ α

whenever x and y are

distinct elements in Since

there is an r ⊂ α

and ⊂ with

θ and whence forms a ∆-system with root r.



Under the assumption of CH or GCH, we calculated many exponentiations of

cardinals in Section 3.2. If we now assume that CH fails, questions arise about the

various infinite cardinals κ < 2

. For example, we have

Question 3.3.1. If

κ < 2

, does 2

= 2

Question 3.3.2. If κ < 2

, does every almost disjoint family A ⊂

(

) of size κ

fail to be maximal?

Since the answer to these questions is clearly “yes” when

κ = ω, they are only

of interest for

ω < κ < 2

. For such κ, it is known by the method of forcing that

neither question can be settled under the axioms ZFC +

CH. In the following we

show how these questions can be settled by using a new axiom, called Martin’s

axiom. Martin’s axiom is known to have numerous important consequences in

combinatorics, set-theoretic topology, algebra, and analysis. For examples other

than those given here, please consult (Martin and Solovay, 1970; Rudin, 1977;

Shoenfield, 1975).