Logic - 2016-08-18 (page 1 of 2)

user36188

05:38

hi

@user21820

hi

user21820

@toto: Hi.

user36188

hi @user21820

user21820

So how is it going?

user36188

hi I have a small Doubt about simple Interset Problems, are you free Now/

user21820

@user36188: Just ask your question. I'll answer it now if it's easy to answer.

user36188

05:49

Hi

Divide rs 2379 into 3 parts so that their amount after 2,3 and 4 years respectively may be equal, the rate of interest being 5% per annum at simple Interest, what will be first Part

I have Tried

amount will be equal for all the three parts for n=2,n=3 and n=4 Amount = Simple Interest + Principal 2379/3= will give the value for each part it constitutes 793 , we cannot directly divide that three parts May be another three different types of Number

let the first part Number part i will be take x, surely the second part will be 2379-x and how will take the value for third part,Please anyone share the Answer and Logi

user21820

room topic changed to Logic: All about logic. Feel free to join in but please stick to one topic at a time. =) [formal-systems] [foundations] [logic]

@user36188: Sorry that's not about mathematical logic. Please either ask on the main site or in another forum.

user36188

ok thank you

user21820

@user36188: I meant "in another chat-room".

user36188

which chat room for this type of question

Actually I am New

user21820

@user36188: Actually, the best is to ask a question, since it will be seen by everybody. Chat-rooms are more for informal or extended discussion.

user36188

05:53

ok

user21820

@user36188: I see you have already asked one question so far. Just carry on asking more!

user36188

ok

user21820

@user36188: Do note that you should use proper sentences and punctuation.

user36188

why they are always Devoting Me for asking the question

user21820

@user36188: You had 10 upvotes and 2 downvotes. You included your attempt in your original question, which is good. But you didn't use proper sentences and punctuation and didn't check your spelling. Furthermore, you didn't use LaTeX, as instructed by the FAQ which you were told to read before posting. Thus the downvotes were justified.

I personally wouldn't have downvoted though.

Martin Sleziak

06:02

@user36188 Probably the main chatroom: chat.stackexchange.com/rooms/info/36/mathematics

user21820

@MartinSleziak: Hello! Thanks.

user36188

ok Now I have Understand My Mistake

user21820

@user36188: No worry. Just format your questions nicely and they'll be good to go.

user21820

07:21

@MartinSleziak: And what to do with crankpots who keep posting nonsense about Godel's incompleteness theorem? I'm tired of them already.

3

Martin Sleziak

07:59

@user21820 ignore? vote to close and vote to delete, uf that makes sense?

user21820

@MartinSleziak: I would like to but since I've interacted with this crankpot quite a lot in trying to encourage them to actually start learning logic, I can't vote to close and delete without it seeming like I'm enforcing my opinion.

@MartinSleziak: The questions themselves are nearly gibberish, but I can guess the underlying ideas, which laymen are bound to have without a proper logic foundation. I guess I'll answer to that idea one more time and see how it goes.

toto

09:42

Hey user21820, how you doing ?

maybe you're sleeping now ?

@user21820 i was just wondering how we can define the minimum element of a subset of natural set

user21820

@toto: It depends on what you mean by "define".

Easiest way is to introduce a new function symbol "min"

toto

actually i'm talking about that because in the proof about the induction theorem

user21820

after you've proven that there is a unique minimum.

toto

well, cause i heard that you can define that by ordinals

using the definition of naturals from von neumann

user21820

Do you know how to prove that there is a unique minimum? You need non-empty set by the way. No ordinals involved.

toto

09:55

no don't know

well, i suppose you have to do it by induction

like proving that : exists y in A, forall x in A, y <= x

and prove that by induction

user21820

I'll leave you to figure out the missing part. It's where you need to use the "no minimum".

That proves existence of a minimum. In this case it is easy to prove uniqueness from that.

toto

That's a prove from absurdum right ?

user21820

Yes.

It's crucial. We can't prove it directly.

toto

i must do the induction part right ? the ... part ?

user21820

Yes.

toto

10:04

ok so, first, you take a subpart of N

you suppose that there isn't a minimum element

you prove that there isn't a minimum element by induction

user21820

No.

toto

then, it means that if you pick an element from the subpart of N

user21820

Read the proof outline carefully.

