Manifesto Of the Manifest (extract from)

Naïve and ZFC-Axiomatic

Set Theories

Laurent Dubois 2004

Mathematics without numbers nor figures!

When more fundamental elements than numbers arise.

From mathematics to mathematic,

When mathematics become a real language,

not a simple collection of theories

Legend:

ZFC axioms

Logics formula

Logics matrices

Problematic sets

Naive theory

demonstrations

ZFC demonstrations

Digressions

Here my introduction to the Zermelo-Fraenkel axiomatic set theory. This is a personal arrangement. Maybe will you experiment this agreeable sensation of being fit out to start to explore strange countries and to build serious foundations to mathematics.

This is an arrangement that focuses on the paradoxes contained in the naïve set theory, the iterative conception of set. The fact that what we have naïvely in mind when we think about sets, closed entity, is really dynamical, expansive. The term “set” itself, is it not moving, fuzzy? On the other hand, it appears that an ontology cannot be satisfied with the restrictions established by the ZFC axiomatic.

Material: numbers and letters (sounds and fruit of observations);

Fundamental relations: relations

Tools/equipment: axioms

L º Í, Î, =, @, Ù, Ú, Ø, ®, Û, ", $, #, ( , ), variables (x, y, z...),…

A Formula is a sentence written in the language L .

If j, y are formula, then j Ú y, j Ù y, Øj, j ® y, j « y, "x j, $y y are formula.

Linked variables are quantified: "x, $y

Parameters: non quantified/free variables: "x $y x Î z Ù z Î y º j

In this formula j, z is a parameter, we cannot determine its truth.

Ø"x j(x,…) º $x Øj(x,…)

Ø$x j(x,…) º "x Øj(x,…)

j(a, b, c) means that the set of the free variables of j is a part of {a, b, c}. Anything with 2 variables can be with 3 or more variables: x² + 3y² + 0z²

sentence = complete phrase º formula without parameters. / so a sentence asserts something, / it can be true or false

G = theory = collection/list of sentences

Theorem of G = sentence s such that from G, one deduces s: G ‌— s

Let’s start with the Null/Empty set:

$y "x xÎy Û x ¹ x

x ¹ x is a formula but any other impossible equality would function :

x = Æ Ù x = ¥

0 = 1

As no element can satisfy this condition/formula, the set y contains no element!

Y = {x | x ¹ x}

y = {} or Æ

Why is it so? In virtue of the principles of non-contradiction and excluded-middle:

Ø(p Ù Øp) º p Ú Øp

They have the same conditions of satisfaction:

Ø(p Ù Øp) º Ø(p) Ú Ø(Øp)

º Øp Ú p

º p Ú Øp

p Ú Øp º Ø(Øp Ù p)

º Ø(p Ù Øp)

p	q	p Ù q	- (p Ù q)	-p Ú -q
0	1	0	1	1
0	0	0	1	1
1	1	1	0	0
1	0	0	1	1

p	-p	p Ù -p	p Ù -p	- (p Ù -p)	p Ú -p
0	1	0	1	1
0	0	0	0	0
1	1	1	0	0
1	0	0	1	1

Normally, “p Ù -p” is true when the two propositions are true only; but here, the situation where they are both false is equivalent by virtue of the commutativity of the connector “Ù”:

p Ù -p º -p Ù p

In the same way, the situations where one is true and the other false can be reduced to one case.

Of course, we work in first order logic. And it is question here of the inclusive OR

(exclusive OR = XOR)

If we consider cases of presupposition, we can be tempted to establish a semantic/non-classical negation

[Ø(p Ù Øp) º p Ú Øp] º [Ø(p Ù Øp) « p Ú Øp] « [Ø(p Ù Øp) º p Ú Øp]

{[Ø(p Ù Øp) º p Ú Øp] º [Ø(p Ù Øp) « p Ú Øp]} « {[Ø(p Ù Øp) º p Ú Øp] « [Ø(p Ù Øp) « p Ú Øp]}

there is an inevitable disequilibria in the occurrences of the “equivalence” operators

S Ç Æ = Æ

S È Æ = S

Æ Ç {Æ} = Æ

Æ È {Æ} = {Æ}

Æ Î {Æ}

Really, the null set is the only non-set object admitted in the axiomatic.

No axiom of unconditional existence!

But let’s come back to the formula, i.e. a sentence that can be determined true or false because it does not contain parameters, free variables:

"x x Î {x | F(x)}º F(x)

with F(x) =

Now, in which measure is it legitimate to use such formula to define a set, were it by default? Is the null set more legitimate than the set of all sets? On the other hand, why would it less legitimate than “0”?

Now the Infinite set :

From one extreme, Æ

to another one ¥

