Logic - 2017-11-14

7:23 AM

@sova Hello there! No problem. =)

Though I must say that I don't know much about fuzzy logic, so what I can give are mostly opinions based on what I know about other logics. =)

123

10:09 AM

It's not that I am complete blank slate about logic, I have attended some classes about logic, though they were very basic.@user21820

Thanks for inviting me.

user21820

@123: Hello! I see. Do you know of a deductive system for first-order logic?

123

@user21820 Frankly no I don't.

user21820

@123 Ah so that's why. In older times, mathematics was done by loads of intuition. To the extent that there were many wrong claims and proofs.

123

@user21820 Yes I know that. People like Euler and Newton don't prove their conjectures. I know a little bit about ZFC axioms. Though If I say nothing more about foundation of maths that would be pretentious.

user21820

@123 So modern mathematics has been set up such that the experts in any field should know how to formalize their proofs.

In this case, we have some claim about the determinant of some matrix.

The main issue is that it is troublesome to formalize arbitrary-size matrices.

But the point is that we need to be very clear on exactly what logical steps we are taking.

123

10:22 AM

@user21820 Most proofs about arbitrary-size matrices that I have seen is done with induction.

user21820

@123 Correct, and for good reason. As I stated in the comments, it is technically not eliminable.

But I can't really say much more without going quite deep into logic.

123

Can you give an overview ?

user21820

Sure.

Firstly, it's much easier to first talk about something other than matrices.

You probably know the following axioms for natural numbers:

Peano axioms

In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are a set of axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly unchanged in a number of metamathematical investigations, including research into fundamental questions of whether number theory is consistent and complete. The need to formalize arithmetic was not well appreciated until the work of Hermann Grassmann, who showed in the 1860s that many facts in arithmetic could be derived from more basic facts about...

123

Yes I know those axioms.

user21820

Great! Notice that induction is separated from them.

Now it turns out that some basic facts cannot be proven without induction. Precisely, there is no proof using the axioms for PA−.

One such fact is ∀n∈N ∃k∈N ( n=k+k ∨ n=k+k+1 ).

123

10:29 AM

PA is Peano axioms ?

user21820

@123 You have to click on the link I provided, which defines PA−.

123

@user21820 Ok, sorry for inadequate comment.

user21820

@123 If you don't mind, please edit out the coarse language. =)

Anyway it's okay; I know the link does not show that it is a direct link to a subsection of the wikipedia article.

So in particular PA is equivalent to PA− plus induction.

Notice that it is 'intuitive' that every natural number is of the form 1+1+1+...+1, and we can group them as (1+1)+(1+1)+...+x where x is either 0 or 1. On first glance, without background in logic it seems like this can be a proof of the above stated fact, and there is no apparent induction.

But that is simply false.

123

For proving ∀n∈N ∃k∈N ( n=k+k ∨ n=k+k+1 ) I assume $n \ne 2k$ then I will prove n has to be of form $n = 2k +1$, then the other way around for $n \ne 2k + 1$. Will this be sound proof ?

My guess is "every natural number is of the form 1+1+1+...+1" is the wrong step.

user21820

@123 Yes, the "..." makes it clearly non-rigorous, but worse still that idea cannot even be formalized in PA.

@123 Just one would suffice, however you will find that you cannot do it.

The reason is that you literally need induction on that property itself.

123

10:43 AM

Oh, right you said it before. Are there some facts about natural numbers that can be proved with just PA- ?

user21820

@123: It is really instructive to try to actually prove that using (the linked axiomatization of) PA− plus induction. If you want we could skip that for now (but you should try it later!) and I will prove that induction is necessary.

@123 Yes, a lot of important facts can be proven with just PA−. But it's not so easy to understand so I'm going to defer that question; remind me later if I forget to answer it.

So to show that PA− cannot prove ∀n∈N ∃k∈N ( n=k+k ∨ n=k+k+1 ), we must find a model of PA− that does not satisfy it.

123

@user21820 I think I can do it now. Before that is 0 a part of natural numbers ?

user21820

@123 Sure. Yes.

123

Ok then the base case is true since x = 0 = 0 + 0.

