Yi Lin. General Systems Theory: A Mathematical Approach

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

Chapter 3

The basic symbols of our formal language include

, =

, and v

for each natural number j. Their grammatical meanings are as follows:

•

means “and.”

•

¬ means “not.”

•

∃ means “there exists.”

•

∈ means membership.

•

= means equality.

•

, for each natural number

, are variables.

The parentheses are used for phrasing. An expression is any finite sequence of basic

symbols. The intuitive interpretation of the symbols indicates which expressions

are meaningful; these are called formulas. Precisely, a formula is defined to be

any expression constructed by the rules:

(a) are formulas for any natural numbers i,j

(b) If

and

are formulas, so are for any

To save ourselves the work of always writing long expressions, we will use

the following abbreviations.

(c)

(d)

(e)

(f)

(g)

(h)

Other letters from English, Greek, and Hebrew are used for variables. In this

chapter, we follow standard mathematical usage of writing expressions mostly in

English, augmented by logical symbols when this seems necessary. For example,

we may say “there are sets

, y, z such that

,” rather than

(3.1)

A subformula of a formula

is a constructive sequence of symbols of

which

forms a formula. The scope of an occurrence of a quantifier ∃v

is the unique

subformula beginning with that

∃

. For example, the scope of the quantifier ∃v

in formula (3.1) is An occurrence of a variable in a

Axiomatic Set Theory

formula is called bound if and only if it lies in the scope of a quantifier acting on

that variable, otherwise it is called free. For example, in formula (3.2),

(3.2)

the first occurrence of

is free, but the second is bound, whereas v

is bound at

its occurrences and

is free at its occurrence.

Note that since

∀v

is an abbreviation for ¬∃ v

, it also binds its variable

, whereas the abbreviations

→

↔

are defined in terms of other propositional

connections and do not bind variables.

We often write a formula as

φ(x

. . .,

) to emphasize its dependence on the

variables

, . . ,x

. Then, if

, . . . ,

are different variables, we use

, . . . ,

)

to indicate the formula resulting from substituting a y

for each occurrence of

the free variable x

. Such a substitution is called free, or legitimate, if no free

occurrence of an

is in the scope of a quantifier

∃

. The idea is that the formula

φ(y

, . . . ,

) says about variables

, . . . ,

what the formula

(

, . . . , x

) said

about

, . . . ,

, but this will not be the case if the substitution is not free and some

gets bound by a quantifier of φ. In general, we will always assume that our

substitutions are legitimate. The use of the notation

(

, . . . , x

) does not imply

that each x

actually occurs free in

, . . . , x

); also, φ(x

, . . .,x

) may have

other free variables, which in this discussion we are not emphasizing.

A sentence is a formula with no free variables. Intuitively, a sentence states an

assertion which is either true or false. If S is a set of sentences and

φ is a sentence,

then

φ means that φ is provable from S by a purely logical argument that may

quote sentences in

as axioms but may not refer to any intended “meaning” of

∈

If S

φ, where S is the empty set of sentences, we write φ and say that φ

is logically valid. If (φ ↔ ψ),

we say that

φ and ψ are logically equivalent.

Let

φ be a formula; a universal closure of φ is a sentence obtained by univer-

sally quantifying all free variables of

φ. For example, let φ be the formula

(3.3)

Then

∀

y φ and ∀y∀x φ are universal closures of φ. All universal closures of a

formula are logically equivalent. In general, when we assert

φ, we mean to assert

its universal closure. Formally, if S is a set of sentences and

φ is a formula, we

define

φ to mean that the universal closure of φ is derivable from S.

We call a formula

φ logically valid if its universal closure is logically valid;

we say two formulas

φ and ψ are logically equivalent if φ ↔ ψ is logically valid.

A set S of sentences is consistent, denoted by Con(S), if for no formula

φ does

φ and S φ

. We can see easily that for any sentence

, S φ if and only if

is inconsistent.

In order to use formal deduction, we need the following important facts: (a) If

, then there exists a finite

⊂ S such that S

φ. (b) If S is inconsistent,

there is a finite

⊂ S such that S

is inconsistent.

Chapter 3

As an exercise, we now list all axioms in the ZFC axiom system.

Axiom 1. (Set Existence)

Axiom 2. (Extensionality)

Axiom 3. (Regularity)

Axiom 4.

(Comprehension Scheme) For each formula φ with free variables

among

x, z, w

, . . . ,

Axiom 5. (Pairing)

Axiom 6. (Union)

Axiom 7.

(Replacement Scheme) For each formula φ with free variables

among

x, y, A, w

, . . . ,

where the symbol

∃

! means “there exists exactly one.”

