@user21820: Sorry, is that not correct?

Anyway, I was wrong about intuitionistic logic, but I think it is possible to prove the theorem in question by contraposition rather than contradiction.

@Joe As I said already, you are using the axiom I stated. You cannot rely on just intuition to change "¬ a ≤ b" into "a > b".

And there's no point at all to "use contraposition" when it is merely a trivial ∨-elim as I showed already.

@user21820: So, if I'm understandinh you correctly, the proof that $\neg(a\le b)\iff a>b$ uses contradiction. I was just making the weaker claim that we if take the fact that $\neg(a\le b)\iff a>b$ for granted, then we can write the proof of $(\forall \varepsilon:a\le b+\varepsilon)\implies a\le b$ by contrapositive.

← 6 messages moved from CURED

@Joe That makes no sense. It's just like saying if we take LEM for granted then we can write the proof as a direct proof.

@user21820: the above result holds when $a, b, \epsilon $ are rational. I suppose the key idea is the order relations and archimedean property which makes it click.

You need to be clear about the foundational assumptions you make, before you claim anything at all. The trichotomy axiom is the axiom in the ordered field axioms. You cannot anyhow say "let's take XXX for granted".

And nothing to do with the archimedean property.

So it holds in any ordered field?

Exactly.

It's such a relief to know that it holds in ordered fields. I was under the impression that it is specific to rationals and reals

See here for an axiomatization of ℚ as an ordered field containing ℤ. Only the axioms [ℤ ⊆ ℚ] and [ℚ = ℤ/ℤ*] distinguishes ℚ from other ordered fields.

Let me check

You need division to get ∀c∈ℚ ( 0<c ⇒ ∃d∈ℚ ( 0<d<c ) ). A possible witness is c/2, but to prove 0<c/2<c you again need trichotomy and the order properties with respect to multiplication.

This is a big part missing from Xander's proof, but can be patched as I just sketched.

Cool. Things are simpler when we get to the very basics

You can also compare with the axiomatization for ℝ given just after that linked message.

It satisfies the axioms of ordered fields plus [ℚ ⊆ ℝ] and [complete].

Necessarily [complete] is not first-order over the language of ordered fields, so for ℝ you necessarily need a bit of set theory.

@user21820: I don't really understand. Suppose we start with the ordered field axioms, and prove that $\neg(a\le b)\iff a>b$. Then, is it not correct to say that we can prove $(\forall \varepsilon:a\le b+\varepsilon)\implies a\le b$ by contrapositive?

@Joe It is arguably correct but in my opinion meaningless. Tell me, what you think "proof by contrapositive" means, formally?

@user21820: Formally, I don't what a proof by contrapositive is. Informally, it is when you prove an implication $P \rightarrow Q$ by instead proving that $\neg Q \rightarrow \neg P$, and then using the fact that $\neg Q \rightarrow \neg P \iff P \rightarrow Q$.

@user21820: I think all these details should be a part of some well framed answer on mathse.

@Joe Let me formalize what you just said. Proof by contrapositive is the deduction rule ( ¬Q ⇒ ¬P ⊢ P ⇒ Q ).

Okay. I think I'm following so far.

Problem is that it is not intuitionistically valid.

I need to leave this chat, but will return later. Bye @user21820

@ParamanandSingh Bye!

@user21820: In intuitionistic logic, does $P\rightarrow Q$ mean $\neg P \lor Q$?

Of course not.

Try P ≡ Q.

can I ask a linear transformation question here?

In intuitionistic logic, "⇒" is primitive, and "¬P" can be defined as "P ⇒ ⊥".

@Koro You can, but wait a while. Also, show your attempt.

If $P\rightarrow Q$ did mean $\neg P \lor Q$, then $P\rightarrow P$ (which is true even in intuitionistic logic) would mean $P\lor\neg P$ (LEM).

Got it. Clearly wrong.

@Joe Yes, absolutely right.

If you want a deductive system for intuitionistic logic, you can take this one and remove ¬¬elim and add explosion, which is ( ⊥ ⊢ A ).

The authors who define "¬P" as "P ⇒ ⊥" can drop the other two ¬ rules altogether because they are derivable from that definition of "¬".

@user21820 ok thanks. Please let me know when the time is right.

Now given such a system, we can easily prove that the contrapositive rule is not intuitionistically valid, by showing that from the contrapositive rule we can derive ¬¬elim.