user21820

Right.

123

10:49 AM

Let us assume that $x \ne k + k$ for some k.

user21820

@123 Interpreted normally, this does not make sense, because it is always true. Namely ∃k∈N ( x ≠ k+k ).

123

@user21820 Actually I am a bit lost on what should I assume in second step.

user21820

Anyway, it's better to work symbolically. Let me show you the outline and you can fill in the gaps.

123

Ok.

user21820

The instance of induction you need is ∃k∈N ( 0=k+k ∨ 0=k+k+1 ) ∧ ∀n∈N ( ∃k∈N ( n=k+k ∨ n=k+k+1 ) ⇒ ∃k∈N ( n+1=k+k ∨ n+1=k+k+1 ) ) ⇒ ∀n∈N ( ∃k∈N ( n=k+k ∨ n=k+k+1 ) ).

This is messy. We can use a definition to simplify it.

Define P(n) ≡ ∃k∈N ( n=k+k ∨ n=k+k+1 ), for every n∈N.

123

10:55 AM

Maybe p(n) : ∃k∈N ( n=k+k ∨ n=k+k+1 )

user21820

Right. This just means that P is a short-hand for the full expression.

Then the induction instance you need is P(0) ∧ ∀n∈N ( P(n) ⇒ P(n+1) ) ⇒ ∀n∈N ( P(n) ).

I purposely stated the relevant axiom in full because that is how it really is. In first-order logic P is just a short-hand.

Now, you have proven P(0).

You need to prove ∀n∈N ( P(n) ⇒ P(n+1) ).

After that you can invoke that induction instance to get the desired result.

So, your turn: prove ∀n∈N ( P(n) ⇒ P(n+1) ).

123

Say P(n) is true then if n = k+ k then n + 1 = k + k + 1 or if n = k + k + 1 then n + 1= k + k + 2 = (k + 1) + (k +1) = m + m where m = k+1. Done ?

user21820

Idea is correct but what is x?

123

Sorry I used x instead of n. I will edit it.

user21820

No need; I just needed to confirm you know what it should be. But never mind. =)

Anyway great; we have shown that PA proves that fact.

Now the more interesting part; to show that PA− does not prove it.

123

11:01 AM

You are going to show me that P is unprovable in PA-.

user21820

Consider the collection of integer polynomials of an indeterminate X that are either 0 or have positive coefficient on the highest power of X.

@123 I will show that ∀n∈N ( P(n) ) cannot be proven in PA−. P is not a sentence.

We saw that PA proved ∀n∈N ( P(n) ).

Define + and · on this collection of polynomials as the standard polynomial arithmetic operations.

123

@user21820 Yes, I used P as a shorthand, I will take care.

Ok.

user21820

Define < on the collection C to compare by degree first and then the coefficients from highest to lowest power of X. And 0 is considered the minimum.

It turns out that this makes (C,0,1,+,·,<) a model of PA−. Of course, this needs checking the axioms of PA− one by one.

The first 7 are obvious.

123

Ok.

user21820

Transitivity of < needs a bit more work, but it's a standard kind of ordering (also known as length-lexicographic ordering in other contexts).

Axioms 9 and 10 are by definition of <.

123

11:06 AM

11 is tricky ?

user21820

Axioms 11 and 12 need yet more work, which if you like you can verify later.

123

Yes I will.

user21820

Axiom 13 is interesting in this context of C.

But easier than 11 and 12.

123

I think I can prove 13. should I try ?

user21820

Sure, though I'd like to finish the explanation first before you try all these at one go.

Axioms 14,15 are obvious.

123

11:09 AM

Ok you can.

user21820

Now back to the claim that C does not satisfy ∀n∈C ( P(n) ).

Now back to the claim that C does not satisfy ∀n∈N ( P(n) ) where N is interpreted as C.

123

Ok.

user21820

Namely, we want to prove ¬ ∀n∈C ∃k∈C ( n=k+k ∨ n=k+k+1 ).

Can you think of a polynomial that witnesses this?

123

