Why Cantor Was Wrong
Mark Adkins
infinite sets (such as the set of real numbers) is fatally
flawed. Cantor's proof begins with what is taken to be a
complete list of real numbers. It then constructs "a real
number not on the list" by a diagonal method which is no doubt
familiar to those with a basic knowledge of this issue. Thus,
his proof claims to demonstrate that the initial assumption
(that the reals are countable) is false. In fact, the analytical
flaw in Cantor's proof is in thinking that such a procedure
would generate a real number at all. Since the list is
assumed complete, there is no real number not on the list,
and no such number can be generated. The flaw is in thinking
that a procedure which can be applied to any single element of
a complete list (to produce a single digit of the diagonal
number), or to any finite number of elements of a complete list
(to produce a finite number of digits of the diagonal number),
or to any infinite *subset* of a complete list (to produce an
infinite diagonal number, i.e. a real number -- albeit one
elsewhere on the list) can be applied to a complete list as a
whole. Obviously not, since this contradicts the axiomatic
assumption that it is complete! And any objective claim to
proof of the existence of uncountable sets must begin with an
assumption that lists of reals may be complete, otherwise one
is simply begging the question. The same procedure which can
be applied to an incomplete infinite list (such as a list of
the rationals) to produce a real number not on the list, cannot
be applied to a complete list of reals as a whole to produce
a real number (or anything else). In such an instance it
produces neither a real number on the list, nor a real number
not on the list, nor does it produce anything else.
I posted this some time ago in sci.math when, after many false
starts and contentious arguments over a period of months, I
finally hit upon the correct analysis. This conclusion did not
sit very well with the (ostensibly) professional mathematicians
in the sci.math newsgroup, but none offered a rebuttal, merely
unsupported claims hidden behind a smokescreen of formalisms.
Much was said that claimed, falsely, to rebut my argument, but
this isn't the same as actually rebutting it. Liars will claim
that I didn't understand their arguments, but the simple fact is
that their arguments were invalid. Those who claim that my argument
above is false either lack comprehension, are liars, or both.
--
Mark Adkins (adk...@cyberspace.org)
Mark Adkins
--
Mark Adkins (adk...@cyberspace.org)
Jeffery J. Leader
[regarding Why Cantor Was Wrong:]
>
>
Hmmm, I see that your answer involves the empty set...how very
fitting!
Jeffery J. Leader
>Since the list is
>assumed complete, there is no real number not on the list
Your argument (I missed it the last time around, I think) seems to be
that "If I assume it, then it's true." So, if I assume that 1+1=3,
then arrive at a contradiction (e.g. 0=1), the latter statement is
false because the former was *assumed* to be true, no? If:
>this contradicts the axiomatic
>assumption that it is complete!
...it is indeed an *axiom*, then its addition creates a new system.
It is not however a new axiom--it is a case of logical deduction. The
diagonalization proof is in essence a lawyer's argument: "You claim
that the reals can be ordered? Hah! I will show that your claim must
be false, as it leads to a contradiction!" It's mathematics by
Matlock. I always present it as a rebuttal of a challenge...as
opposed to the ordering of the rationals in an infinite matrix format,
which is a direct construction.
Speaking of which, constructivist mathematicians use a more limited
set of tools to prove things...you might find their thinking to your
liking.
>Liars will claim
>that I didn't understand their arguments
Others might too.
Brian M. Scott
>
> --
> Mark Adkins (adk...@cyberspace.org)
Most intelligent post Mark's ever made on this subject!
Brian M. Scott
Brian M. Scott
> Cantor's diagonal proof of the uncountability of certain
> infinite sets (such as the set of real numbers) is fatally
> flawed. Cantor's proof begins with what is taken to be a
> complete list of real numbers.
Wrong: the proof shows that for *any* function f from N to R,
not necessarily surjective, there is a real number not in the
range of f. From this it follows immediately from the
definitions that R is uncountable. You've been told this
often enough; that you still either don't understand it or
choose to ignore it is a testament to stupidity or dishonesty
of an impressively high order. Consider us duly impressed
(and by now more than a little bored).
[snip usual idiocies and insults]
Brian M. Scott
Main Night
>>
>> --
>> Mark Adkins (adk...@cyberspace.org)
>
>Most intelligent post Mark's ever made on this subject!
>
Most complimentary post anyone's ever made about Mark!
Peace out, Sam.
May Galois live forever.
Alan Mackenzie
> Cantor's diagonal proof of the uncountability of certain
> infinite sets (such as the set of real numbers) is fatally
> flawed.
..............
> The flaw is in thinking
> that a procedure which can be applied to any single element of
> a complete list (to produce a single digit of the diagonal
> number), or to any finite number of elements of a complete list
> (to produce a finite number of digits of the diagonal number),
> or to any infinite *subset* of a complete list (to produce an
> infinite diagonal number, i.e. a real number -- albeit one
> elsewhere on the list) can be applied to a complete list as a
> whole.
Is this not a good point? Doesn't the diagonal argument rely somewhere,
somehow, on the axiom of choice? (This isn't a rhetorical question, by
the way!)
> Mark Adkins (adk...@cyberspace.org)
-- Alan Mackenzie (Munich, Germany)
Email: ayes...@emmyousee.deeeee; to decode, replace "aye" by 'a', "see"
by 'c', etc.
ull...@math.okstate.edu
Alan Mackenzie<no...@all.de> wrote:
> Mark Adkins <adk...@cyberspace.org> wrote:
> > Cantor's diagonal proof of the uncountability of certain
> > infinite sets (such as the set of real numbers) is fatally
> > flawed.
>
> ..............
>
> > The flaw is in thinking
> > that a procedure which can be applied to any single element of
> > a complete list (to produce a single digit of the diagonal
> > number), or to any finite number of elements of a complete list
> > (to produce a finite number of digits of the diagonal number),
> > or to any infinite *subset* of a complete list (to produce an
> > infinite diagonal number, i.e. a real number -- albeit one
> > elsewhere on the list) can be applied to a complete list as a
> > whole.
> Is this not a good point? Doesn't the diagonal argument rely
somewhere,
> somehow, on the axiom of choice? (This isn't a rhetorical question, by
> the way!)
No, it does not rely on the axiom of choice. Supposing that
f is a function from N to R, the argument gives an explicit
construction of an x in R which is not equal to f(n) for any n.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
Edward van Kervel
Mark Adkins <adk...@cyberspace.org> schreef in artikel
<Pine.SUN.3.96.99071...@grex.cyberspace.org>...
>
>(....) Since the list is
> assumed complete, there is no real number not on the list,
> and no such number can be generated.
For a long time, I have been looking for a good example of "begging the
question".
But now I need search no longer. Thank you very much!
edward van kervel
maky m.
apologise.
--
-signature-
maky m. atheist #Ln(2)
number one theist basher on the internet
http://www.members.tripod.com/~mmanch01/
Virgil
>>Since the list is
>>assumed complete, there is no real number not on the list
Since Mark Adkins is assumed to be an ass (by most of the readers of his posts),
then, by his own argument, he must be an ass!
--
Virgil
vm...@frii.com
Dave L. Renfro
haven’t read all (or even very many) of the postings on this
issue, but see if the following helps.
First, I will give a variation on the Cantor argument (THEOREM
below), and then I’ll give some comments relating to your
criticism of the Cantor argument (NOTE 1 and NOTE 2 below).
NOTATION: R is the set of real numbers, N is the set of
positive integers, and "countable" means "finite or countably
infinite".
THEOREM: Given any countable set of real numbers, there
exists a real number not in this set.
PROOF: Let E be a countable subset of R. If E is finite, the result
is clear. (One can even find a power of 10 not in E.) If E is infinite
(i.e. countably infinite), then there exists a bijection f : N ---> R.
(This is the standard definition of countably infinite.) In
particular, E = {f(1), f(2), f(3), ...}. [See "FOOTNOTE" below.]
Now use a diagonalization procedure to obtain a real number x not
equal to any of f(1), f(2), f(3), ... . Then x belongs to R and
x does not belong to E, which completes the proof.
FOOTNOTE: I say "In particular, ..." because what follows
is actually a consequence of just the surjectivity of f (i.e. a
consequence of f being an onto function). That is, if all I knew was
that f : N ---> R is an onto function, then I could still conclude
that
E = {f(1), f(2), f(3), ...}. Of course, in such a situation it might
be
the case that f is not injective (i.e. not a one-to-one function), and
so it might be the case that some of the entries listed in
{f(1), f(2), f(3), ...} are equal to each other (e.g. f(3) = f(16),
f(7) = f(8) = f(76), etc.). However, in what remains of the
proof, I will only need "E = {f(1), f(2), f(3), ...}", not all of
what is implied by the statement "f : N ---> R is a bijection". Thus,
in the interest of clarity, I single out the specific statement
that I will be using by stripping away from the numerous hypotheses I
presently have at my disposal those which I will not be making use of.
NOTE 1: I’m not going to claim that we "constructed" x, since
the word "construct" has several precise meanings in math.
I will say this, however. If each of the elements of E have
Turing computable decimal expansions, and if the function
f : N ---> E is computable in the sense of there being a Turing
machine representation for f, then it is possible to be
sufficiently specific in the diagonalization procedure so that
the digits of x are given in a Turing computable manner.
[This will work: "For each positive integer n, let the n’th
decimal digit of x be 5 if the n’th decimal digit of f(n)
isn’t 5, and let the n’th decimal digit of x be 6 if the n’th
decimal digit of f(n) is 5."] However, it is known that there
are only countably many Turing computable procedures. Therefore,
since there are uncountably many real numbers, there will
be real numbers whose decimal expansions cannot be described
in a Turing computable manner. Moreover, there are uncountably
many countably infinite subsets of R, and so there are countably
infinite sets E whose elements cannot be listed in a Turing
computable manner. [Indeed, MOST real numbers and MOST countably
infinite subsets of R have these very strange non-Turing
computable properties.] What I'm trying to say is that Cantor's
argument doesn't introduce any non-constructability problems
not already present in trying to describe decimal expansions
of *arbitrary* real numbers or in trying to make a sequential
list the elements of an *arbitrary* countably infinite set
of real numbers.
NOTE 2: If you don’t allow the law of excluded middle, then I’m
not sure whether it is possible to take what has been proved above
and then conclude that R is uncountable. This appears to be your
main point of contention, I think. The way one normally proceeds
is to argue this way: {R is countable or R is uncountable. (True
by definition of "uncountable".) If R were countable, then we
could obtain a number x such that x is in R and x is not in R,
a contradiction. [Definition of contradiction: A statement of the
form "P and (not P)".] Thus, by default (so to speak), we are
forced to conclude that R is uncountable.} If this is indeed what
you wish to contest, then it’s not actually Cantor’s argument that
you object to, but rather a key aspect of the underlying meta-logical
framework that mathematics is presently conducted in. I don’t
know much about this, but I believe that those who wish to
operate under this constraint (of not using the law of excluded
middle, and maybe other things as well) practice what is
called "intuitionistic mathematics". Maybe the following will help.
Do you believe the proof below is valid? (Intuitionists wouldn’t.)
Theorem: There exist irrational numbers x and y such that
x^y is rational.
Proof: If [sqrt(2)]^sqrt(2) is rational, then x = sqrt(2) and
y = sqrt(2) verifies the theorem. If [sqrt(2)]^sqrt(2)
is irrational, then x = [sqrt(2)]^sqrt(2) and y = sqrt(2)
verifies the theorem. [Note that I haven’t given you specific numbers
x and y that you can point to and say "for this specific choice of x
and for this specific choice of y, I know that x^y is rational".]
Intuitionistic mathematics requires that one be extremely careful
in one’s arguments (I probably made several intuitionistic boo-boo’s
in "NOTE 1" above, for instance.), and I believe it is (presently)
practiced almost exclusively by logicians. Here is one way to
think about it. You can play checkers under the constraint of
being forced to take jumps when they are available, or you can
play checkers without this constraint. (I think "having to take
your jump" is the format presently used in tournaments.)
Intuitionistic mathematics is like playing checkers under this
constraint, while the mathematics most commonly practiced
by present day mathematicians is like playing checkers without
this constraint.
CONCLUSION: It seems to me that your criticism has to do
with the meta-logical foundations that mathematics is
practiced under. Cantor’s diagonalization proof is only an
issue to you to the extent that this logical matter is involved.
[There are many, many other (presently) accepted proofs
in mathematics where these same logical matters arise.] More
precisely, your philosophical leanings seem to be with
intuitionistic mathematics, which is not practiced by many
present day mathematicians. (However, this could certainly change
in the future.) Thus, your criticism of Cantor's argument
is not valid within the framework of mathematics as it is
presently being conducted, but it is a valid criticism of
how mathematics is presently being conducted. In the context
of my checkers analogy, here's what I mean. You claim that
someone makes an incorrect move. However, an examination
of your claim shows that the move was in fact correct under
the rules that person was playing by, and what your real
concern turned out to be was that this person was not playing
by the rules that you think are appropriate for checkers.
Dave L. Renfro
Cattabriga
>Cantor's diagonal proof of the uncountability of certain
>infinite sets (such as the set of real numbers) is fatally
>flawed. Cantor's proof begins with what is taken to be a
>complete list of real numbers. It then constructs "a real
>number not on the list" by a diagonal method which is no doubt
>familiar to those with a basic knowledge of this issue. Thus,
>his proof claims to demonstrate that the initial assumption
>(that the reals are countable) is false. In fact, the analytical
>flaw in Cantor's proof is in thinking that such a procedure
>would generate a real number at all. Since the list is
>assumed complete, there is no real number not on the list,
>and no such number can be generated. The flaw is in thinking
>that a procedure which can be applied to any single element of
>a complete list (to produce a single digit of the diagonal
>number), or to any finite number of elements of a complete list
>(to produce a finite number of digits of the diagonal number),
>or to any infinite *subset* of a complete list (to produce an
>infinite diagonal number, i.e. a real number -- albeit one
>elsewhere on the list) can be applied to a complete list as a
>whole. Obviously not, since this contradicts the axiomatic
>assumption that it is complete!
Good point! Till now none has never recognized that this
axiomatic assumption of completeness is incorrect. But not the
same does the theory itself! by means of its own axioms!
The explanation goes directly through Cantor's 'theorem'.
The axiomatic assumption of completeness of the list is
expressed by the axioms of ZF by means of the universal
quantifiers of the Subsets Axiom Schema
AzEyAx(x in y <-> x in z and P(x))
where the existential quantifier states the existence of
a set, i.e. GENERATES the fateful set.
Till now no objection about the fact that in Cantor theorem
the property P which define the incriminate set is in itself
a contradiction, a flaw (The axiom of comprehension was erased by
this reason and it was replaced by the above one which was
considered yielding no contradiction - what irony! the axioms
of the Subsets was constructed by Zermelo to prevent any
contradiction but finished to legitimate the use of the
property P as a contradiction of the kind (A <-> not A) within
Cantor's 'theorem' !).
But it's easy to show that the axioms of ZF itself firmly
objects to this assumption of completeness when the property
P is a contradiction.
By the same axiom of the Subsets the complementary set of the
incriminate Cantor's set
B = {x in A| x notin g(x)}
(which is only another notation for
Ax(x in B <-> x in A and x notin g(x)) )
can be defined
~B = {x in A| x in g(x)} (*
(which is only another notation for
Ax(x in ~B <-> x in A and not (x notin g(x)))
i.e. the relative complement of B in A).
Hence directly by the axiom of Extensionality
(AxAy[Az(z in x <-> z in y) -> x = y]) we get
(b in ~B <-> b in g(b)) -> ~B = g(b)
since A was 'already' defined (by Zermelo axiom ;-)
(b in ~B <-> b in g(b)) is only an example of the
above definition of ~B (*.
We can then derive by modus ponens
~B = g(b)
which is equivalent to
|-ZF not (B = g(b))
(where (B = g(b)) is diagonalization in Cantor's 'theorem').
In simple words, the axioms of ZF by themselves tell us that
to consider P = 'x notin g(x)' along Cantor's 'theorem' is
unacceptable, since in ZF the negation of the
diagonalization can be derived as a theorem of ZF.
More explanations can be found in
http://www.serdata.it/cattabriga/
I know you were talking of the Cantor's diagonal method over reals,
but Cantor's 'theorem' talk of the UNcountability of 'all' the
subsets of a given set and does it by diagonalization (i.e.
a self-referring procedure (i.e. an incontrovertible contradiction))
which is at the end the same thing of the diagonal method (...and
exactly the same of the Goedel formula in the 'theorem' of
UNcompleteness
for PA) and to understand/clarify precisely where the "axiomatic
assumption
of completeness" is wrong you must refer to the universal quantifiers
in front at the formula that usually mathematicians utilize for
defining sets!
I already posted all that in sci.math in the past.
Paola Cattabriga
______________________________________________________________
http://www.serdata.it/cattabriga/
______________________________________________________________
Brian M. Scott
[...]
> Hence directly by the axiom of Extensionality
> (AxAy[Az(z in x <-> z in y) -> x = y]) we get
>
> (b in ~B <-> b in g(b)) -> ~B = g(b)
Gross blunder: g(b) depends on b, so the application of Extensionality
is invalid. The rest is therefore nonsense.
[...]
Brian M. Scott
Virgil
(Cattabriga) wrote:
>Mark Adkins <adk...@cyberspace.org> wrote:
[SNIP]
What they wrote, at great lenght, only shows that there there are more
things in heaven and earth and mathematics than are dreamt of in their
philosophy.
--
Virgil
vm...@frii.com
Cattabriga
Brian M. Scott wrote:
:
An example of an axiom is ALWAYS valid. This holds for ANY theory,
and ZF is not exempt ! ZF can be considered as a logical theory.
For which other reasons the axioms have been defined for it?
Thus the application/example of an axiom does not depend on the belief
of the single person.
Paola Cattabriga.
Cattabriga
Brian M. Scott wrote:
:Cattabriga wrote:
:
:[...]
:
:> Hence directly by the axiom of Extensionality
:> (AxAy[Az(z in x <-> z in y) -> x = y]) we get
:>
:> (b in ~B <-> b in g(b)) -> ~B = g(b)
:
:Gross blunder: g(b) depends on b, so the application of
Extensionality
:is invalid. The rest is therefore nonsense.
:
:[...]
:
An example of an axiom is ALWAYS valid. This holds for ANY theory,
and ZF is not exempt ! ZF can be considered as a logical theory.
For which other reasons the axioms have been defined for it?
Let me add that g(b) depends on A, here (I.E. along Cantor's
'theorem'),
Ax(x in B <-> x in A and x notin g(x)) )
and ~B is the relative complement of B IN A.
Accordingly the ' :Gross blunder: ' is not mine here.
Paola Cattabriga.
______________________________________________________________
http://www.serdata.it/cattabriga/
______________________________________________________________
John Savard
>Cantor's proof begins with what is taken to be a
>complete list of real numbers. It then constructs "a real
>number not on the list" by a diagonal method which is no doubt
>familiar to those with a basic knowledge of this issue. Thus,
>his proof claims to demonstrate that the initial assumption
>(that the reals are countable) is false. In fact, the analytical
>flaw in Cantor's proof is in thinking that such a procedure
>would generate a real number at all. Since the list is
>assumed complete, there is no real number not on the list,
>and no such number can be generated.
No, you are mistaken.
When a _reductio ad absurdum_ proof begins, while we assume
temporarily "A is a list of all the real numbers", we also assume that
to be true *if it is possible for it to be true*, so we do not use
that assumption to conclude that any other fact about mathematics is
false.
Although we _assume_ "A is a list of all the real numbers", we don't
_really_ know if we can make such a list. So the assumption can't
prove anything.
Now, then, we take that list, and using what we know about
mathematics, we show that if we had such a list, we could generate an
infinite string of digits not on the list. *Since* we know that real
numbers correspond to infinite strings of digits, this means our
_assumption_ has led to a contradiction. Which is OK, since it was
only an assumption, NOT a fact.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
N.G. du Bois
I do agree with Paola, my boy's.
Though ofcourse I speak for myself and not for Paola.
I think Cantor handels Infinity with Finit tools.
I told you earlier that to my opinion the diagonalisation trick can also
be applied to the naturals.
You only have to wright them in a binairy system.
You do a bit the same when you apply diagonalisation to the power set of
the naturals.
Take a look at what Nico Benschop already told you about it.
Boy's you are way back into history. Paola and her successors will be
the new mathmeticians. Even for us its easy to understand. Why don't
you?
Why should diagonalisation only be applied on the interval (0,1)?
Cantorians always do it to explain diagonalisation.
That is because it easy and it seemingly leads to no contradictions.
Try diagonalisation on R and you will have a problem.
Why?
Because you use finit ideas on infinit matter.
Succes,
With friendly regards,
Nico du Bois.
Ken Cox
> I think Cantor handels Infinity with Finit tools.
> I told you earlier that to my opinion the diagonalisation trick can also
> be applied to the naturals.
> You only have to wright them in a binairy system.
Details, please. In particular, diagonalization as used with the
reals always produces a symbol-string with an infinite number of
digits, while every integer provably has only a finite number of
digits. How do you get around this problem? Are you sure you
haven't accidentally moved from the naturals to the adics, which
are indeed uncountable?
--
Ken Cox k...@research.bell-labs.com
Virgil
>Why should diagonalisation only be applied on the interval (0,1)?
>Cantorians always do it to explain diagonalisation.
>That is because it easy and it seemingly leads to no contradictions.
>Try diagonalisation on R and you will have a problem.
Not so.
The constructed real is usually in the interval [0,1), but the listing of
reals (equivalently, the function from naturals to reals) can use any (but
not all) reals.
Let f: N -> R be any function from the set {1,2,3,...} to the set R of all
standard reals.
Problem: To show that f is not onto R.
Construct a positive real number, r, in the following way:
The integer part of r is zero (so 0 <= r <1)
if the nth decimal digit of f(n) is 2,
then the nth decimal digit of r is 3,
otherwise the nth decimal digit of r is 2.
Clearly for every n in N,r differs from f(n) in decimal place n, so r <>
f(n), and thus f is not onto.
Since no assumption was made about f except for specifying its domain, N,
and codomain, R, this result applies to all such functions without
exception.
If you cannot accept the above, perhaps you should restrict your
mathematical endeavors to accounting.
--
Virgil
vm...@frii.com
Jeremy Boden
<catt...@mailbox.dsnet.it> writes
...
>Good point! Till now none has never recognized that this
>axiomatic assumption of completeness is incorrect. But not the
>same does the theory itself! by means of its own axioms!
>
>The explanation goes directly through Cantor's 'theorem'.
>
>The axiomatic assumption of completeness of the list is
>expressed by the axioms of ZF by means of the universal
>quantifiers of the Subsets Axiom Schema
>
> AzEyAx(x in y <-> x in z and P(x))
>
>where the existential quantifier states the existence of
>a set, i.e. GENERATES the fateful set.
>
--
Jeremy Boden
Martin Schlottmann
>
<snip, g is an arbitrary function from A to Power(A)>
>
> B = {x in A| x notin g(x)}
>
>
> |-ZF not (B = g(b))
>
Well, that's cool. For any function g: A->Power(A),
we find a subset B of A which is not in the range
of g. IIRC, this proves Cantor's theorem.
--
Martin Schlottmann
Martin Schlottmann
>
> In article <wppw3h...@forum.swarthmore.edu>, Cattabriga
> <catt...@mailbox.dsnet.it> writes
> ...
> >
> > AzEyAx(x in y <-> x in z and P(x))
> >
> >where the existential quantifier states the existence of
> >a set, i.e. GENERATES the fateful set.
> >
> There is no such axiom schema.
>
But you agree that this is a theorem of ZF,
as long as y is not free in P(x)?
--
Martin Schlottmann
Cattabriga
In Message-ID: <3793BA4D...@math.ualberta.ca>
Message-ID: <3793B6CF...@math.ualberta.ca>
Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
<snip>
>But you agree that this is a theorem of ZF,
>as long as y is not free in P(x)?
Do you agree that
Ax(x in ~B <-> x in A and not (x notin g(x)))
is a theorem of ZF ?
><snip, g is an arbitrary function from A to Power(A)>
>>
>> B = {x in A| x notin g(x)}
>>
><snip some manipulations I don't completely agree with>
>>
>> |-ZF not (B = g(b))
>>
>Well, that's cool. For any function g: A->Power(A),
>we find a subset B of A which is not in the range
>of g. IIRC, this proves Cantor's theorem.
Axioms are true BEFORE of whatever theorem.
If by the axioms |-ZF not (B = g(b)), then
not (B = g(b)) holds in ZF BEFORE of any assumption
that B = g(b).
Your "FIND"->"PROVES" above is meaningless in ZF simply by
Ax(x in B <-> x in A and (x notin g(x))
and
EyAx(x in y <-> x in A and x notin B)
Of course asserting a statement which conflicts with the axioms
yields a contradiction.
This is exactly the so-called "Cantor's theorem" which states
B= g(b)
when already by the axioms we have
|-ZF not (B = g(b)).
Paola Cattabriga.
nico_b...@my-deja.com
> > I told you earlier that to my opinion the diagonalisation trick
> > can also be applied to the naturals.
> > You only have to wright them in a binairy system.
>
> In particular, diagonalization as used with the
> reals always produces a symbol-string with an infinite number of
> digits, while every integer provably has only a finite number of
> digits. How do you get around this problem? Are you sure you
> haven't accidentally moved from the naturals to the adics, which
> are indeed uncountable? -- Ken Cox k...@research.bell-labs.com
>
Re[*]: have a look at http://www.iae.nl/users/benschop/cantor.htm
(to which N.duBois referred earlier).
In Cantor's Diagonal (CD): 'diagonal' implies literally a square
w x w table (say over binary codes) where w = |N| = 'omega':
the countable & "1-dimensional" infinity of Peano, viewing the
set of naturals N = 0{+1}* as sequential closure under addition,
starting with initial 0, and generator +1.
Then the integers Z(+) = 0{+1,-1}* which is a group of order 2w = w.
All permutations of Z form a group Z! = {+1,-1,swap2}* where "swap2"
is any permutation of 2 integers, fixing the rest of Z (say: 0 <--> 1)
The CD process starts with a square w x w table, and produces _one_
binary string, coding one real on [0,1) which is not in the table
(as countable infinite binary row, say). OK: so far so good, he made
his point (there are more than countable elements in powerset 2^N).
Next: permute the rows of this doubly countable square table,
and consider ALL generated diagonals & their complements (bitwise
complemented) --> that produces not just _one_, but eventually w!
(omega factorial) "new" reals on [0,1) = binary strings of length w.
Now the clue, back to 2^N, or rather 2^Z: to each permutation (of Z)
corresponds a subset of Z, namely for instance its fixed-points.
And ALL subsets of Z, so 2^Z, occur as fix-point set of permutations
of Z. Nota bene: infinite group Z! has only three sequential
generators, for inst: increment(+1), decrement(-1), swap2(0<-->1).
Interesting, no? The uncountable (UC) infinity of 2^Z can be
sequentially generated by only 3 generators.
(just as the infinite semigroup T(Z) of all transformations of Z
is generated by only 4 generators: T(Z) = {+1,-1,swap2,merge2}*
Re "ISM" : Integer State Machines (and their sequential closure;-)
Comments appreciated ( please check ref[*] first ;-)
Ciao, Nico Benschop - http://www.iae.nl/users/benschop
PS: -------- If stuck@closure (mod...), use the carry --------------
-- A generative view of the "real" line: including groups & lattices.
Ken Cox
It's wrong. The main reason is that you treat the generation of the
list as a process, that is, as if an incomplete list were something
that you could "fix up" by adding other elements. E.g., your line:
> -- Now add all missing strings to the list, which thus expands to
> all 2^(2^k) strings of 2^k bits each. So the missing strings by
> Cantor's argument changed now into "regularly generated" strings
> for the case k' = 2^k.
But it doesn't matter how often you rearrange the list or change the
elements on it -- the diagonalization argument still applies to the
modified list, so we know that there is at least one element not on
the list. Cantor's proof is basically "For *any* list you hand me,
I can find a real number that is not on the list. Therefore no list
has all the real numbers."
--
Ken Cox k...@research.bell-labs.com
Martin Schlottmann
>
> In Message-ID: <3793BA4D...@math.ualberta.ca>
> Message-ID: <3793B6CF...@math.ualberta.ca>
> Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
>
> <snip>
>
>
> >But you agree that this is a theorem of ZF,
> >as long as y is not free in P(x)?
(That was meant as a reply to Jeremy Boden.
Sometimes, the subset "axiom" is not included
among the axioms of ZF, because it is derivable
from a suitable form of replacement. Nevertheless,
the subset axiom is always a theorem of ZF which
is all what matters here.)
>
> Do you agree that
>
> Ax(x in ~B <-> x in A and not (x notin g(x)))
>
> is a theorem of ZF ?
Yes, with the definitions B := { x in A | x not in g(x) },
~B := { x in A | x not in B}.
>
> ><snip, g is an arbitrary function from A to Power(A)>
> >>
> >> B = {x in A| x notin g(x)}
> >>
> ><snip some manipulations I don't completely agree with>
> >>
> >> |-ZF not (B = g(b))
> >>
>
> >Well, that's cool. For any function g: A->Power(A),
> >we find a subset B of A which is not in the range
> >of g. IIRC, this proves Cantor's theorem.
>
>
> Axioms are true BEFORE of whatever theorem.
> If by the axioms |-ZF not (B = g(b)), then
> not (B = g(b)) holds in ZF BEFORE of any assumption
> that B = g(b).
We don't need the assumption B=g(b) to prove
not(B=g(b)) in ZF. Proving not(B=g(b)) in ZF
means proving in ZF that B is not in the range
of g, hence g is not onto. As g was a completely
arbitrary function from A to Power(A), we have
proven in ZF that no such function is surjective.
QED.
>
> Your "FIND"->"PROVES" above is meaningless in ZF simply by
>
> Ax(x in B <-> x in A and (x notin g(x))
> and
> EyAx(x in y <-> x in A and x notin B)
I don't see how this renders my assertions
meaningless.
>
> Of course asserting a statement which conflicts with the axioms
> yields a contradiction.
Lemme give you a primer in proof by contradiction.
Given a set S of axioms, assume we can derive
S,A |- Not(A) for some assertion A. By the usual
theorems on predicate calculus, it follows that
S |- Not(A).
Of course, this doesn't have any relevance to
the proof of Cantor's theorem in ZF which
can be accomplished without any assumption
of its contrary.
>
> This is exactly the so-called "Cantor's theorem" which states
> B= g(b)
That's not the assertion of Cantor's theorem.
> when already by the axioms we have
> |-ZF not (B = g(b)).
>
This is Cantor's theorem (given the appropriate
definition of B). So you agree that Cantor's
theorem is a theorem of ZF?
--
Martin Schlottmann
nico_b...@my-deja.com
I do more with Cantor's diagonal then only producing an extra real:
it is rather a new structured / generative view of 2^N as lattice,
(in fact integer powerset as lattice 2^Z) occurring in a group Z!
with only 3 sequential generators (UnCountable = "seq_dimension" > 1)
Of course there is no end to the described process of generating
new diagonals by permuting the initial (arbitrarily chosen) w x w
table of binary coded reals on [0,1). You missed my point, I think,
namely that it is highly artificial to "compress" the structured
closure 2^N - which is a Boolean Lattice with w = |N| generators
under union, cq intersection - onto a "1-dimensinal" real line segment.
This is asking for interpretative problems... (finite and infinite,
countable vs. uncountable). I just try to qualify 'Uncountable' as
related to "beyond Peano" that is: more than 1-dimensional ( > 1
seq_generator).
These lattice-ordered reals, with top element 1* (all ones string)
and bottom element 0* (all zero string), can be sequentially generated
by only 3 elements: permutations in group Z! (rather 2^Z as described
in my */cantor.htm homepg file. Which opens up a new view to this
"Uncountable" set of reals, namely approached "from above" via group Z!
(of order w!) and the fix-point subset of permutations of integer set
(group) Z.
So I propose to look at Cantors powerset not just as a set, but as
a structured lattice, which can be 'embedded' into a 3-generator
infinite group, as shown by simple (re)coding examples ('isomorphism'):
{0,1}* in 2^Z <--> {a,b,c}* in Z! (a=+1, b=-1, c=swap2)
with ab=ba=+0 and c as comma function in a runlength code: a* b* c
in answer to one of Dave Seaman's questions.
--- Don't you find that interesting at all ?-)
Ciao, Nico Benschop - http://www.iae.nl/users/benschop/cantor.htm
nico_b...@my-deja.com
Cantor's diagonal procedure necessarily *cannot* start with a complete
list, because the word "diagonal" means there is a square table,
for instance of binary coded reals on interval [0,1), which have
countable length w. Hence for a *diagonal* to be considered: there
*must* be countably many such reals in any such (nec. square) table.
So we *know* beforehand that whatever table you take, assuming you
are going to apply Cantors diagonal procedure, it is NOT complete -
just as any finite but square table of k-bit binary strings
necessarily has k numbers in it: no more, no less; while we know
there are 2^k > k (for any k>0) such numbers.
However, Cantors diagonal argument *can* be usefully employed as
generator for the remaining 2^k - k strings (of length k). Namely
by permuting the rows (=binary coded numbers) in the list, yielding
the "missing" numbers and 'completing' the 2^k set. The same works
for k --> w=|N|. The assumption of a complete starting list is
vacuous, and proves only that one more real can be found that is not
in the (incomplete) list -- so what? That list CANNOT have been
complete anyway, for the 'diagonal' (=square table) reason!
Ken Cox
> So we *know* beforehand that whatever table you take, assuming you
> are going to apply Cantors diagonal procedure, it is NOT complete -
> just as any finite but square table of k-bit binary strings
> necessarily has k numbers in it: no more, no less; while we know
> there are 2^k > k (for any k>0) such numbers.
No, not really. You are assuming the very properties of infinite
numbers that the Cantor proof needs to show -- that is, that there
are more reals than there are integers. Until you've actually
proved that, you could say that there *are* a countable number of
reals, and thus they *could* be put into a "square" table. Some
people on this newsgroup actually *do* try to make this argument,
but it's just as invalid either way.
--
Ken Cox k...@research.bell-labs.com
Jeremy Boden
<martin_sc...@math.ualberta.ca> writes
>Jeremy Boden wrote:
>>
>> In article <wppw3h...@forum.swarthmore.edu>, Cattabriga
>> <catt...@mailbox.dsnet.it> writes
>> ...
><snip>
>> >
>> > AzEyAx(x in y <-> x in z and P(x))
>> >
>> >where the existential quantifier states the existence of
>> >a set, i.e. GENERATES the fateful set.
>> >
>> There is no such axiom schema.
>>
>
>as long as y is not free in P(x)?
>
--
Jeremy Boden
John Savard
>Hence for a *diagonal* to be considered: there
>*must* be countably many such reals in any such (nec. square) table.
Yes, we *now* know that a complete list of reals cannot be a list with
a countable number of elements. Why? _Because_ Cantor proved it -
using the diagonal proof!
If that _wasn't_ true, we could make such a list - but wait a minute -
we can make the diagonal, and get new numbers that can't be on the
list! That's a contradiction, so I guess the reals aren't countable,
after all.
Cattabriga
Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
>> Do you agree that
>>
>> Ax(x in ~B <-> x in A and not (x notin g(x)))
>>
>> is a theorem of ZF ?
>
>Yes, with the definitions B := { x in A | x not in g(x) },
>~B := { x in A | x not in B}.
Wrong.
B := { x in A | x not in g(x) },
~B := { x in A | x not in B}.
is the relative complement, lined up with the doctrine,
while
you will never find
Ax(x in ~B <-> x in A and not (x notin g(x)))
in any doctrine.
<snip>
>We don't need the assumption B=g(b) to prove
>not(B=g(b)) in ZF. Proving not(B=g(b)) in ZF
>means proving in ZF that B is not in the range
>of g, hence g is not onto. As g was a completely
>arbitrary function from A to Power(A), we have
>proven in ZF that no such function is surjective.
<snip>
>> Your "FIND"->"PROVES" above is meaningless in ZF simply by
>>
>> Ax(x in B <-> x in A and (x notin g(x))
>> and
>> EyAx(x in y <-> x in A and x notin B)
>I don't see how this renders my assertions
>meaningless.
(As usual you skip the basic role of definitions, you prefer
to think they are insignificant)
g cant be surjective if within A is defined only B:
A
____________________
| | |
| | |
| | |
| | B |
| | |
| | |
| | |
____________________
but g can be surjective if within A is defined also C(B)
(for C(X)= the complement of X) :
A
____________________
| | |
| | |
| | |
| C(B) | B |
| | |
| | |
| | |
____________________
since
[C(B) U B] = A then g:[C(B) U B] |--> P[C(B) U B]
For the function g:[C(B) U B] -> P([C(B) U B]),
* letting C(B) = ... , there IS a b such that C(B)=g(b)
Hence, NOT(for any) function g: A->P(A) ,
* g is not surjective.
Axioms are true BEFORE of whatever theorem.
When I say that there exists no b in A with B=g(b),
I mean that it does not exist BY DEFINITION, i.e. directly
by the axioms, hence this assumption (or statement B=g(b))
immediately conflicts with the axioms of ZF.
Of course asserting a statement which conflicts with the axioms
yields a contradiction.
What I show is exactly that the assumption conflicts with the axioms,
and if we accept to STATE in ZF such assumption then ZF is
inconsistent.
Why we assume something we *already perfectly* know it is
inconsistent?
Martin Schlottmann
>
> In Message-ID: <3794B7BE...@math.ualberta.ca>
> Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
>
> >> Do you agree that
> >>
> >> Ax(x in ~B <-> x in A and not (x notin g(x)))
> >>
> >> is a theorem of ZF ?
> >
> >Yes, with the definitions B := { x in A | x not in g(x) },
> >~B := { x in A | x not in B}.
>
> Wrong.
>
> B := { x in A | x not in g(x) },
> ~B := { x in A | x not in B}.
>
> is the relative complement, lined up with the doctrine,
>
> while
>
> you will never find
> Ax(x in ~B <-> x in A and not (x notin g(x)))
> in any doctrine.
We were talking about theorems of ZF. I have
no idea what a doctrine is. Seriously, I do
not understand what you mean here.
But, B is not in the range of g (agree?).
Therefore, because B is an element of P(A),
g is not a surjective function A -> P(A).
It doesn't matter if the relative complement
of B is in the range of g; as long as B
is not in the range, g is not surjective.
> Hence, NOT(for any) function g: A->P(A) ,
> * g is not surjective.
Because g was a completely arbitrary
function A -> P(A), we have to conclude
that no function A -> P(A) is surjective.
>
>
>
> Axioms are true BEFORE of whatever theorem.
Well, no. Axioms are no different than
theorems. It is just a matter of con-
venience to select a couple of theorems
of a theory, call them axioms, and deduce
all the other theorems of the theory by
logical inference. Axioms are to theories
what basis vectors are to a vector space.
And, Axioms needn't be true :-)
> When I say that there exists no b in A with B=g(b),
> I mean that it does not exist BY DEFINITION, i.e. directly
> by the axioms, hence this assumption (or statement B=g(b))
> immediately conflicts with the axioms of ZF.
We don't make this assumption. Or, at
least we don't have to make it in order
to prove Cantor's theorem.
>
> Of course asserting a statement which conflicts with the axioms
> yields a contradiction.
When the assertion of a statement leads to
a contradiction, then the negation of that
statement is proven. That is how a proof
by contradiction works.
But forget about proof by contradiction:
Cantor's theorem can be proven directly
from the axioms _without_ leading something
to a contradiction.
>
> What I show is exactly that the assumption conflicts with the axioms,
> and if we accept to STATE in ZF such assumption then ZF is
> inconsistent.
>
> Why we assume something we *already perfectly* know it is
> inconsistent?
>
--
Martin Schlottmann
N.G. du Bois
I'm on a holliday,
So I cannot continue to follow the discussion.
But still Paola has my support.
Fuzzy (logic)regards ;-)
Nico du Bois.
jean-phi
<Pine.SUN.3.96.99071...@grex.cyberspace.org>,
Mark Adkins <adk...@cyberspace.org> wrote:
> Cantor's diagonal proof of the uncountability of certain
> infinite sets (such as the set of real numbers) is fatally
> flawed. Cantor's proof begins with what is taken to be a
> complete list of real numbers.
I thought a necessary condition to do mathematics was knowing how to
read.
The Cantor's diagonal proof I've ever seen begins with a list
{X_0,X_1,…} of real numbers. Any list ! Not necessarily a COMPLETE list
of real numbers.
The proof shows then the existence of a number Y not in this list.
It is of course sufficient to say that R is uncountable.
So the following :
> It then constructs "a real
> number not on the list" by a diagonal method which is no doubt
> familiar to those with a basic knowledge of this issue. Thus,
> his proof claims to demonstrate that the initial assumption
> (that the reals are countable) is false. In fact, the analytical
> flaw in Cantor's proof is in thinking that such a procedure
> would generate a real number at all. Since the list is
> assumed complete, there is no real number not on the list,…
has not object.
--
jean-\phi (alias jeanfi61)
Cattabriga
In Message-ID: <3793BA4D...@math.ualberta.ca>
Message-ID: <3793B6CF...@math.ualberta.ca>
Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
<snip>
>as long as y is not free in P(x)?
______________________
*) AzEyAx(x in y <-> x in z and P(x))
In Message-ID: <3794B7BE...@math.ualberta.ca>
Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
>Lemme give you a primer in proof by contradiction.
>Given a set S of axioms, assume we can derive
>S,A |- Not(A) for some assertion A. By the usual
>theorems on predicate calculus, it follows that
>S |- Not(A).
I prefer the following:
if a proof of S,Not(A)|- C and not(C) involves no
________
application of Generalization using a variable free in A,
then S |- A. (Similarly, one obtains S |- Not(A) from
S,A|- C and not(C)).
Do you see the trick now if from *) we have both
B = {x in A| x notin g(x)} and ~B = {x in A| x in g(x)} ?
You know by the doctrine
AzEyAx(x in y <-> x in z and P(x))
then
Ax(x in B <-> x in A and x notin g(x))
and
AzAsEyAx(x in y <-> x in s and x notin z)
Ax(x in ~B <-> x in A and x notin B)
can be both derived from *).
Let me add that
Ax(x in ~B <-> x in A and not (x notin g(x)))
is a valid example of *) from the logical point of view
(as long as y is not free in P(x)).
* * *
--------------------------------------------------------
Assumptions toward a contradiction lead in some cases
to contradiction.
The following is the so-called Cantor's 'theorem'
1) g:A |-> P(A) ==>
2) B = {x in A| x notin g(x)} ==>
3) B=g(b) ==>
4) [(b in B) and (b notin B) and (b notin B) and (b in B)].
maybe you do not accept 3) after or before '|-', only for make you
happy,
we can consider it like
g:A |-> P(A), B = {x in A| x notin g(x)} |- [(b in B) and (b notin B)
and (b notin B) and (b in B)]
BUT how many times it involves no application of Generalization using
a variable free in [the assumption that g:A |-> P(A) is onto] or in
B = {x in A| x notin g(x)} and (as long as y is not free in P(x))
(i.e. B is not free in (x notin g(x))) ?
For many times along this 'proof' do you state 'for every element x
such that ... x in { [the assumption that g:A |-> P(A) is onto] or
in B = {x in A| x notin g(x)} }' and ((as long as y is not free in
P(x))(i.e. B is not free in (x notin g(x))) ?
Do you remind that not(Ey)Ax(x in y <-> x notin x) is a first order
theorem ?
Martin Schlottmann
>
> In Message-ID: <3793BA4D...@math.ualberta.ca>
> Message-ID: <3793B6CF...@math.ualberta.ca>
> Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
>
> <snip>
>
>
> >as long as y is not free in P(x)?
>
> ______________________
>
>
>
> *) AzEyAx(x in y <-> x in z and P(x))
>
>
>
> In Message-ID: <3794B7BE...@math.ualberta.ca>
> Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
>
> >Lemme give you a primer in proof by contradiction.
> >Given a set S of axioms, assume we can derive
> >S,A |- Not(A) for some assertion A. By the usual
> >theorems on predicate calculus, it follows that
> >S |- Not(A).
>
> I prefer the following:
>
> if a proof of S,Not(A)|- C and not(C) involves no
> ________
> application of Generalization using a variable free in A,
> then S |- A. (Similarly, one obtains S |- Not(A) from
> S,A|- C and not(C)).
This is true for propositional calculus
reasons alone, so there is no need for
a restriction on free variables.
>
> Do you see the trick now if from *) we have both
>
> B = {x in A| x notin g(x)} and ~B = {x in A| x in g(x)} ?
No, these are not of the form C and not(C).
>
> You know by the doctrine
> AzEyAx(x in y <-> x in z and P(x))
> then
> Ax(x in B <-> x in A and x notin g(x))
> and
> AzAsEyAx(x in y <-> x in s and x notin z)
> Ax(x in ~B <-> x in A and x notin B)
>
> can be both derived from *).
Yes.
>
> Let me add that
>
> Ax(x in ~B <-> x in A and not (x notin g(x)))
>
> is a valid example of *) from the logical point of view
> (as long as y is not free in P(x)).
Yes.
>
> * * *
>
> --------------------------------------------------------
>
> Assumptions toward a contradiction lead in some cases
> to contradiction.
>
> The following is the so-called Cantor's 'theorem'
>
> 1) g:A |-> P(A) ==>
> 2) B = {x in A| x notin g(x)} ==>
> 3) B=g(b) ==>
> 4) [(b in B) and (b notin B) and (b notin B) and (b in B)].
>
> maybe you do not accept 3) after or before '|-', only for make you
> happy,
> we can consider it like
>
> g:A |-> P(A), B = {x in A| x notin g(x)} |- [(b in B) and (b notin B)
> and (b notin B) and (b in B)]
>
> BUT how many times it involves no application of Generalization using
> a variable free in [the assumption that g:A |-> P(A) is onto] or in
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> B = {x in A| x notin g(x)} and (as long as y is not free in P(x))
> (i.e. B is not free in (x notin g(x))) ?
You don't need that assumptions for the proof.
If you don't like the proof by contradiction,
you can as well take an arbitrary element x
of A and show direktly that not(B=g(x)).
>
> For many times along this 'proof' do you state 'for every element x
> such that ... x in { [the assumption that g:A |-> P(A) is onto] or
> in B = {x in A| x notin g(x)} }' and ((as long as y is not free in
> P(x))(i.e. B is not free in (x notin g(x))) ?
What's that got to do with anything?
>
> Do you remind that not(Ey)Ax(x in y <-> x notin x) is a first order
> theorem ?
A theorem of ZF, yes.
--
Martin Schlottmann
cattabriga
In Message-ID: <37964061...@math.ualberta.ca>
Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
<snip>
: > >> Your "FIND"->"PROVES" above is meaningless in ZF simply by
: > >>
: > >> Ax(x in B <-> x in A and (x notin g(x))
: > >> and
: > >> EyAx(x in y <-> x in A and x notin B)
: >
: > >I don't see how this renders my assertions
: > >meaningless.
: >
: > (As usual you skip the basic role of definitions, you prefer
: > to think they are insignificant)
: >
: > g cant be surjective if within A is defined only B:
: >
: > A
: > ____________________
: > | | |
: > | | |
: > | | |
: > | | B |
: > | | |
: > | | |
: > | | |
: > ____________________
: >
: >
: > but g can be surjective if within A is defined also C(B)
: > (for C(X)= the complement of X) :
: >
: > A
:> ____________________
:> | | |
:> | | |
:> | | |
:> | C(B) | B |
:> | | |
:> | | |
:> | | |
:> ____________________
:>
:>
:> since
:> [C(B) U B] = A then g:[C(B) U B] |--> P[C(B) U B]
:>
:>
:>
:> For the function g:[C(B) U B] -> P([C(B) U B]),
:> * letting C(B) = ... , there IS a b such that C(B)=g(b)
:
:But, B is not in the range of g (agree?).
g:A |-> P(A) is defined such that
Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
B is defined as a subset of A.
You need to assert the conclusion of the
so-called Cantor's 'theorem'
to still be able to believe it.
:Therefore, because B is an element of P(A),
:g is not a surjective function A -> P(A).
:It doesn't matter if the relative complement
:of B is in the range of g; as long as B
:is not in the range, g is not surjective.
:
:
: > Hence, NOT(for any) function g: A->P(A) ,
: > * g is not surjective.
:
:Because g was a completely arbitrary
:function A -> P(A), we have to conclude
:that no function A -> P(A) is surjective.
Whenever in ZF a function like
g:A |-> P(A)
is assumed or defined, by
Ax(x in B <-> x in A and (x notin g(x))
and
EyAx(x in y <-> x in A and x notin B)
A=[C(B) U B], and
g:[C(B) U B] -> P([C(B) U B])
holds. Here the statement "B is not in the range of g"
is meaningless. "Cantor's theorem" is meaningless in ZF.
Martin Schlottmann
>
> In Message-ID: <37964061...@math.ualberta.ca>
> Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
>
<snip>
> :
>
> g:A |-> P(A) is defined such that
> Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
No, g is defined to be an _arbitrary_
function from A to P(A).
>
> B is defined as a subset of A.
>
> You need to assert the conclusion of the
> so-called Cantor's 'theorem'
> to still be able to believe it.
No. You take an _arbitrary_ function g from
A to P(A), define B:={x in A| x not in g(x)}
and show _directly_ that there is no x in A
such that B=g(x), and, hence, that the
_arbitrary_ function g is not surjective.
_Then_ you believe Cantor's theorem. :-)
>
> :Therefore, because B is an element of P(A),
> :g is not a surjective function A -> P(A).
> :It doesn't matter if the relative complement
> :of B is in the range of g; as long as B
> :is not in the range, g is not surjective.
> :
> :
> : > Hence, NOT(for any) function g: A->P(A) ,
> : > * g is not surjective.
> :
> :Because g was a completely arbitrary
> :function A -> P(A), we have to conclude
> :that no function A -> P(A) is surjective.
>
> Whenever in ZF a function like
> g:A |-> P(A)
>
> is assumed or defined, by
> Ax(x in B <-> x in A and (x notin g(x))
> and
> EyAx(x in y <-> x in A and x notin B)
>
> A=[C(B) U B], and
>
> g:[C(B) U B] -> P([C(B) U B])
>
> holds. Here the statement "B is not in the range of g"
> is meaningless.
No, "B is not in the range of g" means
that "there is no element x in A such
that B=g(x)."
> "Cantor's theorem" is meaningless in ZF.
>
Cantor's theorem in ZF means "There is no
surjective function from a set to its power
set. Not ever." Right or wrong, it is most
certainly _not_ meaningless
--
Martin Schlottmann
Pertti Lounesto
> Cantor's theorem in ZF means "There is no
> surjective function from a set to its power
> set. Not ever."
What do you mean by "Not ever"? Are there theorems,
whose truth-value is a function of time? I have falsified
some theorems, whose truth-value jumped from 1 to 0
by my counterexample which satisfied all the assumptions
of the theorem without the conclusion being valid. See
http://www.math.hut.fi/~lounesto/counterexamples.htm.
Cattabriga
In Message-ID: <3798AC6C...@math.ualberta.ca>
Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
>No, g is defined to be an _arbitrary_
>function from A to P(A).
I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
>No. You take an _arbitrary_ function g from
>A to P(A), define B:={x in A| x not in g(x)}
>and show _directly_ that there is no x in A
>such that B=g(x), and, hence, that the
>_arbitrary_ function g is not surjective.
You take an _arbitrary_ function g from
A to P(A), define B:={x in A| x not in g(x)}
~B = {x in A| x in g(x)}
and show _directly_ that there is a x in A
such that ~B=g(x), and, hence, that the
_arbitrary_ function g is surjective.
_Then_ you don't believe Cantor's theorem. ;-)
>No, "B is not in the range of g" means
>that "there is no element x in A such
>that B=g(x)."
You __need to show__ or derive (directly or not)
that "B is not in the range of g".
You can't affirm it immediately or _directly_ after
the definition
Ax(x in B <-> x in A and (x notin g(x)).
The reason is in your own words:
>as long as y is not free in P(x).
as long as B is not free in (x notin g(x)).
Why are your words expected to hold for all
the others but you?
>Cantor's theorem in ZF means "There is no
>surjective function from a set to its power
>set. Not ever." Right or wrong, it is most
>certainly _not_ meaningless
I affirm simply that the so-called Cantor's 'theorem'
does not hold in ZF.
I don't state that Cantor's 'theorem' is wrong in itself
(I don't think this can really be shown, it will be like
to show that "a contradiction is a contradiction").
Instead the way by which ZF defines it sets turns
out to be wrong. I mean Zermelo's Subsets Axiom is inadequate for
the 'show' of the so-called Cantor's 'theorem'.
Whenever in ZF an arbitrary function like
g:A |-> P(A)
is assumed or defined, by
Ax(x in B <-> x in A and (x notin g(x))
and
EyAx(x in y <-> x in A and x notin B)
g:[C(B) U B] -> P([C(B) U B])
holds *before* to 'show' (directly or not) that
"B is not in the range of g". On the contrary
(i.e. if you deny the *before*) you are misapplying
the axiom of subsets and its
rule '>as long as y is not free in P(x)'.
Brian M. Scott
> Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
> >No, g is defined to be an _arbitrary_
> >function from A to P(A).
> I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
No, the range of g is *not* assumed to be P(A); it is assumed to be a
*subset* of P(A).
Brian M. Scott
Martin Schlottmann
>
> Martin Schlottmann wrote:
>
> > Cantor's theorem in ZF means "There is no
> > surjective function from a set to its power
> > set. Not ever."
>
Whatever the set you look at.
Or do you have a counterexample?
--
Martin Schlottmann
Martin Schlottmann
>
> In Message-ID: <3798AC6C...@math.ualberta.ca>
> Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
>
> >No, g is defined to be an _arbitrary_
> >function from A to P(A).
>
> I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
What do you mean by R(g)? g: A-> P(A) means
that g is defined on members of A and has as
values members of P(A). We don't have to
assume from the beginning that all elements
of P(A) are values of g, we can leave this
question open till the end of the proof.
>
> >No. You take an _arbitrary_ function g from
> >A to P(A), define B:={x in A| x not in g(x)}
> >and show _directly_ that there is no x in A
> >such that B=g(x), and, hence, that the
> >_arbitrary_ function g is not surjective.
>
>
> You take an _arbitrary_ function g from
> A to P(A), define B:={x in A| x not in g(x)}
> ~B = {x in A| x in g(x)}
> and show _directly_ that there is a x in A
> such that ~B=g(x), and, hence, that the
> _arbitrary_ function g is surjective.
How does (Ex)~B=g(x) show that g is surjective?
For g to be surjective, B must be the value of g
at some x in A.
>
> _Then_ you don't believe Cantor's theorem. ;-)
No :-)
>
> >No, "B is not in the range of g" means
> >that "there is no element x in A such
> >that B=g(x)."
>
> You __need to show__ or derive (directly or not)
> that "B is not in the range of g".
Yes, I can show that:
Let x be an arbitrary member of A.
Then x in B or x in ~B and not both.
If x in B, then x not in g(x) by definition of B,
hence not(B=g(x)) by extensionality.
If x in ~B, then x in g(x) by definition of ~B,
hence not(B=g(x)) by extensionality.
In both cases not(B=g(x)), therefore,
(Ax)(x in A -> not(B=g(x)).
See? I have derived "B is not in the range of g"
without any assumption on g apart that it is a
function defined on A.
>
> You can't affirm it immediately or _directly_ after
> the definition
>
> Ax(x in B <-> x in A and (x notin g(x)).
I don't affirm it, I show it. See above.
>
> The reason is in your own words:
>
> >as long as y is not free in P(x).
>
> as long as B is not free in (x notin g(x)).
>
>
> Why are your words expected to hold for all
> the others but you?
What?
<snip>
--
Martin Schlottmann
Cattabriga
In Message-ID: <379A2B...@stratos.net>
"Brian M. Scott" <BMS...@stratos.net> wrote:
> I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
>
>No, the range of g is *not* assumed to be P(A); it is
>assumed to be a
>*subset* of P(A).
In Message-ID: <379A5191...@math.ualberta.ca>
Martin Schlottmann <martin_sc...@math.ualberta.ca>wrote:
> >
> >
> > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
>
>What do you mean by R(g)? g: A-> P(A) means
>that g is defined on members of A and has as
>values members of P(A). We don't have to
>assume from the beginning that all elements
>of P(A) are values of g, we can leave this
>question open till the end of the proof.
<snip>
All this is unconcerning and meaningless since
whenever in ZF a function like
g:A |-> P(A)
is considered to be a one-to-one correspondence,
by
Ax(x in B <-> x in A and (x notin g(x))
and
EyAx(x in y <-> x in A and x notin B)
we get
g:[C(B) U B] -> P([C(B) U B])
for pure logical reasons.
Paola Cattabriga.
______________________________________________________________
http://www.serdata.it/cattabriga/
______________________________________________________________
The world is closed under complementation ;-)
Brian M. Scott
> "Brian M. Scott" <BMS...@stratos.net> wrote:
> > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >No, the range of g is *not* assumed to be P(A); it is
> >assumed to be a
> >*subset* of P(A).
> In Message-ID: <379A5191...@math.ualberta.ca>
> Martin Schlottmann <martin_sc...@math.ualberta.ca>wrote:
> > > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >What do you mean by R(g)? g: A-> P(A) means
> >that g is defined on members of A and has as
> >values members of P(A). We don't have to
> >assume from the beginning that all elements
> >of P(A) are values of g, we can leave this
> >question open till the end of the proof.
> All this is unconcerning and meaningless since
> whenever in ZF a function like
> g:A |-> P(A)
> is considered to be a one-to-one correspondence,
The proof of Cantor's theorem contains no such assumption. The function
g is not assumed to be one-to-one (injective), and it is not assumed to
map onto P(A). The rest of your objection is therefore irrelevant.
Brian M. Scott
Martin Schlottmann
>
> In Message-ID: <379A2B...@stratos.net>
> "Brian M. Scott" <BMS...@stratos.net> wrote:
>
> > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >
> >No, the range of g is *not* assumed to be P(A); it is
> >assumed to be a
> >*subset* of P(A).
>
> In Message-ID: <379A5191...@math.ualberta.ca>
> Martin Schlottmann <martin_sc...@math.ualberta.ca>wrote:
> > >
> > >
> > > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >
> >What do you mean by R(g)? g: A-> P(A) means
> >that g is defined on members of A and has as
> >values members of P(A). We don't have to
> >assume from the beginning that all elements
> >of P(A) are values of g, we can leave this
> >question open till the end of the proof.
>
>
> All this is unconcerning and meaningless since
> whenever in ZF a function like
> g:A |-> P(A)
>
> is considered to be a one-to-one correspondence,
Again, we don't consider this.
We consider. An arbitrary function g. Defined
on an arbitrary set A.
We don't. Assume. Anything else. About. The function g.
And then we _show_ that there is a member B of P(A)
which is not the value of g at any point in A. Which
in turn means that g is not surjective.
> by
> Ax(x in B <-> x in A and (x notin g(x))
> and
> EyAx(x in y <-> x in A and x notin B)
>
> we get
>
> g:[C(B) U B] -> P([C(B) U B])
>
> for pure logical reasons.
>
You keep saying this.
And what does "g:[C(B) U B] -> P([C(B) U B])"
have to do _at all_ with the question if
g is surjective or not?
--
Martin Schlottmann
Cattabriga
This message was posted on 23 Jul 99 to forum.swarthmore.edu
Subject: Why Cantor Was Wrong
Author: cattabriga <catt...@mailbox.dsnet.it>
Date: 23 Jul 99 03:43:12 -0400 (EDT)
In Message-ID: <37964061...@math.ualberta.ca>
Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
<snip>
: > >> Your "FIND"->"PROVES" above is meaningless in ZF simply by
: > >>
: > >> Ax(x in B <-> x in A and (x notin g(x))
: > >> and
: > >> EyAx(x in y <-> x in A and x notin B)
: >
: > >I don't see how this renders my assertions
: > >meaningless.
: >
: > (As usual you skip the basic role of definitions, you prefer
: > to think they are insignificant)
: >
: > g cant be surjective if within A is defined only B:
: >
: > A
: > ____________________
: > | | |
: > | | |
: > | | |
: > | | B |
: > | | |
: > | | |
: > | | |
: > ____________________
: >
: >
: > but g can be surjective if within A is defined also C(B)
: > (for C(X)= the complement of X) :
: >
: > A
:> ____________________
:> | | |
:> | | |
:> | | |
:> | C(B) | B |
:> | | |
:> | | |
:> | | |
:> ____________________
:>
:>
:> since
:> [C(B) U B] = A then g:[C(B) U B] |--> P[C(B) U B]
:>
:>
:>
:> For the function g:[C(B) U B] -> P([C(B) U B]),
:> * letting C(B) = ... , there IS a b such that C(B)=g(b)
:
:But, B is not in the range of g (agree?).
g:A |-> P(A) is defined such that
Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
B is defined as a subset of A.
You need to assert the conclusion of the
so-called Cantor's 'theorem'
to still be able to believe it.
:Therefore, because B is an element of P(A),
:g is not a surjective function A -> P(A).
:It doesn't matter if the relative complement
:of B is in the range of g; as long as B
:is not in the range, g is not surjective.
:
:
: > Hence, NOT(for any) function g: A->P(A) ,
: > * g is not surjective.
:
:Because g was a completely arbitrary
:function A -> P(A), we have to conclude
:that no function A -> P(A) is surjective.
Whenever in ZF a function like
g:A |-> P(A)
is assumed or defined, by
Ax(x in B <-> x in A and (x notin g(x))
and
EyAx(x in y <-> x in A and x notin B)
A=[C(B) U B], and
g:[C(B) U B] -> P([C(B) U B])
holds. Here the statement "B is not in the range of g"
is meaningless. "Cantor's theorem" is meaningless in ZF.
Paola Cattabriga
______________________________________________________________
http://www.serdata.it/cattabriga/
______________________________________________________________
--------------------------------------------------------------
Gus Gassmann
>
> You take an _arbitrary_ function g from
> A to P(A), define B:={x in A| x not in g(x)}
> ~B = {x in A| x in g(x)}
> and show _directly_ that there is a x in A
> such that ~B=g(x), and, hence, that the
> _arbitrary_ function g is surjective.
>
I came late to this thread and I feel more than a little dense
morning, so I tried to construct a little example:
For every x in A, g(x) = A \ {x}. This should satisfy your
requirement of an 'arbitrary' function. Now for every x in A
x notin g(x), so B = A and ~B = {}. Every set g(x) is
missing one point, so for no x is g(x) = B, and unless
A is a singleton, g(x) is not empty for all x, so for no
x is g(x) = ~B, either. In other words, this particular
'arbitrary' function g is _not_ surjective.
My faith in Cantor's theorem is thus unshaken, at least for now.
-------------------------------------------------------
gus gassmann (Horand....@dal.ca)
Cattabriga
In Message-ID: <379B57...@stratos.net>
References: <3794B7BE...@math.ualberta.ca>
> > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >No, the range of g is *not* assumed to be P(A); it is
> >assumed to be a
> >*subset* of P(A).
> In Message-ID: <379A5191...@math.ualberta.ca>
> Martin Schlottmann <martin_sc...@math.ualberta.ca>wrote:
> > > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >What do you mean by R(g)? g: A-> P(A) means
> >that g is defined on members of A and has as
> >values members of P(A). We don't have to
> >assume from the beginning that all elements
> >of P(A) are values of g, we can leave this
> >question open till the end of the proof.
> All this is unconcerning and meaningless since
> whenever in ZF a function like
> g:A |-> P(A)
> is considered to be a one-to-one correspondence,
The proof of Cantor's theorem contains no such assumption. The function
g is not assumed to be one-to-one (injective), and it is not assumed to
map onto P(A). The rest of your objection is therefore irrelevant.
Brian M. Scott
In
Message-ID: <379B98EC...@math.ualberta.ca>
References: <3794B7BE...@math.ualberta.ca>
Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
>
> In Message-ID: <379A2B...@stratos.net>
> "Brian M. Scott" <BMS...@stratos.net> wrote:
>
> > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >
> >No, the range of g is *not* assumed to be P(A); it is
> >assumed to be a
> >*subset* of P(A).
>
> In Message-ID: <379A5191...@math.ualberta.ca>
> Martin Schlottmann <martin_sc...@math.ualberta.ca>wrote:
> > >
> > >
> > > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >
> >What do you mean by R(g)? g: A-> P(A) means
> >that g is defined on members of A and has as
> >values members of P(A). We don't have to
> >assume from the beginning that all elements
> >of P(A) are values of g, we can leave this
> >question open till the end of the proof.
>
> <snip>
>
> All this is unconcerning and meaningless since
> whenever in ZF a function like
> g:A |-> P(A)
>
> is considered to be a one-to-one correspondence,
>Again, we don't consider this.
>
>We consider. An arbitrary function g. Defined
>on an arbitrary set A.
>
>We don't. Assume. Anything else. About. The function g.
<snip>
--
Martin Schlottmann
It is clear now we were not referring to the same version of
the so-called Cantor's 'theorem'. All this is especially unfair
from Martin since he knew very well the 'version' I was
talking about, till from the beginning. I am sorry, as regard to
Brian M. Scott, for the misunderstanding.
Well, nothing come on this earth only to hurt. There are many
different versions of the so-called Cantor's 'theorem', but for sake
of brevity I will reproduce here only the two we were
talking/misunderstanding about, which are both extract from well-known
handbooks (references can be found in my hpg).
VERSION I --------------------------------------------------------
(Notation)
x <_{c} y and x =<_{c} y denote respectively that the set x has
cardinality properly less that the cardinality of y, and that the
set x has cardinality less than y.
x ~sim y denotes that the sets x and y are not equal in cardinality,
namely there exixts no one to one correspondence between
their elements.
x sim y denotes that the sets x and y are equal in cardinality,
namely there exixts a one to one correspondence between
their elements.
(Cantor's proposition)
For every set A in ZF,
A <_{c} P(A)
i.e. A =<_{c} (A) but A ~sim P(A).
(so-called Cantor's 'proof')
That A =<_{c} P(A) follows from the fact that the function
x |-> {x}
which associates with each member x of A its singleton
{x} is an injection. To complete the proof, we assume, toward
a contradiction, that there exists a one to one correspondence
g:A |-> P(A)
which establishes that A sim P(A) and we define the set
B = { x in A | x notin g(x)}.
Now B is a subset of A and g is a surjection, so there
must exist some b in A such that B = g(b) (diagonalization),
and (as for each x in A ) either b in B or b notin B.
(*) If b in B then b in g(b) since B = g(b),
so that b does not satisfy the condition which
defines B , and hence b notin B ,
contrary to hypothesis.
(**) If b notin B , then b notin g(b) , so that b now
satisfies the defining condition for B and hence
b in B, which again contradicts the hypothesis.
Thus we reach a contradiction from the assumption that the
bijection g exists.
------------------------------------------------------------------
This is the version I was referring with
<<...
1) g:A |-> P(A) ==>
2) B = {x in A| x notin g(x)} ==>
3) B=g(b) ==>
4) [(b in B) and (b notin B) and (b notin B) and (b in B)].
maybe you do not accept 3) after or before '|-', only for make you happy,
we can consider it like
g:A |-> P(A), B = {x in A| x notin g(x)} |- [(b in B) and (b notin B)
and (b notin B) and (b in B)]
...>>
in a previous posting, answering to Schlottmann when he was talking
of a proof by contradiction.
You both are instead talking of a 'proof' which we could
call 'constructive' of the following type:
VERSION II -------------------------------------------------------
(Notation)
x neq y denotes y is not equal to y.
x subseteq y denotes x is a subset of y.
(x subset y denotes x is a proper subset of y.)
(so-called Cantor's 'proof')
Let g:a |-> P(a). We will construct a subset b of a
that is not in ran g. Specifically let
i) b = { x in a | x notin g(x)}.
Then b subseteq a, but for each x in a
ii) x in b <-> x notin g(x).
Hence b neq g(x).
------------------------------------------------------------------
I wish to state very clearly I will tolerate no longer any mistaken
of B=g(b) (and |-ZF not (B = g(b)) of my previous postings), as referring
to VERSION I, with [b neq g(x)] within VERSION II.
The reasons are simple VERSION II*[b neq g(x)] is a conclusion of a
deduction, while VERSION I* B=g(b) is a statement after or before '|-'
along a proof toward a contradiction ( an assumption if before, i.e.
"so there must exist some b in A such that B = g(b)"
in VERSION I, a consequence if after).
Of course in no case VERSION I* B=g(b) can be considered a conclusion.
(See Schlottmann's Message-ID: <379A5191...@math.ualberta.ca>
Sat, 24 Jul 1999 17:51:46 -0600)
Moreover the notation about set and function are different for the two
versions, thus no type of melting of the two versions will be no more
accepted.
All my previous postings were referring to VERSION I.
Let me resume what I tell about VERSION I:
about VERSION I ----------------------------------------------------
Let us connect again to the step of the definition of B within
VERSION I .
The relative complement can always be defined, C(B) = A - B
as the relative complement of B in A , i. e.
C(B) = { x in A | x notin B}.
One can easily see that
C(B) = { x in A | x in g(x)\}.
Then in ZF we have
g:A |-> P(A)
B = {x in A | x notin g(x)}
C(B) = {x in A | x in g(x)}
Thus B and C(B) are subsets of A , B U C(B) = A .
By its definition g is a surjection ( g:(B U C(B)) |-> P(B U C(B)) )
and for each b in A we have either b in B or b in C(B) ,
so there must exist some b in A such that either B=g(b) or C(B)=g(b) .
Clearly, b in B or b in C(B) but not both, and B=g(b) or
C(B)=g(b) but not both. We then have the main consequence of taking
into consideration the definition of the relative
complement with respect to Cantor's argumentation in ZF.
Immediately by Exstensionality we get
(b in C(B) <-> b in g(b)) -> C(B) = g(b)
and hence by C(B) = {x in A | x in g(x)}
C(B) = g(b).
Moreover since b in B or b in C(B) but not both, and B=g(b) or
C(B)=g(b) but not both we have
not (B = g(b)).
In other terms, by the axiom schema of Subsets and the axiom of
Extensionality diagonalization is not true in ZF. The assertion
<there must exist some b\in A such that B =g(b)> is false by
Extensionality. Accordingly (*) and (**) cannot be accomplished
in VERSION I and Cantor's 'theorem' does not hold in ZF.
In fact we have only two cases
1. b in B and C(B) = g(b), then b notin g(b) so that
b satisfies the condition which defines B, and hence b in B,
accordingly to the hypothesis;
2. b in C(B) and C(B) = g(b), then b in g(b)
so that b satisfies condition which defines C(B), and hence b in C(B),
accordingly to the hypothesis.
-------------------------------------------------------------
But you prefer now to utilize VERSION II.
Well we can do all that.
about VERSION II----------------------------------------------
In VERSION II*[b neq g(x)] is a conclusion and the 'proof'
in VERSION II has the form
g:a |-> P(a) ==>
b = { x in a | x notin g(x)} ==>
x in b <-> x notin g(x) ==> [b neq g(x)]
i.e.
g:a |-> P(a),
b = { x in a | x notin g(x)},
x in b <-> x notin g(x)|- [b neq g(x)]
(OF COURSE THIS IS NOT A PROOF FOR CONTRADICTION)
The treatment is already in the words of Martin:
>Yes, I can show that:
>Let x be an arbitrary member of A.
>Then x in B or x in ~B and not both.
>If x in B, then x not in g(x) by definition of B,
> hence not(B=g(x)) by extensionality.
>If x in ~B, then x in g(x) by definition of ~B,
> hence not(B=g(x)) by extensionality.
>In both cases not(B=g(x)), therefore,
>(Ax)(x in A -> not(B=g(x)).
>
>See? I have derived "B is not in the range of g"
>without any assumption on g apart that it is a
>function defined on A.
except that being not a 'proof' for contradiction (no restriction
on the use of generalization as regard to proof for contradiction),
we don't need extensionality here (which regards, in all my postings,
only VERSION I).
Let me formalize the proof as follows (where eq denotes equal):
g:a |-> P(a),
Aa(a in b <-> a notin g(a)),
(a in b <-> a notin g(a)),
((a in b <-> a notin g(a)) <-> (a notin b <-> not(a notin g(a)))),
((a in b <-> a notin g(a)) -> (a notin b <-> not(a notin g(a)))),
(a notin b <-> not(a notin g(a))),
Aa(a notin b <-> not(a notin g(a))),
Aa(a notin b <-> a in g(a)),
EyAx(x in y <-> x in a and x notin b),
y=c, (y not free in (x in a and x notin b),
EyAa(a in y <-> a notin b),
(a in c <-> a notin b),
(a in c <-> a in g(a)),
Ax(x in c <-> x in g(x)),
c eq g(x).
i.e.
g:a |-> P(a),
b = { x in a | x notin g(x)},
(x in c <-> x in g(x))|- [c eq g(x)].
The existence of c cannot be denied since
EyAx(x in y <-> x in a and x notin b) is an example of
Aussonderung, hence we have
constructed a subset c of a that is in ran g.
*********************************
>You keep saying this.
>And what does "g:[C(B) U B] -> P([C(B) U B])"
>have to do _at all_ with the question if
>g is surjective or not?
Well, as regard to VERSION I I already showed you all that
Version I----------------------------------------------------
g cant be surjective if within A is defined only B:
A
____________________
| | |
| | |
| | |
| | B |
| | |
| | |
| | |
____________________
but g can be surjective if within A is defined also C(B)
(for C(X)= the complement of X)
C(B) = { x in A | x in g(x)}:
A
____________________
| | |
| | |
| | |
| C(B) | B |
| | |
| | |
| | |
____________________
since
[C(B) U B] = A then g:[C(B) U B] |--> P[C(B) U B]
For the function g:[C(B) U B] -> P([C(B) U B]),
* letting C(B) = ... , there IS a b such that C(B)=g(b)
Hence, NOT(for any) function g: A->P(A) ,
* g is not surjective.
--------------------------------------------------------------
as regard to VERSION II maybe better you don't ask to me, you
could find it posted to sci.math next year ;-) .
On my personal point of view as regard to VERSION II
g:[C(B) U B] -> P([C(B) U B])
can lead to the proof that g can be surjective or that g can be
one-to-one working on the composition of functions and their
inverse. All young rebels are invited to think about.
(As regard to me, I am going to take my rest ;-)
Dave Seaman
Cattabriga <catt...@mailbox.dsnet.it> wrote:
>:But, B is not in the range of g (agree?).
>
>g:A |-> P(A) is defined such that
>
>
>so-called Cantor's 'theorem'
>to still be able to believe it.
If S and T are any two arbitrary sets, there are exactly four
possiblilities concerning the comparison of their cardinalities:
Case 1.
-------
There is an injection f: S -> T and also an injection
g: T -> S. In this case, we can apply the
Cantor-Bernstein theorem and conclude that there is a
bijection h: S <--> T, which proves that |S| = |T| (the
cardinalities are equal).
Case 2.
-------
There is an injection f: S -> T, but there is no
injection from T into S. In this case we say that
|S| < |T|.
Case 3.
-------
There is an injection g: T -> S, but there is no
injection from S into T. In this case we say that
|T| < |S|.
Case 4.
-------
There is no injection from S into T, and there also is
no injection from T into S. This case cannot arise if
we assume that the axiom of choice holds. In this case
the cardinalities |S| and |T| cannot be compared.
Questions:
----------
(1) Do you agree that these four cases exhaust all the
possibilities in comparing two sets S and T?
(2) Which case applies when we compare a set A with its power set
P(A)?
>:Therefore, because B is an element of P(A),
>:g is not a surjective function A -> P(A).
>:It doesn't matter if the relative complement
>:of B is in the range of g; as long as B
>:is not in the range, g is not surjective.
>:
>:
>: > Hence, NOT(for any) function g: A->P(A) ,
>: > * g is not surjective.
>:
>:Because g was a completely arbitrary
>:function A -> P(A), we have to conclude
>:that no function A -> P(A) is surjective.
Notice that if there is an injection g': T -> S and if T is nonempty,
then there is necessarily a surjection g: S -> T. The converse of that
statement is false, unless we assume the axiom of choice.
Therefore, the argument here is that Case 2 applies: There is an
injection f: A -> P(A), but there is no injection g': P(A) -> A. If such
an injection g' existed, then there would be a surjection g: A -> P(A)
(using the fact that P(A) is nonempty for every A), but the Cantor
diagonal argument shows that no such surjection exists. This is why it
makes sense to say that |A| < |P(A)| for every A.
Question: Do you agree that Case 2 applies? If not, why not? In
particular, you need to justify your claim by producing a set A such that
either
(1) there is no injection f: A -> P(A), or
(2) there is an injection g: P(A) -> A.
Your example, please?
>Whenever in ZF a function like
> g:A |-> P(A)
>
>is assumed or defined, by
>Ax(x in B <-> x in A and (x notin g(x))
>and
>EyAx(x in y <-> x in A and x notin B)
>
>A=[C(B) U B], and
>
> g:[C(B) U B] -> P([C(B) U B])
>
>holds. Here the statement "B is not in the range of g"
>is meaningless. "Cantor's theorem" is meaningless in ZF.
There is nothing particularly wrong with writing A = C(B) U B, aside from
the fact that when you substitute that notation into g: A -> P(A) it
gives the somewhat misleading impression that B was defined first and
then g was somehow defined in terms of B, when in fact it is just the
other way around.
You keep writing this as if you were absolutely convinced that it had
some significance. Do you think people are denying that A = C(B) U B? Do
you think that the appearance of B on the right-hand side somehow shows
that B is in the range of g? Are you claiming that B = g(x) for some
particular x in A? Please explain yourself.
--
Dave Seaman dse...@purdue.edu
Pennsylvania Supreme Court Denies Fair Trial for Mumia Abu-Jamal
<http://mojo.calyx.net/~refuse/altindex.html>
Cattabriga
In Message-ID: <379B57...@stratos.net>
References: <3794B7BE...@math.ualberta.ca>
Brian M. Scott <BMS...@stratos.net> wrote:
> > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >No, the range of g is *not* assumed to be P(A); it is
> >assumed to be a
> >*subset* of P(A).
> In Message-ID: <379A5191...@math.ualberta.ca>
> Martin Schlottmann <martin_sc...@math.ualberta.ca>wrote:
> > > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >What do you mean by R(g)? g: A-> P(A) means
> >that g is defined on members of A and has as
> >values members of P(A). We don't have to
> >assume from the beginning that all elements
> >of P(A) are values of g, we can leave this
> >question open till the end of the proof.
> All this is unconcerning and meaningless since
> whenever in ZF a function like
> g:A |-> P(A)
> is considered to be a one-to-one correspondence,
The proof of Cantor's theorem contains no such assumption. The
function
g is not assumed to be one-to-one (injective), and it is not assumed
to
map onto P(A). The rest of your objection is therefore irrelevant.
Brian M. Scott
In
Message-ID: <379B98EC...@math.ualberta.ca>
References: <3794B7BE...@math.ualberta.ca>
Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
>
> In Message-ID: <379A2B...@stratos.net>
> "Brian M. Scott" <BMS...@stratos.net> wrote:
>
> > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >
> >No, the range of g is *not* assumed to be P(A); it is
> >assumed to be a
> >*subset* of P(A).
>
> In Message-ID: <379A5191...@math.ualberta.ca>
> Martin Schlottmann <martin_sc...@math.ualberta.ca>wrote:
> > >
> > >
> > > I.e. Eg[Fnc(g) and D(g) = A and R(g) = P(A)]
> >
> >What do you mean by R(g)? g: A-> P(A) means
> >that g is defined on members of A and has as
> >values members of P(A). We don't have to
> >assume from the beginning that all elements
> >of P(A) are values of g, we can leave this
> >question open till the end of the proof.
>
> <snip>
>
> All this is unconcerning and meaningless since
> whenever in ZF a function like
> g:A |-> P(A)
>
<snip>
--
Martin Schlottmann
VERSION II -------------------------------------------------------
-------------------------------------------------------------
i.e.
i.e.
Version I----------------------------------------------------
A
____________________
| | |
| | |
| | |
| | B |
| | |
| | |
| | |
____________________
Hence, NOT(for any) function g: A->P(A) ,
* g is not surjective.
--------------------------------------------------------------
as regard to VERSION II maybe better you don't ask to me, you
could find it posted to sci.math next year ;-) .
On my personal point of view as regard to VERSION II
g:[C(B) U B] -> P([C(B) U B])
can lead to the proof that g can be surjective or that g can be
Dave Seaman
Cattabriga <catt...@mailbox.dsnet.it> wrote:
>It is clear now we were not referring to the same version of
>the so-called Cantor's 'theorem'. All this is especially unfair
>from Martin since he knew very well the 'version' I was
>talking about, till from the beginning. I am sorry, as regard to
>Brian M. Scott, for the misunderstanding.
>Well, nothing come on this earth only to hurt. There are many
>different versions of the so-called Cantor's 'theorem', but for sake
>of brevity I will reproduce here only the two we were
>talking/misunderstanding about, which are both extract from well-known
>handbooks (references can be found in my hpg).
What you are talking about here is not two different theorems, but one
theorem with two different proofs, one direct and one indirect. You have
demonstrated that you do not understand the concept of an indirect proof,
and this is why everyone is trying to steer you to the direct proof
instead.
No matter which proof you use, the conclusion is the same: |X| < |P(X)|
for each X, meaning there is an injection from X into P(X), but there is
no bijection between the two.
>VERSION I --------------------------------------------------------
[Statement and indirect proof snipped.]
>VERSION II -------------------------------------------------------
[Statement and direct proof snipped.]
>I wish to state very clearly I will tolerate no longer any mistaken
>of B=g(b) (and |-ZF not (B = g(b)) of my previous postings), as referring
>to VERSION I, with [b neq g(x)] within VERSION II.
Ok, let's do it your way.
>The reasons are simple VERSION II*[b neq g(x)] is a conclusion of a
>deduction, while VERSION I* B=g(b) is a statement after or before '|-'
>along a proof toward a contradiction ( an assumption if before, i.e.
>"so there must exist some b in A such that B = g(b)"
>in VERSION I, a consequence if after).
>
>Of course in no case VERSION I* B=g(b) can be considered a conclusion.
You are correct that there is a difference between a conclusion in a
direct proof, and a provisional conclusion within the context of an
indirect proof.
>about VERSION I ----------------------------------------------------
>Let us connect again to the step of the definition of B within
>VERSION I .
>The relative complement can always be defined, C(B) = A - B
>as the relative complement of B in A , i. e.
> C(B) = { x in A | x notin B}.
>One can easily see that
> C(B) = { x in A | x in g(x)\}.
>Then in ZF we have
>g:A |-> P(A)
>B = {x in A | x notin g(x)}
>C(B) = {x in A | x in g(x)}
>Thus B and C(B) are subsets of A , B U C(B) = A .
>By its definition g is a surjection ( g:(B U C(B)) |-> P(B U C(B)) )
>and for each b in A we have either b in B or b in C(B) ,
>so there must exist some b in A such that either B=g(b) or C(B)=g(b) .
In fact, we could make a stronger statement than that. Since we are
assuming g is a surjection, there must be *both* a b in A such that B =
g(b) *and* a b' in A such that C(B) = g(b'). I'll ignore that point for
now, since I don't need it to show the mistake in your argument.
>Clearly, b in B or b in C(B) but not both, and B=g(b) or
> C(B)=g(b) but not both. We then have the main consequence of taking
>into consideration the definition of the relative
>complement with respect to Cantor's argumentation in ZF.
>Immediately by Exstensionality we get
>(b in C(B) <-> b in g(b)) -> C(B) = g(b)
>and hence by C(B) = {x in A | x in g(x)}
>
> C(B) = g(b).
>Moreover since b in B or b in C(B) but not both, and B=g(b) or
> C(B)=g(b) but not both we have
>not (B = g(b)).
Let's step back and look at what you just did. You showed that if
B = g(b) or C(B) = g(b)
then it follows that
not (B = g(b)).
In other words, you have shown that
(Ab)((B = g(b)) -> not (B = g(b)))
or
(Ab)(not (B = g(b))
which means that g is not a surjection, contrary to assumption.
Therefore, no such surjection exists, Q.E.D. You have proved the very
theorem that you are attempting to deny.
>In other terms, by the axiom schema of Subsets and the axiom of
>Extensionality diagonalization is not true in ZF. The assertion
><there must exist some b\in A such that B =g(b)> is false by
>Extensionality. Accordingly (*) and (**) cannot be accomplished
>in VERSION I and Cantor's 'theorem' does not hold in ZF.
Diagonalization is not true? Are you claiming that the set B cannot be
defined? That's where the diagonalization comes in. The assertion
(Eb)(B = g(b)) does not come from diagonalization, but from the
assumption that g is a surjection.
What you are overlooking here is the fact that once you have a
contradiction, everything follows. Here is a quiz. Let P be the
proposition "there exists b such that g(b) = B", and let ~P be its
negation. Which of the following have you shown?
(1) There is no proof of P.
(2) There is a proof of ~P.
Think carefully.
If you are thinking that (2) implies (1), think again. The only way (2)
can imply (1) is if we are dealing with a consistent system, which we are
not. Once you assume that a surjection g: A -> P(A) exists, you can
prove everything, including "P and ~P", "0 = 1", and "Bertrand Russell is
the Pope."
Martin Schlottmann
>
<snip>
Let's try again.
Prop.: For every set A and every function g with domain
A there is a subset B of A which is not a member
of the range of g.
Proof:
Let A be an arbitrary set.
Let g be an arbitrary function with domain A.
Let B := { x in A | x not in g(x) }.
Then, B is a subset of A.
Let x be an arbitrary member of A.
If x in B, then x not in g(x), hence not(B=g(x)).
If x not in B, then x in g(x), hence not(B=g(x)).
Therefore, in any case not(B=g(x)).
Therefore, for every x in A, not(B=g(x)).
Therefore, B is a subset of A which is not a member
of the range of g. QED.
This proof is a dirct proof w/o any reference
to a contradiction.
Cantor's Theorem is a trivial corollary of
the proposition above.
I rest my case until:
1) You point to at least one essential gap and/or
specific error in the proof given above,
and/or
2) You admit that the proof above is a correct
proof in (a very weak subsystem of) ZF.
Meanwhile, I won't check any lengthy proofs of the
negation of Cantor's theorem, and I won't listen to
any speaches on how I cannot do what in predicate
calculus w/o a specific reference to a standard
textbook in mathematical logic written in the
English language and available in our math lib.
--
Martin Schlottmann
Virgil
clear that the codomain of the function is the power set of the domain, so
values of the function are subsets of the domain of the function.
In article <379F64A4...@math.ualberta.ca>, Martin Schlottmann
<martin_sc...@math.ualberta.ca> wrote:
>Cattabriga wrote:
>>
><snip>
>
>Let's try again.
>
>Prop.: For every set A and every function g with domain
> A there is a subset B of A which is not a member
> of the range of g.
>
>Proof:
>Let A be an arbitrary set.
>Let g be an arbitrary function with domain A.
>Let B := { x in A | x not in g(x) }.
>Then, B is a subset of A.
>Let x be an arbitrary member of A.
> If x in B, then x not in g(x), hence not(B=g(x)).
> If x not in B, then x in g(x), hence not(B=g(x)).
> Therefore, in any case not(B=g(x)).
>Therefore, for every x in A, not(B=g(x)).
>Therefore, B is a subset of A which is not a member
>of the range of g. QED.
>
>This proof is a dirct proof w/o any reference
>to a contradiction.
>
>Cantor's Theorem is a trivial corollary of
>the proposition above.
>
>I rest my case until:
>
>1) You point to at least one essential gap and/or
> specific error in the proof given above,
>
>and/or
>
>2) You admit that the proof above is a correct
> proof in (a very weak subsystem of) ZF.
>
>Meanwhile, I won't check any lengthy proofs of the
>negation of Cantor's theorem, and I won't listen to
>any speaches on how I cannot do what in predicate
>calculus w/o a specific reference to a standard
>textbook in mathematical logic written in the
>English language and available in our math lib.
--
Virgil
vm...@frii.com
Cattabriga
In Message-ID: <379F64A4...@math.ualberta.ca>
Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
<snip>
>Let A be an arbitrary set.
>Let g be an arbitrary function with domain A.
>Let B := { x in A | x not in g(x) }.
>Then, B is a subset of A.
>Let x be an arbitrary member of A.
> If x in B, then x not in g(x), hence not(B=g(x)).
> If x not in B, then x in g(x), hence not(B=g(x)).
> Therefore, in any case not(B=g(x)).
>Therefore, for every x in A, not(B=g(x)).
>Therefore, B is a subset of A which is not a member
>of the range of g.
<snip>
>I rest my case until:
>1) You point to at least one essential gap and/or
> specific error in the proof given above,
>and/or
>2) You admit that the proof above is a correct
> proof in (a very weak subsystem of) ZF.
>Meanwhile, I won't check any lengthy proofs of the
<snip>
-------------------------------------------------------
EITHER you give me a NAME for the complement of B, EITHER this
is your personal weak subsystem of ZF where the complements
have no names.
Lemme give you a primer on ZF
|- ZF EyAx(x in y <-> x in A and x notin B)
as long as y IS NOT FREE in (x in A and x notin B)
I.E. In. ZF. Complements. Have. Names.
|- ZF y = g(x)
Martin Schlottmann
>
> You functions in the proof below would make more sense if it were made
> clear that the codomain of the function is the power set of the domain, so
> values of the function are subsets of the domain of the function.
>
We don't have to assume that the codomain
of g is the power set of the domain. In
ZF, everything is a set so every expression
I wrote down makes sense.
--
Martin Schlottmann
Martin Schlottmann
>
> In Message-ID: <379F64A4...@math.ualberta.ca>
> Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
> <snip>
> >Let A be an arbitrary set.
> >Let g be an arbitrary function with domain A.
> >Let B := { x in A | x not in g(x) }.
> >Let x be an arbitrary member of A.
> > If x not in B, then x in g(x), hence not(B=g(x)).
> > Therefore, in any case not(B=g(x)).
> >Therefore, for every x in A, not(B=g(x)).
> >Therefore, B is a subset of A which is not a member
> >of the range of g.
> <snip>
> >I rest my case until:
> >1) You point to at least one essential gap and/or
> > specific error in the proof given above,
> >and/or
> >2) You admit that the proof above is a correct
> > proof in (a very weak subsystem of) ZF.
> >Meanwhile, I won't check any lengthy proofs of the
> <snip>
> -------------------------------------------------------
>
> EITHER you give me a NAME for the complement of B, EITHER this
> is your personal weak subsystem of ZF where the complements
> have no names.
>
> Lemme give you a primer on ZF
>
> |- ZF EyAx(x in y <-> x in A and x notin B)
>
> as long as y IS NOT FREE in (x in A and x notin B)
>
> I.E. In. ZF. Complements. Have. Names.
>
> |- ZF y = g(x)
>
>
> ______________________________________________________________
>
> http://www.serdata.it/cattabriga/
> ______________________________________________________________
>
Still waiting for somebody to find a mistake
in my proof of the proposition above...
--
Martin Schlottmann
Cattabriga
Donald G. Palmer
Martin Schlottmann wrote:
> Cattabriga wrote:
> >
> <snip>
>
> Let's try again.
>
> Prop.: For every set A and every function g with domain
> A there is a subset B of A which is not a member
> of the range of g.
>
> Proof:
> Let A be an arbitrary set.
> Let g be an arbitrary function with domain A.
> Let B := { x in A | x not in g(x) }.
> Then, B is a subset of A.
> Let x be an arbitrary member of A.
> If x in B, then x not in g(x), hence not(B=g(x)).
> If x not in B, then x in g(x), hence not(B=g(x)).
> Therefore, in any case not(B=g(x)).
> Therefore, for every x in A, not(B=g(x)).
> Therefore, B is a subset of A which is not a member
> of the range of g. QED.
>
What if the set B is null? If the null set is a sub-set of any set,
then your proposition is false - since B would be a sub-set of both A
and g(x). If B is not considered a sub-set of any set, then your
proposition is still false, since then, B would not exist as a sub-set
of A.
For infinite sets, this possibility has to be entertained - since the
possibility exists that for any infinite set A (and g(x)), B will be the
null set (i.e. if all infinite sets have the same cardinality.)
Pointing to Cantor's levels and proofs as evidence against this
possibility could easily be dealing in self-reference.
>
> This proof is a dirct proof w/o any reference
> to a contradiction.
>
> Cantor's Theorem is a trivial corollary of
> the proposition above.
>
> I rest my case until:
>
> 1) You point to at least one essential gap and/or
> specific error in the proof given above,
>
> and/or
>
> 2) You admit that the proof above is a correct
> proof in (a very weak subsystem of) ZF.
>
> Meanwhile, I won't check any lengthy proofs of the
> negation of Cantor's theorem, and I won't listen to
> any speaches on how I cannot do what in predicate
> calculus w/o a specific reference to a standard
> textbook in mathematical logic written in the
> English language and available in our math lib.
>
> --
> Martin Schlottmann
--
Donald G. Palmer
num...@voicenet.com
http://www.voicenet.com/~numbers
"Only theory decides what it is that we manage to observe." A. Einstein
Dave Seaman
Donald G. Palmer <num...@voicenet.com> wrote:
>Martin Schlottmann wrote:
>> Prop.: For every set A and every function g with domain
>> A there is a subset B of A which is not a member
>> of the range of g.
>>
>> Proof:
>> Let A be an arbitrary set.
>> Let g be an arbitrary function with domain A.
>> Let B := { x in A | x not in g(x) }.
>> Then, B is a subset of A.
>> Let x be an arbitrary member of A.
>> If x in B, then x not in g(x), hence not(B=g(x)).
>> If x not in B, then x in g(x), hence not(B=g(x)).
>> Therefore, in any case not(B=g(x)).
>> Therefore, for every x in A, not(B=g(x)).
>> Therefore, B is a subset of A which is not a member
>> of the range of g. QED.
>What if the set B is null? If the null set is a sub-set of any set,
>then your proposition is false - since B would be a sub-set of both A
>and g(x). If B is not considered a sub-set of any set, then your
>proposition is still false, since then, B would not exist as a sub-set
>of A.
You forget that B depends on the choice of g. There are indeed some
mappings g: A -> P(A) such that the corresponding set B = { x in A | x
not in g(x) } will turn out to be empty. One such mapping is the
injection x |-> {x} for each x in A. It makes no difference; the proof
still works perfectly well, whether B is empty or not. If you disagree,
then show me an x in A such that g(x) = {x} is the empty set. If you
can't do this, then you have admitted that B is not equal to g(x) for any
x in A, exactly as required.
>For infinite sets, this possibility has to be entertained
What do infinite sets have to do with anything? Let A be the empty set.
Then P(A) = {{}}, and the natural injection turns out to be an empty
mapping. Thus, the set B = { x in {} : x not in g(x) } is also empty.
No infinite sets are required. Note that the proof still works, because
{} is a member of P(A) that is not equal to g(x) for any x in the empty
set.
You can also do the same for any finite set, using the natural x |-> {x}
injection.
>- since the
>possibility exists that for any infinite set A (and g(x)), B will be the
>null set (i.e. if all infinite sets have the same cardinality.)
>Pointing to Cantor's levels and proofs as evidence against this
>possibility could easily be dealing in self-reference.
It doesn't happen for just *any* A and g(x). Let A be nonempty (it
doesn't matter whether it's finite or not) and let g: A -> P(A) be given
by g(x) = {} for each x in A. Then B = { x in A : x not in {} } = A, and
therefore B is nonempty whenever A is, for this particular choice of g.
However, for any A there is a g that makes B empty. It still makes no
difference to the argument.
Ronald Bruck
:Martin Schlottmann wrote:
:
...
:> Let B := { x in A | x not in g(x) }.
...
:
:What if the set B is null? If the null set is a sub-set of any set,
:then your proposition is false - since B would be a sub-set of both A
:and g(x). If B is not considered a sub-set of any set, then your
:proposition is still false, since then, B would not exist as a sub-set
:of A.
Being a SUBSET of g(x) is quite a different thing from being IN g(x).
--Ron Bruck
Martin Schlottmann
>
> Martin Schlottmann wrote:
>
> > Cattabriga wrote:
> > >
> > <snip>
> >
> > Let's try again.
> >
> > A there is a subset B of A which is not a member
> > of the range of g.
> >
> > Proof:
> > Let A be an arbitrary set.
> > Let g be an arbitrary function with domain A.
> > Let B := { x in A | x not in g(x) }.
> > Let x be an arbitrary member of A.
> > If x not in B, then x in g(x), hence not(B=g(x)).
> > Therefore, in any case not(B=g(x)).
> > Therefore, for every x in A, not(B=g(x)).
> > Therefore, B is a subset of A which is not a member
> > of the range of g. QED.
> >
>
> then your proposition is false - since B would be a sub-set of both A
> and g(x).
How does this make the proposition false?
Maybe you want to look up the difference
between "member" and "subset".
--
Martin Schlottmann
Martin Schlottmann
>
> In Message-ID: <379F64A4...@math.ualberta.ca>
> Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
> <snip>
> Let g be an arbitrary function with domain A.
> Let B := { x in A | x not in g(x) }.
> Then, B is a subset of A.
> Let x be an arbitrary member of A.
> If x in B, then x not in g(x), hence not(B=g(x)).
> If x not in B, then x in g(x), hence not(B=g(x)).
> Therefore, in any case not(B=g(x)).
> Therefore, for every x in A, not(B=g(x)).
> Therefore, B is a subset of A which is not a member
> of the range of g.
> I rest my case until:
> 1) You point to at least one essential gap and/or
> specific error in the proof given above,
> and/or
> 2) You admit that the proof above is a correct
> proof in (a very weak subsystem of) ZF.
> Meanwhile, I won't check any lengthy proofs of the
> -------------------------------------------------------
>
> EITHER you give me a NAME for the complement of B, EITHER this
> is your personal weak subsystem of ZF where the complements
> have no names.
>
> Lemme give you a primer on ZF
>
> |- ZF EyAx(x in y <-> x in A and x notin B)
>
> as long as y IS NOT FREE in (x in A and x notin B)
>
> I.E. In. ZF. Complements. Have. Names.
>
> |- ZF y = g(x)
>
You really don't know how to point out an
error in a proof, do you?
And concerning a request: You can use every
name you want for the relative complement
of B in A. E.g., ~B will do fine. So, now
you have a name, show me my error.
And, the formula "y=g(x)" ist most certainly
not a theorem of ZF.
--
Martin Schlottmann
Brian M. Scott
<num...@voicenet.com> wrote:
>Martin Schlottmann wrote:
>> Prop.: For every set A and every function g with domain
>> A there is a subset B of A which is not a member
>> of the range of g.
>> Proof:
>> Let A be an arbitrary set.
>> Let g be an arbitrary function with domain A.
>> Let B := { x in A | x not in g(x) }.
>> Then, B is a subset of A.
>> Let x be an arbitrary member of A.
>> If x in B, then x not in g(x), hence not(B=g(x)).
>> If x not in B, then x in g(x), hence not(B=g(x)).
>> Therefore, in any case not(B=g(x)).
>> Therefore, for every x in A, not(B=g(x)).
>> Therefore, B is a subset of A which is not a member
>> of the range of g. QED.
>What if the set B is null?
If B is null, then no matter what x in A you consider, x is not in B.
By the definition of B, it follows that for each x in A, x is in g(x).
Obviously, then, no g(x) is null, and no g(x) = B. This case does not
require special argument; it is covered by the argument given above.
> If the null set is a sub-set of any set,
It is.
>then your proposition is false - since B would be a sub-set of both A
>and g(x).
This has nothing to do with the matter. Who cares whether B is a
subset of some g(x)? The point is that it isn't *equal* to any of
them.
Brian M. Scott
Cattabriga
This message was posted on 30 Jul 99 to forum.swarthmore.edu
In article Message-ID: <37A0B59C...@math.ualberta.ca>
Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
> > Cattabriga wrote:
> > In Message-ID: <379F64A4...@math.ualberta.ca>
> > Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
> > <snip>
> > >Let A be an arbitrary set.
> > >Let g be an arbitrary function with domain A.
> > >Let B := { x in A | x not in g(x) }.
> > >Then, B is a subset of A.
> > >Let x be an arbitrary member of A.
> > > If x in B, then x not in g(x), hence not(B=g(x)).
> > > If x not in B, then x in g(x), hence not(B=g(x)).
> > > Therefore, in any case not(B=g(x)).
> > >Therefore, for every x in A, not(B=g(x)).
> > >Therefore, B is a subset of A which is not a member
> > >of the range of g.
> > <snip>
> > >I rest my case until:
> > >1) You point to at least one essential gap and/or
> > > specific error in the proof given above,
> > >and/or
> > >2) You admit that the proof above is a correct
> > > proof in (a very weak subsystem of) ZF.
> > >Meanwhile, I won't check any lengthy proofs of the
> > <snip>
> > -------------------------------------------------------
> >
> > EITHER you give me a NAME for the complement of B, EITHER this
> > is your personal weak subsystem of ZF where the complements
> > have no names.
> >
> > Lemme give you a primer on ZF
> >
> > |- ZF EyAx(x in y <-> x in A and x notin B)
> >
> > as long as y IS NOT FREE in (x in A and x notin B)
> >
> > I.E. In. ZF. Complements. Have. Names.
> >
> > |- ZF y = g(x)
> >
> > Paola Cattabriga
> >
> > ______________________________________________________________
> >
> > http://www.serdata.it/cattabriga/
> > ______________________________________________________________
> >
>
>Still waiting for somebody to find a mistake
>in my proof of the proposition above...
It was never my intention to find such "mistake"
(see my posting wsinvh...@forum.swarthmore.edu,
Date: 24 Jul 1999). Your proposition simply does
not hold in ZF.
Cattabriga
Martin Schlottmann <martin_sc...@math.ualberta.ca>
<snip>
>And concerning a request: You can use every
>name you want for the relative complement
>of B in A. E.g., ~B will do fine.
Not only a matter to "use" the name, but to "define"
or to assert its "exsistence".
And, the formula "~B=g(x)" is a theorem of ZF.
See all my previous posting.
see for example
....
g:a |-> P(a),
b = { x in a | x notin g(x)},
(x in c <-> x in g(x))|- [c eq g(x)].
....
Clearly you do not read my answers.
Each one of your reply does not take in consideration
any word of mine.
Thus for which reason should I continue to take in
consideration your words?
Cattabriga
This message was already posted on 30 Jul 99 to forum.swarthmore.edu
> > Paola Cattabriga
> >
> > ______________________________________________________________
> >
> > http://www.serdata.it/cattabriga/
> > ______________________________________________________________
> >
>
>Still waiting for somebody to find a mistake
>in my proof of the proposition above...
It was never my intention to find such "mistake"
(see my posting wsinvh...@forum.swarthmore.edu,
Date: 24 Jul 1999). Your proposition simply does
not hold in ZF.
Cattabriga
Martin Schlottmann
>
<snip>
>
> Clearly you do not read my answers.
>
> Each one of your reply does not take in consideration
> any word of mine.
>
> Thus for which reason should I continue to take in
> consideration your words?
>
You shouldn't. It feels much better to
fancy oneself a genius walking among the
whole lot of Cantorians who are too
stupid to know their ass from their
elbows and who wouldn't detect an error
when you rub their noses in it.
--
Martin Schlottmann
Virgil
<martin_sc...@math.ualberta.ca> wrote:
>You shouldn't. It feels much better to
>fancy oneself a genius walking among the
>whole lot of Cantorians who are too
>stupid to know their ass from their
>elbows and who wouldn't detect an error
>when you rub their noses in it.
>
>--
>Martin Schlottmann
A gentleman is a man who never gives offense unintentionally.
You may be a Schlottmann, but are you a gentleman?
--
Virgil
vm...@frii.com
Brian M. Scott
wrote:
>Martin Schlottmann <martin_sc...@math.ualberta.ca> wrote:
[snip correct proof that |A| < |P(A)|]
>>Still waiting for somebody to find a mistake
>>in my proof of the proposition above...
>It was never my intention to find such "mistake"
>(see my posting wsinvh...@forum.swarthmore.edu,
>Date: 24 Jul 1999). Your proposition simply does
>not hold in ZF.
Of course it does. If you think otherwise, you should be able to
produce (in ZF) a mistake in the proof.
Brian M. Scott
Brian M. Scott
<catt...@mailbox.dsnet.it> wrote:
[...]
>Clearly you do not read my answers.
We read your answers. However, they generally don't make much sense.
Part of the problem is the language barrier, but most of it is because
much of what you say makes no sense *mathematically*. For instance,
why do you think that it makes the slightest difference whether we
write g : A --> P(A) or g : B U ~B --> P(B U ~B)? (And though it's a
minor point, it would be helpful if you'd learn the difference between
--> and |-->.)
Brian M. Scott
Cattabriga
In Message-ID: <37a337e7...@news.csuohio.edu>
sc...@math.csuohio.edu (Brian M. Scott) wrote:
>On 31 Jul 1999 09:51:42 -0400, catt...@mailbox.dsnet.it (Cattabriga)
>wrote:
>>(see my posting wsinvh...@forum.swarthmore.edu,
>>Date: 24 Jul 1999). Your proposition simply does
>>not hold in ZF.
>
>Of course it does. If you think otherwise, you should be able to
>produce (in ZF) a mistake in the proof.
Actually >>>>> IN ZF <<<<< I DID already, see
Subject: Why Cantor Was Wrong
Author: Cattabriga <catt...@mailbox.dsnet.it>
Date: 27 Jul 99 08:35:02 -0400 (EDT)
See also,
******************************************************************
>From: "Cattabriga" <catt...@mailbox.dsnet.it>
>Subject: R: Why Cantor Was Wrong
>Date: 31 Jul 1999 00:00:00 GMT
>Message-ID: <7nuh1q$p...@zamboni.dsnet.it>
>
>
>In Message-ID: <37A1D855...@math.ualberta.ca>
>Martin Schlottmann <martin_sc...@math.ualberta.ca>
><snip>
>>And concerning a request: You can use every
>>name you want for the relative complement
>>of B in A. E.g., ~B will do fine.
>
>Not only a matter to "use" the name, but to "define"
>or to assert its "exsistence".
>
>
>And, the formula "~B=g(x)" is a theorem of ZF.
>See all my previous posting.
>see for example
>....
>g:a |-> P(a),
>b = { x in a | x notin g(x)},
>(x in c <-> x in g(x))|- [c eq g(x)].
>....
>
>Clearly you do not read my answers.
>
>Each one of your reply does not take in consideration
>any word of mine.
>
>Thus for which reason should I continue to take in
>consideration your words?
>
************************************************************
And see also,
> > |- ZF EyAx(x in y <-> x in A and x notin B)
> >
> > as long as y IS NOT FREE in (x in A and x notin B)
> >
> > I.E. In. ZF. Complements. Have. Names.
>>>>> "~B" = "A_NAME"_denoting_a_subset_of_A, for pure
deductive rules (see above and all my previous postings), then
for pure deductive rules "A_NAME"_denoting_a_subset_of_A=g(x) <<<<<
Then no statement of the type [(For every) set A, for (every)
function g (.....A.....g(x)..)] can be given as valid in ZF if
the condition "(.....A.....g(x)..)" do not consider that
"A_NAME"_denoting_a_subset_of_A=g(x).
Also you, like your rude pal before, do not read my words.
All that has been already clearly stated in my
previous postings.
I am sure that like for the past my efforts for clarifying
will not be taken in consideration by you, accordingly
I will do the same with you.
Then, only for the others in sci.math I will clarify as follows.
When we deduce in ZF by pure logical rules that "~B=g(x)",
i.e. by EyAx(x in y <-> x in A and x notin B) "~B" is a NAME
for a subset of A,
by
x sub A iff Az(z in x -> z in A),
we can no longer state
"(For every) set A and (every) function g with domain A
[[[there is a x such that x sub A and it is not a member
of the range of g]]]",
while we can state both:
"given a set A and a function g with domain A
[[[there is a x such that x sub A and it is a member
of the range of g]]]",
and
"given a set A and a function g with domain A
[[[there is a x such that x sub A and it is not a member
of the range of g]]]".
In fact in ZF hold both
>>>>> "given a set A and a function g with domain A
[[[there is a ~B such that ~B sub A and it is a member
of the range of g]]] "<<<<<
and
>>>>> "given a set A and a function g with domain A
[[[there is a B such that B sub A and it is not a member
of the range of g]]] "<<<<<
All the mistake in sentence like __For every set A and
every function g with domain A there is a subset B of
A which is not a member of the range of g__ is in a really
wrong management of the links between the universal
quantifiers and the existential quantifier, yielding the
misinterpretation "a subset B of A" = "a x such that x sub A ".
(Only a footnote.In today logic it is well known the importance of
the reciprocal dependece of quantifiers and their ranges, see
for example J. Hintikka and G. Sandu, "A revolution in Logic?",
Nordic Journal of Philosophical Logic, Vol. 1, N 2, pp 169-183, 1966.
AaAg(Ex P(a,g,x)) Aa(AgEx P(a,g,x)) (AaAgExP(a,g,x)) have different
orders giving rise to different interpretation, depending
on the structure of the condition P(a,g,x).)
Cattabriga
In Message-ID: <37a3391c...@news.csuohio.edu>
sc...@math.csuohio.edu (Brian M. Scott) wrote:
>On Sat, 31 Jul 1999 11:50:32 ++0200, "Cattabriga"
><catt...@mailbox.dsnet.it> wrote:
>[...]
>>Clearly you do not read my answers.
>We read your answers.
No you don't.
>For instance,
>why do you think that it makes the slightest difference whether we
>write g : A --> P(A) or g : B U +AH4-B --> P(B U +AH4-B)?
see
Subject: Why Cantor Was Wrong
Author: Cattabriga <catt...@mailbox.dsnet.it>
Date: 27 Jul 99 08:35:02 -0400 (EDT)
Paola Cattabriga
______________________________________________________________
http://www.serdata.it/cattabriga/
______________________________________________________________
Cattabriga
In Message-ID: <37a337e7...@news.csuohio.edu>
>wrote:
>>It was never my intention to find such "mistake"
>>(see my posting wsinvh...@forum.swarthmore.edu,
>>Date: 24 Jul 1999). Your proposition simply does
>>not hold in ZF.
>
>Of course it does. If you think otherwise, you should be able to
>produce (in ZF) a mistake in the proof.
Actually >>>>> IN ZF <<<<< I DID already, see
Subject: Why Cantor Was Wrong
Author: Cattabriga <catt...@mailbox.dsnet.it>
Date: 27 Jul 99 08:35:02 -0400 (EDT)
See also,
******************************************************************
>From: "Cattabriga" <catt...@mailbox.dsnet.it>
>Subject: R: Why Cantor Was Wrong
>Date: 31 Jul 1999 00:00:00 GMT
>Message-ID: <7nuh1q$p...@zamboni.dsnet.it>
>
>
>In Message-ID: <37A1D855...@math.ualberta.ca>
>Martin Schlottmann <martin_sc...@math.ualberta.ca>
><snip>
>>And concerning a request: You can use every
>>name you want for the relative complement
>>of B in A. E.g., ~B will do fine.
>
>Not only a matter to "use" the name, but to "define"
>or to assert its "exsistence".
>
>
>And, the formula "~B=g(x)" is a theorem of ZF.
>See all my previous posting.
>see for example
>....
>g:a |-> P(a),
>b = { x in a | x notin g(x)},
>(x in c <-> x in g(x))|- [c eq g(x)].
>....
>
>Clearly you do not read my answers.
>
And see also,
orders which may give rise to different interpretation, depending
on the structure of the condition P(a,g,x).)
Martin Schlottmann
>
<snip>
Damn, I'm just too stupid to understand
anything of this. So, please, would you
just answer the following two questions
in the most straightforward terms possible
(meaning yes or no):
Given a function g with domain A, given
B := { x in A | x not in g(x) },
a) is B a subset of A ?
b) can there be any member x of A such
that B = g(x)?
Thanks in advance,
--
Martin Schlottmann
Brian M. Scott
> sc...@math.csuohio.edu (Brian M. Scott) wrote:
> >On Sat, 31 Jul 1999 11:50:32 ++0200, "Cattabriga"
> ><catt...@mailbox.dsnet.it> wrote:
> >>Clearly you do not read my answers.
> >We read your answers.
> No you don't.
Unfortunately, I do. The problem is that even allowing for the language
barrier they are incoherent gibberish. You have not yet convinced me
that you know the first thing about ZF or mathematical logic.
> >For instance,
> >why do you think that it makes the slightest difference whether we
> >write g : A --> P(A) or g : B U ~B --> P(B U ~B)?
> see
> Subject: Why Cantor Was Wrong
> Author: Cattabriga <catt...@mailbox.dsnet.it>
> Date: 27 Jul 99 08:35:02 -0400 (EDT)
No. If you had already given a satisfactory response to my question,
I'd not have asked it. So far your comments on the matter have all been
either wrong, irrelevant, or incomprehensible.
Brian M. Scott
Cattabriga
Brian M. Scott <BMS...@stratos.net> wrote:
>> >On Sat, 31 Jul 1999 11:50:32 ++0200, "Cattabriga"
>> ><catt...@mailbox.dsnet.it> wrote:
>
>> >>Clearly you do not read my answers.
>
>> >We read your answers.
>
>> No you don't.
>
>Unfortunately, I do. The problem is that even allowing for the language
>barrier they are incoherent gibberish.
***
(Notation)
x neq y denotes y is not equal to y.
x eq y denotes y is equal to y.
x subseteq y denotes x is a subset of y.
(x subset y denotes x is a proper subset of y.)
ran g denotes the range of g
The so-called Cantor's 'proof' (Elements of Set Theory, H. B. Enderton,
Academic Press, Inc., pag. 132)
VERSION II -------------------------------------------------------
Let g:a -> P(a). We will construct a subset b of a
that is not in ran g. Specifically let
i) b = { x in a | x notin g(x)}.
Then b subseteq a, but for each x in a
ii) x in b <-> x notin g(x).
Hence b neq g(x).
------------------------------------------------------------------
Let me formalize my proof as follows:
g:a |-> P(a),
Aa(a in b <-> a notin g(a)),
(a in b <-> a notin g(a)),
((a in b <-> a notin g(a)) <-> (a notin b <-> not(a notin g(a)))),
((a in b <-> a notin g(a)) -> (a notin b <-> not(a notin g(a)))),
(a notin b <-> not(a notin g(a))),
Aa(a notin b <-> not(a notin g(a))),
Aa(a notin b <-> a in g(a)),
EyAx(x in y <-> x in a and x notin b),
y=c, (y not free in (x in a and x notin b),
EyAa(a in y <-> a notin b),
(a in c <-> a notin b),
(a in c <-> a in g(a)),
Ax(x in c <-> x in g(x)),
c eq g(x).
i.e.
g:a -> P(a),
b = { x in a | x notin g(x)},
(x in c <-> x in g(x))|- [c eq g(x)].
The existence of c cannot be denied since
EyAx(x in y <-> x in a and x notin b) is an example of
Aussonderung (the Axiom of Subsets), hence we have
constructed a subset c of a that is in ran g.
***
I wander which kind of mathematician considers pure logical
deduction as "incoherent gibberish" ? Either is it page
132 of the book of Enderton?
Paola Cattabriga
_________________________________________________________________
http://www.serdata.it/cattabriga/
_________________________________________________________________
"The process of negation is a necessary instrument of theoretical
research; only its unconditional application allows the
completeness and the realization of logic."
David Hilbert 1931
_________________________________________________________________
Cattabriga
theodore hwa
:
: VERSION II -------------------------------------------------------
:
:
:
:
: Let g:a -> P(a). We will construct a subset b of a
: that is not in ran g. Specifically let
:
: i) b = { x in a | x notin g(x)}.
:
: Then b subseteq a, but for each x in a
:
: ii) x in b <-> x notin g(x).
:
:
: Hence b neq g(x).
[...]
: The existence of c cannot be denied since
: EyAx(x in y <-> x in a and x notin b) is an example of
: Aussonderung (the Axiom of Subsets), hence we have
: constructed a subset c of a that is in ran g.
So we have constructed a subset c of a that is in ran g.
Cantor's theorem constructs a subset c of a that is not in ran g.
Those 2 statements are _NOT_ negations of each other. So what are you
saying?
Ted
Dennis Paul Himes
> (Notation)
> x neq y denotes y is not equal to y.
> x eq y denotes y is equal to y.
> x subseteq y denotes x is a subset of y.
> (x subset y denotes x is a proper subset of y.)
> ran g denotes the range of g
>
> The so-called Cantor's 'proof' (Elements of Set Theory, H. B. Enderton,
> Academic Press, Inc., pag. 132)
There are a number of things wrong with the following, mostly due to
inconsistent notation.
> VERSION II -------------------------------------------------------
>
>
>
>
> Let g:a -> P(a). We will construct a subset b of a
> that is not in ran g. Specifically let
>
> i) b = { x in a | x notin g(x)}.
>
> Then b subseteq a, but for each x in a
>
> ii) x in b <-> x notin g(x).
>
>
> Hence b neq g(x).
>
>
> ------------------------------------------------------------------
>
>
> Let me formalize my proof as follows:
>
> g:a |-> P(a),
> Aa(a in b <-> a notin g(a)),
This is confusing. First you use "a" to denote a set given in the
hypothesis, and now you use it as a variable. It makes it hard in the
following to tell when you're using which meaning.
> (a in b <-> a notin g(a)),
> ((a in b <-> a notin g(a)) <-> (a notin b <-> not(a notin g(a)))),
> ((a in b <-> a notin g(a)) -> (a notin b <-> not(a notin g(a)))),
> (a notin b <-> not(a notin g(a))),
> Aa(a notin b <-> not(a notin g(a))),
> Aa(a notin b <-> a in g(a)),
> EyAx(x in y <-> x in a and x notin b),
> y=c, (y not free in (x in a and x notin b),
> EyAa(a in y <-> a notin b),
What happened to "x in a"? Shouldn't this be:
EyAa(a in y <-> a in a and a notin b)?
Actually it shouldn't, because you're using the symbol "a" inconsistently
again.
> (a in c <-> a notin b),
> (a in c <-> a in g(a)),
> Ax(x in c <-> x in g(x)),
> c eq g(x).
Where do you get this? g(x) is a function of x. You can say that a
set c is equal to a set d if Ax(x in c <-> x in d), but only if c and d are
each a single set, not a (potentially) different set for each x. To put it
another way "c eq g(x)" doesn't make sense, since "x" is not defined in that
statement.
Consider the following. Define g:R->P(R) such that
g(x) = {y in R | y > x}. Then "Ax(x in c <-> x in g(x))" means that c is
the empty set. So you claim that g(x) is empty for some x, i.e. the reals
have a greatest element.
============================================================================
Dennis Paul Himes <> den...@sculptware.com
http://www.connix.com/~dennis/dennis.htm
Disclaimer: "True, I talk of dreams; which are the children of an idle
brain, begot of nothing but vain fantasy; which is as thin of substance as
the air." - Romeo & Juliet, Act I Scene iv Verse 96-99
Brian M. Scott
wrote:
[...]
>(Notation)
>x neq y denotes y is not equal to y.
>x eq y denotes y is equal to y.
>x subseteq y denotes x is a subset of y.
>(x subset y denotes x is a proper subset of y.)
>ran g denotes the range of g
>The so-called Cantor's 'proof' (Elements of Set Theory, H. B.
>Enderton, Academic Press, Inc., pag. 132)
>VERSION II -------------------------------------------------------
>Let g:a -> P(a). We will construct a subset b of a
>that is not in ran g. Specifically let
>i) b = { x in a | x notin g(x)}.
>Then b subseteq a, but for each x in a
>ii) x in b <-> x notin g(x).
>Hence b neq g(x).
Notice that what he's really concluding here is:
Ax(b neq g(x)).
>------------------------------------------------------------------
>Let me formalize my proof as follows:
>g:a -> P(a),
>Aa(a in b <-> a notin g(a)),
You're using 'a' to represent both the domain of g and elements of
that domain. This is excessively confusing. Rewrite:
Ax(x in b <-> x notin g(x).
This has problems, since Ax(x notin a -> x notin g(x)). (This is
because if x is not in a, g(x) is undefined.) Consequently your b is
a proper class. This line should read:
Ax(x in b <-> x in a & x notin g(x)).
> (a in b <-> a notin g(a)),
(x in b <-> x in a & x notin g(x))
> ((a in b <-> a notin g(a)) <-> (a notin b <-> not(a notin g(a)))),
((x in b <-> x in a & x notin g(x)) <->
(x notin b <-> not(x in a & x notin g(x))))
> ((a in b <-> a notin g(a)) -> (a notin b <-> not(a notin g(a)))),
((x in b <-> x in a & x notin g(x)) ->
(x notin b <-> not(x in a & x notin g(x))))
> (a notin b <-> not(a notin g(a))),
(x notin b <-> not(x in a & x notin g(x)))
> Aa(a notin b <-> not(a notin g(a))),
Ax(x notin b <-> not(x in a & x notin g(x)))
> Aa(a notin b <-> a in g(a)),
Ax(x notin b <-> (x notin a OR x in g(x)))
>EyAx(x in y <-> x in a and x notin b),
>y=c, (y not free in (x in a and x notin b),
>EyAa(a in y <-> a notin b),
There's no justification for this.
> (a in c <-> a notin b),
(x in c <-> x in a & x notin b)
> (a in c <-> a in g(a)),
(x in c <-> x in a & (x notin a OR x in g(x))),
from which you may derive
(x in c <-> x in a & x in g(x))
> Ax(x in c <-> x in g(x)),
(*) Ax(x in c <-> x in a & x in g(x))
In other words, c = a\b, the relative complement of b in a. Your
formalization, in addition to being wrong, is unnecessary: no one
should have any problem with simply defining c = b\a in the first
place.
> c eq g(x).
Rubbish: the variable x is bound in (*). You've merely shown that
each element of c belongs to *some* g(x), not that there is a g(x)
that contains *all* elements of c. You are in effect claiming that
AxEy(x in c <-> x in g(y))
implies
EyAx(x in c <-> x in g(y)),
which is a classic elementary blunder.
[...]
> hence we have
>constructed a subset c of a that is in ran g.
(1) You have not; see above. If you really want such a c, however, it
is easy enough to construct. Fix any x in a and let c = g(x); by
definition of g this c is a subset of a that is in ran g.
(2) The construction of such a c is irrelevant to Cantor's Th'm. The
conclusion of Cantor's Th'm. says that there is at least one subset of
a that is not in ran g; to show that this is false, you must show that
for some a and g, *every* subset of a is in ran g. Showing that *one*
subset of a is in ran g does not serve your purpose.
>I wander which kind of mathematician considers pure logical
>deduction as "incoherent gibberish" ? Either is it page
>132 of the book of Enderton?
What Enderton wrote is fine. If you wrote pure logical deduction, it
wouldn't be gibberish. This time you did at least manage to make
yourself understood, but in so doing you also clearly exposed the
errors in your reasoning.
Brian M. Scott
Cattabriga
In Message-ID: <37ab4026...@news.csuohio.edu>
>
>>Let g:a -> P(a). We will construct a subset b of a
>>that is not in ran g. Specifically let
>
>>i) b = { x in a | x notin g(x)}.
>
>>Then b subseteq a, but for each x in a
>
>>ii) x in b <-> x notin g(x).
>
>>Hence b neq g(x).
>
>Notice that what he's really concluding here is:
>
> Ax(b neq g(x)).
>
>>------------------------------------------------------------------
>
>>Let me formalize my proof as follows:
>
>>g:a -> P(a),
>>Aa(a in b <-> a notin g(a)),
>
>You're using 'a' to represent both the domain of g and elements of
>that domain. This is excessively confusing.
Yes I perfectly agree, but it was meant to make it easily
understandable, many mathematicians reason as follows, and I could
cite more than one handbook were you can find this usual procedure:
given a, as already DEFINED, and
Ax(x in b <-> x in a & x notin g(x))
we get
(a in b <-> a notin g(a))
since x in a is always true.
Observe for example the above ii),
where it is clearly understood that
x in b <-> x notin g(x)
holds for each x in a.
All my reasoning have to be understood in the same way, i.e.
for each x in a.
>
> Ax(x notin b <-> (x notin a OR x in g(x))) (**)
Yes I perfectly agree this is a valid example of
the Axiom of Subsets, leading to the case of the
existence of something out of a.
>
>>EyAx(x in y <-> x in a and x notin b),
>>y=c, (y not free in (x in a and x notin b),
>>EyAa(a in y <-> a notin b),
>
>There's no justification for this.
Absolutely not! EyAx(x in y <-> x in a and x notin b) is
a valid example of the Axiom of Subsets, and in a logical
deduction example of axioms are ALWAYS justified.
Hence your observation is "Rubbish:",
>(*) Ax(x in c <-> x in a & x in g(x))
>
>In other words, c = a\b, the relative complement of b in a.
No this is not the relative complement. It is one of the consequences.
>Your
>formalization, in addition to being wrong, is unnecessary: no one
>should have any problem with simply defining c = b\a in the first
>place.
You don't know that axioms are always justified in logical
deduction and you don't know that the only admissible definition for
the
relative complement is EyAx(x in y <-> x in a and x notin b) therefore
all your judgment about my deduction is "Rubbish:".
>
>Rubbish: the variable x is bound in (*).
Bound to what?
Not only it is understood that we are "reasoning inside" the already
defined a, but by a simple classical first order axiom from (*) we
can get
(a in c <-> a in a & a in g(a))
>You've merely shown that
>each element of c belongs to *some* g(x),not that there is a g(x)
>that contains *all* elements of c.
Then for you the statement
Ax(x in c <-> x in a & x in g(x))
does not regard all x in a, nor all x in g(x).
<snip>
>which is a classic elementary blunder.
Consequently the blunder is not mine here.
Brian M. Scott
> sc...@math.csuohio.edu (Brian M. Scott) wrote:
> >On 6 Aug 1999 13:04:43 -0400, catt...@mailbox.dsnet.it (Cattabriga)
> >wrote:
[...]
> >>Let me formalize my proof as follows:
> >>g:a -> P(a),
> >>Aa(a in b <-> a notin g(a)),
> >You're using 'a' to represent both the domain of g and elements of
> >that domain. This is excessively confusing.
> Yes I perfectly agree, but it was meant to make it easily
> understandable, many mathematicians reason as follows, and I could
> cite more than one handbook were you can find this usual procedure:
> given a, as already DEFINED, and
> Ax(x in b <-> x in a & x notin g(x))
> we get
> (a in b <-> a notin g(a))
> since x in a is always true.
Rubbish. Find me one competent mathematician who does such an asinine
thing.
> Observe for example the above ii),
> where it is clearly understood that
> x in b <-> x notin g(x)
> holds for each x in a.
> All my reasoning have to be understood in the same way, i.e.
> for each x in a.
But a is not in a.
> > Ax(x notin b <-> (x notin a OR x in g(x))) (**)
> Yes I perfectly agree this is a valid example of
> the Axiom of Subsets, leading to the case of the
> existence of something out of a.
I'm glad that you agree that mine is correct; you do realize that this
means that the one of yours that it replaced was wrong, don't you?
> >>EyAx(x in y <-> x in a and x notin b),
> >>y=c, (y not free in (x in a and x notin b),
> >>EyAa(a in y <-> a notin b),
> >There's no justification for this.
> Absolutely not! EyAx(x in y <-> x in a and x notin b) is
> a valid example of the Axiom of Subsets, and in a logical
> deduction example of axioms are ALWAYS justified.
> Hence your observation is "Rubbish:",
No, your inference is rubbish. I have no problem with
EyAx(x in y <-> x in a and x notin b),
and I have no problem with defining c to be such a y. But the next
line,
EyAa(a in y <-> a notin b),
does not follow from anything in the argument up to that point.
> >(*) Ax(x in c <-> x in a & x in g(x))
> >In other words, c = a\b, the relative complement of b in a.
> No this is not the relative complement. It is one of the consequences.
Find a good English mathematical dictionary and look up 'relative
complement'; c is indeed the relative complement of b in a.
> >Your
> >formalization, in addition to being wrong, is unnecessary: no one
> >should have any problem with simply defining c = b\a in the first
> >place.
> You don't know that axioms are always justified in logical
> deduction and you don't know that the only admissible definition for
> the
> relative complement is EyAx(x in y <-> x in a and x notin b) therefore
> all your judgment about my deduction is "Rubbish:".
No, it isn't. I merely pointed out that you were wasting your time (and
getting the details wrong besides). There's no good reason to formalize
something as trivial as taking the relative complement.
> >Rubbish: the variable x is bound in (*).
> Bound to what?
Your the one who wants to use formal logic when there's no real need;
don't you know what a bound variable is? You do see the universal
quantifier at the front, don't you?
> Not only it is understood that we are "reasoning inside" the already
> defined a, but by a simple classical first order axiom from (*) we
> can get
> (a in c <-> a in a & a in g(a))
So what? This is a true statement, but we knew that anyway, since both
sides of the <-> are obviously false.
> >You've merely shown that
> >each element of c belongs to *some* g(x),not that there is a g(x)
> >that contains *all* elements of c.
> Then for you the statement
> Ax(x in c <-> x in a & x in g(x))
> does not regard all x in a, nor all x in g(x).
It concerns all x, whether they're in a or not; see the universal
quantifier?
> <snip>
You should have studied it instead of snipping it; you might have begun
to learn some elementary logic.
> >which is a classic elementary blunder.
> Consequently the blunder is not mine here.
The mathematical blunders are yours. My blunder was letting myself
think that you *might* be interested in learning from your mistakes.
Since you're not, and since the mistakes aren't particularly
interesting, I will leave you to your delusions of competence.
Brian M. Scott
Cattabriga
In Message-ID: <37ab4026...@news.csuohio.edu>
sc...@math.csuohio.edu (Brian M. Scott) wrote:
>On 6 Aug 1999 13:04:43 -0400, catt...@mailbox.dsnet.it (Cattabriga)
>wrote:
>[...]
>>VERSION II -------------------------------------------------------
>
>>Let g:a -> P(a). We will construct a subset b of a
>>that is not in ran g. Specifically let
>
>>i) b = { x in a | x notin g(x)}.
>
>>Then b subseteq a, but for each x in a
>
>>ii) x in b <-> x notin g(x).
>
>>Hence b neq g(x).
>
>Notice that what he's really concluding here is:
>
> Ax(b neq g(x)).
>
>>------------------------------------------------------------------
>
>>Let me formalize my proof as follows:
>
>>g:a -> P(a),
>>Aa(a in b <-> a notin g(a)),
>
>You're using 'a' to represent both the domain of g and elements of
>that domain. This is excessively confusing.
Yes I perfectly agree, but it was meant to make it easily
understandable, many mathematicians reason as follows, and I could
cite more than one handbook were you can find this usual procedure:
given a, as already DEFINED, and
Ax(x in b <-> x in a & x notin g(x))
we get
(a in b <-> a notin g(a))
since x in a is always true.
Observe for example the above ii),
where it is clearly understood that
x in b <-> x notin g(x)
holds for each x in a.
All my reasoning have to be understood in the same way, i.e.
for each x in a.
>
> Ax(x notin b <-> (x notin a OR x in g(x))) (**)
Yes I perfectly agree this is a valid example of
the Axiom of Subsets, leading to the case of the
existence of something out of a.
>
>>EyAx(x in y <-> x in a and x notin b),
>>y=c, (y not free in (x in a and x notin b),
>>EyAa(a in y <-> a notin b),
>
>There's no justification for this.
Absolutely not! EyAx(x in y <-> x in a and x notin b) is
a valid example of the Axiom of Subsets, and in a logical
deduction example of axioms are ALWAYS justified.
Hence your observation is "Rubbish:",
>(*) Ax(x in c <-> x in a & x in g(x))
>
>In other words, c = a\b, the relative complement of b in a.
No this is not the relative complement. It is one of the consequences.
>Your
>formalization, in addition to being wrong, is unnecessary: no one
>should have any problem with simply defining c = b\a in the first
>place.
You don't know that axioms are always justified in logical
deduction and you don't know that the only admissible definition for the
relative complement is EyAx(x in y <-> x in a and x notin b) therefore
all your judgment about my deduction is "Rubbish:".
>
>Rubbish: the variable x is bound in (*).
Bound to what?
Not only it is understood that we are "reasoning inside" the already
defined a, but by a simple classical first order axiom from (*) we
can get
(a in c <-> a in a & a in g(a))
>You've merely shown that
>each element of c belongs to *some* g(x),not that there is a g(x)
>that contains *all* elements of c.
Then for you the statement
Ax(x in c <-> x in a & x in g(x))
does not regard all x in a, nor all x in g(x).
<snip>
>which is a classic elementary blunder.
Consequently the blunder is not mine here.
Cattabriga
> I will leave you to your delusions of competence.
And I will leave you to all your illusion of competence.
Paola Cattabriga.
Martin Schlottmann
>
<snip>
>
> The mathematical blunders are yours. My blunder was letting myself
> think that you *might* be interested in learning from your mistakes.
> Since you're not, and since the mistakes aren't particularly
>
Welcome to the club!
--
Martin Schlottmann
Cattabriga
On 6 Aug 1999 17:19:08 GMT
theodore hwa <hwat...@leland.Stanford.EDU> wrote:
>Cattabriga (catt...@mailbox.dsnet.it) wrote:
>:
>: VERSION II -------------------------------------------------------
>:
>:
>:
>:
>: Let g:a -> P(a). We will construct a subset b of a
>: that is not in ran g. Specifically let
>:
>: i) b = { x in a | x notin g(x)}.
>:
>: Then b subseteq a, but for each x in a
>:
>: ii) x in b <-> x notin g(x).
>:
>:
>: Hence b neq g(x).
>:
>
>[...]
>
>: The existence of c cannot be denied since
>: EyAx(x in y <-> x in a and x notin b) is an example of
>: Aussonderung (the Axiom of Subsets), hence we have
>: constructed a subset c of a that is in ran g.
>
>So we have constructed a subset c of a that is in ran g.
>Cantor's theorem constructs a subset c of a that is not in ran g.
>Those 2 statements are _NOT_ negations of each other. So what are
you
>saying?
Cantor's 'theorem' constructs a subset b of a that is not in ran g,
and c = a - b is in ran g.
Whenever b is constructed, c is constructed too.
As you see I say nothing of special at all.
Cattabriga
On 06 Aug 1999 19:00:33 GMT
Dennis Paul Himes <den...@sculptware.com> wrote:
>"Cattabriga" <catt...@mailbox.dsnet.it> wrote:
>> (Notation)
>> x neq y denotes y is not equal to y.
>> x eq y denotes y is equal to y.
>> x subseteq y denotes x is a subset of y.
>> (x subset y denotes x is a proper subset of y.)
>> ran g denotes the range of g
>>
>> The so-called Cantor's 'proof' (Elements of Set Theory, H. B.
Enderton,
>> Academic Press, Inc., pag. 132)
>
> There are a number of things wrong with the following, mostly due
to
>inconsistent notation.
We could discuss about notation till the end of time, but let us
make everything simple.
Cantor's 'theorem' constructs a subset b of a that is not in ran g.
But every time that b is constructed a subset c of a that
is in ran g is constructed too.
VERSION II -------------------------------------------------------
Let g:a -> P(a). We will construct a subset b of a
that is not in ran g. Specifically let
i) b = { x in a | x notin g(x)}.
Then b subseteq a, but for each x in a
ii) x in b <-> x notin g(x).
Hence b neq g(x), but
iii) c = a - b,
i.e.
iv) c = { x in a | x in g(x)}.
Then c subseteq a, and for each x in a
v) x in c <-> x in g(x).
Hence c eq g(x).
Whenever b is constructed, c is constructed too.
------------------------------------------------------------------
iii) is the relative complement of b in a. Its existence is ensured
by the axiom of subsets. In fact we are always allowed to assert
AxAwEyAz(x in y <-> x in w & x notin z) whenever the set w is given,
and z is a subset of w. This set y is the relative complement of z in
w.
-
> To put it another way "c eq g(x)" doesn't make sense,
> since "x" is not defined in that statement.
Following your reasoning "b neq g(x)" doesn't make sense too,
since "x" is not defined in that statement.
Dave Seaman
Cattabriga <catt...@mailbox.dsnet.it> wrote:
>Cantor's 'theorem' constructs a subset b of a that is not in ran g.
>But every time that b is constructed a subset c of a that
>is in ran g is constructed too.
Nonsense.
In the first place, your claim is irrelevant. It doesn't matter how many
sets are in ran g, as long as we can find a subset of a that is *not* in
ran g, which is what Cantor's proof demonstrates.
In the second place, your claim is false.
Counterexample: let a be the empty set. Let g: a -> P(a). Then there
is no set that is in ran g.
Since your "proof" does not assume a to be nonempty, your proof must be
incorrect.
--
Dave Seaman dse...@purdue.edu
Pennsylvania Supreme Court Denies Fair Trial for Mumia Abu-Jamal
<http://mojo.calyx.net/~refuse/altindex.html>
theodore hwa
: >: The existence of c cannot be denied since
: >: EyAx(x in y <-> x in a and x notin b) is an example of
: >: Aussonderung (the Axiom of Subsets), hence we have
: >: constructed a subset c of a that is in ran g.
: >
: >So we have constructed a subset c of a that is in ran g.
: >Cantor's theorem constructs a subset c of a that is not in ran g.
: >Those 2 statements are _NOT_ negations of each other. So what are
: you
: >saying?
:
: Cantor's 'theorem' constructs a subset b of a that is not in ran g,
: and c = a - b is in ran g.
: Whenever b is constructed, c is constructed too.
:
: As you see I say nothing of special at all.
That's right. There is nothing special about that. All that matters to
prove Cantor's theorem is if I construct a subset b of a that is not in
ran g. It doesn't matter if something else (the complement) is in ran g.
Secondly, your claim then a - b is in ran g is false. Let a be the empty
set, for example. Or let a = {1,2} and consider the map g sending
1 -> {1}, 2 -> {2}
then the set constructed by the proof of Cantor's theorem is {}, whose
complement is {1,2}, which is _not_ in ran g.
Ted
Dennis Paul Himes
> Dennis Paul Himes <den...@sculptware.com> wrote:
>> There are a number of things wrong with the following, mostly due to
>> inconsistent notation.
>
> We could discuss about notation till the end of time, but let us
> make everything simple.
>
> is in ran g is constructed too.
>
> Let g:a -> P(a). We will construct a subset b of a
> that is not in ran g. Specifically let
>
> i) b = { x in a | x notin g(x)}.
>
> Then b subseteq a, but for each x in a
>
> ii) x in b <-> x notin g(x).
>
> Hence b neq g(x),
Or, more precisely, Ax (b != g(x)). (Using != to mean "not equal to".)
The proof of this from ii) has been left off, probably because it's so
obvious, but what you write below makes be suspect that you don't understand
it, so I'll supply it.
Prove: Ax (b != g(x)).
Assume its negation: Ey (b == g(y))
Either y is in g(y) or y is not in g(y)
Case 1: y in g(y)
Since b == g(y), y in b.
Since y in g(y), y not in b (by definition of b).
(y in b) & (y not in b) is a contraditcion.
Case 2: y not in g(y)
Since b == g(y), y not in b.
Since y not in g(y), y in b (by definition of b).
(y not in b) & (y in b) is a contraditcion.
Since either case leads to a contradiction, the assumption is false.
Since its negation is false, Ax (b != g(x)), QED
> but
> iii) c = a - b,
>
> i.e.
>
> iv) c = { x in a | x in g(x)}.
>
> Then c subseteq a, and for each x in a
>
> v) x in c <-> x in g(x).
>
> Hence c eq g(x).
Do you mean Ax (c == g(x)), or Ex (c == g(x))? The former is false for
all but a few trivial cases. The latter may or may not be true depending
on g.
For whichever answer you give, could you supply a proof in the same way
I proved Ax (b != g(x))?
And while you're at it, could you give some indication why you feel this
invalidates Cantor's proof?
> iii) is the relative complement of b in a. Its existence is ensured
> by the axiom of subsets. In fact we are always allowed to assert
> AxAwEyAz(x in y <-> x in w & x notin z) whenever the set w is given,
> and z is a subset of w. This set y is the relative complement of z in
> w.
No one disputes that c exists. We just fail to see your point in
showing that it exists. Its existence certainly does not contradict any
part of Cantor's theorem.
> > To put it another way "c eq g(x)" doesn't make sense,
> > since "x" is not defined in that statement.
>
> Following your reasoning "b neq g(x)" doesn't make sense too,
> since "x" is not defined in that statement.
As I explained above "b neq g(x)" (which was not my notation) is short
for "Ax (b != g(x)". What is "c eq g(x)" short for? Neither of the obvious
possibilities, "Ax (c == g(x))" or "Ex (c == g(x))" is true in general.
Dave L. Renfro
many posts by Cattabriga, and the numerous
posts by others generated by his (her?) posts.
Therefore, I'm not very knowledgeable concerning
what has gone on in all the prior posts.
However, I did spend a few moments looking over
the first few lines of Cattabriga's "VERSION II"
in the 9 Aug 99 04:51:52 -0400 (EDT) post:
>Let g:a -> P(a). We will construct a subset b of a
>that is not in ran g. Specifically let
>
>i) b = { x in a | x notin g(x)}.
>
>Then b subseteq a, but for each x in a
>
>ii) x in b <-> x notin g(x).
>
>Hence b neq g(x), but
b subseteq a is true, but the second claim in this
same sentence is false. Here is a counterexample.
Let a = {r, s} and define g:a -> P(a) by
g(r) = {s} and g(s) = {r, s}.
In this example, b = {r}.
Let's check your claim for each of the elements
in a, one by one:
[x = r] Your biconditional becomes
r in b <-> r notin g(r).
This biconditional holds, since both "r in b"
(equivalently, "r in {r}") and "r notin g(r)"
(equivalently, "r notin {s}") are true.
[x = s] Your biconditional becomes
s in b <-> s notin g(s).
In this instance, the biconditional DOESN'T hold,
since "s in b" (equivalently, "s in {r}") is FALSE and
"s notin g(s)" (equivalently, "s notin {r, s}")
is TRUE.
Hence, your biconditional "x in b <-> x notin g(x)"
DOES NOT HOLD for each x in a.
*********************************************
WHAT IS TRUE is that for each x in b,
x in b <-> x notin g(x).
[However, this is simply a trivial restatement of the
definition of b.]
Also, the following is meaningless at the point
in your proof where it appears:
>
>Hence b neq g(x), but
At the point where "b neq g(x)" is asserted, x has
not been defined. [You have only used "x" up to
this point as a 'dummy variable'.]
Perhaps you mean
"for all x in <specify a set here>, b neq g(x)"
OR
"there exists x in <specify a set here>, b neq g(x)"?
Dave Seaman
Dave L. Renfro <DaveR...@compuserve.com> wrote:
>In this instance, the biconditional DOESN'T hold,
>since "s in b" (equivalently, "s in {r}") is FALSE and
>"s notin g(s)" (equivalently, "s notin {r, s}")
>is TRUE.
No, "s notin {r, s}" is false. This part of his argument agrees with
Cantor's and is correct.
Dave L. Renfro
post (If indeed I was thinking at all!), but
my "counterexample" isn't one. [I claimed
that a certain biconditional is false when x = s.
Actually, both parts of the biconditional are false
when x = s, rendering the biconditional true.]
Please ignore my previous response to Cattabriga
and substitute in its place what follows.
*************************************************
I have only read a small number of the
many posts by Cattabriga and the numerous
posts by others generated by his (her?) posts.
Therefore, I'm not very knowledgeable concerning
what has gone on in all the prior posts.
However, I did spend a few moments looking over
the first few lines of Cattabriga's "VERSION II"
in the 9 Aug 99 04:51:52 -0400 (EDT) post.
The following is meaningless at the point
in Cattabriga's proof where it appears, just
after biconditional ii):
Ken Cox
> given a, as already DEFINED, and
> Ax(x in b <-> x in a & x notin g(x))
> we get
> (a in b <-> a notin g(a))
> since x in a is always true.
You have some sort of typographical error above; either that or
a really, really bad choice of variable names. The substitution
you are doing would lead to the term "a in a" in the second line,
which would be always false -- not always true as you state.
Now, if you mean that "a" is a set in the first line, but is an
element of the set in the second, then you probably should write
something like
Given sets A and B, and Ax(x in B <-> x in A and x notin g(x))
we get (a in B <-> a in A and a notin g(a)).
--
Ken Cox k...@research.bell-labs.com