If ¬¬¬P:
	If P:
		If ¬P:
			⊥.
		¬¬P.
		⊥.
	¬P.
¬¬¬P ⇒ ¬P.
P ⇒ ¬¬P.  [contrapositive]

So that settles the matter, in case you wonder how we can know for sure that the contrapositive rule is not intuitionistic.

@Koro Ok.

To be precise, we have just shown that intuitionistic PL plus contrapositive rule equals classical PL.

@user21820: Hmm. I don't think I follow. Is $P\rightarrow\neg\neg P$ not intuitionistically valid?

@Joe It's equivalent to ¬¬elim. Check the linked system for the definition of that rule.

Intuitionistic logic IL is defined by the deductive system I described for it, so if you can derive full classical logic CL from that plus the contrapositive rule, then clearly the contrapositive rule is not intuitionistic unless IL = CL.

I'm getting lazy now, so let CP denote the contrapositive rule. I just showed above that IL+CP = CL.

If you want to know why IL ≠ CL, then you need to set up an interpretation of IL that makes IL sound but CL unsound. Two well-known interpretations are Kripke frames and the BHK interpretation. I first learned about Kripke frames from Hanno's answer at this thread:

Hanno's answer not only gives a frame which violates "¬¬P ⇒ P", but also shows that the rule I was asking about is neither intuitionistic nor enough to obtain CL if we add it to IL.

@Koro: You can post your question. I'll answer when I'm back.

@user21820 Thanks. I had erroneously misinterpreted that MCQ question so it's answered now. :)

@user21820: I sorted out the confusion in my mind. Ordered field axioms allow existence of arbitrarily small elements, archimedean property allows us to counter large numbers by taking multiples of any number. They are different ideas. I don't know why i had mixed these..

@Koro Great!

@ParamanandSingh Yes, the archimedean property says that the subring generated by 1 extends beyond any element.

But "generated by" is not a first-order statement over the language of ordered fields. And indeed the archimedean property is not first-order, like completeness.

But now that it is sorted out I can have some peace.

If you know the compactness theorem, for any ordered field F it's easy to construct a non-archimedean field that satisfies Th(F) where Th(F) is the set of sentences over the language L of ordered fields that F satisfies. Just let F' = F ⋃ { c>1 , c>1+1 , c>1+1+1 , ... } where c is a new constant-symbol and apply compactness to get a model M of F'. Let M' be M cut down to L (i.e. drop c and its interpretation). Then Th(M') = Th(F).

But M' has an element i corresponding to the interpretation of c in M, and i>1 and i>1+1 and i>1+1+1 and ... Therefore the subring generated by 1 in M' does not extend beyond i. Thus M' is non-archimedean, and hence also fails to satisfy completeness.

I don't have much idea about non-archimedean fields. Just two examples the hyperreals and field of rational functions in some variable.

If there is any reference to compactness theorem you can add a link

Oops I made a silly typing error. Just let T = Th(F) ⋃ { c>1 , c>1+1 , c>1+1+1 , ... } where c is a new constant-symbol and apply compactness to get a model M of T. Let M' be M cut down to L (i.e. drop c and its interpretation). Then Th(M') = Th(F).

@ParamanandSingh Compactness theorem says that if a set of sentences is finitely satisfiable, then it is satisfiable (i.e. has a model).

In this case, T is finitely satisfiable because any finite subset of T has only finitely many of the sentences involving c, so we could interpret c to be a big enough sum of 1s.

Then sprinkle the compactness magic dust and we get a model of the entire T.

The proof of the theorem itself is easiest via the completeness theorem for FOL (every consistent set of sentences is satisfiable), and should be in every introductory logic text, such as Rautenberg or Enderton. But neither is trivial to prove, so you could skip the proof if you're not that interested in logic.

I like the phrase "sprinkle the compactness magic dust".

@ParamanandSingh I've never liked compactness when applied to uncountable theories, because it is too ridiculous.

Here it's just a countable theory, so I don't mind. But the completeness/compactness theorems for an uncountable FOL theory T (i.e. with uncountably many symbols in its language) requires a well-ordering of T, which is a bit too ridiculous unless you invoke some impredicative set theory like Zermelo's plus Choice.

In everyday mathematics you will never see compactness applied to an uncountable theory. But it's done regularly in higher logic such as model theory, and in that setting it really feels like ridiculous magic.

