A Counterexample to Löwenheim–Skolem
RussellE
as first order Peano Arithmetic (PA) except
Ax (S(x)~=0) is replaced with Ex(S(x)=0).
http://en.wikipedia.org/wiki/Peano_axioms
Let F(x) = 0-x
These are theorems of MA:
Ax(x+F(x) = 0)
AxEy( (x=y+y) or (S(x)=y+y) )
By axiom, we know 0 has a predecessor.
Let z be this predecessor: S(z)=0.
Assume z is even and z=m+m.
S(m+m) = m+S(m) = 0
m+F(m) = 0
S(m)=F(m)
Assuming z is odd, a similar argument with
the predecessor of z proves m=F(m).
Ex( (x=F(x)) or (S(x)=F(x)) )
MA has arbitrarily large finite models.
In a strong enough meta-theory it can
be proven MA must have an infinite model
using the Compactness and upper
Löwenheim–Skolem theorems.
http://en.wikipedia.org/wiki/Compactness_theorem
The downward Löwenheim–Skolem theorem proves
the set of all standard natural numbers, N, is
the universal set of a model of MA.
http://en.wikipedia.org/wiki/Upward_L%C3%B6wenheim%E2%80%93Skolem_theorem
Assume we have a mapping from N to N', where
N' is the universe of an infinite model of MA.
n' = 2^n
F(n') = 3^n
Again, let S(z')=0. z' must be non-standard.
Assume z' is even and z' = m'+m'. We have
S(m')=F(m')
We have encoded the same number twice:
S(m') = 2^(m+1) and F(m') = 3^m.
Notice that m must be a standard natural
number in PA. Applying the successor function
(m+1) times to m' brings us back to 0.
This proves the "chain" is of finite length
and contains 0. All models of MA are finite.
I am going to nitpick my own proof.
I really want to prove:
Ex( (x~=0) and (x=F(x) or S(x)=F(x)) )
This statement is true in every model
of MA except one: the 0-model.
I think I will call this "0-inconsistent".
Russell
- Never never means never in set theory
David Libert
will collect references related to that general topic, though these
are mostly older references and not related to your modular arithmetic
theory MA.
[1] David Libert sci.logic Tues. Dec 17 2002 Re: Skolemization
http://groups.google.com/group/sci.logic/msg/243e8d58c1652c14
discussed relations of familiar theorems of logic to AC or gragments
of AC, and gave some counterexamples to familar theorems of logic in
~AC models. These included upward and downward Lowenheim Skolem.
[2] 4 messages "Equivalents of the axiom of choice"
sci.math Feb 10-14, 2003
http://groups.google.com/group/sci.math/browse_thread/thread/f0f9cdf2610ff438/
discussed how various statements -> AC over ZF, including some
Lowenheim Skolem theorems. The methods of [2] can show that each of
the usual downward and upward Lowenheim Skolem theorems imply AC over
ZF.
[1] defined explicit counterexamples to L-S in particular ~AC
models.
By [2] which came later, there must be L-S counterexample in any ~AC
ZF model.
[3] David Libert "Re: Modular Arithmetic Is Consistent"
sci.logic,sci.math July 9, 2011
http://groups.google.com/group/sci.logic/msg/212936720cb333d4
used the methods of [2] to note over ZF that if every infinite set is
the carrier set of a PA model (a special case of L-S) then AC.
So again by [3], any ~AC ZF model must have an infinite set which
cannot be the underlying set of any PA model.
Finally I will add something new to a last topic, which I have not
written about before.
[4] 18 articles Jan 30 '03 - Feb 6 '03 "Group Structure on any set"
http://mathforum.org/discuss/sci.math/t/478403
asked about endowing any set with a group structure. There was
discussion in [4], along the lines of examples of sets which cannot
carry a group structure in ~AC models.
Recently, I ran across a related topic in mathoverflow. I had not
known about this at the time of [4], and I have never written about
this topic until now.
[5]
http://mathoverflow.net/questions/12973/does-every-non-empty-set-admit-a-group-structure-in-zf
[5] proves in ZF that if every set can carry a group structure then
AC.
So [1] made some explicit counterexamples to theorems in ~AC models,
and later [2] proved the stronger result that those theorems -> AC,
so actually there must be counterexamples in every ~AC model, not just
in some ~AC models as [1] had done.
Now everything is repeating in parallel.
[4] made some examples of no group structures on sets in specific
~AC models. Then the stronger [5] is showing every ~AC model must
have such examples.
[5] starts off posing the question I noted about groups. I read the
proof in [5] that way and seemed to understand it. Then I read on in
[5], and noticed lower in the page was a reference to a published
stronger result over ZF AC <-> every set carries a cancellative
groupoid.
Even though [5] is stronger on the original question than [4], [4]
had some interesting topics in their own right.
There was some followup discussion about issues in [4] in other
threads, which can still be interesting even after [5].
Later there was a mathoverflow question related to some points
from [4].
Then there was a thread here following up on the math overflow
discussion and the previous [4].
That most recent thread is
[6] 14 messages "Dual Cantor-Bernstein (Attn: Herman Rubin)"
sci.math,sci.lgic Sep 16-23, 2010
http://groups.google.com/group/sci.math/browse_thread/thread/ba773c02016aeda/b69482956dad3976
As noted above, after [4] were some followup threads, then later
was the also related mathoverflow question. I am not giving exact
references here to those followups to [4] in threads here or
mathoverflow.
But [6] followed up on mathoverflow and links to that mathoverflow.
Also later articles in [6] give refences to the previous threads
here following on [4].
--
David Libert ah...@FreeNet.Carleton.CA
Frederick Williams
>
> Modular Arithmetic (MA) has the same axioms
> as first order Peano Arithmetic (PA) except
> Ax (S(x)~=0) is replaced with Ex(S(x)=0).
> http://en.wikipedia.org/wiki/Peano_axioms
>
> Let F(x) = 0-x
--
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
David Libert
> RussellE wrote:
>>
>> Modular Arithmetic (MA) has the same axioms
>> as first order Peano Arithmetic (PA) except
>> Ax (S(x)~=0) is replaced with Ex(S(x)=0).
>> http://en.wikipedia.org/wiki/Peano_axioms
>>
>> Let F(x) = 0-x
>
> What is - ?
I have recently been writing some into my wiki about Russell's MA
theory. If I had something to add about MA and I felt it wouldn't fit
well into an ongoing thread here and also was not important enough to
merit a new thread here, I would instead write into the wiki.
My base page for that MA writiing into the wiki is
[1] http://davesscribbles.wikispaces.com/modarithth
The other MA related wiki writing is accessible from [1] by
iterated links.
On my own I wanted to use a - notation in MA similar to what Russell
seems to be doing. I had written a wiki page about that:
[2] http://davesscribbles.wikispaces.com/modarithminus
I am assuming Russell means by - in MA similarly as [2].
--
David Libert ah...@FreeNet.Carleton.CA
Frederick Williams
>
> On my own I wanted to use a - notation in MA similar to what Russell
> seems to be doing. I had written a wiki page about that:
>
> [2] http://davesscribbles.wikispaces.com/modarithminus
>
> I am assuming Russell means by - in MA similarly as [2].
David Libert
> David Libert wrote:
>
>>
>> On my own I wanted to use a - notation in MA similar to what Russell
>> seems to be doing. I had written a wiki page about that:
>>
>> [2] http://davesscribbles.wikispaces.com/modarithminus
>>
>> I am assuming Russell means by - in MA similarly as [2].
>
> Thank you. Is -1 unique?
Yes, -1 as predecessor to 0 is unique.
[1] http://en.wikipedia.org/wiki/Peano_axioms#The_axioms
[1] includes axiom 8:
> 8. For all natural numbers m and n, if S(m) = S(n), then m = n.
> That is, S is an injection.
(I broke a long line to quote).
Russell's MA is like PA except changong only axiom 7. from [1].
So MA includes axiom 8.
My original articles proving and discussing that MA has infinite
models were "[2]-[3]" in
[2] http://davesscribbles.wikispaces.com/modarithth
A similar point arose in "[2]-[3]" and its thread.
In "[2]" I forgot about axiom 8. in PA, and wrote about whether
predecessors were unique in MA models.
In "[3]" I remembered about axiom 8., and corrected that point.
Soon after in the same "[2]-[3]" thread Tim Little pointed out the
same issue about axiom 8. :
[4] http://groups.google.com/group/sci.logic/msg/5d7f4725e14dd9c3
--
David Libert ah...@FreeNet.Carleton.CA
RussellE
<freddywilli...@btinternet.com> wrote:
> David Libert wrote:
>
> > On my own I wanted to use a - notation in MA similar to what Russell
> > seems to be doing. I had written a wiki page about that:
>
> > [2] http://davesscribbles.wikispaces.com/modarithminus
>
> > I am assuming Russell means by - in MA similarly as [2].
>
> Thank you. Is -1 unique?
The predecessor of 0 is unique.
I don't know if this is the only way we can define subtraction.
What is not unique is the m in x=m+m.
For example, 4 = 2+2 = 5+5 mod 6
m would be unique in a model of PA.
Russell
- 2 many 2 count
David Libert
I am following up
[7] David Libert "Re: A_Counterexample_to_Lowenheim-Skolem"
sci.logic, sci.math Oct 11, 2011
http://groups.google.com/group/sci.logic/msg/32235b2d40655ed7
I numbered that as [7], since I will be mentioning reference
numbers from inside [7], which were all "[6]" and below.
[7] was trying to collect references related to the general topic of
counterexample to Lowenheim Skolem, as in the title of this thread.
In this article I will clarify some points from [7], and also note a
sort of correction, see below.
To cite references from [7], I will write as follows. In order to
cite the reference that [7] called "[1]", I will write [7]:[1]. And
so on through to [7]:[6], the highest reference in [7]. I will cite
a range of [7] references in the obvious way: [7]:[1]-[2].
[7]:[1]-[2] were general discussion about L-S ie L-S is Lowenheim
Skolem.
[7]:[3] and [7]:[4] were about every infinite sets being the
carrier set of a PA model or a group respectively.
I didn't spell it out in [7], but these topics are about the case of
L-S specifically for the single theory PA, or specifically for the
theory of groups. (The general L-S is for any theory having infinite
models.) So that was the connection of those 2 to this topic of L-S
counterexamples.
The final part of [7] was about mathoverflow [7]:[5] and the
followup thread here: [7]:[6].
[7] never mentioned what these last 2 had to do with the L-S topic
here. Later it took me a moment to recall that myself, and so this
will be the sort of correction here.
As I was about to write [7], I just recalled that there was some
connection of [7]:[5]-[6] to [7]:[4] about groups. [7]:[4] was
related to our L-S topic as noted above, so that was good enough
reason for me to include [7]:[5]-[6] in [7].
Later I tried to recall more specifically what that connection of
[7]:[4] to [7]:[5]-[6] was.
Then I remembered. In [7]:[4] I had constructed an example ~AC ZF
model, relevant to the [7]:[4] topic.
Later in the earlier threads referenced in [7]:[6] we had a
different property on that topic at hand, which on casual reading
seemed to have nothing to do with the group topic from [7]:[4].
But I had found that my [7]:[4] ~AC constuction could have
techniques copy to make another ~AC model relevant to the new topic.
And that I did in a thread referenced in [7]:[6].
So that is the only connection of [7]:[4] to [7]:[5]-[6] I was
recalling.
So the connection of topic [7]:[5]-[6] is more tenuous to current
L-S topic than I had realized. Its not a connection of the questions,
just a connection of one of the answers.
So the "correction", ie sort of correction as I wrote above, is
[7]:[5]-[6] being so tenuously related could be left off from current
L-S topic.
Also I just remebered something else to add. [7]:[4] pasted in an
old link to mathforum which is now broken. So I will give [7]:[4]
again with a fresh link:
[4] 18 articles Jan 30 '03 - Feb 6 '03 "Group Structure on any set"
http://groups.google.com/group/sci.math/browse_thread/thread/ff541e79b774915d/
--
David Libert ah...@FreeNet.Carleton.CA
Frederick Williams
>
> On Oct 12, 10:21 am, Frederick Williams
> <freddywilli...@btinternet.com> wrote:
> > David Libert wrote:
> >
> > > On my own I wanted to use a - notation in MA similar to what Russell
> > > seems to be doing. I had written a wiki page about that:
> >
> > > [2] http://davesscribbles.wikispaces.com/modarithminus
> >
> > > I am assuming Russell means by - in MA similarly as [2].
> >
> > Thank you. Is -1 unique?
>
> The predecessor of 0 is unique.
> I don't know if this is the only way we can define subtraction.
You began
Modular Arithmetic (MA) has the same axioms
as first order Peano Arithmetic (PA) except
Ax (S(x)~=0) is replaced with Ex(S(x)=0).
http://en.wikipedia.org/wiki/Peano_axioms
Let F(x) = 0-x
which looks like a definition of F. But it only works if what's on the
RHS is expressed using symbols previously defined or symbols of MA's
language.
RussellE
wrote:
> RussellE wrote:
>
> You began
>
> Modular Arithmetic (MA) has the same axioms
> as first order Peano Arithmetic (PA) except
> Ax (S(x)~=0) is replaced with Ex(S(x)=0).
> http://en.wikipedia.org/wiki/Peano_axioms
>
> Let F(x) = 0-x
>
> which looks like a definition of F. But it only works if what's on the
> RHS is expressed using symbols previously defined or symbols of MA's
> language.
You are correct that F(x) can't be defined in MA
without some additional definitions.
I can define a new constant, z, such that S(z)=0.
F(x) = x * z
I could also define a predecessor function and then
define F(x) as applying the predecessor function to 0
x times. P(x) = x+z.
RussellE
>
> So the connection of topic [7]:[5]-[6] is more tenuous to current
> L-S topic than I had realized. Its not a connection of the questions,
> just a connection of one of the answers.
It is interesting ~AC has counter-examples of L-S.
Is there such a thing as an Axiom of Finite Choice?
We can always assume a finite collection has some
order, but, we have to "pick" an order.
David Libert
> On Oct 12, 7:09=A0pm, ah...@FreeNet.Carleton.CA (David Libert) wrote:
>>
>> =A0 So the connection of topic [7]:[5]-[6] =A0is more tenuous to current
>> L-S topic than I had realized. =A0Its not a connection of the questions,
>> just a connection of one of the answers.
>
> It is interesting ~AC has counter-examples of L-S.
>
> Is there such a thing as an Axiom of Finite Choice?
> We can always assume a finite collection has some
> order, but, we have to "pick" an order.
>
>
> Russell
> - 2 many 2 count
Pure first order logic let's you make n choices for each explicit
finite n, by n nexted applications of existential instanitation.
That would be minimal logic and intuitionsitic logic, as well as the
stronger classical.
ZF lets you make finitely many choices, n many for variable n, by
induction on n. Ie for every finite n, every collection of n many
non-empty sets has a choice function. This as a theorem of ZF
universally quantifying on finite n and all n sized cellections of
non-empty sets to choose from.
In the original work producing ~AC ZF models, Paul Cohen got a
countable set of 2 element sets having no choice function in a ZF
model.
--
David Libert ah...@FreeNet.Carleton.CA
RussellE
>
> What is not unique is the m in x=m+m.
> For example, 4 = 2+2 = 5+5 mod 6
> m would be unique in a model of PA.
There is exactly one m such that x=m+m for
every natural number in an odd sized model of MA.
For example:
0 = 0+0 mod 5
1 = 3+3 mod 5
2 = 1+1 mod 5
3 = 4+4 mod 5
4 = 2+2 mod 5
In even sized models, there are two m's
such that x=m+m for every even number.
0 = 0+0 = 3+3 mod 6
2 = 1+1 = 4+4 mod 6
4 = 2+2 = 5+5 mod 6
Russell
- The universe is one dimensional