Basic Mathematics - 2021-06-16

« first day (1135 days earlier) ← previous day next day → last day (1064 days later) »

12:28 PM

@user21820 Thank you. I'll leave my attempt, below.

Prove Strong Induction from Induction:
	Define Q(k) ≡ ∀i∈ℕ ( i<k ⇒ P(i) )
	Given P on ℕ:
		If  ∀k∈ℕ ( Q(k) ⇒ P(k) ): [Strong Induction Hypothesis]
			[Prove Q(0) ≡ ∀i∈ℕ ( i<0 ⇒ P(i) )]
			Given i ∈ ℕ:
				If i < 0:
					⊥
					P(i)
			∀i∈ℕ ( i<0 ⇒ P(i) )
			Q(0)
			[Prove ∀k ∈ ℕ ( Q(k) ⇒ Q(k+1) )]
			Given k ∈ ℕ:
				If Q(k):
					[Prove ∀i ∈ ℕ ( i < k+1 ⇒ P(i) )]
					Given i ∈ ℕ:
						If i < k+1:
							i ≤ k [Lemma]
							If i = k:
								Q(k) ⇒ P(k)
								P(k)
								P(i)
							If i < k:

@user21820 The statement says, in terms of Q and P: "∀k∈ℕ ( Q(k) ⇒ P(k) )"

user21820

12:56 PM

@F.Zer That's right.

@F.Zer But your attempt is incorrect, because "P" is not (yet) defined at line 2.

But that's minor, because once you fix that, everything else is correct!

@Prithubiswas You made the same mistakes I pointed out earlier for your first half, as well as using "P" instead of the property you want.

When I said you didn't have to fix those mistakes, I only meant that you didn't have to repost that half with the mistakes fixed. But they are really mistakes, so you should fix them in all subsequent proofs.

Also:

2 days ago, by user21820

@Prithubiswas: Please let me know if any step in this Fitch-style proof that corresponds to your solution is unclear.

@F.Zer: So now that you have strong induction, it should not be difficult to prove both Well-ordering and (PA3). You can try both at the same time.

The key intuition is that for k > 1 the claim that every k+1 has an irreducible factor is unrelated to the same claim for k, so normal induction applied to the claim is useless. However, applying strong induction to the claim makes it sufficient to prove that every k > 1 has an irreducible factor based on the same claim for every m > 1 that satisfies m < k.

F. Zer

1:53 PM

:58354789 Oh, I see. Should this change suffice ?
	Given P on ℕ:
		Let Q(k) ≡ ∀i∈ℕ ( i<k ⇒ P(i) )

@user21820 Thank you !

@user21820 Good. I'll work on it.

user21820

2:09 PM

@F.Zer Absolutely.

F. Zer

Good !

F. Zer

2:52 PM