@ParamanandSingh: And here's a plausible explanation for why density could be confused with archimedean property. Density implies ∀x∈ℝ ( 0<x ⇒ ∃y∈ℝ ( 0<y<x ) ). Archimedean property implies ∀x∈ℝ ( 0<x ⇒ ∃y∈ℚ ( 0<y<x ) ).

That's a nice observation @user21820

The Archimedean property for reals somehow is used to place rationals within reals in terms of ordering.

Yes.

Otherwise it is very difficult to figure out that rationals are sandwiched between reals very finely.

When I studied the axiomatic version of reals then i found the proof of Archimedean property via completeness. That struck me as rather weird. That such an obvious property needs completeness for proof was rather mysterious to me at first

@ParamanandSingh That's because you have a concrete notion of ℝ, for example π = ([3,4],[3.1,3.2],[3.14,3.15],...). In that concrete notion of ℝ, which is directly built from ℕ, archimedean property is obvious.

And then I realized how this system is used to mix rationals and reals.

Yes i read the construction of reals before the axiomatic approach

So when we attempt to abstract out the properties of ℝ axiomatically, then the one thing missing from the first-order part is completeness. And since the first-order part cannot prove archimedean property AP (due to existence of non-archimedean fields with the same first-order properties), proving AP from the real axioms necessarily must invoke completeness.

In fact I was so perplexed at first that I asked this on mathoverflow

Let me check the link

Ah I see I have said what Ramiro's comment and JDH's answer said. =)

One thing that has not been said on that thread is that the completenessness axiom is completely useless in the absence of any set theory. Thus one must always keep in mind that the full axiomatization of ℝ is not absolute as it must be added on top of some set theory, and different choice of set theories would yield different theorems about ℝ!!

I think textbook should discuss these ideas if not in main text then in some appendix. Usually real analysis books skip all this kind of details and jump on to epsilon delta

@ParamanandSingh Spivak does that in the appendix. =D

Spivak is a good book for sure!!

I came to know of Spivak from mathse.

Nice.

It wasn't used at my university when I was an undergraduate, but my close friend told me to study it before I entered, and I did. I have no idea how he chose that out of all books (because he actually wasn't that good at mathematics), but from what I've seen so far it's one of the best.

Spivak is so famous on mathse that almost all its questions have been asked here

That's actually interesting. I have no idea why it's not more popular as an official university textbook, since it's not really more expensive than other textbooks which appear worse.

(And that's excluding the fact that it's usually possible to get an earlier edition for free from somewhere.)

I think universities prefer Rudin

But Rudin writes very tersely

Maybe Spivak's book is named Calculus and hence many won't prefer it as a textbook of real analysis

Spivak should sell the same book under the title "Real Analysis"

@ParamanandSingh Hahaha yes! I also thought it was strange to be called "Calculus".

@Prithubiswas Yup I agree with you.

It is merely a coincidence that symmetries are more closely related to groups than to other structures.

So I wouldn't say that group theory is only about symmetries.

For example, I don't think it's helpful to try to use "symmetry" to understand the theorem that x^#(G) = 1[G] for every element x in a finite group G.

Rather, it is an example of a group action on itself.

\\ Define P(n) ≡ ∀m ∈ ℕ (n.n = 2.m.m ⇒ n=0)

Given a ∈ ℕ
	If ∀i∈ℕ ( i<a ⇒ P(i) )
		Given b ∈ ℕ
			If a.a = 2.b.b
				If a > 0
					a.a = 2.b.b
					a.a is even
					a is even
					Let c ∈ ℕ such that a = 2c
					4.c.c = 2.b.b
					b.b = 2.c.c
					.
					.
					.
					b < a
					P(b)
					∀m ∈ ℕ (b.b = 2.m.m ⇒ b=0)
					b.b = 2.c.c ⇒ b=0
					b = 0
					a.a = 2.b.b = 2.0.0 = 0
					a.a = 0
					a = 0

				If a = 0
					a = 0

			a.a = 2.b.b ⇒ a=0
		∀m ∈ ℕ (a.a = 2.m.m ⇒ a=0)
		P(a)
	∀i∈ℕ ( i<a ⇒ P(i) ) ⇒ P(a)

@user21820 Is this proof outline correct?

hello, how to simplify this $$ \frac{4Cos^2 \theta - 3}{3Sin^2\theta + 1}$$

I simplified but that went too complicated, but anyways I simplified it, I want to know if we can simplify this in few steps

