A Contradiction in Terms
RussellE
I can derive a contradiction in the language of
MA by assuming MA has an infinite model.
The axioms of MA are the same as those of
Peano Arithmetic (PA), except I replace
Ax (S(x) != 0) with its negation:
Ex (S(x) = 0)
http://en.wikipedia.org/wiki/Peano_axioms#First-order_theory_of_arithmetic
I can derive the following theorems in MA:
( S(0) = 0 ) -> Ax ( x=0 )
( S(S(0) ) = 0) -> Ax ( x=0 or x=S(0) )
( S(S(S(0))) = 0 ) -> Ax ( x=0 or x=S(0) or x=S(S(0)) )
...
I can derive such a theorem for any
closed term in the language of MA.
What these theorems tell us is if
S(x)=0 and x can be represented as
a closed term in the language of MA
(x is nameable), then our model of MA
is finite.
Any infinite model of a first order
theory can have un-nameable individuals.
(Thanks to the various people who
explained this to me.)
Assume MA has an infinite model.
What makes MA different from PA
is we can identify at least one
of these un-nameable individuals.
We know Ex (S(x)=0) and x is
un-nameable.
This is enough to derive the
contradiction P and ~P.
Let P = Ex (S(x) = 0)
and ~P = Ax (S(x) != 0)
P is an axiom of MA.
I can use induction to prove ~P:
( S(x) != 0 ) -> ( S(x+1) != 0 )
This follows from the theorems
I give above and the assumption
our model of MA is infinite.
This statement is true in
any infinite model of MA
for any closed term of MA.
The first order induction axiom schema
allows me to prove:
Ax (S(x) != 0)
This shows the assumption MA has an
infinite model leads to contradiction.
Russell
- Integers are an illusion
William Elliot
> I describe a theory of Modular Arithmetic (MA).
> I can derive a contradiction in the language of
> MA by assuming MA has an infinite model.
>
You've done better than that.
Even without assuming an infinite model, you've shown MA is inconsistent.
Hurray and alleluia! However, before we celebrate, give the details
how you proved ~P, ie Ax (S(x) /= 0). In particular how did you show
S(0) /= 0 which is needed to start the induction.
Marshall
> I describe a theory of Modular Arithmetic (MA).
> I can derive a contradiction in the language of
> MA by assuming MA has an infinite model.
>
> The axioms of MA are the same as those of
> Peano Arithmetic (PA), except I replace
> Ax (S(x) != 0) with its negation:
>
> Ex (S(x) = 0)
>
>
> I can derive the following theorems in MA:
>
> ( S(0) = 0 ) -> Ax ( x=0 )
> ( S(S(0) ) = 0) -> Ax ( x=0 or x=S(0) )
> ( S(S(S(0))) = 0 ) -> Ax ( x=0 or x=S(0) or x=S(S(0)) )
> ...
>
> I can derive such a theorem for any
> closed term in the language of MA.
Can you? I notice you omitted the derivation.
In fact, I believe that, for example:
S(S(0)) = 0 -> (x = 0 | x = S(0)).
is independent of your axioms. That is, while
it is true that there are models of your axioms
where the above is true, there are also models
of your axioms where the above is false.
If I've gotten that correct, then we can't go any
further with your post, since the rest of it depends
on this.
Perhaps you were labeling the above as theorems
on the observation that there is a model in which
they are true. But that's not sufficient to establish
them as theorems of your theory; you also have
to establish that there are NO models in which
they are false.
This is what I used for your theorems:
exists x S(x) = 0.
S(x) = S(y) -> x = y.
x + 0 = x.
x + S(y) = S(x+y).
x * 0 = 0.
x * S(y) = (x * y) + x.
plus induction. Good? I copied it straight from the
Wikipedia section you referenced.
> Any infinite model of a first order
> theory can have un-nameable individuals.
> (Thanks to the various people who
> explained this to me.)
(Actually I don't think there's any requirement that
the model be infinite to have unnameable members.)
Of course it's possible I've made a mistake.
Marshall
Tim Little
> (Actually I don't think there's any requirement that
> the model be infinite to have unnameable members.)
True, a no-axiom theory has finite models, but isn't capable of naming
any members at all.
--
Tim
Marshall
> On 2011-06-16, Marshall <marshall.spi...@gmail.com> wrote:
>
> > (Actually I don't think there's any requirement that
> > the model be infinite to have unnameable members.)
>
> True, a no-axiom theory has finite models, but isn't capable of naming
> any members at all.
That is WAY better than the example I had in my head.
Marshall
Jesse F. Hughes
I thought earlier you were dropping induction from your axioms.
> This follows from the theorems
> I give above and the assumption
> our model of MA is infinite.
Let's see that proof. It's not obvious to me how it goes, given the
axioms you refer to.
So, assume S(x) != 0 and show that S(S(x)) != 0 using the following
axioms.
* 0 != S(x_1)
* S(x_1) = S(x_2) -> x_1 = x_2
* x_1 + 0 = x_1
* x_1 + S(x_2) = S(x_1 + x_2)
* x_1 * 0 = 0
* x_1 * S(x_2) = x_1* x_2 + x_1
(Ay)(P(0,y) & (Ax)( P(x,y)-> P(S(x),y)) -> (Ax)P(x,y))
Maybe I'm missing something, but I don't see any such proof. (What
would the existence of such a proof have to do with the assumption that
there is an infinite model anyway?)
> This statement is true in
> any infinite model of MA
> for any closed term of MA.
>
> The first order induction axiom schema
> allows me to prove:
>
> Ax (S(x) != 0)
>
> This shows the assumption MA has an
> infinite model leads to contradiction.
If you could prove (Ax)(S(x) != 0), then MA doesn't have any finite
models either.
--
"So now, The Hammer is here, and with it, the end of days. The world will be
destroyed, and then remade, as foretold. You will be lost, with your
children, and then there will be others, and one day they will be tested, and
will pass, but that is another story." --James S Harris gets a bit excited.
Jesse F. Hughes
> So, assume S(x) != 0 and show that S(S(x)) != 0 using the following
> axioms.
>
> * 0 != S(x_1)
Oops! Of course, that should be (Ex)(Sx = 0).
Sorry.
> * S(x_1) = S(x_2) -> x_1 = x_2
> * x_1 + 0 = x_1
> * x_1 + S(x_2) = S(x_1 + x_2)
> * x_1 * 0 = 0
> * x_1 * S(x_2) = x_1* x_2 + x_1
> (Ay)(P(0,y) & (Ax)( P(x,y)-> P(S(x),y)) -> (Ax)P(x,y))
--
Jesse F. Hughes
"I post for many reasons [...] and there's no reason to think that
I'll stop." -- James S. Harris
RussellE
Assume: s0 = 0
(s0 = 0) -> (ss0 = s0) -> (ss0 = 0)
(s0 = 0) -> Ax x=0
Assume: ss0 = 0
(ss0 = 0) -> (sss0 = s0)
(sss0 = s0) -> (ssss0 = ss0 = 0)
(ssss0 = ss0) -> (sssss0 = sss0 = s0)
(ss0 = 0) -> Ax (x=0 or x=s0)
Russell
- 2 many 2 count
RussellE
> On Jun 15, 7:28 pm, Marshall <marshall.spi...@gmail.com> wrote:
> > > I can derive such a theorem for any
> > > closed term in the language of MA.
>
> > Can you? I notice you omitted the derivation.
> > In fact, I believe that, for example:
>
> > S(S(0)) = 0 -> (x = 0 | x = S(0)).
>
> > is independent of your axioms.
>
> S(x) = S(y) -> x = y
I am actually using
x = y -> S(x) = S(y)
This is an axiom of equality.
I need to include axioms of
equality in MA.
Marshall
>
> I need to include axioms of
> equality in MA.
Well, *I* don't need you to do that, but it can't hurt.
Marshall
Marshall
I'll assume that this is supposed to be two proofs for your
first two purported theorems in the sequence.
Let's look at that first one:
1. Assume: s0 = 0
2. (s0 = 0) -> (ss0 = s0) -> (ss0 = 0)
3. (s0 = 0) -> Ax x=0
1. you start by assuming something that might or might not
be true. So even if you proceed with valid reasoning from there,
you end up with something that itself might or might not
be true.
2. I don't see the point of this step.
3. I don't see the justification for this step. In fact it doesn't
appear to be necessarily true even if we accept your step 1.
Marshall
Tim Little
> I describe a theory of Modular Arithmetic (MA).
> I can derive a contradiction in the language of
> MA by assuming MA has an infinite model.
>
> The axioms of MA are the same as those of
> Peano Arithmetic (PA), except I replace
> Ax (S(x) != 0) with its negation:
>
> Ex (S(x) = 0)
>
> http://en.wikipedia.org/wiki/Peano_axioms#First-order_theory_of_arithmetic
>
> I can derive the following theorems in MA:
>
> ( S(0) = 0 ) -> Ax ( x=0 )
What is your derivation for that? The rest will have to wait.
--
Tim
David Hartley
<t...@little-possums.net> writes
For any x, if x = 0 then S(x) = S(0) = 0
By induction, Ax(x=0).
Similarly, if S(<n>) = 0 (where <n> = S(S(...(0)...)) with n occurrences
of S) then
Ax (x = 0 or x = <1> or ... or x = <n>)
--
David Hartley
Tim Little
> Suppose S(0) = 0
> For any x, if x = 0 then S(x) = S(0) = 0
>
> By induction, Ax(x=0).
Ah yes, S(0) = 0 -> [S(x) = 0 -> S(S(x)) = S(0) = 0]. Thanks.
--
Tim
Tim Little
> I can derive a contradiction in the language of
> MA by assuming MA has an infinite model.
>
> The axioms of MA are the same as those of
> Peano Arithmetic (PA), except I replace
> Ax (S(x) != 0) with its negation:
>
> Ex (S(x) = 0)
>
> http://en.wikipedia.org/wiki/Peano_axioms#First-order_theory_of_arithmetic
>
> I can derive the following theorems in MA:
>
> ( S(0) = 0 ) -> Ax ( x=0 )
> ( S(S(0) ) = 0) -> Ax ( x=0 or x=S(0) )
> ( S(S(S(0))) = 0 ) -> Ax ( x=0 or x=S(0) or x=S(S(0)) )
> ...
>
> I can derive such a theorem for any closed term in the language of
> MA. What these theorems tell us is if S(x)=0 and x can be
> represented as a closed term in the language of MA (x is nameable),
> then our model of MA is finite.
I disagree that "x can be represented as a closed term" is identical
with "x is nameable". A 1-place predicate P can be said to name an
object if E!x P(x) is a theorem. That is, it is provable that one and
only one object in each model satisfies P.
In particular, the predicate "S(x) = 0" names an object in MA
(assuming MA has any models), but there may be no finite expression
involving 0, S, + or * that evaluates to x.
> Any infinite model of a first order theory can have un-nameable
> individuals. (Thanks to the various people who explained this to
> me.)
I think you need to re-read their explanations. "Naming" does not
mean what you think it means.
> Assume MA has an infinite model. What makes MA different from PA is
> we can identify at least one of these un-nameable individuals. We
> know Ex (S(x)=0) and x is un-nameable.
So let's assume that when you say "un-nameable" you really mean "not
expressible as S(...S(0)) with a finite sequence of S's", instead of
really not nameable.
> This is enough to derive the contradiction P and ~P.
No, it isn't.
> Let P = Ex (S(x) = 0)
> and ~P = Ax (S(x) != 0)
>
> P is an axiom of MA.
> I can use induction to prove ~P:
No, you can't. I doubt that you can even express the proposition "MA
having an infinite model implies ~P" in the language of MA. You
certainly can't use the implied quantification over infinitely many
theorems that you appear to want to do for the induction.
--
Tim
David Libert
Similarly any finite loop over 0. So if a model has a finite loop over
0 then that loop is the entire model.
For every positive integer n, Z/n is a model of this theory. Ie
Z/n ring axioms give the equations on S + * and the model is finite so
the premises of the induction axiom iteratively imply as iteration of
S on 0 satisfies the property, so everything in the model does, hence
the induction axioms.
So the theory has abritrarily large finite models Z/n n positive
integer.
So by compactness the theory has an infinite model, contradicting
Russell's claim from the base of this thread.
Russell's axiom assumes Ex(S(x)=0). Obviously for every y
S(y) has the property Ex(S(x)=S(y)) ie take x = y.
So the 0 and successor clauses are supported for Ex(S(x)=y).
So by induction All y E x S(x)=y .
In particular, 0 must have interated predecessors in any model.
We already noted, if the predecessor of 0 loops back from a finite
successor of 0, then the model is finite.
So in any infinite model, as noted which exist, 0 must be included
in a Z chain of distinct elements.
On this Z chain, the axioms on S, +, * determine that these
operations on the Z chain must be a isomorhic copy of the usual
Z structure.
Can there be only this one Z chain?
It is a theorem of regular number theory that any positive integer
can be expressed as a sum of 4 or fewer squares.
So in the standard Z structure on S, +, * being nonegative in
the usual sense is first order definable as being a sum of 4 or fewer
squares.
But in Z, being non-negative is true of 0 and is closed under
successor.
So in usual Z, thos definable property is a counterexample to
induction.
So an infinite model must include a Z chain, but must also include
more.
As noted above, every element has a predecessor.
Given a model, we can redo by induction the usual theorem that
the fucntions x |-> 2x and x|-> 2x + 1 give definable bijections
of the universe into 2 disjoint copies of itself.
Similarly for real world finite n replacing 2, as a schematum over n.
So with this, I think we can do things like inside a model define
2 disjoint copies of the universe, and make term models the free sum
of the term models. I think by coding finite sequences into this
theory was can also consider collapses of such defined model by
congruences.
And the resulting definable structure inside the model, will still
statisfy induction, since the outer model did.
In this way i think we can get models where predecessor is not
unique.
On the other hand, we can also add to the original theory that
predecessor is unique, and still have all the Z/n models and
apply compactness.
So we can also get infinite models of the base theory where
predecessor is unique.
What do these models look like? There is the Z chain including
0, which by the unique predecessors claim is uniquely determined.
Everywhere else in the model predecessors exist and are unique
also, so these each lie in a Z chain or a finite loop.
Given such a section A and an element of it a, a+a and a*a
determine b+c and b*c for b,c interated S of a,
by the axioms.
For finite loops if they exist, that determines everything.
Oh yes even for Z chains, for b,c also predeccessors,
since we are assuming predeccessors are unique, + anyway
traces backwards as uniquely determined.
I guess by induction + and * are unique in each coordinate
ie x + y = z has at most one solution y for each x.z and
similarly x * y = z.
So I think once you pick a+a and a*a in one of these nonstandard
everything else is unque on that Z chain or loop.
There will be a lot of complexity how +, * operate between those,
ie + or * between diffrent alternatives.
There is Tennebaum's theorem. Any interpretation of "+" and "*"
over omega satifying PA and not ismorpphic to standard PA model
has those interpretations non-recursive.
Maybe something similar applies here to this theory.
I said Z chains and loops because I can't rule out either.
Actually a Z chain can be obtained in a constructed model by
adding axioms for a nonstandard element and that the Z chain doesn't
loop, in the compactness agrument.
Maybe a loop can be obtained by quotienting a model, like I wrote
above to get non unique predecessors.
--
David Libert ah...@FreeNet.Carleton.CA
David Libert
[Deletion]
> As noted above, every element has a predecessor.
>
> Given a model, we can redo by induction the usual theorem that
> the fucntions x |-> 2x and x|-> 2x + 1 give definable bijections
> of the universe into 2 disjoint copies of itself.
>
> Similarly for real world finite n replacing 2, as a schematum over n.
>
> So with this, I think we can do things like inside a model define
> 2 disjoint copies of the universe, and make term models the free sum
> of the term models. I think by coding finite sequences into this
> theory was can also consider collapses of such defined model by
> congruences.
>
> And the resulting definable structure inside the model, will still
> statisfy induction, since the outer model did.
Not so clear. If I add new fake x' elements and I had old ones x,
I get new elements like x + x', that's why I said to do term models.
Then we can get back the equation axioms of the theory by a simply
quotienting.
But getting back induction might need more quotienting and it
is not obiouvs that it will be simple.
For now just forget trying constructions like this
>
> In this way i think we can get models where predecessor is not
> unique.
Opps, I forgot successor 1-1 is a PA axiom, so in Russell's theory.
I was incorrectly thinking usual PA traced that all back to no
predecessor for 0.
So the simple case below of unique predecessors is just for free
from the axioms. And my first intended use of the model contruction
method above is unecessary.
> On the other hand, we can also add to the original theory that
> predecessor is unique, and still have all the Z/n models and
> apply compactness.
>
> So we can also get infinite models of the base theory where
> predecessor is unique.
>
> What do these models look like? There is the Z chain including
> 0, which by the unique predecessors claim is uniquely determined.
>
> Everywhere else in the model predecessors exist and are unique
> also, so these each lie in a Z chain or a finite loop.
I will comment on the finite loops below
> Given such a section A and an element of it a, a+a and a*a
> determine b+c and b*c for b,c interated S of a,
> by the axioms.
>
> For finite loops if they exist, that determines everything.
>
> Oh yes even for Z chains, for b,c also predeccessors,
> since we are assuming predeccessors are unique, + anyway
> traces backwards as uniquely determined.
>
> I guess by induction + and * are unique in each coordinate
> ie x + y = z has at most one solution y for each x.z and
> similarly x * y = z.
>
> So I think once you pick a+a and a*a in one of these nonstandard
> everything else is unque on that Z chain or loop.
>
> There will be a lot of complexity how +, * operate between those,
> ie + or * between diffrent alternatives.
>
> There is Tennebaum's theorem. Any interpretation of "+" and "*"
> over omega satifying PA and not ismorpphic to standard PA model
> has those interpretations non-recursive.
The proof of Tennebaum's theorem involves prime factorization of
numbers, and uses the primitive recursive function enumerating
all primes.
In usual PA, to get defintions of functions by primitive recusrion,
you code seuqneces, using the Chinease remainder theorem which is
proved by induction, specifically an application of it for a finlte
arithmetic sequence of pairwise coprime elements, all that proved
by induction.
I think all that still holds in usual Z, and the PA induction proofs
could be redone in Russell's theory. And then after that everything
should go through. I don't think any of that depends on being in an
axiomatic version of "omega" instead of "Z".
So I think we would get back Tennebaum's theorem for Russell's
theory.
> Maybe something similar applies here to this theory.
>
> I said Z chains and loops because I can't rule out either.
>
> Actually a Z chain can be obtained in a constructed model by
> adding axioms for a nonstandard element and that the Z chain doesn't
> loop, in the compactness agrument.
>
> Maybe a loop can be obtained by quotienting a model, like I wrote
> above to get non unique predecessors.
First off, that quotienting construction is now withdrawn.
But beyond that I think I can directyl rule out finite loops.
Since successors are unique, I think the following can be proved
by induction for any finite iteration of S. I will write it
as 3 S's applied but each formula with those 3 replaced by aother
finite iteration is similarly provable:
All x All y SSS(x) + y = x + SSS(y).
So if we had a nonstandard y from another loop, with a finite loop,
again I will write out the case y = SSS(y),
from this we get for x standard, ie the base Z chain with 0:
SSS(x) + y = x + SSS(y) = x + y .
Then we also have by the cancellation law provable by induction
SSS(x) = x.
Ie a loop off to the side induces a same length loop in the base
chain.
But the base chain is a Z chain in an infinite model, as discussed
last post.
So predeccssors are unique, and we are back to only Z chains.
Wiht predeccors unique + restricted to bpth arguments in a side
Z chain A is completely determined by a + a for any a in A.
And all b + c values for b,x in same A go to same Z chain
as A.
So there is a doubling functioning sending Z chain A to the
Z chain of a + a for a in A.
+ restricted to single Z chains is completely determined by this
doubling function on Z chains and an evaluation of a + a on
one a in argument A.
+ between different Z chains is more complicated.
And * even on one Z chain is compicated, as it depends how
+ combines different chains.
If I am right about Tennebaum's theorem, this is where we
get that complexity. Even in just the + part.
--
David Libert ah...@FreeNet.Carleton.CA
RussellE
Theorems of MA with Identity:
(x=0 -> x+1=0) -> Ax (x=0)
(x=0 or x=S(0) -> x+1=0 or x+1=S(0)) -> Ax (x=0 or x=S(0))
...
Last but not least:
(S(x) != 0 -> S(x+1) != 0) -> Ax (S(x) != 0)
Now we need an infinite model of the natural numbers
where 0 isn't the successor of any natural number
(which would prove the model is finite) and
there is a natural number with successor 0.
Otherwise we can prove a contradiction.
MoeBlee
> I describe a theory of Modular Arithmetic (MA).
> I can derive a contradiction in the language of
> MA
I guess you mean "derive a contradiction in MA".
> by assuming MA has an infinite model.
If you can derive a contradiction in MA, then you can do it
irrespective of any assumptions about models.
MoeBlee
Jesse F. Hughes
> Theorems of MA with Identity:
>
> (x=0 -> x+1=0) -> Ax (x=0)
> (x=0 or x=S(0) -> x+1=0 or x+1=S(0)) -> Ax (x=0 or x=S(0))
> ...
It might be nice if you would choose either +1 or S as a notation and
stop switching back and forth willy-nilly.
> Last but not least:
>
> (S(x) != 0 -> S(x+1) != 0) -> Ax (S(x) != 0)
>
Well, this doesn't appear to be true. After all, in a model of just one
element, 0, and where S(0) = 0 (necessarily), then the antecedent is
(trivially) true, but the consequent is false.
So I don't think you can prove this at all.
What you can prove is, of course,
( S(0) != 0 & (Ax)(S(x) != 0 -> S(S(x) != 0)) ) ->
Ax (S(x) != 0)
But so what if you prove this? This isn't so useful unless you can
prove (Ax)(S(x) != 0 -> S(S(x) != 0)).
>
> Now we need an infinite model of the natural numbers
> where 0 isn't the successor of any natural number
> (which would prove the model is finite) and
> there is a natural number with successor 0.
Er, hm.
> Otherwise we can prove a contradiction.
--
"Maya Nahib is not a Checotah Indian! [...] Maya Nahib is an Englishman!"
"Are you telling us that a civilized white man could kill and ravish
and destroy with all the brutality of a savage?"
-- Adventures by Morse radio program (1944)
Tim Little
> In this way i think we can get models where predecessor is not
> unique.
One of the axioms is Axy S(x) = S(y) => x = y. If you define a
predecessor of w to be any object x such that S(x) = w, then this
directly states the uniqueness of predecessors.
> There is Tennebaum's theorem. Any interpretation of "+" and "*"
> over omega satifying PA and not ismorpphic to standard PA model
> has those interpretations non-recursive.
>
> Maybe something similar applies here to this theory.
I expect so, yes.
--
Tim
Frederick Williams
>
> Now we need an infinite model of the natural numbers
> where 0 isn't the successor of any natural number
> (which would prove the model is finite) and
> there is a natural number with successor 0.
> Otherwise we can prove a contradiction.
"Otherwise"? What you wrote is already contradictory.
--
When a true genius appears in the world, you may know him by
this sign, that the dunces are all in confederacy against him.
Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting
RussellE
> RussellE <reaste...@gmail.com> writes:
> > Theorems of MA with Identity:
>
> > (x=0 -> x+1=0) -> Ax (x=0)
> > (x=0 or x=S(0) -> x+1=0 or x+1=S(0)) -> Ax (x=0 or x=S(0))
> > ...
>
> It might be nice if you would choose either +1 or S as a notation and
> stop switching back and forth willy-nilly.
>
> > Last but not least:
>
> > (S(x) != 0 -> S(x+1) != 0) -> Ax (S(x) != 0)
>
> Well, this doesn't appear to be true. After all, in a model of just one
> element, 0, and where S(0) = 0 (necessarily), then the antecedent is
> (trivially) true, but the consequent is false.
>
> So I don't think you can prove this at all.
>
> What you can prove is, of course,
>
> ( S(0) != 0 & (Ax)(S(x) != 0 -> S(S(x) != 0)) ) ->
> Ax (S(x) != 0)
>
> But so what if you prove this? This isn't so useful unless you can
> prove (Ax)(S(x) != 0 -> S(S(x) != 0)).
If (Ax)(S(x) != 0 -> S(S(x) != 0)) isn't true then
there must exist S(x) !=0 and S(S(x)) = 0.
This allows one of the other theorems to prove the model is finite.
RussellE
wrote:
> RussellE wrote:
>
> > Now we need an infinite model of the natural numbers
> > where 0 isn't the successor of any natural number
> > (which would prove the model is finite) and
> > there is a natural number with successor 0.
> > Otherwise we can prove a contradiction.
>
> "Otherwise"? What you wrote is already contradictory.
Its only a contradiction if we assume MA has an
infinite model. MA has finite models.
David Libert
> On Jun 16, 6:03=A0pm, "Jesse F. Hughes" <je...@phiwumbda.org> wrote:
>> RussellE <reaste...@gmail.com> writes:
>> > Theorems of MA with Identity:
>>
>> > (x=3D0 or x=3DS(0) -> x+1=3D0 or x+1=3DS(0)) -> Ax (x=3D0 or x=3DS(0))
>> > ...
>>
>> It might be nice if you would choose either +1 or S as a notation and
>> stop switching back and forth willy-nilly.
>>
>> > Last but not least:
>>
>>
>> Well, this doesn't appear to be true. =A0After all, in a model of just on=
> e
>> element, 0, and where S(0) =3D 0 (necessarily), then the antecedent is
>> (trivially) true, but the consequent is false.
>>
>> So I don't think you can prove this at all.
>>
>> What you can prove is, of course,
>>
>> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0Ax (S(x) !=3D 0)
>>
>> But so what if you prove this? =A0This isn't so useful unless you can
>> prove (Ax)(S(x) !=3D 0 -> S(S(x) !=3D 0)).
>
> If (Ax)(S(x) !=3D 0 -> S(S(x) !=3D 0)) isn't true then
> there must exist S(x) !=3D0 and S(S(x)) =3D 0.
>
> This allows one of the other theorems to prove the model is finite.
>
>
> Russell
> - 2 many 2 count
In standard FOL semantics MA has an infinite model as discussed in
[1] David Libert "Re: A Contradiction in Terms"
sci.logic, sci.math June 16, 2011
http://groups.google.com/group/sci.logic/msg/9bd08626f435b6a1
[2] David Libert "Re: A Contradiction in Terms"
sci.logic June 16, 2011
http://groups.google.com/group/sci.logic/msg/1eaa9cd91bbe5d6e
I forgot to crosspost [2] to sci.math.
In that model 0 is in a Z chain of S successors, so
(Ax)(S(x) != 0 -> S(S(x) != 0))
is false in that model.
Regarding
> If (Ax)(S(x) != 0 -> S(S(x) != 0)) isn't true then
> there must exist S(x) != and S(S(x)) = 0
Yes there is such an x.
The post continues from there:
> This allows one of the other theorems to prove the model is finite.
Which is not true for standard FOL semantics since [1]-[2] got
a model like this which is infinite.
Here is another version which is probably closer to what you are thinking of.
Let us define a nonstandard semantics for the same language of first order.
The semantics will be based on the signature of the language in question.
We will define the quantifiers to just range over closed terms from the
signature, that is those built by function symbols in nested application
of appropriate arity to constant symbols. More exactly, in a structure the
quantifiers will range over the interpetation in the structure of all such
terms.
We only need define satidfaction for variables interpreted as such
evaluations of terms.
The atomic and inductive Boolean clauses in the definition of satisfaction
are as usual.
This is probably similar to what you has in mind. When you write a natural
number, you probably were thining of a finite iteration of S over 0.
By the way, this semantics would make quantification empty over languages
with no contant symbols.
Given any usual structure for a first order langauge, this smeantics is
equvalent to the suual FOL language semantics on the term substructure of the
original structure, ie with universe all interpretations of closed terms.
So this other satisfaction definition only depends on the term substructure
of a structre.
(These last comments if we allow the empty structyre for langauges without
contant symbols).
So again allowing empty structures, an equivalent restatement of this
alternative semantics is we only consider term structures, those with every element
a denotation of some closed term, and for these structures we use standar FOL
semantics
With this 2nd restatement of the semantics your claim is supported. There are no
finite term models of MA.
Comments regarding this alternative semantics. The semantics induces a
sematic entailment relation as usual, for whether a set of formulas S entails
a formula phi : S |= phi.
We can make a sgnatire for this logic of the PA language S, +, * as you
did and also a new unnary predicate symbol A.
For any first order over S, +, *, A formula phi we can ask which terms t
in the language have
PA |= phi(t).
Any term model is isomorphic to the standard PA model.
The definition of |= quantifies over all term models, so over all
interpretions of A.
So PA |= phi(t) iff the interpretaion of t satisfies (usual FOL
semantics) all A phi(t) .
So from |= we can reduce any Pi^1_1 formula.
On the other hand, the definition of |= , ture in all term models
where a term model can be formalized as a predicate over integers (using
paring functions in iteration possibly), this definition is formalizable
as a Pi^1_1 definition.
So |= over Pi^1_1 definable premise sets is complexity exactly
complete Pi^1_1.
So we have a smewantics for this alternative logic, but no recursively
presented proof system for it.
As I wrote this I just remembered there was a thread about a logic
like this:
[3] 6 authors "alternative 1st-order quantifier semantics"
sci.logic Dec 14-15, 2009
http://groups.google.com/group/sci.logic/browse_thread/thread/41da296d93c53b08/40cac2e8093186e7
--
David Libert ah...@FreeNet.Carleton.CA
RussellE
>
> --
> David Libert ah...@FreeNet.Carleton.CA- Hide quoted text -
>
> - Show quoted text -
Thank you for your excellent explanation.
I am having a problem with the first-order induction axiom schema.
Does induction apply to "un-namable" individuals?
Wikipedia says there is an induction axiom for
every definable subset. I assume this means
every definable inductive set.
How can negative integers be defined as
elements of an inductive set in MA?
If negative numbers can't be part of
an inductive set then I can prove
(Ax)(S(x) != 0 -> S(S(x) != 0))
is true in any infinite "model" of MA.
I can prove it is true of any definable
inductive set.
Uergil
<d347d6ba-d886-45a2...@r2g2000vbj.googlegroups.com>,
RussellE <reas...@gmail.com> wrote:
But the negative integers form a set that, with a slightly modified
"successor" function, is just as "inductive" as the set of positive
integers
> Russell
> - 2 many 2 count
--
"Ignorance is preferable to error, and he is less
remote from the- truth who believes nothing than
he who believes what is wrong.
Thomas Jefferson
Jesse F. Hughes
First, let us assume that in your model (and contrary to what David
Libert has proved), there is no element x such that
S(x) !=0 and S(S(x)) = 0.
Then
(Ax)(S(x) != 0 -> S(S(x) != 0)) (*)
would be true *in that model*. So what? It does not follow that (*) is
provable from your axioms. You are confusing true in a model with
provability.
If a theory T proves P, then P is true in every model. If, on the other
hand, P is true in some models and not others (like you allege (*) to
be), then T does not prove P (nor does T prove ~P).
Thus, (*) is not a theorem and you have not proved MA inconsistent.
> This allows one of the other theorems to prove the model is finite.
--
"The needs of the many outweigh the needs of the few [...] I must
make the same choice as those who came before me without regard to the
impact today, for the sake of the children of humanity, the children
of tomorrow." -- JSH channels Spock and generic politicians everywhere
RussellE
I'm not proving MA is inconsistent.
MA has finite models and there is a finitistic proof
of the consistency of MA.
I prove MA has no infinite models.
While (*) is not a theorem of MA, this is:
( (S(0) != 0) AND (Ax ( (S(x) != 0) -> (S(S(x)) != 0) ) ) )
-> Ax (S(x) != 0)
The first order axioms of induction are axioms.
They are written in the language of MA.
They can only refer to terms in the language of MA.
There is an axiom for every definable inductive set.
I do not include the axioms of set theory in MA.
When I say "definable inductive set" I mean a
statement in the language of MA like:
( P(0) AND P(S(0)) AND P(S(S(0)) ) ->
Ax ( (x=0 OR x=S(0) OR x=S(S(0))) -> P(x) )
The induction axiom schema says if P
is true of all inductive "sets" then Ax P.
I have already shown if x is a member
of a definable inductive set and S(x)=0
then the model is finite.
Assume Z is a model of MA and S(-1) = 0.
Negative integers are not terms in the
language of MA. "-1" is not in any
definable inductive set.
If Z is a model of MA then
( (S(0) != 0) AND (Ax ( (S(x) != 0) -> (S(S(x)) != 0) ) ) )
is true of all definable inductive sets.
This means we can derive Ax (S(x) != 0) by induction.
Russell
- Integers are an illusion
RussellE
> In article
> <d347d6ba-d886-45a2-893d-cf2c5b555...@r2g2000vbj.googlegroups.com>,
>
> But the negative integers form a set that, with a slightly modified
> "successor" function, is just as "inductive" as the set of positive
> integers
Modifying the successor function gives us
a different theory.
It wouldn't matter. I can use the new successor
function and prove if x can be defined with
successor and S(x)=0 then the model is finite.
Uergil
<b8280cd1-36ea-48a9...@d26g2000prn.googlegroups.com>,
RussellE <reas...@gmail.com> wrote:
> On Jun 17, 3:54�pm, Uergil <Uer...@uer.net> wrote:
> > In article
> > <d347d6ba-d886-45a2-893d-cf2c5b555...@r2g2000vbj.googlegroups.com>,
> >
> > But the negative integers form a set that, with a slightly modified
> > "successor" function, is just as "inductive" as the set of positive
> > integers
>
> Modifying the successor function gives us
> a different theory.
Nonsense!
Any well ordered set with one and only one non-successor and no
last/largest member works equally well, as all such systems are
order-isomorphic, which is al that counts.
>
> It wouldn't matter. I can use the new successor
> function and prove if x can be defined with
> successor and S(x)=0 then the model is finite.
>
>
> Russell
> - 2 many 2 count
Jesse F. Hughes
> On Jun 17, 6:30 pm, "Jesse F. Hughes" <je...@phiwumbda.org> wrote:
>> First, let us assume that in your model (and contrary to what David
>> Libert has proved), there is no element x such that
>>
>> S(x) !=0 and S(S(x)) = 0.
>>
>> Then
>>
>> (Ax)(S(x) != 0 -> S(S(x) != 0)) (*)
>>
>> would be true *in that model*. So what? It does not follow that (*) is
>> provable from your axioms. You are confusing true in a model with
>> provability.
>>
>> If a theory T proves P, then P is true in every model. If, on the other
>> hand, P is true in some models and not others (like you allege (*) to
>> be), then T does not prove P (nor does T prove ~P).
>>
>> Thus, (*) is not a theorem and you have not proved MA inconsistent.
>
> I'm not proving MA is inconsistent.
> MA has finite models and there is a finitistic proof
> of the consistency of MA.
>
> I prove MA has no infinite models.
>
> While (*) is not a theorem of MA, this is:
>
> ( (S(0) != 0) AND (Ax ( (S(x) != 0) -> (S(S(x)) != 0) ) ) )
> -> Ax (S(x) != 0)
Yes.
> The first order axioms of induction are axioms.
> They are written in the language of MA.
> They can only refer to terms in the language of MA.
No, not if you mean that the above theorem applies only to x ranging
over closed terms. That's nonsense.
> There is an axiom for every definable inductive set.
>
> I do not include the axioms of set theory in MA.
> When I say "definable inductive set" I mean a
> statement in the language of MA like:
>
> ( P(0) AND P(S(0)) AND P(S(S(0)) ) ->
> Ax ( (x=0 OR x=S(0) OR x=S(S(0))) -> P(x) )
>
> The induction axiom schema says if P
> is true of all inductive "sets" then Ax P.
>
> I have already shown if x is a member
> of a definable inductive set and S(x)=0
> then the model is finite.
>
> Assume Z is a model of MA and S(-1) = 0.
> Negative integers are not terms in the
> language of MA. "-1" is not in any
> definable inductive set.
>
> If Z is a model of MA then
>
> ( (S(0) != 0) AND (Ax ( (S(x) != 0) -> (S(S(x)) != 0) ) ) )
>
> is true of all definable inductive sets.
> This means we can derive Ax (S(x) != 0) by induction.
You are mighty confused. In the structure Z,
(Ax ( (S(x) != 0) -> (S(S(x)) != 0) ) ) )
is false because S(-2) != 0, but S(S(-2)) = 0.
--
Jesse F. Hughes
"You will never manage to completely convince me that Jews weren't at
least a LITTLE bit guilty of irrationnal anti-nazi bias."
-- Attributed to humorist Pierre Desproges
RussellE
> RussellE <reaste...@gmail.com> writes:
> > While (*) is not a theorem of MA, this is:
>
> > ( (S(0) != 0) AND (Ax ( (S(x) != 0) -> (S(S(x)) != 0) ) ) )
> > -> Ax (S(x) != 0)
>
> Yes.
>
> > The first order axioms of induction are axioms.
> > They are written in the language of MA.
> > They can only refer to terms in the language of MA.
>
> No, not if you mean that the above theorem applies only to x ranging
> over closed terms. That's nonsense.
I didn't say axioms only apply to closed terms.
I said the induction axioms must be written
in the language of MA.
I am using the definition for first order induction
schema described on Wikipedia.
http://en.wikipedia.org/wiki/Peano_axioms
Notice the definition of induction refers to Ay
where y is a definable inductive set.
Wikipedia describes a y as {y1,y2,...,yn}.
A definable inductive set must have a
finite number of members and each member
must be a term in the language of MA.
An example of a definable inductive set
would be: {0, S(0), S(S(0))}
The induction schema says if P is
true for all definable inductive sets
then P is true for all x.
> > If Z is a model of MA then
>
> > ( (S(0) != 0) AND (Ax ( (S(x) != 0) -> (S(S(x)) != 0) ) ) )
>
> > is true of all definable inductive sets.
> > This means we can derive Ax (S(x) != 0) by induction.
>
> You are mighty confused. In the structure Z,
>
> (Ax ( (S(x) != 0) -> (S(S(x)) != 0) ) ) )
>
> is false because S(-2) != 0, but S(S(-2)) = 0.
Your problem is that "-2" (as defined in Z) is
not a member of any definable inductive set.
"-2" is not a term in the language of MA.
It can't be written as S(S(...S(0)...).
It doesn't matter if Ax (S(x) != 0) is false in Z.
I can still prove Ax (Sx) != 0) by induction
because Ax ( (S(x) != 0) -> (S(S(x)) != 0) )
is true for all definable inductive sets.
I should write this as:
(S(0) != 0) AND Ay (Ax ( (xey AND (S(x) != 0) -> (S(x)ey AND S(S(x)) !
= 0) ))
where y is a definable inductive set and x is a member of y.
(This can probably be expressed better than the method
used by Wikipedia.)
Jesse F. Hughes
> On Jun 20, 6:17 pm, "Jesse F. Hughes" <je...@phiwumbda.org> wrote:
>> RussellE <reaste...@gmail.com> writes:
>
>> > While (*) is not a theorem of MA, this is:
>>
>> > ( (S(0) != 0) AND (Ax ( (S(x) != 0) -> (S(S(x)) != 0) ) ) )
>> > -> Ax (S(x) != 0)
>>
>> Yes.
>>
>> > The first order axioms of induction are axioms.
>> > They are written in the language of MA.
>> > They can only refer to terms in the language of MA.
>>
>> No, not if you mean that the above theorem applies only to x ranging
>> over closed terms. That's nonsense.
>
> I didn't say axioms only apply to closed terms.
> I said the induction axioms must be written
> in the language of MA.
And so they are.
> I am using the definition for first order induction
> schema described on Wikipedia.
> http://en.wikipedia.org/wiki/Peano_axioms
>
> Notice the definition of induction refers to Ay
> where y is a definable inductive set.
> Wikipedia describes a y as {y1,y2,...,yn}.
> A definable inductive set must have a
> finite number of members and each member
> must be a term in the language of MA.
> An example of a definable inductive set
> would be: {0, S(0), S(S(0))}
You're mis-reading the passage.
The overline y there is a list of variables. They don't mean that y is
a variable interpreted as a finite set. They mean that the scheme
yields an axiom for every formula Phi(x,y1,y2,y3,...,yn), where n > 0.
Didn't you notice that they wrote "where \bar{y} is an abbreviation for
y1,...,yk"? They did not write "where \bar{y} is interpreted as a set
{y1,...,yk}."
Under the usual interpretation of S, an inductive set is *never* finite,
since it includes S^n(0) for every n. (Of course, in MA, this is not
necessarily the case, but the notion of "inductive" is a little funny
there. We usually use the term only in contexts where S is the usual
operator x |-> x u {x}.)
--
Jesse F. Hughes
"Imagine an angry mob in a post-apocalyptic world out for blood
against anyone who even LOOKS like a mathematician--whatever that
vaguely means to them." -- James S. Harris has odd dreams
RussellE
The article goes on to say there is an axiom
for every definable subset of naturals.
Definable means definable in the language of MA.
How are you defining negative integers
in the language of MA?
Jesse F. Hughes
The purported model is Z[1]. We don't have to define it in order to
apply the inductive axiom.
But I wouldn't worry about "definable subsets" so much in any case. The
clearer understanding of the axiom is in terms of formulas Phi. And the
real issue is that you cannot prove that
(S(x) ! 0 -> S(S(x)) ! 0),
contrary to your claim. Indeed, that statement is *not true* in every
model of MA and in particular it is not true in the structure Z, which
you claim (without proof) is a model. Thus you don't get the
contradiction you claimed.
Final note: It is clear to me that Z is a model of MA without the
induction scheme. You really ought to prove that it satisfies the
induction scheme, too, if you're going to insist that it is a fact that
Z models MA.
Footnotes:
[1] It's not at all clear to me that Z *is* a model, since it's not
clear to me that the structure satisfies induction. David Libert
thought more carefully on what the infinite model would be, and I don't
think he said it was Z, but you should check his work.
--
Jesse F. Hughes
"Yesterday was Judgment Day. How'd you do?"
-- The Flatlanders
David Hartley
<je...@phiwumbda.org> writes
>Footnotes:
>[1] It's not at all clear to me that Z *is* a model, since it's not
>clear to me that the structure satisfies induction. David Libert
>thought more carefully on what the infinite model would be, and I don't
>think he said it was Z, but you should check his work.
He did indeed carefully show that Z is *not* a model of MA. The negative
integers can be described within Z in the language of MA,by
NOT(Ep,q,r,s)(p^2 + q^2 + r^2 + s^2 = x)
--
David Hartley