Axiom 8. (Infinity)

Axiom 9. (Power Set)

Axiom 10. (Choice (Axiom of choice or AC))

∀

∃

(

R well orders A)

Axiomatic Set Theory

In the following, we write the meanings of the axioms in English.

Axiom 1.

Axiom 2.

Axiom 3.

Axiom 4.

Axiom 5.

Axiom 6.

Axiom 7.

Axiom 8.

Axiom 9.

Axiom 10.

(Set Existence) There exists a set.

(Extensionality) Two sets x and y are identical if they contain the

same elements.

(Regularity) Each nonempty set x has an element y such that

∧

(Comprehension Scheme) For each given formula and each set z,

there exists a set y such that y = {x

∈ z :

(

)}.

(Pairing) For any sets x and y, there exists a set z such that x ∈ z

and

∈

(Union) For any given set of sets there exists a set

which

consists of all elements belonging to at least one element set in

(Replacement Scheme) For each formula

and any set A, if to

each element x

∈ A there corresponds exactly one y satisfying

(

x,y), then there exists a set Y consisting of all y satisfying

(

x,y), for some x ∈ A.

(Infinity) There exists a set x satisfying (1)

∈ x

, and (2) for each

y ∈ x there exists a set S

(

y) ∈ x which contains all elements in y

and y itself.

(Power Set) For any set x, there exists a set y, called the power set

of the set x and denoted by p(x), such that all subsets of x are

contained in y.

(Choice) Any set can be well-ordered.

An interpretation of the language of set theory is defined by specifying a

nonempty domain of disclosure, over which the variables are intended to vary,

together with a binary relation defined on that domain, which is the interpretation

of the membership relation

∈. If is a sentence in the language of set theory,

is either true or false under a specified interpretation.

In the intended interpretation, under which the axioms of ZFC are presumed

true, the symbol x

∈ y is interpreted to mean that x is a member of y. Since we

wish to talk only about sets and their elements in our domain of discourse, all

Chapter 3

elements of such a set should be sets also. Repeating this, we can see that the

domain of our discourse consists of those x such that

x is a set, and

We call such an x a hereditary set.

If S is a set of sentences, we may show that S is consistent by producing an

interpretation under which all sentences of S are true. Usually,

∈ will still be

interpreted as membership, but the domain of discourse will be some subdomain

of the hereditary sets.

The justification for this method of producing consistency proofs is the easy

direction of the Gödel completeness theorem, which says that if S holds in some

interpretation, then S is consistent. The reason this theorem is true is that the rules

of formal deduction are set up so that if S

then

must be true under any

interpretation which makes all sentences in S true. If we fix an interpretation in

which S holds, then any sentence that is false in that interpretation is not provable

from

Since

and

cannot both hold in a given interpretation,

cannot prove

both

and

; thus S is consistent.

We now conclude this section with a few extremes of mathematical thought.

For a more serious discussion, see (Fraenkel et al., 1973; Kleene, 1952; Kreisel

and Krivine, 1967).

Platonists believe that the set-theoretic universe has an existence outside the

spirit of human beings. From this point of view, the axioms in ZFC are merely

certain obvious facts in the universe, and we might have failed to list some other

obvious but basic facts in the ZFC axiom system. Platonists are still interested in

locating principles of the universe which are not provable from ZFC.

A finitist believes only in finite objects. It is meaningless to consider any sort

of concept like that of “whole.” If, say, “human knowledge” does not exist, the set

of all rational numbers is not a practical concept; hence, the theory of infinite sets is

a piece of meaningless garbage. There is some merit in the finitist’s position, since

all objects in known physical reality are finite, so infinite sets may be discarded

as figments of the mathematician’s imagination. Unfortunately, this point of view

also discards a big portion of modern mathematics.

The formalist can hedge his bets. The formal development of ZFC makes sense

from a strictly finitistic point of view: the axioms of ZFC do not say anything, but

are merely certain finite sequences of symbols. The assertion ZFC means that

there is a certain kind of finite sequence of finite sequences of symbols, namely,

a formal proof of Even though ZFC contains infinitely many axioms, notions

like ZFC will make sense only when a particular sentence is recognized as

an axiom of ZFC. A formalist can thus do mathematics just as a platonist, but if

Axiomatic Set Theory

challenged about the validity of handling infinite objects, he can reply that all he

is really doing is juggling finite sequences of symbols.

In this chapter, we will develop ZFC from a platonistic point of view. Thus,

to establish that ZFC we simply produce an argument that is true based on

the assumption that ZFC contains true principles.

3.2. Constructions of Ordinal and Cardinal Number

Systems

The

