Basic Mathematics - 2021-07-16

user21820

09:09

@Prithubiswas Well, just don't use "n" for negation, use "¬" or plain "not". I don't mind pure ASCII, like "( A implies not B ) and B". But the proof is correct. So go on to the next exercise!

@F.Zer You misled yourself with the z. Actually, it's supposed to be obvious from the canonicalization idea.

Jul 10 at 17:14, by user21820

Also, the goal, which is to find x,r∈ℕ such that k·x = m+r where 0 ≤ r < k, is itself a typical instance of the canonicalization technique. In this case, we are finding the closest multiple of k that is at least m, where "the" is justified because it exists (by well-ordering) and is unique. Why do I consider this a canonicalization? Because we are basically decomposing m in a determinate manner into a big and small piece.

Jul 10 at 17:34, by user21820

When you view x,r as related to k,m via that notion of canonical representation (of m in relation to copies of k plus a remainder), you won't easily forget what x (number of copies) and r (remainder) stand for.

In the case of k < m, we want to decompose m into copies of k plus as small a remainder as possible.

In the case of k > m, we want to decompose ... into copies of ... plus ... So if k = m·y+r, and r ≥ k, then you're supposed to prove that r was not the smallest possible.

Prithu biswas

@user21820 I actually type o for disjunction , a for conjuction , > for implies and T for the ⊥ sign and n for negation.Then I use the text-editor to replace them with the proper symbols.I forgot to replace n with the ¬ symbol.Sorry for that.

user21820

@Prithubiswas Oh I see. If you are using Windows, you can use AHK hotstrings, which I use to type unicode symbols.

Prithu biswas

If ¬(A∨B):
   If A:
      A∨B
      ¬(A∨B)
      ⊥
   A⇒⊥
   ¬A
   If B:
      A∨B
      ¬(A∨B)
      ⊥
   B⇒⊥
   ¬B
   ¬A∧¬B
¬(A∨B)⇒¬A∧¬B
If ¬A∧¬B:
   ¬A
   ¬B
   If A∨B:
      If A:
         ¬A
         ⊥
      A⇒⊥
      If B:
         ¬B
         ⊥
      B⇒⊥
      ⊥
   A∨B⇒⊥
   ¬(A∨B)
¬A∧¬B⇒¬(A∨B)
¬(A∨B)⇔¬A∧¬B

@user21820 attempt for P4.

user21820

@Prithubiswas Correct!

Note that this kind of case-split ending in contradiction is one reason for having a dedicated "⊥" symbol.

Otherwise if you make do with a literal contradiction of the form "C∧¬C", you would have to deduce that in every case just to obtain a contradiction outside the cases.

Prithu biswas

@user21820 I will probably not use AHK because it seems a bit too complicated to me.I am more confortable with the find and replace method.Next time I will just check to see if I missed something to replace.

If ¬(A∧B):
   If ¬(¬A∨¬B):
      ¬(¬A∨¬B)⇒¬¬A∧¬¬B [P4]
      ¬¬A∧¬¬B
      ¬¬A
      A
      ¬¬B
      B
      A∧B
      ¬(A∧B)
      ⊥
   ¬(¬A∨¬B)⇒⊥
   (¬A∨¬B)
¬(A∧B)⇒(¬A∨¬B)
If ¬A∨¬B:
   If A∧B:
      A
      B
      If A:
         If ¬A
            A
            ⊥
         ¬A⇒⊥
         ¬¬A
      A⇒¬¬A
      ¬¬A
      If B:
         If ¬B:
            B
            ⊥
         ¬B⇒⊥
         ¬¬B
      B⇒¬¬B
      ¬¬B
      ¬¬A∧¬¬B
      ¬¬A∧¬¬B⇒¬(¬A∨¬B) [P4]
      ¬(¬A∨¬B)
      ¬A∨¬B
      ⊥
   A∧B⇒⊥

@user21820 attempt for P5.

user21820

09:38

@Prithubiswas Clever, using (P4). One way without would be:

If ¬(A∧B):
  If ¬(¬A∨¬B):
    If A:
      If B:
        A∧B.
        ⊥.
      ¬B.
      ¬A∨¬B.
      ⊥.
    ¬A.
    ¬A∨¬B.
    ⊥.

But your second part is unnecessarily long.

Note that you almost never have to create a subcontext "If A:" after having deduced "A".

If ¬A∨¬B:
  If A∧B:
    A.
    B.
    If ¬A:
      ...
    If ¬B:
      ...

Like this will do.

@F.Zer: I made a mistake; my last comment to you should have said "So if k = m·y+r, and r ≥ m, then you're supposed to prove that r was not the smallest possible.

Prithu biswas

@user21820 Your solution is much better than mine.I wondered if there was a way to prove it without (P4).Turns out there was a much simpler way.

@user21820 Agreed. If A and if B are unnecessary because A and B are already deduced.

I will probably work on P6 and P7 tomorrow.

user21820

@Prithubiswas Okay! =)

F. Zer

12:29

@user21820 Thank you. When you say: "So if k = m·y+r, and r ≥ m, then you're supposed to prove that r was not the smallest possible." That's good since that is exactly what I am trying to prove !

@user21820 It's seems I still don't get the canonicalisation idea and that is an important concept.

user21820

@F.Zer But you're not following the exact same reasoning as in the other case!

You have to understand how you managed to prove in the other case that r was not the smallest possible.

And then use the same kind of reasoning here.

Obviously you can't expect it to be a copy-and-paste job.

F. Zer

@user21820 Indeed. I am trying to decode how can I emulate the exact same reasoning.

@user21820 In the other case, I added m to both sides r ≥ k.

I thought perhaps adding k to both sides of r ≥ m.

r + k ≥ m + k

user21820

@F.Zer But why? You can't be adding for no good reason. Otherwise I can add 1,2,3 to both sides too.

F. Zer

@user21820 Yes, you're right.

@user21820 The most sensible thing for me is adding m·y to both sides of r ≥ m and get r + m·y ≥ m + m·y and then k ≥ m + m·y

Would be a good thing to use the equality "k = m·y + r"

These exercises are really interesting because they force me to reason. It's difficult to do them resorting to brute-force. It's necessary to really understand the problem.

user21820

@F.Zer And then?

F. Zer

12:44

@user21820 k ≥ m·(1 + y)

There are two cases. In the equal case, m divides k.

F. Zer

12:57

@user21820 Regarding this quote, in which way we are trying to decompose m in the expression k·x = m·y + r ? This puzzles me.

I see it as decomposing the expression "k·x".

user21820

@F.Zer I never said "k·x = m·y + r". You do not seem to have read my quoted messages before that carefully.

F. Zer

Re-reading once more.

@user21820 I apologise. That was a typo. I had in my mind "k·x = m + r" but instead wrote the other thing in auto-pilot.

Oh, m is equal to copies of k (plus a remainder).

@user21820 Shouldn't it be m plus a reminder is equal to copies of k ?

So, in the case k < m, we want to decompose k into copies of m (plus a reminder).

If someday "re-reading your explanations" becomes an olympic sport, I will have chances of getting a Silver medal, at least. I probably read them at least 30 times, on average :-)

user21820

13:29

@F.Zer Yes that is what it technically is, but who cares whether the remainder is positive or negative? The idea is still the same; making one number close to a multiple of the other.

@F.Zer Yes, and so look at your last statement.

46 mins ago, by F. Zer

@user21820 k ≥ m·(1 + y)

F. Zer

@user21820 Good.

@user21820 Oh, rearranging the LHS gives k ≥ m·y + m...

That certainly looks familiar...

I see k is (at least) equal to copies of m (plus m).

And I see m is (at most) r. Perhaps, I should prove r ≠ m and conclude m < r,

user21820

Look, originally you claimed "r∈ℕ is minimum such that ∃t∈ℕ ( k = m·t+r )". If r is too big, ...

F. Zer

@user21820 I do have "r ∈ ℕ is minimum...". Seems like an obvious step. I am trying to understand why r ≥ m is impossible as a consequence of the former statement. Why r can't be too big...

user21820

@F.Zer You can't understand because you still do not think what it is minimum for. You just think "it is minimum". But you don't think about how to actually find the minimum.

F. Zer

@user21820 Oh, perhaps that is the key. Thank you.

I will think.

@user21820 To satisfy the equality, I'd have to adjust m, I think. So, if r' > r, then m' < m in the expression ∃t∈ℕ ( k = m'·t+r' )

If I change r, I should change m, I think.

user21820

13:47

???

9 mins ago, by user21820

Look, originally you claimed "r∈ℕ is minimum such that ∃t∈ℕ ( k = m·t+r )". If r is too big, ...

Go and find the minimum. I'm now pretty sure you didn't try small cases.

F. Zer

@user21820 I should change t !! k and m are fixed !

6 = 3·1 + 3

6 = 3·2 + 0

The second expression has the minimum remainder. I've changed t.

@user21820 I did it in an incorrect way. I do not know how can I actually find the minimum. As you said, I just thought "it is minimum". My small cases didn't include a step by step of finding the minimum.

user21820

@F.Zer So you're changing t to find a minimum. Is just one small case good enough for you to see what's going on?

F. Zer

@user21820 Of course, not. I will try more !

user21820

It's also odd that you pick such a 'poor' small case; it's like picking a right-angled triangle when told about a theorem for general triangles, because you picked one which gave remainder 0.

Sometimes, a single good case is enough, but many poor cases may not be.

F. Zer

Excellent advise.

F. Zer

14:10

@user21820 I picked another case.

17 = 2*0 + 17
17 = 2*1 + 15
17 = 2*2 + 13
17 = 2*3 + 11
17 = 2*4 + 9
17 = 2*5 + 7
17 = 2*6 + 5
17 = 2*7 + 3
17 = 2*8 + 1

user21820

So? Why r < m?

F. Zer

@user21820 Because r is the minimum value that satisfies "∃t∈ℕ ( k = m·t+r )". Every other value is greater than r.

shintuku

hey @user21820, hope you are well! thanks again for the help last time. I was wondering if you were up for a quick question about the implicit function theorem for $f:\mathbb{R}^n \rightarrow \mathbb{R}$

user21820

@F.Zer Err... Why based on your method of finding r is r < m?

@shintuku Just ask. And yes, I'm doing fine, thanks for asking!

shintuku

great, good to know! alright:

The implicit function theorem for $f:\mathbb{R}^n \rightarrow \mathbb{R}$ requires that there exist $f(\vec a) = 0$, and also requires that $\frac{\partial f}{\partial x_n}(\vec a) \neq 0$ for some variable $x_n$ of $f$, and then states there is a neighborhood of $V$ of $\vec a$ such that for $\vec x \in V$, we have $f(\vec x)=0$ and $x_n$ as a function of $x_1, ..., x_{n-1}$.

But doesn't the requirement that $\frac{\partial f}{\partial x_n}(\vec a) \neq 0$ imply that $f(\vec a + t\vec e_n) \neq 0$, where $\vec e_n$ is the nth standard basis vector and $t$ goes to $0$, and therefore contradict the statement that $f(\vec x) = 0$ in a neighboorhood of $\vec a$?

user21820

14:22

@shintuku The statement seems broken, so I don't think you're quoting it correctly.

shintuku

hm, give me a second

user21820

Looks very very different...

shintuku

hm I think my understanding of it is completely wrong hehe

there is no contradiction between the requirement that $f(\vec a + t\vec e_n) \neq 0$ and the consequence that $f(\vec x) = 0$?

user21820

Well, firstly you need the derivative to be continuous, so that you don't get oscillations arbitrarily close to the point.

shintuku

right

user21820

14:28

Secondly, even the cited version seems logically unclear.

shintuku

I was thinking that was a possibility, you have no idea how many hours I spent on it yesterday, very painful hehe

user21820

It looks like the author wanted to say "f(x) = 0 ∧ x[1..n-1]∈V ∧ x[n]∈W ⇔ x[n] = φ(x[1..n-1])".

F. Zer

@user21820 I found r by increasing t. Because t is the greater value that satisfies "∃t∈ℕ ( k = m·t+r )" ?

user21820

@F.Zer So...

1 hour ago, by user21820

46 mins ago, by F. Zer

@user21820 k ≥ m·(1 + y)

You got this when r was too big. "Because t is the greater(?) value ...". Don't you see a problem?

F. Zer

@user21820 Maximum value, sorry.

user21820

14:34

@F.Zer Yes, I know that. So why are you not seeing...

F. Zer

@user21820 Mmm...what would be the problem ?

user21820

5 hours ago, by user21820

@F.Zer: I made a mistake; my last comment to you should have said "So if k = m·y+r, and r ≥ m, then you're supposed to prove that r was not the smallest possible.

> ... y is the greatest value that satisfies ... but k ≥ m·(1 + y) ...

shintuku

hm, but wouldn't f(x) = 0 still contradict df(a)\dx_n \neq 0?

user21820

@shintuku Why? You already have f(a) = 0.

shintuku

right, f(a) = 0, and x is in a neighborhood of a, and a + te_j is such an x in this neighborhood, but isn't f(a + te_j) not equal to 0?

user21820

14:38

@shintuku Nobody is talking about anything else other than f(a) being equal to zero.

Do you know what "f(x) = 0 ∧ x[1..n-1]∈V ∧ x[n]∈W ⇔ x[n] = φ(x[1..n-1])" means?

shintuku

I think so, f(x) = 0 means x[1...n] is mapped to 0, for x[1...n-1] in V and x[n] in W such that it is a function of x[1...n-1]

user21820

No.

Please read the logical structure before attempting to read the individual pieces.

A ∧ B ∧ C ⇔ D.

shintuku

sorry

do I read (A ^ B ^ C) iff D, or A^B^(C iff D)?

user21820

The first. The standard precedence rules are (highest to lowest): ¬,∧,∨,{⇒,⇔}.

shintuku

oh, that changes things quite a bit

user21820

14:43

The author's phrasing is unclear, because one should not mix English with symbols.

That's why I changed to purely logical.

shintuku

ahhhhhhhhhhhh, f(x) = 0 only if x[n] is actually a function of x[1...n-1]!

user21820

In fact, English is typically taken as lowest precedence, and if so then the author's statement would (as you say) be quite different.

@shintuku *is actually φ of x[1..n-1].

shintuku

right right

wow, thanks truly

user21820

You're welcome!

shintuku

i spent so much time on this and couldn't figure it out hehe, that was super helpful

user21820

14:46

Glad it put an end to the "painful hours"!

shintuku

hehe

cheers, have a good day!

F. Zer

@user21820 y + 1 is greater than y ! I would try to phrase it precisely.

@user21820, before meeting you, I have never thought possible this kind of logical reasoning. No mathematician had ever taken me into a trip like this one. Derived results were simply given and we moved on. I deeply appreciate your knowledge and teachings.

user21820

@F.Zer Exactly, so you ought to apply your own procedure for finding the minimum to extract a contradiction from this.

F. Zer

@user21820 Good. I'll work on that. I have to go, now. Have a nice day !

user21820

Ok bye!

Tapi

18:03

find the number of solutions to cos(cos(x))=x/10. How can I sketch a graph for this/ are there other ways to do it?

user21820

18:20

@Tapi Well you can start by finding the period and bounds of cos∘cos.

F. Zer

@user21820 I think perhaps proving y is the greatest value that satisfies k = m·y + r would be good.

user21820

@F.Zer No, not because it's not a good idea, but because the required proof is so short that it is pointless to take a longer route.

F. Zer

Good.

user21820

You found a bigger y, and you know that's a problem. Translate that bigger y into smaller r!

F. Zer

I realise now r and y are mutually dependent. You know, fortunately I previously thought something like that. However, I still don't have enough confidence on my intuition to carry on. I frequently distrust my intuition.

@user21820 That's great. I found a bigger y. However, the statement k ≥ m·(1 + y) lacks r.

I would have to think how can I connect the dots between k = m·y + r and k ≥ m·(1+y)

I feel very close to understanding it.

user21820

18:34

@F.Zer Take a look again at your proof for the other case, and see how it produced the needed counter-example. It's going to be the same flavour here, even if superficially different.

F. Zer

Good.

user21820

@F.Zer Technically, you do not need intuition here. You are in a context where k,m are fixed, and asking for minimum r such that ∃t ... so clearly r,t are tied together. When you get y from ∃elim on that, the y,r are tied in the same way.

F. Zer

@user21820 That's great ! There is an Existential ! So, I do not know anything about t. I see no intuition is needed.

F. Zer

19:01

If k+m = n:
  If m > 1 ∧ ¬∃d∈ℕ ( d > 1 ∧ d | k ∧ d | m ):
    If k = m:
    k ≠ m.
    [Prove ∃x,y ∈ ℕ ( k·x = m·y + 1 ) ]
    If k < m:
    If k > m:
      Let z ∈ ℕ such that m + z = k
      k = m·1 + z
      ∃t,u∈ℕ ( k = m·t+u ).
      Let r∈ℕ be minimum such that ∃t∈ℕ ( k = m·t+r ).
      Let y∈ℕ such that k = m·y+r.
      If r ≥ m:
        r + m·y ≥ m + m·y
        k ≥ m + m·y
        k ≥ m·(1 + y)
        [Prove y is the maximum value such that k = m·t + r]
        Given y' ∈ ℕ:
          If k = m·y' + r:

@user21820, you already said I shouldn't take the longer route.

Unfortunately, it doesn't occur to me how can I translate bigger y into smaller r. At least, I am producing something instead of getting stuck forever.

By the way, I do realise my latest attempt is wrong.

There is a typo, here: y ∈ ℕ is the maximum value such that k = m·t + r. That t should be y.

user21820

@F.Zer It's not just a typo. It is fatally flawed, because you used the same r for both y and y'.

I mean, it cannot possibly get you anywhere because once you fix r and get y from that you obviously cannot change either.

F. Zer

@user21820 Yes, that proof attempt is a disaster.

user21820

Ok so just go back to your example of 17. It's still not a good small case, because 2 is too small. But at least you should have run through the steps with that.

Why in that example did every r fail except the last one?

F. Zer

@user21820 Going back there.

user21820

5 hours ago, by F. Zer

@user21820 Because r is the minimum value that satisfies "∃t∈ℕ ( k = m·t+r )". Every other value is greater than r.

Before you even talk about r, you need to find it. And that means you need to explain why every other candidate failed even before you reach the correct r.

F. Zer

19:15

That’s good.

@user21820 I have some explanation; however, don’t want to enter into circular reasoning mode.

I will try another case.

@user21820 I was going to say that, in each case, r > y but that’s not true.

@user21820 To find r, I would subtract multiples of m from k.

@user21820, in every case, y is not the greatest value that satisfies k ≥ m·y. That's why it fails !

I want the closest multiple of m to k. That multiple is bound to variable y.

user21820

19:47

@F.Zer Well, that's correct, but not the way it was set up. We did not pick maximum y∈ℕ such that k ≥ m·y. We picked minimum r∈ℕ such that k is a multiple of m plus r.