$x (Æ Î x Ù "y (y Î x Þ {y}Îx))

Thanks to the existence of the null set, it is possible to build an infinite set. It was funny to begin this tutorial with these seemingly two opposite sets!

0 = Æ 1 = {Æ} 2 = {Æ, {Æ}} 3 = {Æ, {Æ}, {{Æ}}}…

0 = {} 1 = {{}} 2 = {{}, {{}}} 3 = {{}, {{}}, {{{}}}}…

x = {Æ, {Æ}, {{Æ}}…} º x = {{}, {{}}, {{{}}}…}

This is an illustration of the Induction principle. You show that the formula is correct for a minimal element, in general 0. After that you try to establish that if it is true for x, it must be true for x + 1.

Thanks to the replacement axiom scheme:

"u "v "w ((F(u, v) « F(u, w)) ® v = w)) ® "x $y "v (v Î y « $u u Î x Ù F(u, v))

we can build the Naturals :

$x (Æ Î x Ù "y (y Î x Þ y È {y}Îx))

This is the translation of integers in set theory by Von Neumann, using the recursive algorithm:

0 := Æ

N + 1 := N È {N}

Zero, the smallest von Neumann integer, is defined as the empty set. The von Neumann integer N is defined as the finite set with N elements which are the von Neumann integers 0 to N-1.

0 := Æ

1 := 0 È {0} = {Æ}

2 := 1 È {1} = {0, 1} = {Æ, {Æ}}

3 := 2 È {2} = {0, 1, 2} = {Æ, {Æ}, {Æ, {Æ}}}…

N + 1 := N È {N} = {0, 1, 2,…, N} = {Æ, {Æ}, {Æ, {Æ}},…, {Æ, {Æ}}, {Æ, {Æ}, {Æ, {Æ}}}…}}…

0 := {}

1 = {{}}

2 = {{}, {{}}}

3 = {{}, {{}}, {{}, {{}}}}

N+ 1 = {{}, {{}}, {{}, {{}}},…, {{}, {{}}}, {{}, {{}}, {{}, {{}}}}…}}…

x = {Æ, {Æ}, {Æ, {Æ}}…} º x = {{}, {{}}, {{}, {{}}}…}

von Neumann integers is infinite but every of its element N is finite.

The von Neumann integer transcription grows exponentially, for N>0 it has 5*2^N-1-1 characters (braces and commas).

Of course, this representation doesn’t make sense, since N is infinite! This is the paradox of set theory.

:= := by definition

Axiom of foundation or regularity:

$x F(x) ® $x F(x) Ù "y Ø(F(y) ® y Î x)

$x F(x) ® $x F(x) Ù Ø($y F(y) Ù y Î x)

This axiom allows to avoid the circular inclusions (Heinlein auto generation) like:

x Î y Ù y Î z Ù z Î x

and infinitely descending chains of sets :

… x₃ Î x₂Î x₁ Î x₀

In other words, increasing infinite allowed, descending infinite excluded.

So once again, we see the limits of this axiom in the frame of a universal ontology

We consider now the problematic sets.

sets that does not contain themselves

$y "x xÎy Û x Ï x

y = {x | x Ï x}

With the short comprehension axiom,

$y "x xÎy Û F(x)

that gives :

x Î y º x Ï x

If we instantiate y for x, we have :

y Î y º y Ï y

which is, of course, absurd !

" x x Î {x | x Î y Þ x È {x}Î y} º F(x)

Here, the separation axiom scheme will be useful, we can save:

""x $y "z (z Î y Û zÎ x Ùj (z, ))

Indeed we have now :

z Î y Û zÎ x Ù z Ï z

which gives, with the instantiation of y for z :

(y Î y Û yÎ x Ù y Ï y)

the condition to keep the validity of the axiom – otherwise an axiom would be false - is to consider that :

y Ï x Ù y Ï y

which shows that, for any set, there is something not contained by it ;

so there is no set of all sets !

with Zermelo, this axiom has two conditions to build sets on the basis of a property:

- to start from an existing set

- well-defined property

as this second condition itself is not “well-defined”, Skolem will precise that a property is well-defined if:

- it is expressed in a first-order predicate calculus language

- it uses logical constants

- it uses the two predicate symbols = and Î only.

Separation axiom scheme:

""x $y "z (z Î y Û zÎ x Ù j (z, ))

" x x Î {x | F(x)} º j(x)

" x x Î {x | F(x)} º F(x)

" x x Î {x | x Î y Þ x È {x}Î y} º F(x)

Replacement axiom scheme:

"u "v "w ((F(u, v) « F(u, w)) ® v = w)) ® "x $y "v (v Î y « $u u Î x Ù F(u, v))

The open sentence F(u, v) is a functional condition, a function that relates each member in set u to a unique member in set v.

