Tag Info

New answers tagged

2

This skill comes with lots of practice. Generally speaking, direct proofs are used when the result is "positive-sounding". In your example, the result is, "the product of two odd integers is odd". This result is positive-sounding (as opposed to a result like, "there is no smallest positive real number"). For the result, "if $x^2$ is even, then $x$ is ...


2

There are many ways to write down a proof. The question is, apart from correctness, which one is more elegant, more concise, more constructive, and last not least easier und thus clearer. In your case, for me the easiast way is to do first an obvious computation, i.e. $$ (2k+1)(2l+1)=4kl+2k+2l+1. $$ Your first step here is wrong, because you assume that both ...


0

The answer to your question depends on what exactly you mean by "question", "decidability" and "only a single valid answer". A question in the sense of computability theory is usually identified with the set of its yes-instances. E.g. the question "which natural numbers have the property P?" is identified with the set of natural numbers having the property ...


0

As pointed out in the comments, it is definitely a theorem. Here is the shortest proof I could think of. If the parallelogram is a rectangle, then the equality holds. Therefore we can assume the parallelogram has an acute angle. Label the parallelogram as in the figure, where the lines of length $h$ are perpendicular to the top and bottom. Also, notice that ...


4

There are many undecidable statements about the integers, but most people (including me) believe that the integers truly exist. So any statement about the integers is either true or false, even if it is undecidable.


1

Using the tips by Christian Remling, I have been able to formulate the following explicit proof, which is quite long due to the removal of the use of the deduction theorem ($\land$ has higher precedence than $\to$): 1 $\vdash \forall x(A \to B) \to (A \to B)$ (aax) 2 $\vdash (\forall x(A \to B) \to (A \to B)) \to (\forall x(A \to B) \land A \to B)) $ ...


1

As you already observed, $$ \vdash \forall x(A\rightarrow B)\rightarrow (A\rightarrow \forall x B) $$ if $x$ is the only free variable in $A, B$, by the deduction theorem. In the general case, you can enlarge your language by new constants and replace the additional free variables (if any) by those constants to prove $$ \vdash \forall x(A(c_j)\rightarrow ...


0

I can't understand what you wrote, but the proof can be easy and pretty short: Let $\;x\in\Bbb R\;$ be an indeterminate, and look at the equation: $$0\le(xu+v)\cdot(xu+v)=x^2||u|^2+2x\,u\cdot v+||v||^2$$ The above is a non-negative quadratic in $\;x\;$ and thus its discriminant is non-positive: $$\Delta=4u\cdot v-4||u||^2||v||^2\le 0$$ and this proves ...


1

$0 <= ||u||^2 ||v||^2 - |u . v|^2$ if and only if $0 <= (u_1^2 + u_2^2)(v_1^2+v_2^2) - (u_1v_1+u_2v_2)^2$ if and only if $0 <= u_1^2v_2^2 + u_2^2v_1^2-2u_1v_1u_2v_2=(u_1v_2 - u_2v_1)^2$ which is true. So Cauchy-Schwartz inequality holds.


1

So we're starting with this: $$\frac{2^n - 1}{2^n} + \frac{1}{2^{n+1}}.$$ Note that the denominators are not the same. They need to be the same in order to combine them to get to the next step. To do this we multiply the numerator and denominator of the first term by $2$. This makes the denominators the same, because $2^n \cdot 2 = 2^{n+1}$: $$\frac{2 ...


1

$$\frac{2^{n}-1}{2^{n}} + \frac{1}{2^{n+1}}$$ $$= \frac{2(2^{n}-1)}{2^{n+1}} + \frac{1}{2^{n+1}}$$ $$= \frac{2^{n+1}-2}{2^{n+1}} + \frac{1}{2^{n+1}}$$ $$= \frac{2^{n+1}-1}{2^{n+1}}$$


0

The essential point here is that recursive definitions can be formalized in PA as explicit definitions. Specifically, if we have a recursion of the form $f(0)=a$ and $f(n+1)=g(f(n))$, and if we already know how to formalize $g$ in PA, then we can formalize $f$ by defining $f(n)=z$ to mean "there is an $s$ that codes (via your favorite sequence coding) a ...


0

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} ...


0

Let’s assume the contrary. For simplicity, I have changed the region of x to an open interval. That is, there exists an $x ∈ (π/2, π)$, such that $\sin x − \cos x \lt 1$. [Please skip the following line and continue from its next.] Then, try some values for x in that range to see the contradiction. An example is x = 3π/4. Then, $\sin x \lt 1 + \cos x$ ...


0

Hint: start to prove that if $S(n)$ is the sum of the digits of $n$, then $ n - S(n) $ is a multiple of 9.


1

You know that $n=9i + k$ and $5n = 9j+ k$. So $4n = 9(j-i)$ is divisible by $9$. But since $\gcd(4,9)=1$, we must have that $n$ is divisible by $9$.


1

Hint: If you are to use the Euclidean Algorithm, perhaps you should start by writing $a = qb + r$, and continuing until you compute the $\gcd$ of $a$ and $b$. Once you have that list of equations in front of you, how would you turn that into a computation of the $\gcd$ of $na$ and $nb$?


0

A useful theorem involving the intersection of vector spaces is the following: $$\dim(U+W) = \dim U + \dim W - \dim(U \cap W)$$ We prove this as follows: suppose $(v_1,\dots,v_n)$ is a basis of $U\cap W$. This list is linearly independent in both $U$ and $W$, so we can extend it to a basis $(v_1,\dots,v_n,u_1,\dots,u_m)$ of $U$ and a separate basis ...


5

Essentially due to Gödel's Incompleteness Theorems, proofs of the consistency of $\mathsf{PA}$ must involve methods that transcend $\mathsf{PA}$ itself. If one has any doubts about the consistency of $\mathsf{PA}$, those doubts are likely only to be amplified concerning the methods used to prove the consistency of $\mathsf{PA}$. (For example, from ...


0

For standard PC, Intuitionist logic, and a number of other logics: IF the theorem being proven contains no double negations, THEN there is a proof for it that has no double negation. This was proven by Michael Beeson, Robert Veroff, and Larry Wos in the paper "Double-Negation Elimination in Some Propositional Logics" ...



Top 50 recent answers are included