i.e: 5 steps

@Prithubiswas It works. It shouldn't be hard for you to finish it.

@ParamanandSingh Can you help in ?

@user21820 suppose we say the following $\forall x(x\in \mathbb{R}\impliesx^2>0$

now this should be true

but....

if we put $x={R}$ then obviously we want it to be true

since it doesn't belong to R

and a false stament implies anything

but..

@Ishwaran If you show your attempt, I will comment on it.

the part after the implies doesn't even make sense...

I don't understand how to resolve this problem

@PaxDaga No it's not true. What you want is ∀x ( x∈ℝ ⇒ x^2 ≥ 0 ).

YES Thats what I meant my question still holds

I know. I'm coming to that.

ℝ is constructed as some object. ≥ can be defined as a 2-input predicate-symbol. ^ can also be defined as a 2-input function-symbol, just like we can define new predicate-symbols. The formal mechanism is more complicated, and you are not ready for it now, but I will of course teach you when it's time for you to learn it. For now assume that ^ is a 2-input function-symbol that you're already given.

A function/predicate-symbol accepts any objects as inputs. But when we define ≥ on ℝ, we only specify its (boolean) output for inputs from ℝ, and we do not specify its outputs for inputs not from ℝ (because we don't care about them).

So the statement is true no matter what junk you apply it to. {ℝ}∈ℝ ⇒ {ℝ}^2 ≥ 0. It's true. No problem at all.

If you don't see why it's true, it's because you don't know what implication from PL (propositional logic) means.

if we want can always specify it to be false(or true) if. not from R ?

That's the point. If "{ℝ}∈ℝ" is false, then the truth-value of "{ℝ}^2 ≥ 0" is completely irrelevant.

This is how standard FOL works. When you have finished learning basic FOL, I can teach you about more complicated variants that block this kind of 'not meaningful' statements, but believe me that they are complicated.

but if we want to define the two input predicate how do we do it in such a way ?

beacause I would start by $\for all x,y \in \mathbb{R}$

the two input predicate > I mean

le

[lemma]
Given a,b ∈ ℕ
	If a.b > 0
		If a = 0
			a.b = 0
			0 > 0
			⊥
		a > 0
		If b = 0
			a.b = 0
			0 > 0
			⊥
		b > 0
		a > 0 ∧ b > 0
	a.b > 0 ⇒ a > 0 ∧ b > 0
∀x,y ∈ ℕ (x.y > 0 ⇒ x > 0 ∧ y > 0)

(PA4)
\\ Define P(n) ≡ ∀m ∈ ℕ (n.n = 2.m.m ⇒ n=0)

Given a ∈ ℕ
	If ∀i∈ℕ ( i<a ⇒ P(i) )
		Given b ∈ ℕ
			If a.a = 2.b.b
				If a > 0
					a.a = 2.b.b
					a.a is even
					a is even
					Let c ∈ ℕ such that a = 2c
					4.c.c = 2.b.b
					b.b = 2.c.c

					a > 0
					a.a > 0
					2.b.b > 0
					b.b > 0 [lemma]

@PaxDaga: Not now. I cannot teach you the proper mechanism for definitions until you know basic FOL, because it depends on FOL. Since you said you wanted to learn FOL from me, let me tell you where to start. I'll teach you the same way I taught F.Zer and Prithu in this room, starting from PL. For PL, read and make sure you understand the first few sections up to "Boolean operations" in this post.

Then do the exercises here.

I need to go. Bye!

@user21820 yes

how to show $$ ( \int |x|^2 d \mu(x,y) )^{1/2} \leq ( \int |x-y|^2 d \mu(x,y) )^{1/2}+ ( \int |y|^2 d \mu(x,y) )^{1/2} $$ for some probability measure $\mu$

@onemorecupof For some or for every? For some is trivially true, witnessed by the standard measure, isn't it?

evry

@user21820 I've updated PA-3. Is the proof of the Lemma correct ?

@F.Zer Yep. It's easy with "≥", right? Also, you should have updated line 18 to chain properly so that you can drop lines 15 to 17.

@PaxDaga: Sorry I gave you an outdated link. Here is the updated list of exercises.

@onemorecupof Ok. I'll take a look later. I need to do something now.

@user21820 Yes, it's easy with "≥" ! I've updated it. Is that what you meant ?

The file didn't update. I will push again.

The file is updated, now.

Am I making a big leap ?

PA-3

@user21820 Can you check my last attempt?

@F.Zer It's better the other way around. As I told you before, you want to make things as clear to the reader as possible. The direction of your inequalities of course does not affect the correctness, but readers read from top to bottom and left to right, so it makes no sense to start from k+2 when you actually started from b and can present it that way.

Sometimes, you can't present it the way you found the proof. In that case, if it is a crucial thing you could use a comment to indicate it such as:

[We shall now prove X.]
...
...
X.

But that's only useful when it's a really big step.

@Prithubiswas Sorry I missed it. Give me a while.

@Prithubiswas Yes you've gotten it. Are you satisfied with your proof? Note that the equivalent proof by well-ordering would start by using proof by contradiction straightaway: If the desired claim is false then there exists a minimum k∈ℕ such that there is some m∈ℕ satisfying k·k = 2·m·m and k ≠ 0. Then you just use the reasoning you did (k must be even, so you get a smaller pair).

@user21820 Are there any improvements I can do?

Hmm. I'd say there's no need for any improvements. There's nothing wrong with following the intuitive approach to proving sqrt(2) irrational, and your proof does that fine. The strong induction or well-ordering is doing the 'reduced fraction' part of the informal proof.

@user21820 I used strong induction in my proof. If I get some time I might write a proof using well-ordering.

Don't need. It's just a copy-paste of your inside part into the well-ordering outline.

Ok. Now I have PA5 and Q10 left to solve.

@Prithubiswas @F.Zer: Curiously though, there's a funny alternative proof avoiding the division by 2 if you use subtraction. If a·a = 2·b·b, then (2·b−a)·(2·b−a) = 4·b·b−4·b·a+a·a = 2·b·b−4·b·a+2·a·a = 2·(a−b)·(a−b), and you can show that 2·b−a < a and proceed. Subtraction can be simulated in PA using the [diff] axiom, but this is not really any better than the division by 2. It's just a curiosity.

@Prithubiswas: If you're going to try (PA5), you might need some hints. First hint is to define Q(n) ≡ ∀k,m∈ℕ ( k+m = n ⇒ ( m > 1 ∧ ¬∃d∈ℕ ( d > 1 ∧ d | k ∧ d | m ) ⇒ ∃x,y∈ℕ ( k·x = m·y+1 ) ) ) and apply strong induction to Q.

Second hint is that inside that strong induction, given k,m∈ℕ satisfying m > 1 ∧ ¬∃d∈ℕ ( d > 1 ∧ d | k ∧ d | m ), the easiest way is to use well-ordering a few times. If k < m, let x∈ℕ be minimum such that k·x ≥ m, and use that and the strong induction to prove ∃x,y∈ℕ ( k·x = m·y+1 ). If k ≥ m, let r∈ℕ be minimum such that ∃t∈ℕ ( k = m·t+r ), and use that and the strong induction to prove ∃x,y∈ℕ ( k·x = m·y+1 ).

If you still can't get it, fill in the blanks in this proof outline.

@user21820 Is PA5 a well known theorem? I never encountered it in high-school?

@Prithubiswas It is a well-known theorem called Bezout's lemma. There are many proofs, but the outline I gave is probably one of the shortest you can get in PA.

And ideally, you shouldn't go to look at proofs of it if you want to get it by yourself.

It's more or less the most important theorem of PA that can be handled at this level.

Is it correct to assume "people do not ask about your tailor if your suit is not good" from "you know that your suit is excellent when people ask about your tailor who tailored the suit." ?

@Wolgwang Erm, I would say that it is likely correct, but there's no end to English ambiguity in such phrasings.

Wait, what am I saying. Forget what I just deleted.

@user21820 Interesting. I thought it was completely made up .

@Prithubiswas Haha it's easier to pick known theorems from my head than to make up an interesting but hard exercise.

@user21820 Due to some reasons, I thought it is wrong to assume that, but I don't know anything about logic.

@Wolgwang Well, you can unpack the second sentence. It is ambiguous, but strongly suggests at least the following:

> For every time t and every person p, if p asks at time t about your tailor for the suit you are wearing, then that suit is excellent.

So it cannot be that someone asks about your tailor at a time when you are wearing a non-excellent suit.

I see. Thanks.

@user21820: Could you please explain why you emphasise so strongly that beginning students of mathematics learn logic? I'm not trying to question your teaching—I'm just genuinely curious why you think it is so important.