Basic Mathematics - 2021-07-04

« first day (1153 days earlier) ← previous day next day → last day (1031 days later) »

7:57 AM

We use strong induction along k+m, so we can assume (PA5) holds for any k,m with a smaller sum. Prove that k ≥ 1. Then k·(m+1) > m. By well-ordering, let x∈ℕ be minimum such that k·x > m. By well-ordering again let y∈ℕ be minimum such that k·x > m·y. Let r∈ℕ such that k·x = m·y+r. Prove that 0 < r < m. If r = 1, we are done. If r > 1, apply the induction on r,k since r+k < k+m, and let p,q∈ℕ such that r·p = k·q+1, and hence k·(x·p) = m·y·p+r·p = m·y·p+k·q+1, so k·(x·p−q) = m·(y·p)+1.

@F.Zer: I just posted a fixed sketch (the original was wrong and can be fixed but I found a simpler way).

Also, PA does not have subtraction but you can use the appropriate PA− axiom to obtain x·p−q after you have proven x.p ≥ q.

3 hours later…

10:36 AM

@user21820 If I have a sequence X for A , I want to "separate" the sequence into two sequences Y and Z which are sequences for B and C. Is there any terminology for it ?

@Prithubiswas There is a formal way to do it, but I don't need you to know or do it yet. Just describe it a bit.

Don't worry about the details; I just want to see the correct logical structure to make sure you understand induction. How to reason about sequences and construct sequences is not important now.

@user21820 Also in the proof outline:

Given A∈Game such that P(k) and A has (m+1) copies of (k+1):
Let B,C∈Game such that ... [fill this in] ...
Given any move sequence X for A:
Let Y,Z be ... which are move sequences for B,C.
...
Thus Y,Z are finite.
Therefore A eventually ends.
Therefore Q(m+1).

Shouldn't we first say After "Thus Y,Z are finite" that "X is finite" and then "Therefore A eventually ends" ?

Please paste the indented proof outline separately from normal messages, so that you can preserve indentation, otherwise it becomes meaningless.

@Prithubiswas Yes you can, to be more explicit. Do note that the "Therefore A eventually ends" is outside the "Given any X ..." subcontext because A is the game and so claiming that it eventually ends is claiming that every move sequence for A is finite.

With the "fixed font" button?

@Prithubiswas Yes.

1 hour later…

11:56 AM

Define P(k) := A starts with numbers all at most k+1
Define R(k) := ∀A∈Game ( P(k) ⇒ A eventually ends )
R(0)
Given k∈ℕ such that R(k)
  Define Q(m) ≡ ∀A∈Game ( P(k) and A has m copies of (k+1) ⇒ A eventually ends)
  Q(0).
  Given m∈ℕ such that Q(m):
    Given A∈Game such that P(k) and A has (m+1) copies of (k+1):
      Let B,C∈Game such that
      B has all of the positive integers of A which are less than k+1
      C has m+1 copy of k+1
      Given any move sequence X for A:
        Let Y,Z be subsequences of X which are move sequences for B,C.

@user21820 Inform me if there are mistakes.

@Prithubiswas: Next time, you can use the Sandbox for experiments on SE chat. =)

@Prithubiswas Give me a moment.

@Prithubiswas By the way, is it only my browser or is it displaying the unicode symbols wrongly in yours? I don't see "∀" showing correctly (unlike just yesterday), though I know how to fix it (by overriding the CSS using greasemonkey).

12:18 PM

@user21820 Ok I will use sandbox if I want to learn something new about SE chat. Also , I think I forgot to implement induction on my proof. And the forall symbols is displaying correctly in my browser.

@Prithubiswas Ok thanks. I've fixed it on my end.

@Prithubiswas Your "Therefore Q(m+1)" is at the wrong indentation level; its "m" is undefined outside "Given m ...", and of course you need it inside so that you can apply induction on Q. You need to be clearer in how you obtain Y,Z. Your definition is not good enough. For example, if A starts with (3,2,1) and X is (3↦(2,2,2,2),2↦(1,1,1,1,1),...), how do you know whether to assign the second move to Y or Z?

That's why I left blanks at that line for you to fill in, because it is not quite trivial to deal with that.

@Prithubiswas Same goes with your "R(k+1)"; it's at the wrong indentation level.

For conciseness, it suffices to write the following in the outline:

...
P(0).
Given k∈ℕ such that P(k):
  ...
  P(k+1).
