« first day (1094 days earlier)      last day (1387 days later) » 

Billy Rubina
Billy Rubina
01:10
@user21820 I'll ask a - perhaps - vague question: If we have a theory, say PA for example. Can we always find a "supertheory" such that PA is a consequence of this supertheory?
 
7 hours later…
user21820
user21820
08:09
@BillyRubina Err what do you mean by "supertheory"?
@F.Zer No. Your second line came from nowhere.
But you did manage to figure out that 0 < k·k implies 1 ≤ k and so it cannot be that (k+2)·(k+2) < k·k+3·k+5. So fix your proof and you'll be done!
 
2 hours later…
Billy Rubina
Billy Rubina
10:05
@user21820 Another theory from which a theory happens to me a consequence. For example, it seems we can write Peano axioms in set theory, right? In this case, set theory would be a super theory.
 
2 hours later…
user21820
user21820
12:35
@BillyRubina What do you mean by "write"? When we say "ZFC interprets PA" we mean that we can computably translate sentences over PA to sentences over ZFC such that theorems of PA become theorems of ZFC. But any theory trivially interprets itself, so what's the point of asking for such?
F. Zer
F. Zer 
(PA-3): ∀k∈ℕ ¬∃m,n∈ℕ ( 0 < k·k < m·m < n·n < k·k+3k+5 ).
	Given k ∈ ℕ:
		If ∃m,n∈ℕ ( 0 < k·k < m·m < n·n < k·k+3k+5 ):
			Let m,n ∈ ℕ such that 0 < k·k < m·m < n·n < k·k+3k+5
			0 < k·k < m·m < n·n < k·k+3k+5
			∀ k, m ∈ ℕ ( k · k < m · m ⇒ k + 1 ≤ m )
			m · m ≤ n · n
			m + 1 ≤ n
			k + 1 ≤ m
			k + 2 ≤ m + 1
			k + 2 ≤ n
			( k + 2 ) · ( k + 2 ) ≤ n · n
			( k + 2 ) · ( k + 2 ) < k·k + 3 · k + 5
			k · k + 4 · k + 4 < k·k + 3 · k + 5
			k · k + 4 · k + 5 ≤ k·k + 3 · k + 5
			If 0 = k:
				0 < k · k
@user21820 Fixed it.
user21820
user21820
@BillyRubina: See the following post for related notions that you might want to know:
8
A: In what sense is $\sf ZFC$ "stronger" than Peano arithmetic?

user21820Hanul Jeon gave a typical definition for "interpretation", but that is a rather restricted definition. In particular, it only applies for FOL theories. So for example we are unable to express statements like: Intuitionistic logic interprets classical logic (via the double-negation translation). ...

@F.Zer Hmm. I noticed that you often do not clean up your work before posting it. I'm only going to say that it is still wrong.
(Not because you haven't solved it, but because you're not ensuring that what you wrote is actually correct.)
F. Zer
F. Zer
@user21820 Oh, you mean "clean up" regarding checking each step is actually a valid inference ?
I always try to double check before posting. Sometimes, I forget the use of "If" in headers due to habits from the past.
I will try to triple check.
@user21820 Checked again. Everything seems good. Is the step 3 < 4 a big leap ? If you like, I could start with 0 < 1 and add 1 to both sides.
user21820
user21820
13:00
@F.Zer I'm not talking about skipped small steps. I am talking about blatant errors. You need to learn to check your work properly.
Anyway I need to go.
F. Zer
F. Zer
@user21820 Thanks for your insight ! I will try to find those blatant errors !
See you !
F. Zer
F. Zer
13:15
@user21820 I found those two blatant errors. On one line, I wrote: "m · m ≤ n · n" instead of "m · m < n · n". And, assuming "If ∃ m,n ∈ ℕ..." and reaching a contradiction, I derived "∃ m,n ∈ ℕ...". That's certainly a big mistake.
Shortened and cleaned-up the proof. What do you think, now ? 
(PA-3): ∀k∈ℕ ¬∃m,n∈ℕ ( 0 < k·k < m·m < n·n < k·k+3k+5 ).
	Given k ∈ ℕ:
		If ∃m,n∈ℕ ( 0 < k·k < m·m < n·n < k·k+3k+5 ):
			Let m,n ∈ ℕ such that 0 < k·k < m·m < n·n < k·k+3k+5
			0 < k·k < m·m < n·n < k·k+3k+5
			∀ k, m ∈ ℕ ( k · k < m · m ⇒ k + 1 ≤ m )
			m · m < n · n
			m + 1 ≤ n
			k + 1 ≤ m
			k + 2 ≤ m + 1
			k + 2 ≤ n
			( k + 2 ) · ( k + 2 ) ≤ n · n
			( k + 2 ) · ( k + 2 ) < k·k + 3 · k + 5
			If k < 1:
				0 · 0 < k · k
				∀ k, m ∈ ℕ ( k · k < m · m ⇒ k + 1 ≤ m )
				0 + 1 ≤ k
				1 ≤ k
 