Sorry to interrupt. In your statement "Now back to the claim that C does not satisfy ∀n∈N ( P(n) ) where N is interpreted as C." it should be "Now back to the claim that N does not satisfy ∀n∈N ( P(n) ) where N is interpreted as C." right ?

user21820

@123 Yea that's what I meant.

123

11:14 AM

Coefficients of any polynomial in C should be 0 or 1 right ?

user21820

13 mins ago, by user21820

Consider the collection of integer polynomials of an indeterminate X that are either 0 or have positive coefficient on the highest power of X.

Any integer coefficients, except the highest power must have positive coefficient unless the polynomial is zero

If not you wouldn't have been able to satisfy the closure of C under +,·.

That's the other thing I forgot to say just now; also got to check that.

123

Ok. Let me think of a counterexample.

@user21820 Will x^2 - x work?

user21820

It does, but there's a much simpler counter-example. =)

123

-1 ?

user21820

−1 is does not fit the criterion on the coefficients.

123

11:22 AM

Sorry I mean x - 1 ?

user21820

Yes that works too.

In fact, any non-constant polynomial whose highest power of x has odd coefficient will work.

Let's just use x.

123

Ok.

user21820

For any constant polynomial k in C, k+k and k+k+1 are both constant polynomials, and hence cannot be x.

For any non-constant polynomial k in C, k ≥ x and hence k+k ≥ 2x > x.

So C does not satisfy ∀n∈C ∃k∈C ( n=k+k ∨ n=k+k+1 ).

Got it?

123

I think so.

Yes I am satisfied.

user21820

That's great!

I love teaching logic hahaha..

10

=)

123

11:25 AM

I can see that.

How proving our statement for C prove it for N

user21820

@123 Hmm what do you mean?

123

We proved ¬ ∀n∈C ∃k∈C ( n=k+k ∨ n=k+k+1 ) right ? Original statement was ∀n∈N ( P(n) ) cannot be proven in PA−. How those two equivalent ? Have I missed something ?

user21820

Oh yes; major thing I forgot to say.

First-order logic is sound, meaning that if you start with true sentences about a model, and use the deductive rules of first-order logic, then you can only deduce (more) true sentences about that model.

I claimed that C is a model of PA− but not a model of PA− plus induction.

If PA− could prove ∀n∈N ( P(n) ) then it would necessarily be true for every model of PA−.

But ∀n∈N ( P(n) ) isn't true for C, so PA− cannot prove it.

However earlier we saw that PA− plus induction proves it, so C cannot be a model of PA− plus induction.

123

Ok I think I get.

user21820

@123: So all that is left is to verify that C is really a model of PA−.

Then this proof finishes the job.

Leaky Nun

11:38 AM

@123 the thing is that if PA- can prove Φ, then PA- U {not Φ} is inconsistent, so there is no model of PA- U {not Φ}. By constructing such a model, we have essentially proved that Φ is not provable from PA-. That’s the important bit we missed.

@user21820 though I would have to object to your usage of ∀n∈N instead of just ∀n

user21820

@LeakyNun It's friendlier to non-logicians.

=)

123 didn't have background in logic, so I was phrasing everything in terms without logic.

Your way of looking at it is of course correct as well.

Leaky Nun

well at least you need to mention that thing I just did, in my opinion

user21820

@LeakyNun No I don't; soundness is enough.

123

@LeakyNun Yes, I understand the proof.

@user21820 Thanks you, that was insightful.

I really like your proof.

user21820

@123 Thank you! I'm glad to help.

Anyway, I need to get something done, but feel free to frequent this room, and post anything you like, and I'll respond the next time I'm here. =)

@LeakyNun: If you don't get why I said soundness is enough, I'll explain again next time! =)

123

11:44 AM

@user21820 I would say you got me interested in logic. See you bye.

user21820

=)

@123: Bye!

Leaky Nun

@user21820 sorry but what is soundness?

user21820

12:06 PM

@LeakyNun I defined it roughly here:

35 mins ago, by user21820

First-order logic is sound, meaning that if you start with true sentences about a model, and use the deductive rules of first-order logic, then you can only deduce (more) true sentences about that model.

If you want I can give a precise definition in logic terms.

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic