Logic - 2017-09-16

Leaky Nun

9:43 AM

in Set theory, 3 mins ago, by Leaky Nun

Is there a model of PA in which Goodstein's theorem doesn't hold?

@user21820

Please ping me if you respond anything.

user21820

@LeakyNun Hello! Well since Kirby-Paris proved that PA cannot prove Goodstein's theorem G, it follows that (PA+¬G) is consistent, and hence must have a model by the completeness theorem.

Leaky Nun

@user21820 but is there any model?

that we have constructed?

user21820

Well do you count the model constructed via the completeness theorem?

Leaky Nun

I don't know much about the construction indicated by completeness theorem

I don't know much about completeness theorem.

user21820

10:07 AM

@LeakyNun Well I suppose you'd have to look in a standard reference text then. I'm not sure where you can find a very illuminating explanation, though.

Leaky Nun

@user21820 alright, thanks

user21820

There are a few basic ideas that I can explain if you want.

Leaky Nun

are there any constructed models then?

user21820

There is a theorem that there are no computable non-standard models of PA. This means that there is no computer implementations of the domain and arithmetic operations that obeys PA but is not isomorphic to the standard natural numbers.

Leaky Nun

:O

user21820

10:10 AM

Tennenbaum's theorem

Tennenbaum's theorem, named for Stanley Tennenbaum who presented the theorem in 1959, is a result in mathematical logic that states that no countable nonstandard model of Peano arithmetic (PA) can be recursive. == Recursive structures for PA == A structure M {\displaystyle \scriptstyle M} in the language of PA is recursive if there are recursive functions + and × from N × N {\displaystyle \scriptstyle N\times N} to N...

Leaky Nun

can you write "n is a 0-successor" in second order PA?

user21820

Yes, but there is no need because second-order PA is already categorical (has only one model up to isomorphism).

Leaky Nun

then how does one typically write that?

user21820

It may be instructive to see it: ∀X ( 0∈X ∧ ∀k ( k∈X ⇒ k+1∈X ) ⇒ n∈X ).

It says basically that every inductive set includes n.

Note that the set of elements generated from 0 by successors is inductive.

Leaky Nun

but doesn't every inductive set also include the unaccessible number?

user21820

10:16 AM

No.

Some do, and some don't.

Leaky Nun

hmm...

@user21820 but we can't write this in PA right?

user21820

It's a second-order formula, and yes we can't write this in first-order PA.

Leaky Nun

but do we have to use second-order PA to write that?

user21820

There are many reasons for this. The simplest reason is that second-order PA is categorical but first-order theories never have exactly one infinite model.

Leaky Nun

how do you denote the inaccessible number?

user21820

10:20 AM

In any model of arithmetic, the elements that interpret terms of the form 0+1+...+1 are called standard naturals, and other elements are called non-standard naturals.

Leaky Nun

I mean, I want to use a letter to refer to it lol

user21820

If you have a non-standard natural in some structure over arithmetic, you can just refer to it by any name you wish. The only thing is that you cannot uniquely pick out a single non-standard natural.

Leaky Nun

wait what?

I'll just call it $\kappa$ for now.

And I'll assume you just meant that $\kappa$ and $\kappa+1$ are kind of the same

Now my question: what the hell would $2^\kappa$ look like?

(and it's defined because of some you-can-encode-sequence-in-first-order-PA thing)

user21820

Yes it's defined. And yes it's weird. Just think of non-standard models as weird structures that have the same first-order properties as the standard naturals.

Nothing else much you can say.

Leaky Nun

This is very weird

is $^\kappa2$ also defined?

user21820

10:24 AM

Of course, you have some facts like 2^n ≥ n+1 for every natural n, which PA can prove by induction.

"x^y" is definable over PA, where x,y are arbitrary variables.

Leaky Nun

I've heard that a non-standard model can have order type $\Bbb N + \Bbb Z \times \Bbb Q$, amirite?

user21820

The initial part is going to look like N, and then there is some element k that is more than all the standard ones, and then you have k*k.

k*k is in the middle of a copy of Z.

There is a copy to the left around k*(k−1).

And a copy to the right around k*(k+1).

And many more copies on both sides.

Leaky Nun

Look

I can't write "standard natural" in first order PA

and second order PA is boring

so what should I do at all?

user21820

Lol.

Leaky Nun

@user21820 and where is $2^\kappa$?

@user21820 I'm serious

user21820

10:31 AM

@LeakyNun I don't understand what you're looking for. Non-standard models are not interesting precisely because we don't believe they make any sense to the real world. If you do, then you face a lot of issues, such as the uncomputability that I mentioned, and also the fact that it won't satisfy second-order induction.

Leaky Nun

I mean, if it's $\Bbb N + \Bbb Z \times \Bbb Q$, then where is $2^\kappa$?

@user21820 oops, I meant second order PA is boring because we know all about it and there's only one model up to isomorphism

oh, and I find it astonishing that algebraically closed fields are complete and consistent...

user21820

@LeakyNun This comes at a cost; you can't pick out the natural numbers using a first-order formula over field arithmetic.

Leaky Nun

@user21820 right

inconsistent theorem :)

