Basic Mathematics - 2021-07-06

« first day (1155 days earlier) ← previous day next day → last day (1033 days later) »

10:40 AM

@avistein No need for that. If 15x ≡ y (mod 7), then x ≡ y−14x (mod 7).

2 hours later…

12:57 PM

If k < m:
  If k < 1:
  k ≥ 1.
  k·m ≥ m.
  Let x∈ℕ be minimum such that k·x ≥ m.
  Let r∈ℕ such that k·x = m+r.
  If r ≥ k:
    If r = 0:
      0 ≥ k
      ⊥
    ...
  r < k.

@user21820, Hi, there ! I feel there is something with x being a minimum such that...However, I don't seem to find it. I've used all the other information available.

@user21820, you gave me great advice, once. You said that I should believe a sentence was true inside a given context in order to prove it. I don't see why r ≥ k is impossible in this context.

I will quote you correctly. You didn't phrase it like that.

@F.Zer No need; it's roughly correct.

@F.Zer If you want to contradict minimality of x, of course you have to find some x' < x such that k·x' ≥ m.

Did you try small cases?

@user21820 Yes ! Per your advice :-)

But in every case you tried, you find that r < k, isn't it?

Why?

@user21820 I will check my notes.

@user21820 For example, k = 1 and m=2 gives 1 · x ≥ 2, and x is the minimum so it would be x = 2. This gives r = 0. Is this what you are suggesting ?

@F.Zer Yes, but that is a rather poor case to try. Didn't you try any others?

1:09 PM

@user21820 Yes, k=2 and m=2 gives 2 · x ≥ 2. So, x = 1 and r = 0.

@F.Zer That's not a valid case. You're not obeying the outer conditions.