Therefore ∀k∈ℕ ( P(k) ).  [induction]

@F.Zer: ^ You can do this too, in your proofs; no need to spell out every step involved in the induction.

12:40 PM

@user21820 I am also having trouble with that part.

The problem of how to assign a move to Y or Z.

@Prithubiswas The obvious approach to solve that issue is to define a relationship between numbers written on the board, relating each number to those written in the same move that erased it.

This is what I did in my (official) solution.

Another approach is just to label your moves one by one according to the game B,C that you want to make it in.

You can't do it all-at-once, obviously. However, you can do it inductively.

That is, if you have labelled all moves before the k-th move, then the k-th move acts on some number which either was original (and so you already assigned it to either B or C) or was written later due to a previous move (and so you can assign based on the previous move).

I think you should use the second approach, as it is easier for you to make it 100% convincingly rigorous to yourself.

@user21820 I guess I have to think about two issues:

(1) Indentation
(2) Y-Z issue (I will use your second approch)

Sure. Take your time.

1:10 PM

@user21820 Is this indentation structure correct?

Define P(k) := A starts with numbers all at most k+1
Define R(k) := ∀A∈Game ( P(k) ⇒ A eventually ends )
R(0)
Given k∈ℕ such that R(k)
  Define Q(m) ≡ ∀A∈Game ( P(k) and A has m copies of (k+1) ⇒ A eventually ends)
  Q(0).
  Given m∈ℕ such that Q(m):
  ...
    Therefore Q(m+1).
  Therefore ∀m∈ℕ ( Q(m) ).
  Therefore R(k+1).
Therefore ∀k∈ℕ ( R(k) ).

@Prithubiswas That's right, with the "..." one level deeper.

@user21820 Sorry about the multiple messeges deleting . I have never programmed in my life and indentation is very new to me.

@Prithubiswas No problem at all. Deleted messages don't show up in the transcript. And it's okay if you've never programmed in your life. Thanks for telling me so that I can avoid using too much programming-related concepts when explaining to you. But if you ever get a chance, it's good to pick up programming. For most people, it will sharpen their thinking precision. For you, it may not do much of that, since you are already quite okay in your logical reasoning, but programming is still useful.

2 hours later…

2:45 PM

A student has to write an exam in which there are two questions. The
likelihood of any question on the exam being seen before by the student is
60%.
The student finds out somehow that one of the questions on the exam
is an unseen question. What is the probability that the other question has
been seen by the student before?
This question came in a quiz. When creating the answer key, our teacher referenced the boy girl problem

However, I feel that in the boy girl problem, its assumed that the parent knows the gender of both of his kids.

But, here, there is a probability that the source of "at least one unseen" had infact only seen the unseen question, but never the whole question paper. This changes the probability of the problem

The instructor claims that I'm unnecessarily introducing ambiguity where there isn't any. Is that so?

should I elaborate further?

@user21820 Here is my thoughts about the Y-Z issue:

Let X be a sequence for A

At the start of the sequence , label each integer in A that are smaller than
k+1 by "b" and label each integer that are equal to k+1 by "c".

If a move in X erases an integer labeled "b" , then the integers that has been
added to A by that move will also be labeled "b". Same rule applies for "c".

Then , Y is defined as a subsequence of X which has all of the moves of X that
during the sequence erases an integer in A labeled "b". Z is defined as a subsequence of X which has all of the moves of X that during the …

3:03 PM

@FitzWatson In standard English, we do not say "write an exam" but rather "take an exam" or "sit for an exam". We can write on the exam paper, or write a solution, but the exam is not what we write. Rather, the exam is given by the examiner. Anyway the question is not at all clear. I do not know what on earth "finds out somehow" means.

@Prithubiswas It's now good! You then need to verify that Y is a valid sequence of moves in B, and same for Z in C. At this point, it's okay to just claim this and go on. As long as you are now 100% convinced that there is no more logical gap, it's good.

@FitzWatson: Note that once the student sees the questions, there are no more probabilities; the probability that a question you have seen is one that you have not seen before is either 0 or 1, never something in-between.

Probability can be between 0 and 1 only for events that still have some (perceived or declared) randomness to it.

Before we flip a fair coin, it makes sense to declare that the probability of getting a head is 1/2. After we flip, there is no more randomness and no more probability. So until you precisely specify what "finds out somehow" means, the question you cited is too vague to have a meaningful answer.

3:47 PM