It is necessary to prove the existence of a limit of the increasing series of transfinite cardinals () º {: i Î N}

Axiom of extensionality:

"x "y "z ((z Î x « z Î y) ® x = y)

Sets are uniquely defined by their members. There cannot be two different sets that have the same elements. As the identity of sets is treated extensionally and not intentionally, two different set definitions can lead to identical sets.

The notions of “set”, “element” and “membership” are indissociable!

Note that the converse,

x = y ® "x "y "z ((z Î x « z Î y)

is an axiom of the predicate calculus. Hence we have,

x = y « "x "y "z ((z Î x « z Î y)

Therefore the Axiom of Extensionality expresses the most fundamental notion of a set: a set is determined by its elements. This is the reason why this axiom is ordinarily the introductive axiom of the theory. But if there is an infinity of sets with one or more members, there is “only one” null set!

Where the use of the null set as fundamental element is justified!

Two examples of demonstration:

Let A = {0, 1}, let B = {1, 0}

Let’s show that A = B

1) "x "y ("z (z Î x « z Î y) ® x = y) / Axiom or "x "y ("z (z Î x º z Î y) ® x = y) Axiom

2) x = A, y = B / We have set A and set B

3) "z (z Î A « z Î B) ® A = B / 1, 2 Instantiation

4) 0 Î A º 0 Î B / set definition of A, B

5) 1 Î A º 1 Î B / set definition of A, B

6) "z (z Î A « z Î B) / 4, 5

7) A = B / Modus ponens

Let A = {0, 0}, let B = {0}

Let’s show that A = B

1) "x "y ("z (z Î x « z Î y) ® x = y) / Axiom or "x "y ("z (z Î x º z Î y) ® x = y) Axiom

2) x = A, y = B / We have set A and set B

3) "z (z Î A « z Î B) ® A = B / 1, 2 Instantiation

4) Let’s 0₁ stand for “the first element” in A, and 0₂ stand for “the second element” in A

5) 0₁Î A º 0 Î A º 0 Î B / set definition of A, B

6) 0₂Î A º 0 Î A º 0 Î B / set definition of A, B

7) "z (z Î A º z Î B) / from 5, 6

8) A = B / Modus ponens

The principle of “anti-symmetry” leads to the same result:

Let A = {0, 1}, let B = {1, 0}

A Í B Ù B Í A Þ A = B

Since Í ® Ì, we can put a higher condition:

A Ì B Ù B Ì A Þ A = B

In the same way, we have:

A £ B Ù B £ A Þ A = B

and

A < B Ù B < A Þ A = B

As the order of the elements of a set has no importance, it is necessary to elaborate a definition of ordered elements.

A collection of elements in which multiplicity but not order is relevant is called a multi-set.

As for the order, it is taken into account in this way:

(x, y) ¹ (y, x)

Indeed, by definition,

(x, y) = {{x}, {x, y}}

(y, x) = {{y}, {x, y}}

let’s prove that (x, y) ≠ (y, x) as long as x is different of y;

(x, y) = {{x}, {x, y}}

(y, x) = {{y}, {x, y}}

If {x, y} is equal to {x, y},

{x} is really different of {y} by hypothesis,

otherwise, by axiom of extensionality, we would have a

singleton {x} or {y]

in place of {x, y},

hence (x, y) is really different of (y, x)

if we make a demonstration in a constructive way, we have

(x, y) = (x’, y’) Iff x = x’ & y = y’

{{x}, {x, y}} = {{x’}, {x’, y’}} º ({{x} = {x’} Ú {x’, y’}} Ù {x, y} = {x’} Ú {x’, y’}}

{x, {x, y}} = {x’, {x’, y’}} º ({x} = {x’} Ù {x, y} = {x’, y’}) Ú ({x} = {x’, y’} Ú {x, y} = {x’})

º ({x} = {x’} Ù {x, y} = {x’, y’})

º (x = x’ Ù y = y’) by Axiom of Extensionality

Since we are dealing with “orders”, let’s consider triplets, quadruplets, n-uplets.

(x, y, z) = (x, (y, z))