We are not proving what you think by induction.

toto

If not exists m in N ( forall x in S ( m <= x ) ):

Doesn't it means that you suppose that a minimum element doesn't exist ?

user21820

Yes. But the induction is not what you think.

The induction is about something else.

toto

10:08

Isn't a proof by induction ?

user21820

You must read what P is instead of assuming.

As I said, the induction is not about what you think.

toto

i thought induction was about

having a predicate P(n)

proving P(0), then P(n)=>P(n+1)

and then conclude P(n) forall n in N

isn't it ?

user21820

Yes, but you're still not paying attention to what I'm saying.

You said "you prove that there isn't a minimum element by induction".

That's wrong.

If you read carefully what P says, it is not about minimum elements.

toto

hum

Let P(k) assert that forall x in S ( k <= x ).

so it means that given a k integer >= 0, for every element x in the set S, k<=x

user21820

Yes. Sorry I forgot to say "for k in N".

toto

10:16

ah well, it means supposing that there exist a minimum called k

right ?

and prove that it exists by induction

user21820

No.

Just read it at face value; don't guess.

P(0) is trivially true, and says nothing about minim elements.

*minimum

Oops.

Sorry typo.. Corrected version below.

What I said about P is correct. I just accidentally put "N" instead of "S" in the assumption.

toto

i don't understand what i misunderstand

user21820

What does P(0) say?

toto

P(0) says that 0 is less or equal than every elements in S

user21820

Exactly. It is trivially true and has nothing to do with minimum elements.

P(1) says that every element in S is at least 1.

toto

10:23

yeah

user21820

And so on. Your goal is to finish the induction step, which does not prove that the minimum element exists.

toto

so it says that 1 is the minimum element

user21820

No!!

That's exactly why I keep saying you're guessing wrong.

toto

oh, okay

i thought the aim was to say that every subpart of N has a min element doing so

user21820

Find me a counter-example to your claim that P(1) says that 1 is the minimum element.

toto

10:27

well, if 1 is the minimum element

it means that every i in S is greater or equal than 1

so a counter example would be if S contains 0

user21820

No.

A counter-example to your claim means that P(1) holds but 1 is not the minimum element.

toto

you want me to find a counter example of P(1) ?

user21820

Your claim is "P(1) <=> 1 is the minimum element".

This is false. Find me a counter-example.

toto

well, if S contains 0, it will be a counter example

and the only one i though

no ?

user21820

No. Compute the truth value of both sides. They are the same.

toto

10:31

I think i don't understand the idea

what i see though your request is

user21820

Because you're not reading P correctly.

toto

"you have a set S, which contains some elements"

user21820

You read it correctly at first and then you guess its meaning until it becomes something else different.

toto

"i claim through P(0) that you an take each element of S, and every element of S will by less or equal than 0"

user21820

Wrong.

Read what you write carefully.

toto

10:33