user21820

@LeakyNun I have to think about this; I never really thought about non-standard models; by the way where did you see this mentioned? I don't immediately see why we have Q copies of Z.

Leaky Nun

@user21820 oh I think it's because floor(pk/q) is a thing

user21820

10:35 AM

@LeakyNun You are right; that's interesting I didn't realize it.

Leaky Nun

oh, I found the answer to my question "how does one talk about the standard naturals"

it turns out that to build a model with an inaccessible number $c$, you add countably infinitely many axioms to PA:

0 < c; S0 < c; SS0 < c; etc.

user21820

Yes that is the standard compactness method of constructing a non-standard model, which relies on the completeness theorem that I mentioned earlier.

Leaky Nun

oh, lol

is it provable in this model that there exists a k such that n|k for every standard natural n?

user21820

@LeakyNun So what is happening is that floor(k*r) is in the middle of some copy of Z for each positive rational r, and so we have N followed by Q copies of Z, and then some more stuff! What we need to show is that any countable non-standard model has N followed by a dense linear order without endpoints of copies of Z, using the same trick, and so we get the result we want.

Where exactly 2^κ is can't be described well.

@LeakyNun Not using those extra sentences you had above.

Leaky Nun

@user21820 so it's independent?

user21820

10:40 AM

But you just use 1|c, 2|c, 3|c, 4|c, ...

Leaky Nun

@user21820 so "$2^\kappa$ is in those copies" is also independent?

@user21820 is the conjunction of these sentences independent from my model above?

basically everything is independent?

user21820

@LeakyNun I'm not sure. I cannot think of an easy reason that this is false. Perhaps this is true?

I doubt though.

Leaky Nun

@user21820 I have no idea.

Should I ask it on main?

user21820

@LeakyNun If you do, post the link here. I'm curious to know the answer. I guess it's false. =)

Leaky Nun

@user21820 I'm not sure if infinite conjunction is a thing though

user21820

10:52 AM

There's no need for infinite conjunction.

Leaky Nun

hmm?

user21820

Just ask whether in every non-standard model of PA there exists an element that is divisible by every standard natural.

Leaky Nun

I'm trying to phrase my question of the form "let $P$ be the proposition ..."

but I can't write $P$

user21820

We're talking about the model from the outside, and can ask the question from the outside.

Leaky Nun

:c

does "non-standard" mean "containing an inaccessible number"?

Are they equivalent?

user21820

11:05 AM

@LeakyNun Yes.

Leaky Nun

@user21820 oh, thanks

user21820

We don't say "inaccessible" because it's non-standard terminology.

=P

Leaky Nun

oh, ok

0

Q: Existence of inaccessible natural number divisible by every standard natural number under PA

Let $P$ be the proposition that there exists a non-zero number that is divisible by every standard natural number. Denote by $PA+\kappa$ a non-standard model. Is $P$ provable from $PA+\kappa$? Is $\neg P$ provable from $PA+\kappa$? Are $PA+\kappa$ and $P$ consistent? Are $PA+\kappa$ and $\neg ...

26 mins ago, by Leaky Nun

@user21820 so "$2^\kappa$ is in those copies" is also independent?

how about this?

user21820

Your question does not make sense.

Leaky Nun

must there be standard naturals $p,q,r$ such that $2^\kappa = \left\lfloor \dfrac{p\kappa}q \right\rfloor + r$?

user21820

11:09 AM

I meant that the question you just posted does not make sense.

"PA+κ" already makes no sense.

And even if it refers to a theory, asking whether it proves P makes no sense if P is not a first-order sentence over arithmetic.

Leaky Nun

how should I phrase it?

user21820

Don't say "provable". P is either true or false about a model, not provable...

And (3) and (4) don't correspond to the question I stated above for you.

Leaky Nun

is it better now?

user21820

Yes it's now correct.

Leaky Nun

thanks

user21820

11:12 AM

So let's wait for an answer.

Leaky Nun

5 mins ago, by Leaky Nun

must there be standard naturals $p,q,r$ such that $2^\kappa = \left\lfloor \dfrac{p\kappa}q \right\rfloor + r$?

user21820

@LeakyNun No, because 2^κ > κ·n for any standard natural n.

Leaky Nun

wat

alright

user21820

That's why I said it's beyond those copies of Z that I could easily refer to.

It's just somewhere out there far away.

Leaky Nun

oh and what do you study?

user21820

11:18 AM

Officially, CS, but as you might guess I like logic too.

I see you got an answer. Yes it's so obvious in hindsight.....

Because PA can define any recursive function.

Leaky Nun

yep, in hindsight.

I was thinking that you can't multiply infinitely many numbers together

user21820

Well you can't.

Leaky Nun

hmm

user21820

But you see, when you define fact(n) over PA, you would be able to prove by induction that ∀n,k ( k < n ⇒ k | fact(n) ).

Leaky Nun

right

non-standard models are weird.

do you do ZF as well?

user21820

11:21 AM

I know some stuff about ZFC, but not anywhere near a set theorist.

I didn't say C :3

ZFC includes ZF. =)

hmm

As a matter of fact, I dislike ZFC's impredicativity. While I believe it is syntactically consistent, I don't believe it is very meaningful.

Leaky Nun

what do you mean?

user21820

11:25 AM

Impredicativity is a vague term but basically refers to defining something based on the properties of a collection that includes that something.

If that collection is somehow already previously well-defined, then this is fine.

Leaky Nun

you mean something like R/Q?

user21820

No that's fine because we can construct R quite predicatively.

Russell's paradox is an example in naive set theory.

Leaky Nun

then what do you mean?

user21820

"Let R = { x : x∉x }." is an impredicative definition because it defines an object R whose properties depend on the actual membership in all sets including R itself.

Leaky Nun

but this isn't ZFC...

user21820

11:28 AM

This is an example of impredicativity.

ZFC blocks it by restricting to definable subsets of previously constructed sets.

Leaky Nun

so you dislike this?

user21820

But that definition still can quantify over all sets (including the one to be constructed).

Leaky Nun

hmm?

I don't get it

user21820

For example { x : ∃y ( P(x,y) ) } is a valid definition in ZFC for any 2-parameter sentence P.

The problem is that the "∃y" ranges over all sets including the one to be constructed.

Leaky Nun

oh

schema of replacement

user21820

11:33 AM

I could add a "!" there if I want to avoid AC.

It is conceivable that allowing such constructions can lead to contradiction because the thing to be constructed may somehow diagonalize against itself.

Leaky Nun

but i thought it is consistent

user21820

By the incompleteness theorems, you can never be sure that it is. You can only be sure that it isn't, if you find an explicit contradiction.

I don't believe ZFC actually proves a contradiction, for syntactic reasons rather than semantic reasons.

Leaky Nun

alright

wait that isn't replacement right

you need to specify a set for replacement

user21820

Oh yes, sorry. Forget about replacement, just take S = { x : x∈2^N ∧ ∃y ( P(x,y) ) }.

The thing is that if 2^N was some absolute entity, then this is well-defined because we are just using a formula to pick out some of them and collect them in a set.

But 2^N is not absolute at all, as Lowenheim Skolem should tell you. After all, 2^N, or the powerset of N, is more or less syntactically defined, namely the collection of all sets whose members are in N.

Simply Beautiful Art

(just peaking by before I head off)

user21820

11:47 AM

@SimplyBeautifulArt: Peeking you mean? =)

Leaky Nun

welcome

user21820

Come by more often! Haha.. see you around!

Simply Beautiful Art

No, peaking, as in reaching the top obviously

user21820

@SimplyBeautifulArt Now you're making me confused.

Leaky Nun

@user21820 who is that not well-defined?

Simply Beautiful Art

11:48 AM

@user21820 that's the plan! :D