@user21820 Sorry ! True in its context. I quoted and forgot it :( k < m is the restriction.

@F.Zer That's NOT the only restriction that you broke.

@user21820 k and m are coprimes !

Yes. So you didn't try small cases...

1:16 PM

@user21820 And because the invariant is preserved , we can say that Y is a sequence for B. right?

@user21820 Seems to be the case :( I forgot about the outer restriction.

Became too focused on the inner context.

@Prithubiswas Yes. Technically, however, the invariant is preserved because the moves along the way are valid, and the moves are valid because of the invariant. You cannot prove one first before the other.

And note that in that explanation there is no need to even construct Y or Z.

That's why I said "make the same move in B, which is possible by the invariant" and also said "after that the invariant is still preserved".

k = 3 and m = 2 give 3 · x ≥ 2. Then, x = 1 and r = 1.
k = 4 and m = 3 give 4 · x ≥ 3. Then, x = 1 and r = 1.
k = 5 and m = 3 give 5 · x ≥ 3. Then, x = 1 and r = 2.

@F.Zer Wrong.

@user21820 Maybe we can say that Y is a sequence for B because :
(1) The first move of Y is a valid move on B.
(2) If for a nth move of Y , every move before the nth move is a valid move for B , then the nth move is a valid move for B.

1:22 PM

Ok.

12 mins ago, by F. Zer

@user21820 Sorry ! True in its context. I quoted and forgot it :( k < m is the restriction.

Not following your own advice...

@user21820 That's funny :-)

I will fix it.

@Prithubiswas Yes that is the proper way to do it. In fact, in my explanation we are implicitly constructing Y,Z, because claiming that we can continue playing A,B,C as described is effectively an inductive construction. Without induction there is no reason why we can continue indefinitely. It's just that it is convenient to think in terms of this procedure rather than explicitly constructing the sequences.

But to really do the proper way, to prove (2) you would have to essentially prove the invariant by induction.

@F.Zer And it's bad that you didn't find a counter-example for k > m, because there are small counter-examples.

@user21820 Keep in mind that, before you told me about "try small cases", I probably did that once in my entire life. So, trying cases that don't go against restrictions is really new for me :-)

2 · x ≥ 3. Then, x = 2 and r = 1.
3 · x ≥ 4. Then, x = 2 and r = 2.
4 · x ≥ 5. Then, x = 2 and r = 3.

I see, in every case, r < k.

Every one of those cases, I should say.

@F.Zer: I made a mistake; there are no counter-examples up to that point for k > m.

1:35 PM

Ok.

@user21820, where is the connection about those small cases and the reason why r < k ?

You're supposed to figure that out.

Good.

39 mins ago, by user21820

@F.Zer If you want to contradict minimality of x, of course you have to find some x' < x such that k·x' ≥ m.

Turns out I mixed up the last parts of both cases (but you haven't reached them yet). Give me a minute.

@user21820 Sure.

@user21820 Well, I can't find some x' < x such that k · x' ≥ m since x is the minimal element. I think there is an underlying important concept, here. Could you explain a bit (without revealing the solution) why in proofs sometimes I choose an element that satisfy a condition and then try to contradict it !

Perhaps, the reason is a new assumption is made and that's how I can find the contradiction ? I am not sure.

@user21820 Oh, something happened. Unfortunately, I have to leave. See you !

@F.Zer Ok bye!

1:51 PM

@user21820 Maybe the way we inductively construct Y and Z already ensures that Y and Z will be valid sequences for B and C.correct?

@F.Zer You want to prove r < k. If r ≥ k, then you have to find some x' < x such that k · x' ≥ m, so that you can contradict minimality of x. It is typical to use minimality this way.

@Prithubiswas That's what happens in my explanation. But in your original explanation you constructed Y,Z from X directly, so there is no direct tie to whether they are valid move sequences for B,C. It's up to you which approach you prefer. In my explanation, the invariant is basically two parts: (1) we have made valid moves in B,C so far; (2) the invariant I actually stated. I didn't state (1), because it's implicit in the explanation.

In your original idea, you constructed Y,Z from X directly, so you also would have to prove a similar invariant: (1) the first k moves in Y are a valid move sequence for B; (2) the same invariant as in the other approach.

But as I said, if you are fully convinced of the correctness of the argument, whichever approach doesn't really matter much for now.

@user21820 I will probably use my original approach.

Sure. Explicitly constructing Y,Z is a bit more 'concrete', so it's understandable if you prefer it.

@F.Zer: Here's the fixed outline:

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+r < k+m = n.
						Q(r+k).
						...
						¬∃d∈ℕ ( d > 1 ∧ d | r ∧ d | k ).
						If k = 1:

2:07 PM

@user21820 What is exactly computability theory and why it is a branch of mathematical Logic?

@Prithubiswas If you have heard about the halting problem, it is the first basic result in computability theory. Logic is closely connected to computability theory. Godel's incompleteness theorem can be easily proven for any computable formal system that can do very basic reasoning about programs. (Note that every useful formal system is computable.)

2:22 PM

@user21820 Is it based on the meta-system?

2:38 PM

@Prithubiswas Is what based?

0

A: Distribution of last digits in fibonacci series

Fibonacci modulo $2$ is $0,1,1,\cdots$ (repeats with cycle length $3$). Fibonacci modulo $5$ is $0,1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,\cdots$ (repeats with cycle length $20$). Note that the remainders mod $5$ occur with the same frequency in each such repeating interval, so each occurs $\frac1...

3:15 PM

@user21820 Is computability theory based on the meta-system?

@Prithubiswas Every branch of mathematics is carried out relative to some foundational system. It isn't really correct to call it a meta-system unless we are talking about logic, just because logic is about formal systems and so our foundational system appears to be 'one level up', even though it isn't correct to think that way.

Some parts of logic can be carried out in a weak meta-system, and that is another reason for using the term "meta-system".

Mathematics outside of logic are not talking about logic, so there's little point in calling the foundational system "meta".

3:33 PM

@user21820 Thank you ! I will paste the fixed version to my notebook.

@user21820 Inside r ≥ k, I've found r ≥ 1.

Now, I'm searching for some x' < x. I can't see in which way r ≥ k is related to x.

My thoughts around r being that x', fail. I can't find a way of proving r < x.

Also, I can't find a way of proving k · r ≥ m.

3:55 PM

Hello! I want to ask, if we convert a terminating decimal into a fraction, is there a way to get the numerator?

@F.Zer k·x = m+r. If r ≥ k, then what do you get?

@soupless Yes if you don't require it to be simplified. I'm sure there's a detailed explanation somewhere on Math SE.

Google "decimal to fraction site:math.stackexchange.com".

@user21820 I could derive (doesn't seem useful), r + m ≥ k + m.

@user21820 To clarify, it needs to be simplified. For example, consider 0.5. We know that this is, in lowest terms, 1/2. Is there a way to get the "1"?

@F.Zer And then?

@user21820 k · x ≥ k + m

4:05 PM

@F.Zer And then...

Jul 3 at 7:37, by user21820

@F.Zer Indeed the simplification lemma is how you should simplify equalities or inequalities. Same for addition, no need to prove it. Note that the square ordering is the same, ultimately arising from ∀k,m∈ℕ ( k < m ⇒ k^2 < m^2 ). All of them are the same, because it's just splitting cases by ordering of variables to simplify a given [in]equality.

@soupless Well just find the unsimplified fraction first and then simplify using the gcd algorithm.

@user21820 Not sure I can connect your quote with the inequality "k · x ≥ k + m".

@F.Zer If you were not working within PA, what would you do to simplify that?

@user21820 Oh, well I'd do: "k · x - k ≥ m", "k · (x - 1) ≥ m"

@F.Zer Exactly. And all basic arithmetic that you can do outside PA you can do inside as long as it doesn't involve negative integers.

Certainly, (x - 1) < x.

4:13 PM

So you just have to prove x ≥ ...

@user21820 Good teaching strategy :-)

@user21820 x ≥ x - 1

No. Subtraction doesn't exist in PA, so you need to do something to get x−1 without subtraction...

@user21820 So "logic" and "computability theory" are two different ways to study mathematics?

@user21820 Good. I'll continue thinking.

@user21820 Sorry, I am doing this on Desmos, and the GCD function there only works for integer values. Is this possible only by using floor/ceiling and arithmetic operations?

4:15 PM

@F.Zer: Observe that your simplification lemmas are cancellation lemmas, which you need to use in the absence of subtraction. Of course, you cannot cancel what is not there. That's why you need to prove that your x is big enough so that you can express it as a sum where you can cancel from both sides.

@soupless The unsimplified fraction already has integral numerator and denominator. Why can't you use gcd on that?!

@Prithubiswas No. They are branches of mathematics. Just like combinatorics and field theory.

Of course, mathematics itself cannot be done rigorously without using basic logic, but basic logic is not the field of mathematical logic.

You can use a language to write in various subjects, but that language is not linguistics. It is not even the same type of thing.

You use basic FOL to do mathematics in all branches, but FOL is not the branch called "mathematical logic".

Alright, I got to go soon. Bye everyone.

4:32 PM

See you !

4 hours later…

8:23 PM

@user21820 Thank you. I am thinking about "you need to do something to get x−1 without subtraction". I have no clue, so far.

How can I prove my x is big enough so that I can express it as a sum where I can cancel from both sides. Also, no clue about this, either.

« first day (1155 days earlier) ← previous day next day → last day (1033 days later) »

Transcript for

Jul '216

♦ $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