Can ZFC prove Addition is Associative?
Charlie-Boo
about proving that addition is associative, you know, A+(B+C) = (A+B)+C
for all numbers A,B,C? It is a simple statement so it shouldn't take
more than a few steps. Could someone show it (the formal derivation)
here?
C-B
DmitryKovtun
"Charlie-Boo" <shyma...@gmail.com> wrote in message
news:1166192828.2...@f1g2000cwa.googlegroups.com...
Yes, Zentuckey Frid Chicken theorm indicates that A+B = D - C and that B +
C = D - A
therfore A + B + B + C = D + D - C - A
Simplyfying A + C + 2*B = 2*D - ( A + C)
or B = D
Chip Eastham
What "numbers" do you have in mind, Charlie? Formal proof
depends on formal definitions. Are we talking natural numbers?
Ordinals? Cardinals? Integers? Reals? Complex?
Your assertion that it is "a simple statement so it
shouldn't take more than a few steps" is argumentative.
I know of no reason to suspect this is true. We could
sketch the development of ordinal arithmetic here, with
the natural numbers developed as an initial segment,
in a post of reasonable length.
--c
Bob Kolker
Showing that addition is associative using just PA takes more than a few
steps.
Bob Kolker
Charlie-Boo
> Charlie-Boo wrote:
> > Many people say that all of Mathematics can be done using ZFC. Ok, how
> > about proving that addition is associative, you know, A+(B+C) = (A+B)+C
> > for all numbers A,B,C? It is a simple statement so it shouldn't take
> > more than a few steps. Could someone show it (the formal derivation)
> > here?
>
> What "numbers" do you have in mind, Charlie? Formal proof
> depends on formal definitions. Are we talking natural numbers?
Let's just say natural numbers to keep it simple (and still preserve
the point.)
> Ordinals? Cardinals? Integers? Reals? Complex?
>
> Your assertion that it is "a simple statement so it
> shouldn't take more than a few steps" is argumentative.
> I know of no reason to suspect this is true. We could
> sketch the development of ordinal arithmetic here, with
> the natural numbers developed as an initial segment,
> in a post of reasonable length.
Ok. Or if you (anyone) would like to simply present the proof and we
can work backwards as needed (back to definitions and other theorems
utilized), that might also work.
C-B
> --c
Charlie-Boo
LOL : )
Yeh, it taste good - but is it nutritional? Did we follow the Rules of
the Colonel (Secret Recipe)? Or do we make up rules as we go along -
uh oh!
Don't you just love asking for a simple little example and people flip
out? Makes me think they do know the truth - and sense we are getting
a bit closer to it!
C-B
Charlie-Boo
PA I believe in. It describes a specific domain (recursively
enumerable universal set) and has rules particular to that. In fact,
it is an example of what I maintain must be done: rules for each
domain.
But how would ZFC do it? It seems to only describe what we should
allow as sets - nothing about Arithmetic. We can use sets in place of
the natural numbers, but that is true of a subset of the functions, of
directed graphs, of any infinite set for which we have a formal
(finite) representation of each element. But you need special rules to
go beyond that. ZFC is supposed to be only the rules it already set
out.
C-B
> Bob Kolker
Dave Seaman
If A and B are cardinal numbers, then A+B is defined to be the
cardinality of the disjoint union. That is,
A+B = | Ax{0} U Bx{1} |,
where "x" denotes Cartesian product. Notice that if A and B are any
sets, then |Ax{0}| = |A|, |Bx{0}| = |B|, and the sets Ax{0} and Bx{1} are
necessarily disjoint, so that the sum of the cardinalities is the
cardinality of the union.
From the definition it follows that
A+(B+C) = A + | Bx{0} U Cx{1} |
= | Ax{0} U (Bx{0} U Cx{1})x{1} |
= | Ax{0} U (Bx{1} U Cx{2}) |
= | (Ax{0} U Bx{1}) U Cx{2} | (using associativity of union)
= | (Ax{0} U Bx{1})x{0} U Cx{1} |
= | Ax{0} U Bx{1} | + C
= (A+B) + C.
--
Dave Seaman
U.S. Court of Appeals to review three issues
concerning case of Mumia Abu-Jamal.
<http://www.mumia2000.org/>
Charlie-Boo
Dave Seaman wrote:
> On 15 Dec 2006 06:27:08 -0800, Charlie-Boo wrote:
> > Many people say that all of Mathematics can be done using ZFC. Ok, how
> > about proving that addition is associative, you know, A+(B+C) = (A+B)+C
> > for all numbers A,B,C? It is a simple statement so it shouldn't take
> > more than a few steps. Could someone show it (the formal derivation)
> > here?
>
> If A and B are cardinal numbers, then A+B is defined to be the
> cardinality of the disjoint union. That is,
>
> A+B = | Ax{0} U Bx{1} |,
>
> where "x" denotes Cartesian product. Notice that if A and B are any
> sets, then |Ax{0}| = |A|, |Bx{0}| = |B|, and the sets Ax{0} and Bx{1} are
> necessarily disjoint, so that the sum of the cardinalities is the
> cardinality of the union.
>
> From the definition it follows that
>
> A+(B+C) = A + | Bx{0} U Cx{1} |
> = | Ax{0} U (Bx{0} U Cx{1})x{1} |
> = | Ax{0} U (Bx{1} U Cx{2}) |
> = | (Ax{0} U Bx{1}) U Cx{2} | (using associativity of union)
Thanks. However, here you do as I predicted: you add the rule for the
Associativity of Union (which in this context means Addition!) So ZFC
(alone) did not prove it. As I said, you have to add new rules for
each branch of Mathematics e.g. Arithmetic.
Is there a real proof (using only ZFC)?
C-B
Dave Seaman
>> = | (Ax{0} U Bx{1})x{0} U Cx{1} |
>> = | Ax{0} U Bx{1} | + C
>> = (A+B) + C.
Let I be the set {A,B,C}. Then (AUB)UC = AU(BUC) = UI, where the existence of
UI is guaranteed by the union axiom of ZFC.
Charlie-Boo
LOL : )
Herman Rubin
>Bob Kolker
This is NOT the case. The customary treatment from Peano
postulates, after addition has been characterized, makes
this the first theorem, easily proved by induction on C.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hru...@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558
Dave L. Renfro
I don't know why you think simple statments must
have simple proofs. Probably the best known "hard"
mathematical achievement of the past 20 years is
a counterexample to this (Fermat's Last Theorem).
Anway ...
See: [1] Chapter 4, Theorem 4K(a), p. 81 in
Enderton's book; [2] Chapter 5, Section 2, Theorem 30,
pp. 146-147 in Suppes' book. Or, see any number
of other elementary set theory texts.
Incidentally, the relevant pages of Patrick
Suppes' book are available at google-books.
When you get to his book there, type "by
Theorem 28" (including quotes) into the window
'Search in this book'.
Herbert B. Enderton, ELEMENTS OF SET THEORY,
Academic Press, 1977, xiv + 279 pages.
Patrick Suppes, AXIOMATIC SET THEORY, Dover
Publications, 1960/1972, xii + 267 pages.
http://books.google.com/books?vid=ISBN0486616304
Dave L. Renfro
Herman Rubin
Charlie-Boo <shyma...@gmail.com> wrote:
>Dave Seaman wrote:
>> On 15 Dec 2006 06:27:08 -0800, Charlie-Boo wrote:
>> > Many people say that all of Mathematics can be done using ZFC. Ok, how
>> > about proving that addition is associative, you know, A+(B+C) = (A+B)+C
>> > for all numbers A,B,C? It is a simple statement so it shouldn't take
>> > more than a few steps. Could someone show it (the formal derivation)
>> > here?
>> If A and B are cardinal numbers, then A+B is defined to be the
>> cardinality of the disjoint union. That is,
>> A+B = | Ax{0} U Bx{1} |,
>> where "x" denotes Cartesian product. Notice that if A and B are any
>> sets, then |Ax{0}| = |A|, |Bx{0}| = |B|, and the sets Ax{0} and Bx{1} are
>> necessarily disjoint, so that the sum of the cardinalities is the
>> cardinality of the union.
>> From the definition it follows that
>> A+(B+C) = A + | Bx{0} U Cx{1} |
>> = | Ax{0} U (Bx{0} U Cx{1})x{1} |
>> = | Ax{0} U (Bx{1} U Cx{2}) |
>> = | (Ax{0} U Bx{1}) U Cx{2} | (using associativity of union)
>Thanks. However, here you do as I predicted: you add the rule for the
>Associativity of Union (which in this context means Addition!) So ZFC
>(alone) did not prove it. As I said, you have to add new rules for
>each branch of Mathematics e.g. Arithmetic.
Associativity of union of disjoint sets is proved
from the theorem of logic that disjunction is associative.
Mathematics does use the first-order predicate calculus
together with its axioms to prove theorems.
>Is there a real proof (using only ZFC)?
>C-B
>> = | (Ax{0} U Bx{1})x{0} U Cx{1} |
>> = | Ax{0} U Bx{1} | + C
>> = (A+B) + C.
>> --
>> Dave Seaman
>> U.S. Court of Appeals to review three issues
>> concerning case of Mumia Abu-Jamal.
>> <http://www.mumia2000.org/>
--
Charlie-Boo
LOL : )
CBT...@gmail.com
Yes. Again, ZFC says which sets exist, but where does it say that
(AUB)UC = AU(BUC) - how do we establish that?
(Answer: With additional axioms relating to union, intersection,
subsets et. al., which parallel Arithmetic.)
C-B
Charlie-Boo
Dave Seaman wrote:
> On 15 Dec 2006 06:27:08 -0800, Charlie-Boo wrote:
> > Many people say that all of Mathematics can be done using ZFC. Ok, how
> > about proving that addition is associative, you know, A+(B+C) = (A+B)+C
> > for all numbers A,B,C? It is a simple statement so it shouldn't take
> > more than a few steps. Could someone show it (the formal derivation)
> > here?
>
> If A and B are cardinal numbers, then A+B is defined to be the
> cardinality of the disjoint union. That is,
>
> A+B = | Ax{0} U Bx{1} |,
>
> where "x" denotes Cartesian product. Notice that if A and B are any
> sets, then |Ax{0}| = |A|, |Bx{0}| = |B|, and the sets Ax{0} and Bx{1} are
> necessarily disjoint, so that the sum of the cardinalities is the
> cardinality of the union.
>
> From the definition it follows that
>
> A+(B+C) = A + | Bx{0} U Cx{1} |
> = | Ax{0} U (Bx{0} U Cx{1})x{1} |
> = | Ax{0} U (Bx{1} U Cx{2}) |
> = | (Ax{0} U Bx{1}) U Cx{2} | (using associativity of union)
Thanks. However, here you do as I predicted: you add the rule for the
Associativity of Union (which in this context means Addition!) So ZFC
(alone) did not prove it. As I said, you have to add new rules for
each branch of Mathematics e.g. Arithmetic.
Is there a real proof (using only ZFC)?
C-B
Dave L. Renfro
See Chapter 4, Theorem 4K(a), p. 81 in Enderton's book.
See Chapter 5, Section 2, Theorem 30, pp. 146-147 in Suppes' book.
Or any number of other elementary set theory texts.
Dave L. Renfro
See Chapter 4, Theorem 4K(a), p. 81 in Enderton's book.
See Chapter 5, Section 2, Theorem 30, pp. 146-147 in Suppes' book.
Or any number of other elementary set theory texts.
Incidentally, the relevant pages of Patrick Suppes' book
are digitized at google's book project. When you get to
Dave L. Renfro
See Chapter 4, Theorem 4K(a), p. 81 in Enderton's book.
See Chapter 5, Section 2, Theorem 30, pp. 146-147 in Suppes' book.
Or any number of other elementary set theory texts.
Incidentally, the relevant pages of Patrick Suppes' book
are available at google-books. When you get to his book
Arturo Magidin
Charlie-Boo <shyma...@gmail.com> wrote:
>Chip Eastham wrote:
>> Charlie-Boo wrote:
>> > Many people say that all of Mathematics can be done using ZFC. Ok, how
>> > about proving that addition is associative, you know, A+(B+C) = (A+B)+C
>> > for all numbers A,B,C? It is a simple statement so it shouldn't take
>> > more than a few steps. Could someone show it (the formal derivation)
>> > here?
>>
>> What "numbers" do you have in mind, Charlie? Formal proof
>> depends on formal definitions. Are we talking natural numbers?
>
>Let's just say natural numbers to keep it simple (and still preserve
>the point.)
And what properties are you allowing as given?
Anyway... We define the function +_n :N --> N using
induction/recursion, by
+_n(0) = n
+_n(s(m)) = s(+_n(m))
where s is the successor function of the natural numbers. This is
interpreted as saying that
0 + n = n
s(m) + n = s(m+n)
and this tells you how to "add n" to any natural number. Using Peano's
fifth postulate, you can verify that this defines a function from N to
N.
Induction is of course an application of Peano's 5th postulate, which
can be justified in ZFC since N is proven to be the smallest inductive
set.
Then we define addition +: N x N --> N by currying:
+(m,n) = +_n(m)
and interpret +(m,n) as "m+n".
First:
LEMMA: For all natural number n, n+0 = n.
Proof: Induction on n. 0+0 = +_0(0) = 0 by definition of +_0,
If k+0 = k, then s(k)+0 = +_0(s(k))
= s(+_0(k)) by definition of +_0
= s(k) (by the induction hypothesis).
QED.
THEOREM: For all natural number m and n, m+n = n+m.
Proof: induction on n. If n =0, then
n+m = 0+m = +_m(0) = m by definition.
m+n = m+0 = m by Lemma.
QED
LEMMA 2: For all natural numbers m and n, m+s(n) = s(m)+n.
Proof: m+s(n) = s(n)+m by Theorem
= s(n+m) by definition
= s(m+n) by Theorem
= s(m)+n by definition of +_n.
QED
THEOREM: For all natural number m, n, k,
(m+n)+k = m+(n+k).
Proof: Induction on k.
(m+n)+0 = +_0(m+n) (by definition)
= m+n (by Lemma)
= +_n(m) by definition.
m+(n+0) = +_(n+0)(m) by definition
= +_n(m) by Lemma (since n+0 = n).
So the result holds for k=0.
Assume the result is true for k and any natural numbers m and n. Then
(m+n)+s(k) = s(m+n)+k (by Lemma 2)
= (s(m)+n) + k (by definition)
= s(m) + (n+k) (by the induction hypothesis)
= m + s(n+k) (by Lemma 2)
= m + (s(n)+k) (by definition)
= m + (n+s(k)) (by Lemma 2).
so the results holds for s(k) if it holds of k.
QED
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================
Arturo Magidin
magidin-at-member-ams-org
Dave Seaman
By using basic properties of logical primitives such as "and" and "or".
For all x, if x in U{A,B,C} <-> (x in U{A,B} or x in C)
<-> (x in A or x in U{B,C}).
> (Answer: With additional axioms relating to union, intersection,
> subsets et. al., which parallel Arithmetic.)
No, I haven't used any axioms relating to union, intersection, or subsets
other than the union axiom of ZFC.
CBT...@gmail.com
Dave L. Renfro wrote:
> Charlie-Boo wrote:
>
> > Many people say that all of Mathematics can be
> > done using ZFC. Ok, how about proving that addition
> > is associative, you know, A+(B+C) = (A+B)+C for
> > all numbers A,B,C? It is a simple statement so
> > it shouldn't take more than a few steps. Could
> > someone show it (the formal derivation) here?
>
> I don't know why you think simple statments must
> have simple proofs.
Not any one, just this one. Because it asks for a formal proof within
a formal system.
> Probably the best known "hard"
> mathematical achievement of the past 20 years is
> a counterexample to this (Fermat's Last Theorem).
That's not a formal proof within a formal system.
The problem is people will make claims and point to publications (and
refer to terms like "elementary" and "introductory") when the
publication is BS or doesn't include what is claimed, then refuse to
simply present their supposed substantiation here so that it can be
critiqued. I don't want any excuses as to why the proof can't be
shown here. (I know the real reason it will never be.)
> Anway ...
>
> See: [1] Chapter 4, Theorem 4K(a), p. 81 in
> Enderton's book; [2] Chapter 5, Section 2, Theorem 30,
> pp. 146-147 in Suppes' book. Or, see any number
> of other elementary set theory texts.
Suppes borrows from PA. Now if you want to claim that ZFC includes PA
in its definition, then I will have to propose a theorem outside of
both Number Theory and the question of which sets exist.
C-B
Arturo Magidin
That may be "an" answer, but it is not the correct answer.
ZFC includes the basic propositional logic, in which the associativity
of the disjunctive "or" holds.
The fact that (AUB)UC = AU(BUC) follows as a theorem from this. From
Union and Separation, and Extension, we get that
X U Y = { x | x in X or x in Y}.
So
(AUB)UC = {x | x in (AUB) or (x in C) }
= {x | ((x in A) or (x in B)) or (x in C)}
= {x | x in A or ((x in B) or (x in C)) } (Extension)
= {x | x in A or (x in BUC) }
= A U (BUC).
CBT...@gmail.com
You have to specify those, otherwise it isn't a formal proof (the set
of theorems isn't r.e.) and you haven't stayed within ZFC. Each time
you try, you wil find yourself needing principles (read: axioms) not
included in ZFC, as we have seen by your last several attempts.
> For all x, if x in U{A,B,C} <-> (x in U{A,B} or x in C)
> <-> (x in A or x in U{B,C}).
(The above is one possible axiom to add to ZFC to be able to prove
Associativity of Addition. You have not shown it to be a formal
theorem.)
Thanks,
C-B
Charlie-Boo
Dave Seaman wrote:
> On 15 Dec 2006 06:27:08 -0800, Charlie-Boo wrote:
> > Many people say that all of Mathematics can be done using ZFC. Ok, how
> > about proving that addition is associative, you know, A+(B+C) = (A+B)+C
> > for all numbers A,B,C? It is a simple statement so it shouldn't take
> > more than a few steps. Could someone show it (the formal derivation)
> > here?
>
> If A and B are cardinal numbers, then A+B is defined to be the
> cardinality of the disjoint union. That is,
>
> A+B = | Ax{0} U Bx{1} |,
>
> where "x" denotes Cartesian product. Notice that if A and B are any
> sets, then |Ax{0}| = |A|, |Bx{0}| = |B|, and the sets Ax{0} and Bx{1} are
> necessarily disjoint, so that the sum of the cardinalities is the
> cardinality of the union.
>
> From the definition it follows that
>
> A+(B+C) = A + | Bx{0} U Cx{1} |
> = | Ax{0} U (Bx{0} U Cx{1})x{1} |
> = | Ax{0} U (Bx{1} U Cx{2}) |
> = | (Ax{0} U Bx{1}) U Cx{2} | (using associativity of union)
Thanks. However, here you do as I predicted: you add the rule for the
Associativity of Union (which in this context means Addition!) So ZFC
(alone) did not prove it. As I said, you have to add new rules for
each branch of Mathematics e.g. Arithmetic.
Is there a real proof (using only ZFC)?
C-B
CBT...@gmail.com
That's right. My question is whether you can do it using ZFC (axioms),
as some claim implicitly.
C-B
CBT...@gmail.com
If you're going to claim that PA is part of ZFC, then I will have to
propose a theorem outside of Number Theory.
C-B
Dave Seaman
See the two lines below. Which part do you not consider as "specified"?
>> For all x, if x in U{A,B,C} <-> (x in U{A,B} or x in C)
>> <-> (x in A or x in U{B,C}).
> (The above is one possible axiom to add to ZFC to be able to prove
> Associativity of Addition. You have not shown it to be a formal
> theorem.)
It's not an axiom of ZFC. It's a principle of logic.
MoeBlee
> Bob Kolker wrote:
> > Charlie-Boo wrote:
> >
> > > Many people say that all of Mathematics can be done using ZFC. Ok, how
> > > about proving that addition is associative, you know, A+(B+C) = (A+B)+C
> > > for all numbers A,B,C? It is a simple statement so it shouldn't take
> > > more than a few steps. Could someone show it (the formal derivation)
> > > here?
> >
> > Showing that addition is associative using just PA takes more than a few
> > steps.
>
> PA I believe in. It describes a specific domain (recursively
> enumerable universal set) and has rules particular to that. In fact,
> it is an example of what I maintain must be done: rules for each
> domain.
Every axiom of PA is a theorem of Z set theory.
Associativity of addition of natural numbers is a theorem of Z set
theory.
Another poster has since mentioned such textbooks as Suppes's and
Enderton's. They both have proofs in Z set theory of the associativity
of addition.
> But how would ZFC do it? It seems to only describe what we should
> allow as sets - nothing about Arithmetic.
Wrong. In Z set theory we can define the basic operations on natural
numbers such as addition and prove basic theorems about addition such
as associativity.
> We can use sets in place of
> the natural numbers, but that is true of a subset of the functions, of
> directed graphs, of any infinite set for which we have a formal
> (finite) representation of each element. But you need special rules to
> go beyond that. ZFC is supposed to be only the rules it already set
> out.
Using only the axioms of Z set theory (which, of course, subsumes first
order logic with identity) we prove the associativity of addition. Of
course, along the way toward that proof, we will have made defintions,
but only as supported by proving, from the axioms of Z set theory
alone, the existence of the defined objects. Anyway, if we didn't mind
longer formulas, we could give the proof of the associativity of
addition of natural numbers strictly in primitive set theoretic
notation.
It's simply a plain stone cold fact that we do prove the associativity
of addition of natural numbers from the axioms of Z set theory alone.
You claim to know the basics of set theory, yet you don't know this
very basic first semester material.
MoeBlee
MoeBlee
> Every axiom of PA is a theorem of Z set theory.
>
> Associativity of addition of natural numbers is a theorem of Z set
> theory.
Just to be clear, I am not saying that associativity of addition is an
axiom of PA.
MoeBlee
MoeBlee
> Thanks. However, here you do as I predicted: you add the rule for the
> Associativity of Union (which in this context means Addition!) So ZFC
> (alone) did not prove it. As I said, you have to add new rules for
> each branch of Mathematics e.g. Arithmetic.
Associativity of union is a theorem of Z set theory. That is covered in
chapter one Set Theory 101. Yet you claim to be familiar with basic set
theory.
MoeBlee
MoeBlee
> Yes. Again, ZFC says which sets exist, but where does it say that
> (AUB)UC = AU(BUC) - how do we establish that?
Easily. Just look at chapter one of just about any basic set theory
textbook. Enderton or Suppes are both fine.
I could type out the proof for you in a blink, but you really do need
to learn chapter one set theory for yourself anyway.
MoeBlee
Mitch
MoeBlee wrote:
> It's simply a plain stone cold fact that we do prove the associativity
> of addition of natural numbers from the axioms of Z set theory alone.
>
So associativity of addition (of suitably defined numbers in ZFC)
depends on the associativity of conjunction in FOL (which is
understood as part of the specification of ZFC). Maybe CB doesn't
think of ZFC as the content full ZFC plus the logic FOL?
Mitch
Michael Stemper
>Many people say that all of Mathematics can be done using ZFC. Ok, how
>about proving that addition is associative, you know, A+(B+C) = (A+B)+C
>for all numbers A,B,C?
I don't know it off the top of my head, but _Axiomatic Set Theory_ by
Suppes has a proof of this -- for naturals. Once you've got that, it's
easy enough to use it to prove associativity for the integers (defined
as an equivalence class of ordered pairs of naturals), and then the
rationals (defined as an equivalence class of ordered pairs of integers),
and then the reals (defined as an equivalence class of Cauchy sequences
of rationals), and finally the complex numbers (defined as an equivalence
class of ordered pairs of reals).
> It is a simple statement so it shouldn't take
>more than a few steps.
As I recall (I'm at work and don't have Suppes with me), it takes about
a page and a half. Of course, FLT and 4CT have simple statements, as
well.
--
Michael F. Stemper
#include <Standard_Disclaimer>
No animals were harmed in the composition of this message.
MoeBlee
> Suppes borrows from PA.
Not in proving associativity of addition of natural numbers. Rather, he
proves that all the axioms of PA are theorems of Z set theory. And he
gives a proof of associativity straight from Z set theory anyway.
> Now if you want to claim that ZFC includes PA
> in its definition, then I will have to propose a theorem outside of
> both Number Theory and the question of which sets exist.
No, in Z we prove the existence of a unique least successor inductive
set, which we define as 'omega'; we prove the existence of the addition
function on omegaXomega; and we prove the associativity of that
function.
That is basic first semester set theory 101. And you don't even know
about it. Wow.
MoeBlee
MoeBlee
> MoeBlee wrote:
> > It's simply a plain stone cold fact that we do prove the associativity
> > of addition of natural numbers from the axioms of Z set theory alone.
> >
>
> So associativity of addition (of suitably defined numbers in ZFC)
> depends on the associativity of conjunction in FOL (which is
> understood as part of the specification of ZFC).
Sentential DISjunction (not conjunction, though it is also a sentential
theorem), I think you meant.
And, as you and I understand, of course Z set theory subsumes
sentential logic. But even then, I don't recall (I'd have to look back
at all the steps) that the other proof that comes from the recursive
definition of addition (as opposed to the definition based on unions of
disjunct sets) uses associativity of disjunction (though it might, as I
mentioned, if we looked back at all steps).
> Maybe CB doesn't
> think of ZFC as the content full ZFC plus the logic FOL?
Maybe. Clearly, he's unfamiliar with even the basic notions.
MoeBlee
Alan Smaill
> Many people say that all of Mathematics can be done using ZFC. Ok, how
> about proving that addition is associative, you know, A+(B+C) = (A+B)+C
> for all numbers A,B,C? It is a simple statement so it shouldn't take
> more than a few steps. Could someone show it (the formal derivation)
> here?
CB says that CBL is a universal system.
How does CBL show that A+(B+C)=(A+B)+C, over the natural numbers?
Be careful not to add any additional ad hoc axioms to the 8
universal rules of inference.
> C-B
>
--
Alan Smaill
Arturo Magidin
I'm not "claiming" something. It is a fact that the "axioms of PA" are
in fact ->theorems<- of ZF.
The axiom of infinity guarantees the existence of a set that contains
{}, and contains the successor of each of its elements.
From such a set A, we can define the set N to be the intersection of
all subsets of A which contain {} and contain the successor of each of
its elements.
It is then a theorem that if B is ANY set that contains {} and
contains the successor of each of its elements, then the intersection
of all subsets of B which contain {} and contain the successor of each
of its elements is in fact equal to N, so that N is well-defined and
does not depend on the choice of A.
Then the "Peano axioms" are theorems of ZF:
1. {} is in N follows by construction;
2. If n is in N, then s(n) is in N follows by construction;
5. If S is a subset of N such that {} is in S, and for every n in N,
if n is in S then s(n) is in S, then S=N follows by construction of N;
3. If n is in N, then s(n) is not equal to {} follows by definition of
s(X) for any set X, since S(X) = X \/ {X}, hence is not empty.
4. If n and m are in N, and s(n)=s(m), then n=m is the only nontrivial
one, but it is still a theorem of Z.
First you prove that for every n in N, if x is in n, then n is not a
subset of x. This can be done without invoking regularity, given the
construction of N, using induction:
Let S be the set of all n in N such that n is not a subset of any of
its elements. Then 0 is in S, since 0 satisfies the
property. Suppose that n is in S; since n is a subset of n, it
follows that n is not an element of n, so s(n)=n \/ {n} is not a
subset of n (since n is an element of s(n) but not of n). If s(n)
were a subset of an element of s(n), then it would therefore be a
subset of an x in n. But n is a subset of s(n), hence n would be a
subset of s(n), which would be a subset of x, which is an element of
n; this contradicts the assumption that n is in S, hence s(n) is not
a subset of any element of x, and is not a subset of n, hence s(n)
is not a subset of any element of s(n). Thus, if n is in S, then
s(n) is in S; By 5, S=N.
Then you prove that elements of N are transitive; that is, if n is in
N, and m is an element of n, then m is a subset of m.
This is also done using 5. Let S be the set of all n in N which are
transitive. Then 0 is in S vacuously. Assume that n is in S. If x is
an element of s(n) = n\/{n}, then either x is in n, or x=n. If x=n,
then x is a subset of s(n), since n is a subset of s(n) by
construction. If x is an element of n, then x is a subset of n since
n is in S, hence x is a subset of n, n is a subset of s(n), and so x
is a subset of s(n). Therefore, s(n) is in S. By 5, S=N, so every
natural number is transitive.
Now we can prove the 4th "Peano Axiom". Suppose that n,m are in N, and
s(n)=s(m). Since n is an element of s(n), then n is an element of
s(m) = m \/ {m}. So either n=m, and we are done, or else n is an
element of m. Symmetrically, since m is in s(m), it is in s(n)=n\/{n},
hence m = n, or else m is an element of n. If n is an element of m
and m is an element of n, then n would be a subset of an element of n,
which we proved was impossible. Therefore, we cannot have both "m is
an element of n" and "n is an element of m". Therefore, we must have
n=m, proving the "4th Peano Axiom" as a theorem of ZF.
So the 5 Peano Axioms are ->theorems<- of ZF.
>then I will have to
>propose a theorem outside of Number Theory.
In other words, you are just looking for a question which is
sufficiently hard to explain easily so you can claim some kind of
pyrrhic victory, rather than trying to actually learn something? I
should have guessed.
Charlie-Boo
You're doing what everyone else is doing: using an axiom from another
domain that parallels Arithmetic. Addition, Union, and Disjunction are
"recursive functions away from each other" (my term.) You have not
shown a formal derivation. (ZFC states what sets exist, not which set
definitions define the same sets!)
Now an aside: How do we abstract all of these into a higher level
(LOA)?
Answer: I call a function a "set function" if the same result is
obtained when it is applied to all elements of a (generally finite) set
in any order. This is easily proved to be associative, commutative,
etc. from this one axiom.
So we need to relate these 3 functions to this new concept.
> So
>
> (AUB)UC = {x | x in (AUB) or (x in C) }
> = {x | ((x in A) or (x in B)) or (x in C)}
> = {x | x in A or ((x in B) or (x in C)) } (Extension)
You're using an Axiom of The Associativity of Disjunction, not ZFC.
(Just like I described at the beginning of this thread.)
C-B
Charlie-Boo
Proof? Just think of models of ZFC in which addition (defined as it is
in ZFC) is NOT associative.
C-B
Arturo Magidin
Oh, well. In that case, you are "an idiot" (my term).
>You have not
>shown a formal derivation. (ZFC states what sets exist, not which set
>definitions define the same sets!)
ZFC not only states what sets exists. It also states a condition under
which sets are "the same." It's called the Axiom of Extension.
ZF states that two sets are the same if they have the same
elements. It also states that given a set, one can use certain types
of expressions to define another set (separation).
Those two already imply that if two expressions which are distinct are
equivalent in first order logic, then the two expressions will yield
the same set (by extension).
But you aren't really asking questions. You are pontificating; and you
are making false claims. Good for you. As Darrow said to Bryan:
--
======================================================================
Bryan: "When you display my ignorance, could you not give me the
facts so I would not be ignorant any longer? [...]"
Darrow: "You know, some of us might get the facts and still be
ignorant."
-- The examination of William Jennings Bryan by Clarence Darrow,
during the Scopes Trial. (From _Attorney for the Damned_,
edited by
Arthur Weinberg)
======================================================================
Arturo Magidin
magidin-at-member-ams-org
Arturo Magidin
Given a set Z, the Axiom of Union guarantees that
{x | exists y (x in y and y in Z)}
is a set.
Given sets X and Y, the Axiom of Pairing guarantees that {X,Y} is a
set. (Other axiomatizations only guarantee the existence of a set A
such that X in A and Y in A; in that case, you use Separation to
obtain the set {X,Y} by using the property "p = X or p=Y").
So from X and Y, we get Z={X,Y}, and from Z we get the set
A = {x | exists y ( x in y and y in {X,Y})}.
From extension you have that "y in {X,Y}" is equivalent to "y=X or
y=Y". And then you have
A = {x | exists y ( x in y and (y=X or y=Y) )}
and from basic first order logic you get that this is the same as
A = {x | exists y ( (x is in y and y=X) or (x is in y and y=Y))}
and again, extension gives you that this is equivalent to
A = {x | x is in X or x is in Y}.
> Just think of models of ZFC in which addition (defined as it is
>in ZFC) is NOT associative.
If addition of cardinals is defined "as it is in ZFC", then it ->is<-
associated. If it is "not associative", then it is not "defined as it
is in ZFC". I would have thought that was obvious. Maybe it's just
because I tried to learn, instead of pontificating on what I think is
true, reality notwithstanding?
--
======================================================================
"I have yet to encounter a problem, no matter how complicated,
that when you look at it from the right angle does not become
still more complicated."
--- Poul Anderson
======================================================================
Arturo Magidin
magidin-at-member-ams-org
MoeBlee
Charlie-Boo wrote:
> You're using an Axiom of The Associativity of Disjunction, not ZFC.
> (Just like I described at the beginning of this thread.)
Association of disjunction is not usually an axiom of sentential logic
but is a theorem of sentential logic.
OF COURSE with formal Z set theory we make whatever use of first order
logic (which itself subsumes sentential logic) we want. That is on PAGE
ONE of many basic set theory textbooks. That you don't understand that
reveals what people have been saying all along - you know virually
nothing in the subject of set theory and mathematical logic. You are
saddled with basic misunderstandings that cause you to have a plainly
incompetent involvement in the subject.
MoeBlee