Let z be any set. Axiom 3 (comprehensive scheme) implies that

axiom

on set existence says that our domain of discourse is not empty.

{

∈

≠

}

(3. 4)

defines the existence of the empty set. By extensionality, such a set is unique.

The Comprehension Axiom is intended to formalize the construction of sets

of the form {x : P

(

x)}, where P

(

x) denotes a property of x. Since the notion

of property is made rigorous via formulas, it is tempting to set forth as axioms

statements of the form

(3.5)

where

is a formula. Unfortunately, such a scheme is inconsistent by the famous

Zermelo–Russell paradox (Section 2.6): Let be x

≠ x then this axiom gives a y

such that

(3.6)

whence y

∈ y ↔ y ∉ y. To avoid this contradiction the Comprehension Axiom is

given as follows: For each formula without y free, the universal closure of the

following is an axiom:

We can also prove, not simply to avoid this paradox, that there is no universal

set.

Theorem 3.2.1.

Proof:

If ∀x

(

x ∈ z ), by the Comprehension Axiom we can form

which would yield a contradiction by the Zermelo–

Russell paradox.

prod(

A,B) = {prod(A,y) : y ∈ B

}

Chapter 3

We let A ⊂ B abbreviate ∀x(

∈

→

∈

). So, A ⊂ A and ⊂ A.

The example {

x : x = x

} shows that for a given formula

(x ) , there need not

exist a set {x :(x)}.

Generally,

this collection (or class) may be too big to form

a set. The Comprehension Axiom says that if the collection is a subcollection of a

given set, then it is a set. Axioms 4–8 of ZFC say that certain collections do form

sets.

By the Pairing Axiom, for given x and y we may let z be any set such that

∈ z ∧ y ∈ z; then {v ∈ z : v = x ∨ v = y } is the unique (by extensionality)

set whose elements are precisely x and y; we call this set {x,y}. Note that

(

x,y

) = {{

x}, {x,y}} is the ordered pair of x and y.

In the Union Axiom, we think of as a family of sets and postulate the

existence of a set A such that each member Y of is a subset of A. This justifies

our defining the union of the family, denoted by

, by

(3.7)

When

we let

(3.8)

then

and

“should be” the set of all sets, which does not exist.

Finally, we let

For any sets A and B, we define the Cartesian product

(3.9)

To justify this definition, we must apply replacement twice. First for any y ∈ B,

we have

so by replacement (and comprehension) we can define

Now

so by replacement we may define

Finally, we define

prod'(

A,B ).

Axiomatic Set Theory

A relation H is a set all of whose

elements

are ordered pairs.

Let

(3.10)

and

(3.11)

We define H

–1

= {(x,y) : (y,x) ∈ H }, so (

–1

)

–1

= H.

A function (or mapping) is a relation ƒ such that

(3.12)

A total ordering (or strict total ordering or linear ordering) is a pair (

A,H

) such

that H totally orders A; that is, A is a set, H is a relation such that

(3.13)

(3.14)

and

(3.15)

where we write xHy for (x,y) ∈ H.

Note that our notation does not assume

⊂ A × A, so if (A, H) is a total ordering so is (B, H) whenever B ⊂ A.

Whenever H and K are relations and A and B are sets, we say (A, H

)

(B,K

)

if there exists a bijection ƒ : A → B such that ∀

x,y

∈ A

(

xHy

↔

ƒ(

)Kƒ

(

y)). This

