1610912322-b551b095a53deaf3d3fbd1ed05ae9b84 (824701), страница 11
Текст из файла (страница 11)
Thus (card X < card Y ) :=(card X ≤ card Y ) ∧ (card X = card Y ).As before, let ∅ be the empty set and P(X) the set of all subsets of the set X.Cantor made the following discovery:Theorem card X < card P(X).Proof The assertion is obvious for the empty set, so that from now on we shallassume X = ∅.Since P(X) contains all one-element subsets of X, card X ≤ card P(X).To prove the theorem it now suffices to show that card X = card P(X) if X = ∅.Suppose, contrary to the assertion, that there exists a bijective mapping f : X →/ f (x)} consisting of the elements x ∈ XP(X). Consider the set A = {x ∈ X : x ∈that do not belong to the set f (x) ∈ P(X) assigned to them by the bijection.
SinceA ∈ P(X), there exists a ∈ X such that f (a) = A. For the element a the relationa ∈ A is impossible by the definition of A, and the relation a ∈/ A is impossible,also by the definition of A. We have thus reached a contradiction with the law ofexcluded middle.This theorem shows in particular that if infinite sets exist, then even “infinities”are not all the same.1.4.2 Axioms for Set TheoryThe purpose of the present subsection is to give the interested reader a picture of anaxiom system that describes the properties of the mathematical object called a setand to illustrate the simplest consequences of those axioms.10 . (Axiom of extensionality) Sets A and B are equal if and only if they have thesame elements.This means that we ignore all properties of the object known as a “set” exceptthe property of having elements. In practice it means that if we wish to establish thatA = B, we must verify that ∀x ((x ∈ A) ⇔ (x ∈ B)).20 .
(Axiom of separation) To any set A and any property P there corresponds aset B whose elements are those elements of A, and only those, having property P .More briefly, it is asserted that if A is a set, then B = {x ∈ A | P (x)} is also a set.This axiom is used very frequently in mathematical constructions, when we select from a set the subset consisting of the elements having some property.For example, it follows from the axiom of separation that there exists an emptysubset ∅X = {x ∈ X | x = x} in any set X.
By virtue of the axiom of extensionality281 Some General Mathematical Concepts and Notationwe conclude that ∅X = ∅Y for all sets X and Y , that is, the empty set is unique. Wedenote this set by ∅.It also follows from the axiom of separation that if A and B are sets, then A\B ={x ∈ A | x ∈/ B} is also a set. In particular, if M is a set and A a subset of M, thenCM A is also a set.30 . (Union axiom) For any set M whose elements are sets there exists a set M,called the union of M and consisting of those elements and only those thatbelong to some element of M.If we use the phrase “family of sets” instead of “a set whose elements are sets”the axiom of union assumes a more familiar sound: there exists a set consistingofthe elements of the sets in the family.
Thus, a union of sets is a set, and x ∈ M ⇔∃X ((X ∈ M) ∧ (x ∈ X)).When we take account of the axiom of separation, the union axiom makes itpossible to define the intersection of the set M (or family of sets) as the setM := x ∈M | ∀X (X ∈ M) ⇒ (x ∈ X) .40 . (Pairing axiom) For any sets X and Y there exists a set Z such that X and Yare its only elements.The set Z is denoted {X, Y } and is called the unordered pair of sets X and Y .The set Z consists of one element if X = Y .As we have already pointed out, the ordered pair (X, Y ) differs from the unordered pair by the presence of some property possessed by one of the sets in thepair.
For example, (X, Y ) := {{X, X}, {X, Y }}.Thus, the unordered pair makes it possible to introduce the ordered pair, and theordered pair makes it possible to introduce the direct product of sets by using theaxiom of separation and the following important axiom.50 . (Power set axiom) For any set X there exists a set P(X) having each subset ofX as an element, and having no other elements.In short, there exists a set consisting of all the subsets of a given set.We can now verify that the ordered pairs (x, y), where x ∈ X and y ∈ Y , reallydo form a set, namely X × Y := p ∈ P P(X) ∪ P(Y ) | p = (x, y) ∧ (x ∈ X) ∧ (y ∈ Y ) .Axioms 10 –50 limit the possibility of forming new sets. Thus, by Cantor’s theorem (which asserts that card X < card P(X)) there is an element in the set P(X)that does not belong to X.
Therefore the “set of all sets” does not exist. And it wasprecisely on this “set” that Russell’s paradox was based.In order to state the next axiom we introduce the concept of the successor X +of the set X. By definition X + = X ∪ {X}. More briefly, the one-element set {X} isadjoined to X.1.4 Supplementary Material29Further, a set is called inductive if the empty set is one of its elements and thesuccessor of each of its elements also belongs to it.60 .
(Axiom of infinity) There exist inductive sets.When we take Axioms 10 –40 into account, the axiom of infinity makes it possibleto construct a standard model of the set N0 of natural numbers (in the sense ofvon Neumann),20 by defining N0 as the intersection of all inductive sets, that is, thesmallest inductive set. The elements of N0 are∅, ∅+ = ∅ ∪ {∅} = {∅},{∅}+ = {∅} ∪ {∅} , . .
. ,which are a model for what we denote by the symbols 0, 1, 2, . . . and call the naturalnumbers.70 . (Axiom of replacement) Let F(x, y) be a statement (more precisely, a formula)such that for every x0 in the set X there exists a unique object y0 such thatF(x0 , y0 ) is true. Then the objects y for which there exists an element x ∈ Xsuch that F(x, y) is true form a set.We shall make no use of this axiom in our construction of analysis.Axioms 10 –70 constitute the axiom system known as the Zermelo–Fraenkel axioms.21To this system another axiom is usually added, one that is independent of Axioms 10 –70 and used very frequently in analysis.80 . (Axiom of choice) For any family of nonempty and mutually nonintersectingsets there exists a set C such that for each set X in the family X ∩ C consists ofexactly one element.In other words, from each set of the family one can choose exactly one representative in such a way that the representatives chosen form a set C.The axiom of choice, known as Zermelo’s axiom in mathematics, has been thesubject of heated debates among specialists.1.4.3 Remarks on the Structure of Mathematical Propositionsand Their Expression in the Language of Set TheoryIn the language of set theory there are two basic, or atomic types of mathematicalstatements: the assertion x ∈ A, that an object x is an element of a set A, and the20 J.
von Neumann (1903–1957) – American mathematician who worked in functional analysis, themathematical foundations of quantum mechanics, topological groups, game theory, and mathematical logic. He was one of the leaders in the creation of the first computers.21 E. Zermelo (1871–1953) – German mathematician. A. Fraenkel (1891–1965) – German (later,Israeli) mathematician.301 Some General Mathematical Concepts and Notationassertion A = B, that the sets A and B are identical.
(However, when the axiomof extensionality is taken into account, the second statement is a combination ofstatements of the first type: (x ∈ A) ⇔ (x ∈ B).)A complex statement or logical formula can be constructed from atomic statements by means of logical operators – the connectors ¬, ∧, ∨ ⇒ and the quantifiers∀, ∃ – by use of parentheses ( ). When this is done, the formation of any statement,no matter how complicated, reduces to carrying out the following elementary logicaloperations:a) forming a new statement by placing the negation sign before some statementand enclosing the result in parentheses;b) forming a new statement by substituting the necessary connectors ∧, ∨, and⇒ between two statements and enclosing the result in parentheses.c) forming the statement “for every object x property P holds”, (written as∀x P (x)) or the statement “there exists an object x having property P ” (writtenas ∃x P (x)).For example, the cumbersome expression ∃x P (x) ∧ ∀y P (y) ⇒ (y = x)means that there exists an object having property P and such that if y is any object having this property, then y = x.
In brief: there exists a unique object x havingproperty P . This statement is usually written ∃!x P (x), and we shall use this abbreviation.To simplify the writing of a statement, as already pointed out, one attempts toomit as many parentheses as possible while retaining the unambiguous interpretation of the statement. To this end, in addition to the priority of the operators ¬, ∧,∨, ⇒ mentioned earlier, we assume that the symbols in a formula are most stronglyconnected by the symbols ∈, =, then ∃, ∀, and then the connectors ¬, ∧, ∨, ⇒.Taking account of this convention, we can now write∃!x P (x) := ∃x P (x) ∧ ∀y P (y) ⇒ y = x .We also make the following widely used abbreviations:(∀x ∈ X) P := ∀x x ∈ X ⇒ P (x) ,(∃x ∈ X) P := ∃x x ∈ X ∧ P (x) ,(∀x > a) P := ∀x x ∈ R ∧ x > a ⇒ P (x) ,(∃x > a) P := ∃x x ∈ R ∧ x > a ∧ P (x) .Here R, as always, denotes the set of real numbers.Taking account of these abbreviations and the rules a), b), c) for constructingcomplex statements, we can, for example, give an unambiguous expressionlim f (x) = a := ∀ε > 0 ∃δ > 0 ∀x ∈ R 0 < |x − a| < δ ⇒ f (x) − A < εx→A1.4 Supplementary Material31of the fact that the number A is the limit of the function f : R → R at the pointa ∈ R.For us perhaps the most important result of what has been said in this subsectionwill be the rules for forming the negation of a statement containing quantifiers.The negation of the statement “for some x, P (x) is true” means that “for any x,P (x) is false”, while the negation of the statement “for any x, P (x) is true” meansthat “there exists an x such that P (x) is false”.Thus,¬∃x P (x) ⇔ ∀x ¬P (x),¬∀x P (x) ⇔ ∃x ¬P (x).We recall also (see the exercises in Sect.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