well, it seems i've got a big problem so, because i don't understand P :(

user21820

You're not systematically translating P.

Don't anyhow guess. It's the worst thing to do.

State precisely in English what P(1) says.

toto

P(k) assert that forall x in S ( k <= x ).

user21820

English.

toto

so, i replace k by 1

P(1) assert that forall x in S (1 <= x)

so in english now

P(1) says that, in the set S which is a subset of N. If i take each element x of S

x will verify the predicate 1<=x

for me it's the same as saying

int check(k, S) {
foreach (x in S)
{
if (k > x)
return false;
}
return true;
}

isn't it a good way of thinking ?

user21820

Yes that is correct so far.

toto

10:38

okay

user21820

But just now you said:
> "i claim through P(0) that you an take each element of S, and every element of S will by less or equal than 0"

That's incorrect.

toto

oh yeah you're right

every element of S will be greater or equal than 0

user21820

Right. And also, earlier you claimed that P(1) <=> 1 is the minimum of S. That's also false.

toto

and for 1

user21820

Find me a counter-example.

toto

10:40

ah well, i see

if k is 1, and S contains the integer greater than 3 for example

P(1) will be true

but 1 will not be the minimum of S

user21820

Give me a specific counter-example.

{1,3} contains 3 but 1 is still the minimum of S.

toto

let S := {n in N | n > 3}

user21820

Good.

Or just {2,3}

toto

yes

user21820

Anyway so you can see that P(1) says nothing about the minimum.

toto

10:42

right

user21820

So at first you may find the induction strange.

We're simply proving that 0 is not a lower bound, 1 is not, 2 is not, and so on.

By induction every natural number is not a lower bound.

Argh1!

I don't know what I'm talking.

We're simply proving that 0 is a lower bound, 1 is also, 2 is too, and so on.

By induction every natural number is a lower bound.

toto

yes

that's right

Let c in S.
| Then P(c+1).
| Thus c+1 <= c.

i don't get this part

i understand it like

chose a c element in S

user21820

S is non-empty so we can get some c in S.

toto

then we know that P(c) is true, and P(c+1) true too

user21820

We don't need P(c).

We only need P(c+1).

toto

10:46

so if P(c+1) is true

it means that

forall x in S, c+1<= x

user21820

Yes, and now apply it to c.

toto

forall x in S, c <= x

user21820

No apply the quantified statement.

Not P.

c in S.
forall x in S ( c+1 <= x ).
Thus what?

toto

thus c <= x-1 ?

user21820

No.

"forall x in S ( c+1 <= x )" says something about every x in S.

Apply that to c, which is in S.

toto

10:52

ah, you mean, replace x by c ?

c+1 <= c

and thus contradiction since c+1>c

user21820

Right. Note that "c <= x-1" is meaningless because "x" is undefined.

toto

hu... that's great, but well, i never find that by myself

user21820

I purposely didn't want to say "replace" or "substitute" because although that's the programmer's way (systematic and excellent), you must first grasp the meaning.

toto

yes

so well, i'm now trying to catch the global idea

we try to prove that each element of N is a lower bound

user21820

If you haven't read my post about Fitch-style natural deduction for quantifiers, you should. It gives you the systematic rules for deduction using them, including this one.

toto

10:54

and then, when we succeed

user21820

Yes.

toto

we prove that an element can't be it's own lower bound right ?

user21820

an element of S plus 1 can't be a lower bound.

You need the "+1".

toto

hum, okay, hard to visualize (actually i try to visualize everyting, don't know if it's a great way ?)

user21820

I always try to balance your reasoning out. Sometimes you think syntactically and miss the semantics (meaning). Sometimes you want an intuitive visualization but it may be easier to just chase the symbols.

There is a visualization though.. Just follow the induction.

At first we know that 0 is a lower bound.

So 0 can't be in S, otherwise it would be a minimum of S.

So 1 is a lower bound.

So 1 can't be in S, otherwise it would be a minimum of S.

So 2 is a lower bound.

Induct.

toto

11:01

"At first we know that 0 is a lower bound"

why ?

from P(0) ?

but it states that for 0, forall x in S, 0<=x

meaning that we can have an x element in S equal to 0

so 0 could be a minimum and not a lower bound

user21820

0 is always a lower bound on any set S <= N.

my "lower bound" means "less than or equal to"

toto

oh

user21820

"strict lower bound" means "strictly less than"

Just terminology issues.

toto

i thought lower bound means strickly less, sorry

user21820

No problem; I could see that.

toto

11:04

so well wait

P(0) means, 0 is a lower bound of S

then you suppose that P(k)'s true, so k is a lower bound of S by hypothesis

and then we try to prove P(k+1) from P(k)

user21820

Yes.

toto

well i'm trying to prove the induction step from the hypothesis

meaning that from a given k we assume that forall x in S, k <= x

user21820

Yes.

toto

so i tried

k+1 <= x+1

k+1 >= x

right ?

well no

absolutely not

user21820

I don't know what's happening haha.

Ask yourself whether k in S or not.

toto

11:11

k+1 <= x+1

so that means that x+1 could not be in S

user21820

I don't know what you mean.

toto

well, since x isan element of S

x+1 could be outside of S ?

user21820

How about this. I know you don't want to leave this topic, but it might be more efficient if you first learn natural deduction.

toto

yes

user21820

Specifically look at the rules for quantifiers in math.stackexchange.com/a/1684204.

toto

11:13

haven't you a book about that ?

user21820

Nobody does it the way I do, although there are similar variants. Unfortunately there is no online reference I could find.

Just look at the rules I gave; you're a programmer so it should be no trouble for you.

Notice that there is only one way to derive a sentence of the form "forall x in S ( P(x) )".. You must open a new subcontext "Given x in S".. and the proof will always look like:

Given x in S:
| ...
| P(x).
forall x in S ( P(x) ).

I want you to attempt to fill in the gap in the induction proof here in the format of natural deduction.

Let me reproduce the outline with a bit more detail so that you can see where this is going.

toto

actually, i don't know what is the "way to follow" in order to do correctly a proof

hum, well, you're right, i must learn natural deduction first

but it feels weird for me

(go eating, come back in half an hour :))

