Tag Info

New answers tagged

0

Your question depends on the use calculus. I am now assuming a natural deduction. There are two forms of proof by contradiction as found on wikipedia. The first form is: Contra 1: G, A |- f --------- G |- ~A Contra 2: G, ~A |- f ---------- G |- A If we now assume that ~A is just a short hand for A -> f. Then the first form can be already seen as a ...


0

I think your description of Curry-Howard correspondance is not precise enough: The proof is correct if the program is well-typed and has as type the formula to be proved. Any well-typed program of the right type is a correct proof of this formula, you don't need to check 'correctness'.


1

See : Joseph Shoenfield, Mathematical logic (1967), page 27, for the : Tautology Theorem : If $B$ is a tautological consequence of $A_1,\ldots,A_n$, and $\vdash A_1, \ldots, \vdash A_n$, then $\vdash B$. Thus, due to the fact that $A∨(B∨C)$ is a tautological consequence of $(A∨B)∨C$, by the above theorem we conclude with the "derived rule" : if ...


0

The famous Gödel's Incompleteness Theorem is relative to another "property" of a formula of the relevant formal system : to be true in the "standard" (or intended) model.


0

Are we allowed to start at any point in the circle? Anyway we can view it as using clock arithmetic or "modulus" or $\mathbb{Z}_{2n}$. Another approach is by matrix representation of groups. Then we can write the problem as $$ \left(P^l\sum_{k=1}^n P^{kt} \right)[1,0,\cdots,0]^T = v$$ where v is a binary vector being 1 in the bad guys positions and P being ...


0

You are working on a particular variant of the Josephus Problem. Executing every $m^{\text{th}}$ person in a circle of $n$ defines the Josephus Permutation $$J_{n,m}=\begin{pmatrix} 1&2&3&\cdots &n\\ a_1&a_2&a_3&\cdots&a_n\end{pmatrix}$$ where $a_i$ is the $i^{\text{th}}$ person to be killed. Now, there is a simple condition ...


1

The short intuitive answer is that if $A=B$ then $cA=cB$ for any $c$. This must be the case for multiplication to be well-defined. Though $A$ and $B$ may be written differently, they are in fact the same number. If multiplication is well defined then when I multiply $c$ by something, say $A$, it shouldn't matter how I've written $A$, or what day of the ...


4

The question of proof equivalence is quite an old one! In fact, David Hilbert considered adding it (or a similar one) to his celebrated list of open problems, but finally decided to leave it out, so it is sometimes referred to as Hilbert's 24th problem. There is a rather well-established field investigating proof equivalence, though definitely no clear ...


1

Your proof is correct, but there is no reason to use contradiction here: it just makes the argument unnecessarily complicated. You’ve basically taken the natural direct proof and turned it into a proof by contradiction. We know that $g\mid x$, so there is an integer $m$ such that $x=mg$. Similarly, there is an integer $n$ such that $y=ng$. But then ...


0

This is an immediate consequence of Cauchy's Integral Formula. Let $p: \mathbb{C} \to \mathbb{C}$ be a polynomial, thus $$ p(z)=a_0+a_1z+\cdots +a_nz^n $$ For $0<t<R$, let $\gamma:[0,2\pi] \to \mathbb{C}$, given by $\gamma(\theta)=a+te^{i\theta}$($\{\gamma\} \subset B(a,R)$ ). Clearly $p$ is analytic on $B(a,t)$, then by Cauchy's Integral Formula $$ ...


0

It is a proof by contradiction. 1) Let $p(z)$ be a nonconstant polynomial. 2) Assume $p(z)$ has no root. 3) Conclude $p$ is constant. Point 3) contradicts point 1). The conclusion isn't that 3) holds, it is that 2) fails.


0

Hint $\ $ By a very simple transformation we can reduce the induction to a very trivial induction, namely if $\,g(n)\,$ is constant $\,g(n\!+\!1)=g(n)\,$ then $\,g(n) = g(0)\,$ The $\rm\ RHS$ and $\rm LHS$ have equal first difference $\,f(n\!+\!1)-f(n) = 2\cdot 3^n,\,$ therefore defining $\,g(n) := \rm RHS - LHS$ $\Rightarrow$ ...


1

Base Step: $2 \cdot 3^{1-1} = 2 = 3^1 - 1$ The inductive hypothesis is: $\sum_{n=1}^{k} 2 \cdot 3^{n-1} = 3^k - 1$ We must show that under the assumption of the inductive hypothesis that $$3^k - 1 + 2 \cdot 3^k = 3^{k + 1} - 1$$ We verify this as $$3^k - 1 + 2 \cdot 3^k = 3^k(1 + 2) - 1$$ $$= 3^{k+1} - 1$$