Define P(k) := A starts with numbers all at most k+1
Define R(k) := ∀A∈Game ( P(k) ⇒ A eventually ends )
R(0)
Given k∈ℕ such that R(k)
  Define Q(m) ≡ ∀A∈Game ( P(k) and A has m copies of (k+1) ⇒ A eventually ends)
  Q(0).
  Given m∈ℕ such that Q(m):
    Given A∈Game such that P(k) and A has (m+1) copies of (k+1):
      Let B,C∈Game such that
      B has all of the positive integers of A which are less than k+1
      C has m+1 copy of k+1
      Given any move sequence X for A:
        At the start of the sequence , label each integer in A that are smaller

@user21820 Inform me if there are other mistakes.

@user21820 I myself agree on the ambiguity of the question. But the instructor claims that probability word problems are ambiguous by nature and that if I want to claim to the contrary, I need to provide an official citation (paper/some textbook)

Is there a way to do that?

4:07 PM

@FitzWatson Your instructor is wrong, but if you are at high-school level there is little you can do about that. The most is you can tell him/her that a Math SE user (me) with expertise in logic says so, and it's up to your instructor to believe or not. Natural language is ambiguous by nature, but that is not a valid excuse to make word problems ambiguous, otherwise you (i.e. the instructor) are not testing mathematical skill but rather mind-reading skill.

@Prithubiswas Shouldn't you say a little bit to justify why Y,Z are move sequences for B,C? I mean, if you're already fully convinced by yourself, it's fine to leave it just like that.

The key principle is that you must have zero doubt that your argument is absolutely correct. Once you reach that point, there is no need to explain further, as I am satisfied with your level of understanding concerning the double-induction.

4:23 PM

Proof by induction:
  ...
  P(0).
  Given k∈ℕ such that P(k):
    ...
    P(k+1).
  P(0) ∧ ∀ k ∈ ℕ ( P(k) ⇒ P(k+1) ) [Omitted step]
  Therefore ∀k∈ℕ ( P(k) ).  [induction]

@user21820 So, I can omit that specific step ? By the way, I changed the indentation to 2 spaces (instead of a Tab). Is it nicer to read for you or do you prefer the old one ?

@user21820 Thank you. I'm starting to read it.

@F.Zer Both are fine. When I type directly into chat (using Shift+Enter to make new-line), I use spaces because Tab doesn't enter characters. However, I do use tabs in programming because it's neater (you can't be missing half a tab) and for no other reason.

As for that omitted step, you've done it so many times that it doesn't matter if you omit it. My concern is always for steps that you've not done before, as you know. =)

@user21820 Yes, I also use Tab when programming and spaces in chat (for the reason you noted). I just thought perhaps 2 spaces make lines a little shorter. Good to know that both are fine.

@user21820 Perfect :-)

@F.Zer Indeed. I don't like the extra-long tabs in browsers, but well I just live with it. I like 4-space tabs. =)

@user21820 Me too. I always prefer 4-space tabs. That's why I just did an automation that allows me to (1) type using tabs in my text-editor and (2) copy a stringified version of the whole tree using 2 spaces for indentation.

@user21820, I am translating "k, m is smaller sum" as: "∀ k,m ∈ ℕ ( k + m = n ∧ ∀ k',m' ∈ ℕ ( k'+m' ≥ n ) )". Is it correct ?

@user21820, are you sure PA5 is right for my current level? I am reading through your hint and I don't understand 99% of it. Or, perhaps this exercise is there so I can learn how to translate an English (informal) proof into a formal proof ?

Not even in 10 years it'd occur to me using well-ordering twice, trying to prove those inequalities and so on...

4:49 PM

@F.Zer Yes just follow that sketch and try to fill in all the gaps that I left behind.

Ok

Using well-ordering like this is actually a very common technique in solving problems in number theory or combinatorics.

@F.Zer No it is wrong, and what you had earlier was correct. Not sure why you didn't continue with that.

Good.

@user21820, you said "Prove that k ≥ 1". Where does it go ? Outside strong induction ?

5:06 PM

@user21820 B has only integers that are labeled "b" in A , and all moves of sequence Y only erases integers that are labeled "b" in A during the sequence. So , Y is a sequence for B.

Is this justified?

@F.Zer No, everything from that point onwards goes inside. To be clear, like this:

5:26 PM

@F.Zer: Ehh... give me 10 min. When actually writing out the proof I discovered that I was missing some case lol. I'll give you an actual proof outline when I'm done.

@user21820 Sure. Take your time.