user21820

shashank

Can we discuss physics in this chat room?

user21820

11:33

@shashank: If and only if it is related to the mathematical study of logic.

A little bit of related meta-physics is fine, but not too much. =)

shashank

Nope, it isn't.

Sorry to bother you.

user21820

@shashank: There are chat-rooms for physics. See chat.stackexchange.com/….

toto

12:08

oh, by the way @user21820

i was looking at the proof of the recusion theorem

and i didn't get why do we need to prove the tird step

third*

this third step was about finding two function h1 and h2

such that h1 and h2 agree on {0...n}

user21820

12:25

Quote it.

toto

The third step is to let (hk)k∈N(hk)k∈N be a sequence of functions such that hkhk witnesses P(k)P(k) for every k∈Nk∈N, and show that hihi and hjhj agree on {0..i}{0..i} for every i,j∈Ni,j∈N such that i<ji<j. Again, this is by induction ('on jj').

user21820

Quote the formal one.

toto

how ?

user21820

The one I gave you yesterday.

toto

hu, i'll have to scroll back for a moment :o

Step 3 first does
for each k in N let h[k] : {0..k}->E such that ( h(0) = c and forall n in N[<k] ( h(n+1) = g(h(n)) ) ) )
Note that this is valid because we proved uniqueness. Here I'm reusing the variable name "h" and this time it is a sequence, which is nothing more than a function with domain N.

user21820

12:31

Although this is a chat-room, you should save whatever you wish to keep, because it's a waste of time for me to keep searching for what I've typed previously. As you can see, it's troublesome to find it. I want the later version:

Given set E and function g : E->E and c from E:
| [Steps 1,2,3,4]
Step 1 proves
forall k in N ( exists h : {0..k}->E ( h(0) = c and forall n in N[<k] ( h(n+1) = g(h(n)) ) ) )
Step 2 proves
forall k in N ( forall h,h' : {0..k}->E ( h(0) = c and forall n in N[<k] ( h(n+1) = g(h(n)) ) ) and ( h'(0) = c and forall n in N[<k] ( h'(n+1) = g(h'(n)) ) ) implies h = h' )
Step 3 first does
foreach k in N let H[k] : {0..k}->E such that ( H[k](0) = c and forall n in N[<k] ( H[k](n+1) = g(H[k](n)) ) ) )
by lots of set-theoretic machinery and then proves

toto

well yes, you're right

so, i don't uderstand why we must prove step 3

since we prove existence and uniqueness of h

why do we need to prove that restrictions agrees ?

user21820

Ok that allows us to do the first part of Step 3 which is to construct a sequence of functions H[k] for k in N.

The second part is needed for Step 4 to work.

Whether or not you classify it under Step 3 is a matter of taste.

in Step 4 we took the union of the whole sequence of functions. It is not obvious that the result is a function!

That is what the second part of step 3 is for. In general when we have a sequence of functions where the appropriate restrictions agree, the union will also be a function.

toto

in step 4, i understood that we do the union of all the functions

and then we proof it's still a function

seems pretty logic to do that

user21820

Yes that proof will essentially be the same as proving that the restrictions agree, though you can do it directly.

toto

but, why do we prove that each function agrees with another one which is it's restriction

ah well, i think i understood

you mean that, we create many functions which are a restriction of h on every n of N

user21820

12:37

I'm not sure what you mean by your last sentence.

toto

then you prove that they share the same element on the stronger restriction

and then you do the union of all functions

user21820

I think you mean "which are the restriction of the intended f"

not "restriction of h"

toto

the first part of Step 3 which is to construct a sequence of functions H[k] for k in N.

user21820

Yes.

We can jump straight to Step 4 and take their union.

Then we need to prove that the union is a function.

toto

oh, okay

user21820

12:40