@LeakyNun how*?

user21820

LS shows that if ZF is consistent then ZF has a countable model, and in that model 2^N has only countably many members.

Leaky Nun

ugh, how.

@user21820 but 2^N cannot be countable in ZFC

user21820

@LeakyNun That model doesn't have the bijection to see that 2^N is countable, so there's no contradiction.

Simply Beautiful Art

*sighs* when someone asks a question and it would certainly help to know what definitions they are using

Leaky Nun

@user21820 but Cantor's theorem doesn't require choice right

user21820

11:51 AM

@LeakyNun It doesn't. I think you've never heard of Skolem's paradox?

Leaky Nun

I haven't

there's little i know, more that I don't know, and even more that I don't know that I don't know

2

user21820

Assuming that ZF is consistent, we can (via the same proof as the completeness theorem) construct a Henkin model M, which is countable. Then note that any set in M must have countably many members, because each member is itself a set in M.

M still satisfies Cantor's theorem that 2^N is uncountable.

You must always remember where you are, whether inside the model or outside. Inside there is no bijection from N to 2^N, due to Cantor's theorem. Outside there is.

Leaky Nun

I see no problem with that

you just can't define every set inside

wait, outside there is???

user21820

Of course outside there is; we constructed M via the Henkin construction and it produces a countable model!

That's why it's called Skolem's paradox, because people take some time to get their head around it.

Leaky Nun

so why is there no bijection inside?

because a bijection is a function is a relation is a set...

user21820

11:56 AM

Yea, M has not many of those bijections.

So inside M we cannot see that 2^N has 1-to-1 correspondence with N.

Leaky Nun

my mind is exploding from the inside

is there any concrete example?

user21820

The Henkin construction is non-constructive.

But not very non-constructive.

Leaky Nun

not very constructive either? :P

user21820

You just need to make countably many decisions, each of which is based on whether some countable set of sentences is consistent or not.

Leaky Nun

my mind is imploding upon itself

user21820

12:00 PM

So if you believe that the halting problem is well-defined, you should believe that each step of Henkin's construction is well-defined.

Leaky Nun

I'm not believing in any of that shit :P

Simply Beautiful Art

lol

user21820

@LeakyNun Why not? Do you believe that there is some program and some input for which the question of whether it halts on that input has no truth value?

Leaky Nun

@user21820 I'm just kidding.

aka shitposting

@user21820 well, the halting program...

I think there's an animation on that

user21820

@LeakyNun Couldn't tell whether you're joking, because it's indeed one of the first philosophical commitments needed to climb higher up the meta-system strength.

9

A: Are sets and symbols the building blocks of mathematics?

The things you actually write on the paper or some other medium are not definable as any kind of mathematical objects. Mathematical structures can at most be used to model (or approximate) the real world structures. For example we might say that we can have strings of symbols of arbitrary length,...

Simply Beautiful Art

12:03 PM

Huh, I didn't know Martin still asks questions

user21820

@SimplyBeautifulArt There are a couple of Martins on Math SE...

Simply Beautiful Art

Our Martin, the one who's in CRUDE

user21820

Haha..

You remind me of a children's book I read called Martin's Mice.

Simply Beautiful Art

well, I'm off

Catch everyone later

user21820

@SimplyBeautifulArt See you! =)

@SteveChamaillard: Hello and welcome! Do you have anything you would like to talk about regarding (mathematical) logic?

Leaky Nun

12:13 PM

oh no, an enemy from CR :P

user21820

Lol.

@LeakyNun: By the way, what's your specialization in mathematics?

Leaky Nun

@user21820 I haven't started :P

it's two weeks from now

user21820

@LeakyNun Oh okay. And yet you already know so much.

Leaky Nun

@user21820 I like to learn about mathematics

user21820

I knew practically nothing of what I told you today before I started university.

Leaky Nun

12:17 PM

24 mins ago, by Leaky Nun

there's little i know, more that I don't know, and even more that I don't know that I don't know

@user21820 I see

user21820

I agree with that saying. If you are interested in logic, you may want to take a look at the posts linked from my profile, including the introduction one that links to a few online references.

Leaky Nun

thanks

user21820

@LeakyNun: I've to go now. See you next time!

Leaky Nun

@user21820 see you

Leaky Nun

7:30 PM

@user21820 how doesn't the diagonalization argument fail from the outside?