Prove Well-ordering from Strong Induction:
	Given P on ℕ:
		If ∃k ∈ ℕ:
			[Prove ¬∃ m ∈ ℕ ( P(m) ∧ ∀ k ∈ ℕ ( P(k) ⇒ k ≥ m) ) ⇒ ∀ k ∈ ℕ ( ¬P(k) )]
			If ∃ m ∈ ℕ ( P(m) ∧ ∀ k ∈ ℕ ( P(k) ⇒ k ≥ m) ):
				Given m ∈ ℕ:
					Let k ∈ ℕ:
					[Prove ∀ i ∈ ℕ ( i < m ⇒ P(i) ) ⇒ P(m) ]
					If ∀ i ∈ ℕ ( i < m ⇒ P(i) ):
						k < m ⇒ P(k)
						If k < m:
							P(k)
							...
			∃m∈ℕ ( P(m) ∧ ∀k∈ℕ ( P(k) ⇒ k≥m )

@user21820 This is my first attempt.

user21820

@F.Zer What? You have ill-formed stuff that don't even seem to follow what you want.

F. Zer

3:08 PM

Checking...

Prithu biswas

4:07 PM

@user21820

Statement : Q(n):= “f(-m) = 3^(-m) – 2^(-m) for all natural numbers m<=(n+1)”

Base Case: We have to prove that Q(0) holds.
1. if n=0 , then (n+1) = (0+1) = 1
2. The set of natural numbers less than or equal to 1 is= {0,1}
3. f(-0) = 0 , 3^(-0) – 2^(-0) = 1 – 1 = 0 , so f(-0) = 3^(-0) – 2^(-0)
4. f(x+1) + 6.f(x-1) = 5.f(x) for all integers x.
5. f(1) + 6.f(-1) = 5.f(0)
6. f(-1) = [5.f(0) – f(1)]/6
7. f(0) = 0 and f(1) = 1
8. f(-1) = [5.0 – 1]/6 = -1/6
9. 3^(-1) – 2^(-1) = 1/3 – 1/2 = -1/6

2 hours later…

user21820

5:40 PM

@Prithubiswas Good! Have you gone through the Fitch-style version of your solution? It is shorter, cleaner, and shows the logical structure explicitly. Until you comment on it, I would have no idea whether you understood or not.

@Prithubiswas Note that in your conclusion, (5) is meaningless because "p≤p+1" is trivially always true so "if m=p" is useless. Maybe you meant "if m=p, then m≤p+1", but as before the clearest is simply to discard the useless "if". Just state "p≤p+1" so that from this and (4) you get (6).

F. Zer

Prove Well-ordering from Strong Induction: [1]
	Given P on ℕ: [2]
		If ∃k ∈ ℕ: [3]
			[Prove ¬∃ m ∈ ℕ ( P(m) ∧ ∀ k ∈ ℕ ( P(k) ⇒ k ≥ m) ) ⇒ ∀ k ∈ ℕ ( ¬P(k) )] [4]
			Let m ∈ ℕ [5]
			If ¬∃ m ∈ ℕ ( P(m) ∧ ∀ k ∈ ℕ ( P(k) ⇒ k ≥ m) ): [6]
				Given k ∈ ℕ: [7]
					If k < m: [8]
						If ∀ i ∈ ℕ ( i < m ⇒ P(i) ): [9]
							k < m ⇒ P(k) [10]
							... [11]
			∃m∈ℕ ( P(m) ∧ ∀k∈ℕ ( P(k) ⇒ k≥m )  [12]

@user21820 Is this any better ?

user21820

@F.Zer Your ill-formed stuff is in the first 3 lines...

You need to be more careful than me... I am allowed to be careless since I already know how to do these. =P

F. Zer

@user21820 Ok :-)

Prithu biswas

@user21820 I dont know that much about "fitch style" but I still I read your fitch-style proof. It seems to skip alot of unnecessary steps of my own proof , which is nice .
@user21820 Yes , it is meaningless and unnecessary

F. Zer

@user21820 I've just numerated the lines. Could you tell me the range ?

user21820

5:54 PM

But at least you caught the missing negation at [6].

F. Zer

@user21820 Yes, I noticed it after you pointed out the error.

user21820

@Prithubiswas That's really the point of Fitch-style; it's not something obscure. I was using Fitch-style for 2-3 years before finding out that it had already been introduced by a logician called Fitch (hence Fitch-style).

F. Zer

@user21820 Is line [1] the problem ? I've used it as a header for the proof.

user21820

@Prithubiswas: The key idea behind Fitch-style is merely that the logical structure (i.e. quantification and conditional assumption) are explicitly shown via indentation, just like in programming (though Fitch came long before programming).

@F.Zer [3]...

F. Zer

@user21820 Oh, sorry ! I missed a very important piece of data :-)

Doing it again...

user21820

5:58 PM

@Prithubiswas: You should also take a look at F.Zer's derivation of strong induction from normal induction, which is essentially an abstraction of what you did to solve the exercise I gave you.

Also feel free to join F.Zer in solving the next two tasks I gave him: Derive Well-ordering from strong induction (since he has shown that strong induction can be derived from normal induction), and prove (PA3), which is from my list of exercises for PA (Peano Arithmetic).

Prithu biswas

@user21820 wait .... am I done with your first test ?

user21820

@Prithubiswas I suppose you can say so, since you did eventually solve it with a bit of prodding.

Prithu biswas

@user21820 Oh ok . So what is your second test ?

user21820

@Prithubiswas Lol you really want to see what it's like. Alright:

> Some positive integers are written on the board. At each step one of the integers n is erased and replaced with any number of positive integers that are all less than n. Of course, if the erased integer is 1 then no new positive integers can be written on the board. Prove that no matter how this procedure is carried out the board must eventually become empty.

Ok I got to go. See you all!

F. Zer

See you !

F. Zer

6:40 PM

Prove Well-ordering from Strong Induction:
	Given P on ℕ:
		If ∃k ∈ ℕ ( P(k) ):
			[Prove ¬∃ m ∈ ℕ ( P(m) ∧ ∀ k ∈ ℕ ( P(k) ⇒ k ≥ m) ) ⇒ ∀ k ∈ ℕ ( ¬P(k) )]
			Let m ∈ ℕ such that P(m)
			If ¬∃ m ∈ ℕ ( P(m) ∧ ∀ k ∈ ℕ ( P(k) ⇒ k ≥ m) ):
				Given k ∈ ℕ:
					[Prove ∀k∈ℕ ( ∀i∈ℕ ( i<k ⇒ P(i) ) ⇒ P(k) )]
					Given k ∈ ℕ:
						If ∀i∈ℕ ( i<k ⇒ P(i) ):
							m < k ⇒ P(m)
							...
			∃m∈ℕ ( P(m) ∧ ∀k∈ℕ ( P(k) ⇒ k≥m )

@user21820 I fixed my attempt above (and tried other things).

I'm trying to use Strong Induction inside the proof.

« first day (1135 days earlier) ← previous day next day → last day (1064 days later) »

all rooms