5 hours later…
user21820
user21820
18:05
@F.Zer Correct! (Assuming I didn't miss any other errors.)
Now you're done with my PA− exercises! =)
Have you finished (Q9) yet?
Apr 12 at 16:00, by user21820
(Q9) ∀x,y∈V ( c(x,y) ⇒ c(y,x) ) ∧ ∀x,y,z∈V ( c(x,y) ∨ c(y,z) ∨ c(z,x) ) ⇒ ∀w∈V ∃x,y,z∈V ( c(x,y) ∧ c(y,z) ∧ c(z,x) ∧ x ≠ y ∧ y ≠ z ∧ z ≠ x ) ∨ ∃x,y,z,w∈V ∀t∈V ( t = x ∨ t = y ∨ t = z ∨ t = w ), where c : V^2→Bool.
Besides that, you can also start on to the PA exercises:
Apr 4 at 19:26, by user21820
(PA1) ∀k∈ℕ ∃m∈ℕ ( k = m·2 ∨ k = m·2+1 ), where "2" denotes "(1+1)".
(PA2) ∀k,m,n∈ℕ ( 4 | k·k ∨ 4 | k·k+3 ), where (infix) | : ℕ^2→Bool is defined via ∀x,y∈ℕ ( x | y ⇔ ∃t∈ℕ ( x·t = y ) ).
(PA3) ∀k∈ℕ ( k > 1 ⇒ ∃p∈ℕ ( p > 1 ∧ p | k ∧ ¬∃q∈ℕ ( 1 < q < p ∧ q | p ) ), where "1 < q < p" is short-hand for "1 < q ∧ q < p".
(PA4) ∀k,m∈ℕ ( k·k = m·m·2 ⇒ k = 0 ).
(PA5) ∀k,m∈ℕ ( m > 1 ∧ ¬∃d∈ℕ ( d > 1 ∧ d | k ∧ d | m ) ⇒ ∃x,y∈ℕ ( k·x = m·y+1 ) ).
PA− has already given you the flavour of what basic arithmetic is like. PA is just PA− plus induction. Finding a proof of a given theorem is harder for PA than for PA−, and (in case you're wondering) not because PA has infinitely many axioms, but because induction is really powerful.
Oops I see my (PA3) has a missing ")" at the end.
F. Zer
F. Zer
18:21
Good !
user21820
user21820
By the way, it wasn't needed, but "m∈ℕ is the minimum such that Q(m)" can be expressed as "Q(m) ∧ ∀k∈ℕ ( Q(k) ⇒ k≥m )". You definitely need to learn to express such things.
F. Zer
F. Zer
@user21820 I wondered about that.
@user21820 I haven't finished it, yet. Will work on that.
user21820
user21820
Ok I'm off. Bye!
F. Zer
F. Zer
Goodbye !
F. Zer
F. Zer
19:22
@user21820, I am going to tackle Q9 again. My idea is rephrasing the conclusion as: "¬ There are at most 4 vertices ⇒ There is a triangle". So, using what I've learned in PA- exercises, I rephrase it as: "There are (at least) 5 vertices ⇒ There is a triangle". I assume "There are (at least) 5 vertices" and symbolise it as: ∃ x,y,z,w,t ∈ V (true). My proof skeleton is: 
(Q9) ∀x,y∈V ( c(x,y) ⇒ c(y,x) ) ∧ ∀x,y,z∈V ( c(x,y) ∨ c(y,z) ∨ c(z,x) ) ⇒ ∀w∈V ∃x,y,z∈V ( c(x,y) ∧ c(y,z) ∧ c(z,x) ∧ x ≠ y ∧ y ≠ z ∧ z ≠ x ) ∨ ∃x,y,z,w∈V ∀t∈V ( t = x ∨ t = y ∨ t = z ∨ t = w ), where c : V^2→Bool.
	If ∃ x,y,z,w,t ∈ V (true):
		Let x, y, z, w, t ∈ V
		...

« first day (1094 days earlier)      last day (1387 days later) »