The proof will involve the same reasoning.

toto

but why in the post you said that we first should prove

user21820

That's because it's the general structure of all such proofs.

toto

that H[k] and H[k+1] are equal on the domain {0...k}

general structure ?

user21820

Yes. This technique is not just applicable for this proof.

toto

what is the "general idea" ?

prove existence

then uniqueness

and union which is still a function ?

user21820

12:42

In general, it goes: (1) Build a sequence of approximations; (2) Prove that any term in the sequence contains every preceding term; (3) Take union to get the result.

It applies not just to functions.

Note that for functions f,g to agree on Dom(f), it means that f is a subset of g. This is how it fits the general technique.

toto

approximation ? what did you hear from that ?

user21820

Hmm. Do you understand the English word?

toto

i don't know, maybe, i'll check the translation

for me the meaning is about finding something that is more or less what is expected

user21820

π ~= 3;
π ~= 3.1;
π ~= 3.14;
...
π == 3.1415926...

This is a reasonable analogy. We have a sequence of approximations to π.

toto

huu ! great !

user21820

12:45

Note that each approximation agrees with the preceding ones on all the digits that the preceding ones have.

toto

yeah right

user21820

So we can 'union' (combine) them all to get an infinite sequence of digits

toto

that's great !

where did you learn that ?

user21820

Nowhere.

toto

from yourself ?

user21820

12:47

Probably.

toto

but how did you know that is a valid reasoning ?

user21820

I said it's an analogy. It's not valid reasoning since we didn't define π.

toto

yeah okay, but, my question was much general

it was about, how did you know that a proof is a valid one ?

user21820

It's a general technique but you will have to verify each step of course.

toto

i mean, you're on a problem, you want to find a proof of a theorem for example

how can you ensure yourself that the way you're reasoning is a valid one ?

user21820

12:49

I didn't say it would always work!

In this case it does, because we can prove Steps 1 to 3.

user131753

Why don't you use LaTeX in chat?

toto

yes okay, but my question is, how can you convince yourself that the prove is complete ?

what does tell you "okay, you're done, proof complete"

user21820

If you succeed, then the technique works and we know that Step 4 will work even without trying to prove it. (But for you, you must go and prove it.)

@user170039: Because it's slow to type LaTeX and I don't have MathJax support here.

@user170039: But everyone else is free to type in LaTeX. I can certainly read.

toto

$\exists a \in C$

ho well just trying if latex was formatted

user21820

Let me repeat the technique.

toto

12:53

@user21820, the thing that disturb me

user21820

(1) Build a sequence of approximations; (2) Prove that any term in the sequence contains every preceding term; (3) Take union to get the result.

toto

is that we try to prove something on an infinite set

so how can you say that you're resoning is valid on the infinite ?

Yeah, i understood

user21820

Erm, the proof doesn't involve infinity.

At least for the recursion theorem.

toto

but, i just wanted to know if something tells us "that's okay to do it that way"

@user21820, but, you prove that the function is defined on all the natural integers

so you prove it on infinity no ?

user21820

Point out the step that fails. Each step is justified by the ZF axioms. If you disagree with ZF, then you'll have to pick another formal system. The first part of my answer at math.stackexchange.com/a/1893865/21820 is what you might expect to see in a system that does not have the notion of infinite sets.

toto

12:57

ah i see

user21820

If you already accept the notion of N as a single collection of all natural numbers, then you essentially have accepted enough of ZF to be satisfied by the ZF proof.

toto

(1) Build a sequence of approximations; (meaning that you construct the approximations according to ZF, so, they're valid) (2) Prove that any term in the sequence contains every preceding term (proved by recurrence, so it was proved by a valid theorem, so true in ZF) (3) Take union to get the result (since the union is an axiom of ZF it's valid to do it).

user21820

Yes.

That's right.

But if you don't accept that there is a single entity that is infinite, then you can't take the union so simply, and I think you need to have a notion of procedures that may not halt, which is the way my first proof goes.

Notice that in that proof we construct a procedure (treat it as the description itself), which we can perform for any finite number of steps.

toto

well, actually, i know the axiom of infinty (from ZF), used by the von neumann construction of naturals, so that's ok

Transcript for

♦ $Mathematics$ Logic

Transcript for

♦ Logic

♦ $Mathematics$ Logic