# Tag Info

6

$x (1-x) = \frac 14 - (x - \frac 12)^2 \le \frac 14$ holds for all $x \in \mathbb R$. (Alternatively, use the GM-AM inequality, or visualize $y = x(1-x)$ as a parabola with vertex at $(\frac 12, \frac 14)$.) Then from $$a(1-b) \cdot b (1-c) \cdot c (1-a) = a(1-a) \cdot b (1-b) \cdot c (1-c) \le \frac 14 \cdot \frac 14 \cdot \frac 14$$ it follows that at ...

5

$$a^3+a=b^3+b\iff a^3-b^3=b-a$$ $$\iff (a-b)\left(a^2+ab+b^2\right)=b-a$$ If $a=b$, then we're done. For contradiction, assume $a\neq b$. Then $a-b\neq 0$ and we can divide both sides by $a-b$: $$a^2+ab+b^2=-1\iff 4a^2+4ab+4b^2=-4$$ $$\iff (2a+b)^2+3b^2=-4,$$ contradiction, because $(2a+b)^2+3b^2\ge 0$ for all $a,b\in\Bbb R$.

4

What you defined could be called a valid formal proof. A valid mathematical proof (or a proof accepted by the mathematical community) on the other hand might be described as an informal(!) arrangement of arguments that the reader finds convincing in the sense that he/she strongly believes that it is possible to write down a valid formal proof reflecting the ...

3

Your first question has a simple answer — this ternary connective does the trick: $$\triangleright(A,B,C):=(A\Rightarrow(B\land C)).$$ In terms of this connective, we can define $$A\Rightarrow B:=\triangleright(A,A,B)$$ and then $$A\land B:=\triangleright(A\Rightarrow A,A,B).$$ Clearly, $\{\triangleright\}$ and $\{\Rightarrow,\land\}$ are ...

2

Yes, if you prove something by showing that a minimal counterexample would necessarily lead to an even smaller counterexample (and so, contradiction), that is the same thing as the induction principle. Often the same proof can easily be framed as an induction proof or as a minimal counterexample proof. However, it does also happen that one of the two is a ...

2

You can prove $$\psi\land \chi \to \psi\land\chi$$ by going through $(\psi\land\chi)\land(\psi\land\chi)$. Now apply rule 10 to get $$\psi \to (\chi\to\psi\land\chi)$$ Then your assumed derivations of $\psi$ and $\chi$, plus modus ponens twice concludes $\psi\land \chi$.

2

Hint: You actually don't know that $n$ doesn't divide $6,$ for example $n=3$ satisfies your assumption. However you do know that there is an integer $k$ for which $n=6k+3.$ Now substitute that into $n^2+27$ and expand, and see what it looks like.

2

What $n\equiv3 \pmod6$ means is that $\exists k\in \mathbb{Z}$ such that $n=6k+3$. We need to prove that $36\mid(n^2+27)$ so plugging in $6k+3$ for $n$ we get $$(6k+3)^2+27=36k^2+36k+36$$ This is divisible by $36$.

2

It means $\Gamma\vdash (\phi \Rightarrow \psi)$. The alternative reading, $$(\Gamma\vdash \phi) \Rightarrow \psi \tag{*}$$ is a conceptual mess: $\Gamma\vdash \phi$ is a statement of the metatheory, $\psi$ a formula of the theory, and (*) seems to be a formula of the theory — or wants to be one, or something — but it isn't. Re the reverse implication part ...

2

Here is Doron Zeilberger's opinion bearing on this topic with a pointer to some feedback from me (which includes some remarks on Hagen's point about Principia Mathematica).

2

Actually, it is possible using induction. Notice that $1 = 3\times 5 - 2\times 7 = -4\times 5 + 3\times 7$. So, suppose that $n\ge 24$, with $n = 5p + 7q$ for $p,q\in\mathbb{N}$. Then you just have to show that we can pick $(p,q)$ such that either $$q\ge 2$$ so that we can add $3\times 5 - 2\times 7$ and get $n+1 = 5(p+3) + 7(q-2)$, or that $$p\ge 4$$ so ...

1

You’re missing part of the definition of a wqo: it must be a quasi-order, meaning that it must be reflexive and transitive. Equivalently, $\preceq$ is a wqo on $A$ iff it is a well-founded quasi-order with no infinite antichain. This means that a partial order with an infinite antichain is not a wqo even if it’s well-founded. For example, the order $\preceq$ ...

1

To prove the induction step, you first need to show $\phi_n\rightarrow \phi_1$. In your proof you directly used it but that would be incorrect you have to prove it although the proof is simple: $\phi_n\rightarrow \phi_{n+1}$ and $\phi_{n+1}\rightarrow \phi_1$ implies $\phi_n\rightarrow \phi_1$. Now we can use our induction hypothesis to conclude that ...

1

Yes, $PA$ can prove that the "propositional busy beaver" is total. In fact, the bound you cite is provable in $PA$ - the standard proof doesn't use anything beyond $PA$!

1

First of all the distinction is not as important as one would think. When you use an informal formulation it can be considered a short hand description of how you would go about in creating the formal proof - just like a recipe for gingerbread is not a gingerbread, but it allows anyone to produce gingerbread if they're interested in doing so. Note that ...

1

My personal opinion goes more along: A proof is valid if it convinces a significant number of experts in the field to declare it valid. A prime example was Andrew Wiles proof of FLT, a long and complicated proof, with initial flaws as well, in a subject only a few were deep into. A PhD student in algebra told me at that time that he would need two ...

1

Using analysis: define $f(x)=x^3+x$. Since $f'(x)=3x^2+1>0$, the function is strictly increasing, hence, injective, and the result follows.

1

The key point ultimately boils down to: If $\lim_{n\to\infty} a_n$ and $\lim_{n\to\infty} b_n$ exist, then $\lim_{n\to\infty} a_nb_n$ exists and equals $\left(\lim_{n\to\infty} a_n\right)\left(\lim_{n\to\infty} b_n\right)$. Recall that existence of a limit (within $\Bbb R$) means specifically that the limit is a real number, so finite.

1

Note that the hypothesis of the theorem is differentiability; hence the theorem is not applicable to non-differentiable functions. A function $f$ not differentiable at a point $c$ is by definition such that $\lim_{h \to 0}[f(c+h) - f(c)] /h$ does not exist. The function $x \mapsto x^{1/3}$ is, for example, not differentiable at $0$; for we have  h^{1/3}/h ...

1

Revised edition We have to see : Saul Kripke, Semantical Analysis of Intuitionistic Logic I (1965), page 97-on, and : Melvin Fitting, Intuitionistic logic, Model theory and Forcing (1969), page 28-on. According to Kripke's explanation [page 99] : To assert $\lnot A$ intuitionistically in the situation $H$, we need to know at $H$ not only that ...

1

Assume $2^k\geq k^2$. Then $2^{k+1}\geq 2k^2$. If you can show $2k^2\geq (k+1)^2=k^2+2k+1$ for $k\geq 4$, you are done. $2k^2\geq k^2+2k+1$ iff $0\geq -k^2+2k+1$, which is true for $k\geq 4$ (parabola opening downward with largest root $<4$).

1

Yes, your intuition is correct. The precise way to formulate (and prove) your claim is that the principle of induction is equivalent to the well-ordering principle or $\mathbb N$, namely that every non-empty subset of the naturals has a smallest element. The proof is not at all hard.

Only top voted, non community-wiki answers of a minimum length are eligible