The former is not given by any preceding lemma. The latter is given by well-ordering.

Yes, if r ≥ m then you can find k ≥ m·(y+1), which gives "bigger y" than ought to be possible, but why can't you just find "smaller r"?

I'm just going to give the answer. If r ≥ m then r is m plus something, so k = m·y+r = m·(y+1)+?

F. Zer

Excellent. Very clear. I will sketch something before looking at your solution.

F. Zer

20:16

@user21820 If I find a y’ greater than y, that forces r to be negative ! What do you think ?

I haven’t looked at the solution, yet.

@user21820 k = m·y+r = m·(y+1)+a, for some a.

user21820

@F.Zer Exactly. Was that so hard?

Should be easy to get your contradiction from that.

F. Zer

@user21820 Of course not. I could find the answer really quickly. Lol :-)

@user21820 Good.

I will sketch the solution.

F. Zer

20:39

@user21820 From k = m·(y+1)+a, ∃ t ∈ ℕ ( k = m·t + a) ∧ a < r.

@user21820 Seriously, that wasn't hard. I can't believe missed the use of axiom: "∀x,y∈ℕ ( x≤y ⇒ ∃z∈ℕ ( x+z = y ) )"

I will write the full solution in a moment.

Given n∈ℕ:
  ∀i∈ℕ ( i < n ⇒ Q(i) ):
    Given k,m∈ℕ:
      If k+m = n:
        If m > 1 ∧ ¬∃d∈ℕ ( d > 1 ∧ d | k ∧ d | m ):
          If k = m:
          k ≠ m.
          [Prove ∃x,y ∈ ℕ ( k·x = m·y + 1 ) ]
          If k < m:
          If k > m:
            Let z ∈ ℕ such that m + z = k
            k = m·1 + z
            ∃t,u∈ℕ ( k = m·t+u ).
            Let r∈ℕ be minimum such that ∃t∈ℕ ( k = m·t+r ).
            Let y∈ℕ such that k = m·y+r.
            If r ≥ m:
              r + m·y ≥ m + m·y

Clearly, since r = m + a and m > 1, a < r. However, I should justify it.

My justification is:

m > 1
m + a > 1 + a
r > 1 + a > a
a < r

@user21820, does that justification satisfy you ?

I can now understand why you said the proof for the other case was similar: the first step was "Let z ∈ ℕ such that m + z = k". That was the crucial step here. For some reason, I didn't connect the ≥ symbol with that PA- axiom. Well, really it is the lemma: "∀x,y∈ℕ ( x≤y ⇒ ∃z∈ℕ ( x+z = y ) )"

user21820

20:59

@F.Zer What's z for? You didn't use it... You're confusing yourself with your later (crucial) use of that axiom to get a (opposite from z).

Anyway, the rest looks ok, and well you can check each step yourself, right? =)

F. Zer

@user21820 Yes, I did use it in the other case. I quote:

If k > m:
	Let z ∈ ℕ such that m + z = k
	k = m·1 + z
	∃t,u∈ℕ ( k = m·t+u ).

But perhaps I am missing your point.

@user21820 Yes, I am satisfied with it !

@user21820 What do you mean by "opposite of z" ?

user21820

@F.Zer Oh I forgot about that, since k = m·0+k, though of course that way is easier (less axioms).

But what I just said shows that it is not crucial, contrary to your comment.

It's only the "let a ..." that is crucial because without that a you simply don't have a counter-example to the minimality of r.

Alright, I'm off! See you next time!

F. Zer

@user21820 Oh, you're right ! In this latest proof, it was the crucial step. In the older, not crucial.

@user21820 Thank you so much for all your help ! See you !

Transcript for

♦ $Mathematics$ Basic Mathematics

Transcript for

♦ Basic Mathematics

♦ $Mathematics$ Basic Mathematics