(x, (y, z)) = {x, {x, {y, {y, z}}}

(x, y, z) = {{x}, {x, y}, {x, y, z}}

(a₁, a₂, a₃, …, a_n) = (a₁, (a₂, a₃, …, a_n)) = (a₁, (a₂, (a₃, …, a_n))) = (a₁, (a₂, (a₃, (…, a_n))))

We immediately see the limits of the axiom of extensionality in the frame of an high-level ontology. What does mean “to have the same elements”?

This is a way of erasing the time factor.

We can introduce a relativity scale (// Russell types?); referential

A set has the dimension of its elements (space-time matter continuum)

Axiom of the pairs:

"x "y $z "t (t Î z « t = x Ú t = y) or "x "y $z "t (t Î z º t = x Ú t = y)

From sets x and y, one can build {x, y}, and from that, recursively, the sets

{x, {x, y}}, {y, {x, y}}…

One can also build {x, x} that, by virtue of the principle of extensionality, is reduced to the singleton {x}.

If x = Æ º x = {}, we have {{}}, and by recursivity, {{{…}}}.

The way to build sets as big as one wants.

Axiom of the parts or Power axiom :

Divergent infinites.

"x $y "z (z Î y « "u u Î z ® z Î x)

A way of expressing the inclusion, the potentiality

The road to differences in cardinality between infinite sets!

Indeed, we will make the demonstration that the elements of a set and the elements of the set of its parts cannot be made in bijection.

Only constructive axiom with the axiom of the pair.

If we start from the null set, we can build the singleton:

Ã₍_Æ₎ = {Æ}

by recursivity:

Ã_({_Æ_})= {Æ, {Æ}}

Ã_({_Æ_{, {}_Æ_}}) = {Æ, {Æ}, {{Æ}}, {Æ, {Æ}}}

If #X = n, then #Ã_(X) = 2ⁿ

The axiom of the parts allows, as that of the pairs, to build infinitely big sets.

In geometry, the line L is a set of points and the set L is of the lines of a plane p is a set of sets.

If m is a point of the plane p and D a line getting over m, we have:

m Î p m Î L L Í p L Î L

Induction principle:

It is the demonstration that it will function because it has to function!

If E has n elements, then Ã_(E)has 2ⁿ elements.

Demonstration: by recurrence on n.

Be P the above property to demonstrate.

P(0) is true because then E = Æ and Ã(Æ) = {Æ} contains 1 element.

Let’s suppose that P(n) is true; be then E with n + 1 element;

Be a one of these elements that we fix. We can divide P(E) in two parts:

parts of E that contain a

parts of E that does not contain a;

let’s compute the number of elements of each of these parts;

be A the parts of E that does not contain a

be B the parts of E that contain a

We have a bijection between A and Ã(E-{a}) defined by a(a) = a for each A Î A. So these two sets have the same number of elements;

Since E – {a} has n elements, since P(n) is true, the cardinality of A is 2ⁿ.

We also have a bijection between B and Ã(E-{a}) defined by b(b) = B – {a}.

So B has 2ⁿ elements too. So Ã(E) has 2ⁿ + 2ⁿ elements, i.e. 2^{n + 1} elements.

QED

If n = 3, Ã₍₃₎= 8

is it a legitimate translation of:

Axiom of union:

"x $y "z (z Î y « $u u Î x Ù z Î u)

If we apply the axiom of union to the Power set, we find the initial set w. Really, as revealed by the Burali-Forti paradox, w cannot be a set; it is a class!

Axiom of simplification in the same way as that of extensionality

Burali-Forti paradox:

w cannot be a set, because it would be indexed by a type and would have to contain itself, because the definition of the ordinals

construction of ordinals each ordinal is constituted of its predecessors

maximal element

x_g = f(strict Maj.{x_b½b < g})

induction principle

how do the axioms play a role in the following developments?

Injection, Bijection, Surjection

Be a function f : E ® F

f is injective if we have

f(x) = f(y) Þ x = y

Of course, if f is a function,

x = y Þ f(x) = f(y)

is always true, which means that the graph is functional. So, for an injective application,

we have:

x = y Û f(x) = f(y)

f is surjective if f(E) = F.

It means that any element of F can be written f(x) with x Î E.

f is surjective Û "y Î F $x Î E ½y = f(x)

Bijection: f is bijective if it is both injective and surjective

Bijection Þ Injection (max. bij.)

Bijection Þ Surjection (min. bij.)

Injection: each element of target set has at most 1 antecedent in source set; or each element of source set is the only antecedent of an element of target set when it is an antecedent. Target set is at least as big as source set.

Surjection: each element of target set has at least 1 antecedent in source set; or each element of source set is the only antecedent of an element of target set when it is an antecedent. Target set is at least as big as source set.

Be A(dom) and B(image)

Surjection: either B contains as many elements as A,and we have a bijection; either B contains more elements than A. To have a proper identity, some elements of B have to have more than one antecedent in A; but then j: A ® B is no more injective, which admits only one or 0 antecedent for each b Î B in A.

Ø (À # Ã(À))

Transfinites: the institutionalisation of paradoxes in mathematics.

Set is infinitely far from infinite.

That doesn’t prevent set and infinite to be very together.

Demonstration:

Ã(N) is infinite since we have an injection of N in Ã(N): n ® {n}; / indeed, N Ì RÃ(N)

consequently, it’s not a finite set.

Now, we have to show that there is no bijection between N and P(N).

Be j: N® Ã(N); let’s show that j cannot be a bijection. / there is an injection of N in Ã(N) º j: N® Ã(N) º n ® {n} º j(n) = {n}

Be A = {n Î N | n Ï j(n)}.

Let’s suppose there exists a Î N such that j(a) = A;

if a Î A, according to the definition of A, a Ï j(a) = A; this is not possible;

if a Ï A, since A = j(a), a Ïj(a), so, by definition of A, a Î A, which is not possible either; consequently, that means that a doesn’t exist and that j is not surjective, thus not bijective. / since j is injective, to show that it is not bijective, it is necessary to show that it is not surjective.

/ If A $, there must be free n in N and A must be in Ã(N) since it is constituted of n only; A is obligatory a part of N.

/ If a doesn’t exist, A = j(a) doesn’t exist either, and there is no n Î N such that n Ï j(n), and there is no possible surjection between n and Ã(N) because of the lack of free elements in N.

It seems to be counter-intuitive that A doesn’t exist because we can have, for example,,

/ Since N Î Ã(N), if we make a bijection between N and N in j: N® Ã(N), we cannot use N for another bijection. If we make a bijection

/ between N and N + (x, y) , one cannot use N for another bijection. The problem is that there is an infinity of additional sets which we can make N in

/ correspondance with. So one cannot begin to attribute a n to all the parts/sets of Ã(N).

/ If there are n Î N such that n Ï j(n), these n constituting the set A, they could be used for a surhection between N and Ã(N). There must be enough elements in N such that each element of Ã(N) has at least one specific antecedent.

of course, N and Ã(N) are infinite, even in different ways:

#N = À₀

#Ã(N) = = À₁

Complementary demonstration of the unaccountability of Ã(E) that will be useful to establish that R is not countable.

Proposition: no injection from Ã(E) in N.

Demonstration:

Be w: Ã(N) ® N. Let’s show it is not injective.

We define A = {n Î N|"E ÎÃ(N), if nÎ E, then w(E) ¹ n}. / the formula says that N must be as big as Ã(N) in order to have unused n in N.

-w(a) Ï A; indeed, if w(a) Î A (thus in N), then "E ÎÃ(N), if w(a) Î E, then w(E) ¹ w(A); since we suppose ¹ w w(A) Î A, we can have E = A, consequently w(A) ¹ w(A); consequently, w(A) Ï A.

From an other point of view, the image of E must be different of the elements of E; thus different of w(A), which is an element of E. Now, A is a E, then,

thus w(E) ¹ w(E).

From the definition of A, w(A) Ï A means that $ E ÎÃ(N) | w(A) Î E Ù w(A) = w(E).

Thus we have w(A) = w(E), though A ¹ E since w(A) Ï A Ù w(A) Î E;

so w is not injective.

Remark:

This demonstration would be acceptable for any set X, so there is no injection from Ã(X) in X.

"E ÎÃ(N) n Î e Þ w(E) ¹ n Þ n Î N

n Î E Ùw(E) ¹ n Þ n Î N

- (n Î N) Þ - (n Î E Ù w(E) ¹ n)

n Ï N Þ -"E ÎÃ(N) (n Î E Ù w(E) ¹ n)

n Ï N Þ ($E ÎÃ(N) (n Î E Ù w(E) = n)) Ú ($E ÎÃ(N) (n Ï E Ù w(E) ¹ n))

and we consider w(A) Î E, so

Target set bigger than N? This is not a problem if we can make a finite choice of elements that allows a recursive process in the correspondence with the naturals. This is the case with Q but not with Ã(N).

Nevertheless there is a difference between Ã(E) and R, even if they have the same cardinality, because Ã(E) allows a choice, even though infinite, while R doesn’t even allow to select a first element.

w: Ã(N) ® N ¹ inj. º j: N ® Ã(N) ¹ surj.

Thus by recursivity, P(n) is true for any n Î N.

ÁÃ

Î ® Ì

Í (inclusion) is the membership in a large sense, i.e. real and potential

Axiom of choice well-ordering principle Zorn lemma are equivalent

Axiom of choice º well-ordering principle º Zorn lemma

well-ordering principle = total order on a set E with the property that every non empty subset of E has a least element in this ordering. The set E with the well-order is then called a

standard ordering of natural numbers, yes, but standard ordering of integers and positive real numbers, no!

well-ordered set.

A total order has the following properties:

- Reflexivity: E £ E

- Anti-symmetry: E £ F Ù F £ E Û E = F

- Transitivity: E £ F Ù F £ G Þ E £ G

- Totalness: E £ F or F £ E

Theorems implying the axiom of choice are non-constructive, i.e. mathematical proofs that purport to demonstrate the existence of something, but not how to construct it! Frequent use of contraposition.

Banach-Tarski paradox

By use of the axiom of choice, cut a solid ball in 3-dimensional space into a finite number of pieces, re-assemble the pieces to get two balls, both of equal size to the first and using only rotation and translation, moving the pieces and reassemble them into two balls of the same radius as the original.

Axiom of choice:

If set x is constituted of non empty subsets disjoined two to two, there exists at least one set y that contains exactly one element of each of the subsets of x.

"X $f fct.: X ® ÈX |"tÎ X/{0} f(t) Î t

f defined on X such that for each set S in X, f(t) is an element of t.

For any X without nul set, there exists a choice function f with arguments domain t, such that for any t belonging to X, f(t) belongs to t.

Good order: "x $ relation £ on x½ (x, £) G.O.

Zorn lemma:

Any inductive admits at least one maximal element.

Inductive: an order (X, £) is inductive iff X ¹ Æ Ù any chain is majored

A chain is a totally ordered part by £_Ù_c

Be (X, £) an inductive, we have to show that there is a maximal element.

Let’s take f a choice fct. over Ã_x\{Æ} (this parenthesis has not the same meaning as that of set)

x₀ = f(x)

either x₀is maximal and then, stop.

either x₀is not maximal, then strict Maj. {x₀} ¹ Æ

x_a: x_a maximal? OK, stop!

If not, then

strict Maj. {x_a} ¹ Æ Þ a + 1 = f(strict Maj. x_a)

A totally ordered chain x₀x₁x_a a < g limit ordinal

{x_b ½b < g limit}is an increased chain

to build

x_g = f(strict Maj. {x_b ½b < g})

a a x_a F fct. Defined by induction over O_n

2 possible cases:

a) stop: there exist a maximal

b) no stop: ® f injective fct. We never have two a sent on the same point. O_n ® X set Now a fct. can never send a class on a set: Ø$ F injective fct. proper class ® set

So the case b) is impossible.

Let’s show this:

We reverse the arrows. We build a F^-1. it will be functional since it is sufficient to say how it works.

F^-1(z) = a Û (z Î image F Ù F(a) = z) Ú (z Ï image F Ù a = 0)

So O_n is the image of F^-1: O_n = image F^-1(X).

So O_n must be a set by virtue of axiom of replacement.

But it is impossible since O_n is a class.

Conclusion: any chain is increased; any inductive admits at least one maximal element.

Demo: 3 ® 2

X = {(A, £)|½ A Ì x Ù £ is a good order on A}

X, £_X is an inductive, and we have X, £_X Iff A Ì B Ù £ is £’_A

“ ’ ” in (B, £’) because the order is not the same as in (A, £)

what is needed is to see “where” the chain goes, to build a raising element to the chain

(B, £’) ® Raising ,

(A_i, £_I)

OK? Then, Î X

It is to verify that Good Order are OK.

Binary relations are seen as set of couples.

By Zorn: $ (A*, £*) maximal in X, £_X .

We would need a maximal part different of whole X.

But then there is an external point x and we could build a really bigger Good Order!

If A* ¹ X, then (A* {x}, £* followed by x) is (A*, £*)!!

But A* is maximal, thus A* = X

Conclusion, A* = X and £* is a Good Order on X.

For any subset x of set y, there exists

Hyper sets or non-well-founded sets:

$x (x = {x})

proofs implying the axiom choice are non-constructive since they purport to demonstrate the existence of something without saying how to construct it.

either x₀is maximal and then, stop.

either x₀is not maximal, then strict Maj. {x₀} ¹ Æ

In mathematics, a function is a relation such that each element of a set is associated with a unique element of another (possibly the same) set. The concept of a function is fundamental to virtually every branch of mathematics and every quantitative science.

The terms function, mapping, map, transformation and operator are usually used synonymously.

Another formulation of the axiom of choice (AC) states:

Given any set of mutually exclusive non-empty sets, there exists at least one set that contains exactly one element in common with each of the non-empty sets.

It seems obvious: if you've got a bunch of boxes lying around with at least one item in each of them, the axiom simply states that you can choose one item out of each box. Where's the controversy?

Well, the controversy was over what it meant to choose something from these sets. As an example, let us look at some sample sets.

in which measure extensionality and choice are in relation?

1. Let X be any finite collection of non-empty sets. : Then f can be stated explicitly (out of set A choose a, ...), since the number of sets is finite. : Here the axiom of choice is not needed, you can simply use the rules of formal logic. 2. Let X be the collection of all non-empty subsets of the natural numbers {0, 1, 2, 3, ... }. : Then f can be the function that chooses the smallest element in each set. : Again the axiom of choice is not needed, since we have a rule for doing the choosing. 3. Let X be the collection of all sub-intervals of (0,1) with a length greater than 0. : Then f can be the function that chooses the midpoint of each interval. : Again the axiom of choice is not needed. 4. Let X be the collection of all non-empty subsets of the reals. : Now we have a problem. There is no obvious definition of f that will guarantee you success, because the other axioms of ZF

The axioms are the result of work by Thoralf Skolem in 1922, based on earlier work by Adolf Fraenkel in the same year, which was based on the axiom system put forth by Ernst Zermelo in 1908 (Zermelo set theory).

The following set must exist, it gathers parts of N:

{{0, 2}, {1, 3}, {4, 5}, {6, 7}, {8, 11}, {9, 13}, {10, 17}, {12, 19}, {14, 23}, {15, 29}, {16, 31}, {18, 37}, {20, 41},…}

it is countable since there is a bijection: N x N ® N

the choice axiom says that it functions but not “how” it functions.

(Zermelo set theory).

Cantor-Bernstein theorem

Let A and B be two sets. If there exists a one-to-one function f from A to B and another one-to-one function g from B to A, then card(A) = card(B).

"A "B (f: A ® B « g: B ® A) Þ #A = #B

"A "B (f: A ® B: inj. Ù g: B ® A: inj.) Þ #A = #B / h: A ® B: bij.

A total order always contains a co-final and well-ordered part, which means that any chain is raised/increased; so we have an inductive set E, £

The choice axiom allows to

Contraposition:

two main cases of use:

- - when the conclusion to demonstrate is divided in numerous cases and sub cases, which corresponds to several “OR” between several propositions; then, it is better to start from the negation of this conclusion that will then be written as a conjunction of several propositions, i.e. with “AND” rather than “OR”.

Example: to show that if the prime number p divides all the numbers

for k = 0 to n, either than p divides all the a_keither p divides all the b_i.

Demonstration:

p divides a₀ b₀; thus, p divides either a₀ either b₀ either both.

p divides a₀ b₁ + a₁ b₀; if p divides a₀ and b₀, this gives us no info; if p divides a₀ only, then, it divides a₁ too.

p divides a₀ b₂ + a₁ b₁ + a₂ b₀; since p divides a₀ and a₁ and not b₀, it divides a₂ too.

p divides a₀ b₃ + a₁ b₂ + a₂ b₁ + a₃ b₀; since p divides a₀, a₁ and a2 and not b₀, it divides a₃ too.

So we see it is possible to continue the demo by subdividing at each step according to the different cases, but it can become rather laborious.

So a contraposition demonstration seems to be judicious:

If p doesn’t divide all the a_k nor all the b_i, then there exist a k such that p doesn’t divide .

Demonstration:

If p doesn’t divide all the a_k, be r the first index such that p doesn’t divide a_r (thus p divide all the previous k); / p divides a to a_r-1

in the same way, be s the first index such that p doesn’t divide b_s; / p divides b₀ to b_s-1

then, p doesn’t divide a₀ b_r+s… + a_r b_s + … a_r+s b₀ since it divides all the terms but a_r b_s.QED

/ it is necessary that p divides at least all the a_k or all the b_i since there is a pair, a combination 2 by 2, of each a_k with b_i

- If a demonstration doesn’t end in the direct sense or seems to be more and more complicated, contraposition is often salutary too.

Example: to show that

("e > 0 | a | £ e) Þ a = 0

An attempt of direct demonstration could consist to show that:

| a | £ , | a | £ , … | a | £

but we don’t see how we can arrive to the conclusion a = 0; indeed, we cannot make a lead to 0 since the result we intend to demonstrate is precisely that that will all to justify such a passage to the limit!

Let’s take the contraposition:

a ¹ 0 Þ $e > 0 | a | > e

the demonstration is direct: if we have a ¹ 0, we take e = and we have indeed e > 0 and a > = e. QED

Ab absurdo Demonstration:

Principle: to demonstrate A Þ B

We demonstrate A Þ Ø C and (A Ù Ø B) Þ C

If B was false, and nevertheless A was true, we would deduce C;

now Ø C comes from A true; it is absurd since we cannot have C and Ø C at the same time; hence the two hypothesis A and Ø B are incompatible;

consequently, B comes obligatory from A, in other words, A implies B, A Þ B.

Let’s show that

Ï Q

A º x² = 2 Ù x > 0

B º x Ï Q

C º any rational is written where p and q are prime between them.

A Þ B├─┤ x² = 2 Ù x > 0 Þ x Ï Q

Let’s suppose that x Î Q;

then x = where p and q are two integers with no common prime factors;

thus x² = , which gives p² = 2q²; / indeed, x² = 2; so p = ; p = q; now, x = ; thus = Þ q = 1; in any case p (=) is not an integer!

so 2 is a prime factor of p² ; / indeed, 2 is a prime number

but the prime factor of p² are at an even power because it is a square, thus the power of 2 in p² is at least 2;

thus there is 2² in factor in 2q², thus there is 2 in factor in q²;

which causes that there is 2 in factor in q;

bbut then 2 is a common factor to p and q, which is not possible given the choice of p and q;

thus the demonstration is achieved by absurd.

This is a true demonstration by absurd.

A Þ (B Þ C) Schema:

Example:

A Ç B = B Þ B Ì A

Even if not obvious, it is a sentence of the type considered; indeed,

(A Ç B = B Þ B Ì A) º A Ç B = B Þ (x Î B) Þ (x Î A)

the demonstration must begin with the middle sentence, i.e. here by x Î B; the validity of this way of proceeding is justified by the rule that says that

A Þ (B Þ C) º B Þ (A Þ C)

First, let’s consider the transformation of A Þ B into B Ú Ø A

Ø (A Þ B) º A Ù Ø B / as we can see in the matrix below, the only case where the implication is false is when the antecedent is true and the conclusion false.

Ø (Ø (A Þ B)) º Ø (A Ù Ø B)

(A Þ B) º Ø A Ú Ø (Ø B)

A Þ B º Ø A Ú B

A Þ B º B Ú Ø A

p	q	p Ù q	- (p Ù q)	-p Ú -q	p ® q
0	1	0	1	1	1
0	0	0	1	1	1
1	1	1	0	0	1
1	0	0	1	1	0

If we come back to A Þ (B Þ C), we have

A Þ (B Þ C) º (B Þ C) Ú ØA

º (C Ú Ø B) Ú ØA

º C Ú Ø B Ú ØA

º C Ú Ø (B Ù A)

º (B Ù A) Þ C

º B Þ (A Þ C) / by commutativity of (B Ù A)

To demonstrate a sentence of the type A Þ (B Þ C), it is simpler to start from the middle proposition B and to use, in the process of the demonstration, the premise A in order to come to the conclusion C. Contrary to what we could think at first look, we don’t have to write A first!/ this would deserve a demonstration!

So here, we have x Î B;

We use the premise that says: A Ç B = B

So we have x ÎA Ç B

Thus, x Î A

So we have x Î B Þ x Î A

Another example:

P divides q Þ qZ Ì pZ (nZ being the set of the multiple of n in Z)

q Þ qZ Ì pZ º x Î qZ, Þ x Î pZ,

We start from the middle sentence:

Be x Î qZ, then by definition, this means that x is written qk;

Now, p divides q

Thus q = rp

Thus x = rpk

Consequently, x is a multiple of p.

/ q £ p because p contains all the possible divisors, thus the prime numbers too, while q doesn't. But q can contain 0 while p cannot!

About Í (inclusion in its extended meaning as opposed to the strict inclusion Ì): this relation is:

- reflexive: E Í E

- transitive: E Í F Ù F Í G Þ E Í G

- antisymmetrical: E Í F Ù F Í E Û E = F / double inclusion method

È and Ç are dual notions

È ® Ç

" ® $

set Í set

element Î set

Linear diagrams:

Æ Í A Ç B Í A Í A È B Ù Æ Í A Ç B Í B Í A È B

is the translation of the following Euler Diagram:

Symmetrical difference:

A ∆ B = (A È B) - (A Ç B)

A ∆ B	Í	A È B
XOR (exclusive OR)		OR (inclusive OR)

Properties of the symmetrical difference:

- associativity: A Δ (B Δ C) = (A Δ B) Δ C

- neutral element Æ: A Δ Æ = A / no common element to exclude

- any set is its own symmetric: A Δ A = Æ / all the elements are obviously common, thus to be excluded

- commutativity: A Δ B = B Δ A

With these four properties, the symmetrical difference is a law of commutative group over Ã_(E) or Ã_(E) fit with this law is a commutative group.

p Þ q

can be read:

- - p is a sufficient condition for q

- - q is a necessary condition for p

The sentence “this sentence is false” is true if it is false!

Short history

Frege Peano Russell Zermelo Fraenkel Zorn

Part of mathematics and of computer science (property)

Logic: classes, property ® Î (comprehension): if the element has the property, it belongs to “class”

math: Î ® sets if the element belongs to the “set”, it has the property extension iterative conception of set belongs to the naïve set theory cardinality: extension of the notion of equality

with Zermelo, a set is anything that makes true an axiom

ordinal type of a well-ordered set. Sets with the same ordinal type, in other words identical good orders, whose respectives members are linked by an univocal relation respecting the order, have the same ordinal type.

Null set extensionality (null set is unique) pairs (to build bigger and bigger sets) infinite foundation parts comprehension/separation scheme choice replacement scheme