Basic Mathematics - 2021-07-04

user21820

07:57

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.

Prithu biswas

10:36

@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 ?

user21820

@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.

Prithu biswas

@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" ?

user21820

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.

Prithu biswas

With the "fixed font" button?

user21820

@Prithubiswas Yes.

Prithu biswas

11:56

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.

user21820

@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).

Prithu biswas

12:18

@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.

user21820

@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.

Prithu biswas

12:40

@user21820 I am also having trouble with that part.

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

user21820

@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.

Prithu biswas

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

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

user21820

Sure. Take your time.

Prithu biswas

13:10

@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) ).

user21820

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

Prithu biswas

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

user21820

@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.

Fitz Watson

14:45

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?

Prithu biswas

@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 …

user21820

15:03

@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.

Prithu biswas

15:47

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.

Fitz Watson

@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?

user21820

16:07

@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.

F. Zer

16:23

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.

user21820

@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. =)

F. Zer

@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 :-)

user21820

@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. =)

F. Zer

@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...

user21820

16:49

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

F. Zer

Ok

user21820

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.

F. Zer

Good.

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

Prithu biswas

17:06

@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?

user21820

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

user21820

17:26

@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.

F. Zer

@user21820 Sure. Take your time.

user21820

17:48

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.

F. Zer

@user21820 Thank you ! I will study it carefully.

user21820

@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.

Fitz Watson

18:15

@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) :(

user21820

18:29

@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.

F. Zer

(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

user21820

@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.

F. Zer

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 ?

user21820

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

F. Zer

Yes. Exactly.

user21820

18:42

Ok I'm off now!

F. Zer

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 !

user21820

@F.Zer That's right! Bye!

F. Zer

@user21820 Thank you ! Bye !

Transcript for

♦ $Mathematics$ Basic Mathematics

Transcript for

♦ Basic Mathematics

♦ $Mathematics$ Basic Mathematics