# Tag Info

1

You already found $\Delta OBC \sim \Delta OBD$. Since $\angle CBD = 120^\circ$, you know $\angle CBO = \angle OBD = 60^\circ$. Furthermore, $\angle BCO = \angle BDO = 90^\circ$ since $BC$ and $BD$ are tangent lines. Thus $\Delta OBC$ is a $30^\circ$-$60^\circ$-$90^\circ$ triangle, so $OB = 2 \cdot BC$.

0

since U not equal to W, the basis for W must have at least one vector linearly independent from U, so $\dim(\operatorname{span}(U + W))$ is at least 4. but they are subspaces of $\mathbb R^4$, so $\dim (U \cup W)=4$. Use the fact that $\dim U +\dim W=\dim(U + W)+ \dim(U\cap W)$, i.e. $6=4+\dim(U\cap W)$

3

Various good answers here, but the following seems to have been left out and is surely the simplest. Consider the propositional calculus. (If you are not familiar with this term: essentially it is logic using basic terms like "and", "or", "not", but which does not have quantifiers "for all" or "there exists".) One can determine whether or not a statement ...

0

$$2p^n \ge 2p^2 = p^2 + p^2$$ Here $p^2 = 2p + (p-2)p \ge 2p + 1$ for (p > 4) since $(p-2)p > 1$ for p > 4 So $$2^{p + 1} = 2\,2^p > 2 p^2 = p^2 + p^2 \ge p^2 + 2p + 1 = (p + 1)^2$$

0

Just don't try to do “if and only if”: $$2^{p+1}=2\cdot 2^p\ge2p^2$$ because of the induction hypothesis. Now, try proving that, for $p\ge5$, $2p^2\ge(p+1)^2$ Hint: this is equivalent to $p^2-2p-1\ge0$, which is true when $p\ge\dots$

1

You can only find proofs for any given valid formula, if your calculus is complete. Under the precondition that your calculus is complete, it is possible to create an algorithm that will terminate for every valid formula. However, if your language is undecidable (e.g. first-order logic), you cannot find an algorithm that will terminate for every (valid and ...

9

I'd like to expand Brian Tung's answer above, and add a further example. In the following I'll be talking about first order (FO) sentences and structures. In a nutshell, a FO structure is a set $A$ with some operations and relations attached to it (e.g., a group, an ordered field, a graph), and a FO sentence is a statement you can write about $A$ with the ...

7

There are two different notions of proof that other answers did not distinguish. Proofs from 'without' One is when we are in a meta-system and talking about proofs inside a formal system. For example, the completeness theorem for first-order logic says that for any set $S$ of formulae and formula $φ$, we have $S \vdash φ$ if and only if $S \vDash φ$, which ...

25

There are various ways to interpret the question. One interesting class of examples consists of "speed up" theorems. These generally involve two formal systems, $T_1$ and $T_2$, and family of statements which are provable in both $T_1$ and $T_2$, but for which the shortest formal proofs in $T_1$ are much longer than the shortest formal proofs in $T_2$. One ...

11

Henkin's completeness proof is an example of what you seek: It demonstrates that for a certain statement there is a proof, but does not establish what that proof is.

11

One can prove that either there is a proof that $1361$ is prime or there is a proof that $1361$ is composite without knowing which alternative is right. But what if I can prove that there is a proof that $X$, where $X$ is some proposition? Is that a proof of $X$? In one sense it is: it is a convincing argument showing that $X$ must be true. However, ...

0

For $\Box\bot\to\Box\neg\Box\neg p$, use the tautology $\bot\to\neg\Box\neg p$. For $\Box\neg\Box\neg p\to\Box\bot$, use the tautology $\bot\to\neg p$ to infer $\Box\bot\to\Box\neg p$, thus $\neg\Box\neg p\to\neg\Box\bot$, from which you can derive $\Box\neg\Box\neg p\to\Box\neg\Box\bot$. Then, as the hint tells you, $\Box\neg\Box\bot\to\Box\bot$ is an ...

2

If you take a purely mechanical notion of "proof" as suggested in some of the comments, then yes, there are lots of "different" proofs for any given theorem. If a "proof" is just a sequence of statements, starting with assumptions/axioms, where each subsequent statement logically follows from those before it, and the last statement is the conclusion of the ...

4

There are many proofs, in fact, I have seen a book with a title like "100 Proofs of the Pythagorean Theorem." One of the proofs listed there was developed by a President of the United States (Grover Cleveland). Here is a site with many proofs: http://www.cut-the-knot.org/pythagoras/ The first proof I did (and I am obviously not the first one to find this ...

1

I'm not sure if anyone has tried to make a direct connection (probably they have, though not quite in these terms), but there is a very straightforward indirect connection. Local soundness and local completeness are the triangle identities of the adjunctions that define logical connectives; parallel, no junk and no noise are also represented by the triangle ...

2

If $x+y=0$ then we have \eqalign{x &=x+0\cr &=x+yy'\cr &=(x+y)(x+y')\cr &=0(x+y')\cr &=0\ .\cr}

1

If the measure of the angle can be divided by two, then there is a bisector. Since any number can be divided by two, then any angle has a bisector. Edit: I found another question similar to this one that you asked, but it was about midpoints and line segments. You could just apply the same thing written here.

1

Here's an informal sketch. Assume we've proved $A$ and $\neg A$, and fix any proposition $P$. Then we have $$\neg P\implies \neg A,$$ since we have the stronger proposition $\neg A$ (this uses AX1). Similarly, we have $\neg P\implies A$. So by AX3, we have $P$.

1

Here's some structure: Your base case is when the list is null. Assume that the property holds for a list of length $n$, and look at lists of length $n + 1$. Now we can split the list into head and tail. The tail is a list of length $n$. Apply the above definitions, but keep in mind that $a = b$. Let me know in the comments if you'd like a hint.

Top 50 recent answers are included