5:48 PM

Define Q(n) ≡ ∀k,m∈ℕ ( k+m = n ⇒ ( m > 1 ∧ ¬∃d∈ℕ ( d > 1 ∧ d | k ∧ d | m ) ⇒ ∃x,y∈ℕ ( k·x = m·y+1 ) ) )
Given n∈ℕ:
	∀i∈ℕ ( i < n ⇒ Q(i) ):
		Given k,m∈ℕ:
			If k+m = n:
				If m > 1 ∧ ¬∃d∈ℕ ( d > 1 ∧ d | k ∧ d | m ):
					...
					k ≠ m.
					If k < m:
						...
						k ≥ 1.
						k·m ≥ m.
						Let x∈ℕ be minimum such that k·x ≥ m.
						Let r∈ℕ such that k·x = m+r.
						...
						r < k.
						r+m < k+m = n.
						Q(r+m).
						...
						¬∃d∈ℕ ( d > 1 ∧ d | r ∧ d | m ).
						Let p,q∈ℕ such that r·p = m·q+1.

@F.Zer: There. The less steps I do in my head, the less likely there is a bug. Sigh.. I'm too careless.

@user21820 Thank you ! I will study it carefully.

@Prithubiswas The idea is correct, but you can phrase it more precisely. Like this: We start playing A,B,C at the same time, and we shall preserve the invariant that before every step the remaining numbers in B are exactly the remaining numbers in A labelled "b", and likewise for C. At each step, we make one move in A following X. If it is on a number labelled "b" then we make the same move in B, which is possible by the invariant, and after that the invariant is still preserved.

Similarly if the move is on a number labelled "c".

@Prithubiswas: Are you fully convinced by this? If not, then try to work out the details of why the invariant is preserved.

6:15 PM

@user21820 I'm doing undergrad, but I guess there's still nothing I can do about the issue at hand as she wants a verified source (paper/textbook) :(

6:29 PM

@FitzWatson What does "verified source" mean? If I write a gibberish sentence, is it the responsibility of other people to find a reputable source that explicitly claims that what I wrote is gibberish? No. It is the responsibility of the one who writes anything to be precise enough. Your instructor's word problem was not precise enough. If she doesn't believe it, you could post a question on MathEd SE asking for feedback.

(PA5):
  Define Q(n) ≡ ∀k,m∈ℕ ( k+m = n ⇒ ( m > 1 ∧ ¬∃d∈ℕ ( d > 1 ∧ d | k ∧ d | m ) ⇒ ∃x,y∈ℕ ( k·x = m·y+1 ) ) )
  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:
              ¬∃d∈ℕ ( d > 1 ∧ d | m ∧ d | m )
              m > 1 ∧ m | m ∧ m | m
              ∃d∈ℕ ( d > 1 ∧ d | m ∧ d | m )
              ⊥
            k ≠ m.
            If k < m:
              If k < 1:
                k = 0
                0 + m = n

@F.Zer Instead of saying "m > 1 ∧ m | m ∧ m | m", you probably want to have a "| k" somewhere...

But yea that's the first "..." done.

As for the second, you seem to be lost, even though it's again the same reason why you cannot have k = 0.

If k = m:
  m > 1 ∧ m | m ∧ m | m
  m > 1 ∧ m | k ∧ m | m
  ∃d∈ℕ ( d > 1 ∧ d | k ∧ d | m )
  ⊥

@user21820 Yes, it's nicer. Thank you. Is that what you meant ?

@F.Zer Oh! Your way is fine too; I didn't realize you substituted the k for m in the copied ¬∃-statement.

Yes. Exactly.

6:42 PM

Ok I'm off now!

If k < m: @now
	If k < 1:
		k = 0
		m > 1 ∧ m | 0 ∧ m | m
		m > 1 ∧ m | k ∧ m | m
		∃ d ∈ ℕ ( d > 1 ∧ d | k ∧ d | m )
		⊥
	k ≥ 1.

@user21820 Filled the other gap. I leave it here.

See you !

@F.Zer That's right! Bye!

@user21820 Thank you ! Bye !

« first day (1153 days earlier) ← previous day next day → last day (1031 days later) »

Transcript for

Jul '214

♦ $Mathematics$ Basic Mathematics

This room is meant for all basic mathematical discussion, incl...

join this room
about this room

00:00

06:00

12:00

18:00

all times are UTC

$Mathematics$

site design / logo © 2024 Stack Exchange Inc; legal

mobile