mapping ƒ is called an isomorphism from (

A, H) to (B, K

We say H well-orders A, or

(

A,H

) a well-ordering, if (

A,H

) is a total ordering

and every nonempty subset of A has an H-least element; i.e.,

∀B ⊂ A

(

B ≠ Ø →

∃

x ∈ B ∀y ∈ B

(

xHy

)). If x ∈ A, let pred(

A,x,H

) = {y ∈ A : yHx

Lemma 3.2.1. If (

A,H

) is a well-ordering, then

(A,H

) (pred(

A,x,H

),H

) for each x ∈ A

Proof: If ƒ : A

→ pred

(A,x,H

) were an isomorphism, let z be the H-least

element of {y

∈ A : ƒ

(

y) ≠ y}. Then for each y ∈ A with yHz,ƒ(y) = y. Since ƒ

is an isomorphism it follows that ƒ(z

)

= z. This contradicts the definition of z.



Lemma 3.2.2. If (A, H) and (B, K) are isomorphic well-orderings, then the iso-

morphism between them is unique.

Chapter 3

Proof:

and

were different isomorphisms, let

be the

-least y ∈ A such

that ƒ(

y) ≠ g

(

y). Then a similar contradiction as in the proof of Lemma 3.2.1 will

occur.

Theorem 3.2.2. Let (

A,H

) and (

B,K

) be two well-orderings. Then exactly one

of the following holds:

(a) (

A,H

)

(B,K

(b) ∃y ∈ B

((

A,H

)

(pred(B,y,K),K)).

(c)

∃x ∈ A

((pred(

A,x,R

)

(B,K)).

Proof: Let

f = {(v,w) : v

∈ A ∧

∈

∧

(pred(

A,v,H

),H

)

(pred(B,w,K),K

)}

Note that f is an isomorphism from some initial segment of A onto some initial

segment of B, and that these segments cannot both be proper.

A set x is transitive if every element of x is a subset of x.

Examples of

transitive sets are Ø, {Ø} , {Ø, {Ø}}

,…. The set {{Ø}} is not transitive. A set x

is an ordinal if x is transitive and well-ordered by the relation

∈. More formally,

the assertion that x is well-ordered by

∈ means that (x, ∈

) is a well-ordering,

where

∈

{(

y,z) ∈ x × x : y ∈ z

}. Examples of ordinals are Ø, {Ø} , {Ø, {Ø}}. If

x = {x}, then x is not ordinal since we have defined orderings to be strict. Without

causing confusion, we write x

(

A, H

) for (

x, ∈

)(

A, H) and y ∈ x, pred(x,y

)

for pred(

x,y, ∈

Theorem 3.2.3.

(1) If x is an ordinal and y

∈ x, then y is an ordinal and y = pred(x,y

(2)

If x and y are ordinals and x y, then x = y.

(3) If x and y are ordinals, then exactly one of the following is true: x = y,

∈y,y∈x.

(4) If x, y, and z are ordinals, x

∈ y and y ∈ z implies that x ∈ z.

(5) If C is an nonempty set of ordinals, then

∃

∈

∀ y ∈ C

(

x ∈ y ∨ x = y

Axiomatic Set Theory

Proof: For(3), we use (1), (2), and Theorem 3.2.2 to show that at least one

of the three conditions holds. That no more than one holds follows from the fact

that no ordinal can be a member of itself, since x

∈ x would imply that (x, ∈

) is

not a strict total ordering (since x

∈

x). For (5), we note that the conclusion is,

by (3), equivalent to

∃x ∈ C

(

x ∩ C =

). Let x ∈ C be arbitrary. If x ∩ C # Ø,

then since

is well-ordered by

∈,

there is an

∈

-least element

∩

and then

∩

= Ø

Theorem 3.2.3 implies that the set of all ordinals, if it existed, would be an

ordinal, and thus cannot exist, because if such an ordinal existed, denoted by

η,

then Theorem 3.2.3(5) implies that η ∩ { η} = Ø, but the definition of η implies

η ∈ η

∩

{

η}, contradiction. This fact takes care of the Burali-Forti paradox (see

Section 2.6 for details).

Lemma 3.2.3. Let A be a set of ordinals and

∀x ∈ A∀y ∈ x

(

y ∈ A) then A is an

ordinal.

Theorem 3.2.4. If (

A,H

)

is a well-ordering, then there exists a unique ordinal C

such that (

A,H

)

Proof: The uniqueness of the ordinal C follows from Theorem 3.2.3(2). to

prove existence, let

B = {a

∈ A : ∃x(

is an ordinal ∧ (

pred

(

A,a,H

)

)}

(3.16)

Let ƒ be the function with domain B such that for each a ∈ B, f (

) = the unique

ordinal

such that (pred(

A, a, H), H

)

x, and let C = R

(

). Now, we check that

is an ordinal (from Lemma 3.2.3), that ƒ is an isomorphism from (

B, H) onto C,

and that either B = A (in which case we are done), or B = pred(A, b, H) for some

∈ A (in which case b ∈ B, and hence a contradiction).

Theorem 3.2.4 implies that ordinals can be used as representatives of the

order types of well-ordered sets.

Thus, we have the following: If (A, H) is a

well-ordering, the type (

A,H

) is defined to be the unique ordinal C such that

(

A, H

)

C. From now on we use Greek letters α, β, γ ,… to indicate ordinals.

We may thus say, e.g.,

∀ α

…

instead of

∀

(

is an ordinal

→

… ). Since

∈

orders

the ordinals, we write α < β for α ∈ β and use α ≥ β to indicate β ∈ α ∨ β = α.

Lemma 3.2.4.

(1)

∀

(

≤

→

α⊂

(2) If X is a set of ordinals, then

∪

X is the least ordinal ≥ all elements in X,

and, if X

≠

∩

X is the least ordinal in X.