1

General question: For which odd primes $p$ does $n^2+m^2 \equiv 0 \bmod p$ have solutions, where $m$ is coprime to $p$? $n^2+m^2 \equiv 0 \implies n^2 \equiv -m^2$ In order for $-m^2$ to be a quadratic residue $\bmod p$, Euler's criterion requires that $(-m^2)^{\frac{p-1}{2}} \equiv 1$. However we already know that Euler's criterion holds for $m^2$, so ...


1

Answer using Quadratic Reciprocity. We use Euler's criterion, which states that $n \in \mathcal QR(p)$ iff $n^{\frac {p-1}{2}} \equiv 1 \bmod p$. We use the Legendre symbol $(\frac np) = \begin{cases} 1 \text{, n} \in \mathcal QR(p)\\ -1 \text{, n} \in \mathcal NR(p)\end{cases}$ for the sake of contradiction, assume $3 \mid n^2+4$ $3 \mid n^2+4 ...


0

Well, You have two cases 1st case $n$ is odd then $n=2k+1$ for some integer $k$ Then $n^2 + 4 = (2k+1)^2 + 4 = 4k^2 + 4k + 5 = 4k(k+1) +5$ Here we have either $k$ or $k+1$ is even and the other is odd or vice versa and we know that even $\times$ odd = even and so $4k(k+1) + 5 = 4(2m)+5$ for some integer $m$ and so have $8m +5$ Now it's obvious that $3 ...


8

For any integer $n$ we have, $$n\equiv\{0,1,2\}\pmod3\implies n^2\equiv \{0,1,4\}\equiv \{0,1,1\}\equiv\{0,1\}\pmod3\\ \implies n^2+4\equiv\{4,5\}\equiv\{1,2\}\pmod3\implies n^2+4\not\equiv0\pmod3$$ $$\therefore\quad 3\not\mid n^2+4~\forall~n\in\Bbb{Z}$$


5

Look at the expression mod $3$, $$n^2 + 4 \equiv n^2 + 1.$$ Could $n^2\equiv 2$? What are the squares mod $3$? $0^2 \equiv 0, 1^2 \equiv 1, 2^2 \equiv 4 \equiv 1$. Thus $2$ isn't a square mod $3$!


17

Write $n=3r+q$ with $q\in\{0,1,2\}$. Then $$ n^2+4=9r^2+6rq+q^2+4=(9r^2+6rq+3)+q^2+1. $$ The expression in the parentheses is divisible by $3$ whereas inspecting the three possibilities for $q$ reveals that $q^2+1$ is never divisible by $3$.


3

Consider cases. For example, what happens if $n=3k$, $n=3k+1$, and $n=3k+2$?


-1

Hint: What does $-4$ equal to in $\mathbb{Z_3}$?


1

This proof irrelevance is one of the problems of classic foundations. In Type Theory, however, we represent mathematical statements as types, which enables us to treat proofs as mathematical objects. This is because of a well-known isomorphism between types and propositions a.k.a. Curry-Howard Correspondence, which roughly says that to find a proof of a ...


1

For any $n \in \mathbb{N}$, we have $ n \equiv 0,1,2 \text{ mod } 3 $. Hence $ n^2 \equiv 0,1 \text{ mod } 3 $. Thus $ n^2+4 \equiv 1,2 \neq 0 \text{ mod } 3 $. So for any integer $n \in \mathbb{N}$ , $ n^2+4$ is not divisible by $3 $.


1

Maybe there is a confusion here between definitions and axioms. In the former, we do not assume somethings exists when defining it, we just ascribe it a name. In the latter, we postulate that some sentence holds. Take the following example in ZFC: $\text{Axiom of Existence}: \text{there exists a set with no elements}$ Here we postulate existence of a ...


3

What definitions are in the most primitive sense (mathematical and linguistic): Definition, n. $\qquad$ The settings of bounds or limits; limitation, restriction. The above is the primary meaning of definition from the authoritative Oxford English Dictionary. Of course, you are more interested in the role(s) of definitions in mathematics. The following ...


7

Definitions are just shorthand. For example "$f$ is a function from $A$ to $B$" is shorthand, in set theory, for $$f\subseteq A\times B \land \left(\forall x(x\in A\implies\exists_1 y((x,y)\in f))\right)$$ And here, even $\exists_1$ is a shorthand. Definitions are a way to avoid writing the same thing over and over again. Another example: Saying "$p,q$ ...



Top 50 recent answers are included