58

It's perfectly normal. In fact, I think that's how a mathematitian's mind grows. First, you are naive and "intuistic", and you do a lot of "well, of course this is so!" like statements that are not well founded. After you are repeatedly hit over the head with examples where your intuition fails, you take a huge step back. You realize that even simple ...


39

The primary reason to write down a proof is in order to communicate with other mathematicians. If mathematicians acquainted with the relevant literature cannot understand your argument (i.e: do not find it convincing) then I think the author has failed to write down a proof.


18

Split the house however you like. Let $E_i$ be the number of enemies person $i$ has in their group, and let $E = \sum E_i.$ For any person having more than $1$ enemy in their group, i.e. at least $2$, move them to the other group, where they will have at most $1$ enemy. This decreases $E.$ Since $E$ is always non-negative, this process must end eventually, ...


13

Well, there was a book with 367 proofs of the Pythagorean Theorem published. I'm sure there's more.


13

One can say that a proof of a statement $X$ is a finite sequence of statements where a) each statement in the sequence is either an axiom or follows from some previous staements via one of a handful of rules of inference and b) the last statement in the sequence is $X$. - So if the statement $X$ is already an axiom, the one-term sequence with only term $X$ ...


11

Proofs of Euler's polyhedral formula in The Geometry Junkyard: Proof 1: Interdigitating Trees Proof 2: Induction on Faces Proof 3: Induction on Vertices Proof 4: Induction on Edges Proof 5: Divide and Conquer Proof 6: Electrical Charge Proof 7: Dual Electrical Charge Proof 8: Sum of Angles Proof 9: Spherical Angles Proof 10: Pick's Theorem Proof ...


11

Everything about a mathematical proof is psychological. Including the valid and convincing part. Who gets to decide if it is valid and if it is convincing? The primary audience for a proof is the writer of the proof. Presumably the writer thinks it is valid and convincing. If the proof is convincing enough, then others may agree. Understand that what is ...


10

The question is ambiguous in two ways: we are not told whether being an enemy is a symmetric or asymmetric relation, nor whether the parliament has a finite or infinite number of members. I will show that the assertion is false for asymmetric relations, even in the finite case; in fact, I give an (asymmetric) example of $15$ people, each having only $2$ ...


10

Mathematical proofs often, if not always, have some gap, and consequently, we have the 'convincing' part of the definition. Note that the author indicates gaps in his/her proof as he/she talks about the rule that from $a=b$ and $b=c$ we can deduce $a=c$. I would take such basics of equational reasoning as assumed for some arithmetic, but I don't regard ...


9

I would like not to use de morgan law, as you would need to include that as a premise. I was thinking of this proof. $\lnot (p \lor \lnot p) \quad \quad \quad (H)$ $p \quad \quad \quad \quad \quad (H)$ $p \lor \lnot p \quad \quad \; \;(\lor \text{I} 2)$ $ \bot \quad \quad \quad \quad \;\;(\lnot \text{E}1,3)$ $\lnot p \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\...


9

We can assume that the number does not have any digit equal to $0$. For if it has, then the statement is obvious. Note that the prime factors of the remaining digits are $2$, $3$, $5$ and $7$. Now, for a given number whose prime factors are among ${2,3,5,7}$ define the function $$f(2^{a_2}3^{a_3}5^{a_5}7^{a_7})=(g(a_2),g(a_3),g(a_5),g(a_7))$$ Where $g(k)$ ...


9

$(a+b)(c+d)=a(c+d)+b(c+d)$ by distributive law. $a(c+d)+b(c+d)=(c+d)a+(c+d)b$ by commutativity of multiplication. $(c+d)a+(c+d)b=(ca+da)+(cb+db)$ by distributive law twice. $(ca+da)+(cb+db)=(ac+bc)+(ad+bd)$ by associativity and commutativity of addition.


8

I assume you can use modus ponens as a deductive rule. Here is a Hilbert-style proof. As you can see, there is no reason to use the deduction theorem. $A \to B$ [assumption] $B \to C$ [assumption] $(B \to C) \to (A \to (B \to C))$ [by A1] $A \to (B \to C)$ [modus ponens, 2 and 3] $(A \to (B \to C)) \to ((A \to B) \to (A \to C))$ [by A2] $(A \to B) \to (A \...


8

I will give a counter-example for the case where the enemy relationship is not assumed to be symmetric (but is assumed to be irreflexive). Imagine four kingdoms called North, South, East, and West. Each kingdom has many citizens and a king and a pretender to the throne (actually, the pretender to the throne might be the only citizen, awkward). The enemies of ...


7

Layout: To prove that $\neg P\lor Q$ is a formal consequence of $P\to Q$, start by assuming $P\to Q$ and further suppose that $\neg (\neg P\lor Q)$ holds. At this point you should prove $P\lor \neg P$ and perform $\lor$-$\text{Elim}$ on this disjunction. It's easy to find contradictions on both cases yielding $\neg \neg (\neg P\lor Q)$. For the other ...


7

Do what Gauss did, reverse the sequence and add it with the original. Now each term is 2n + 4, and there are n such terms. The sum is n(2n+4). Since this results from two sequences, divide by 2 and you get the answer.


7

.Since the equation: $$ (a-d)x^2 + (b-e)x+(c-f)=0 $$ is true for all values of $x$, we can substitute values of $x$ and the resulting equation will still be true: Put $x=0$, then we get $c-f=0$, so $c=f$. Now our equation simplifies to : $$ (a-d)x^2 + (b-e)x=0 \implies x((a-d)x+(b-e)) = 0 $$ Take $x=1$ here: $(a-d) + (b-e) = 0$ Take $x=-1$ here:$(d-a) + (...


7

Not a valid proof. From $$-K < \sqrt{n} < K$$ one cannot conclude that $$K^2 < n < K^2$$ Example: $-3<1<3$ is true but $9<1<9$ is not true because $9<1$ is not true.


7

It must be Pythagoras's theorem. There's hundreds of proofs (famously, a whole book of them). Cut-the-Knot has a few of them...


7

There are actually a surprisingly large number of ways to prove the Fundamental Theorem of Algebra, ranging from real analysis to complex analysis to Galois theory to Riemannian Geometry. At least one example of each of these categories is listed here. Not sure what category you want to count that theorem as, but if it's a sufficently sparse category it ...


7

There are also a lot of ways to prove that there are infinitely many primes. See for example: Euclid's theorem on the infinitude of primes: A hisorical survey of its proofs on arXiv, by Romeo Meštrović. Of course, a lot of them look like each other, but there are several different approaches as well. "In this article, we provide a comprehensive ...


7

Figuring out exactly how much "strength" a system needs to have before Godel applies to it is a complicated task, and lots of questions have been asked on this topic both here at at mathoverflow (see e.g. this question or this other question). However, there is a snappy answer to the more specific question Is there, then a simple explanation of why the ...


7

You were right to doubt your proof; it's not quite right. The main mistake is that you are effectively closing two subproofs at once once you go from 2.2.3 to 3, but you can only close one subproof at a time, in the reverse order in which you opened them. Also: you need to have line 1 as an assumption of a subproof, and close that subproof once you have ...


6

The most likely reason one would use natural deduction in a proof is because it parallels the way people think. When trying to prove some complicated implication chain like $$(A\to(B\to C))\to((A\to B)\to(A\to C)),$$ most people find it more logical and reasonable to assume the left part and deduce the right part rather than working with axioms that deal ...


6

This boils down to showing that $b^4 + b + 1$ is never the fourth power of an integer. The difference between consecutive fourth powers is $$(b+1)^4 - b^4 = 4b^3 + 6b^2 + 4b + 1,$$ which is greater than $b+1$ for all $b > 0$. Since $b^4 + b + 1$ is a fourth power of an integer, plus $b+1$, you'll never reach another fourth power of an integer by ...


6

Well by Fermat's little theorem, $a^{p-1} \equiv 1 \pmod{p}$ for all $a$ such that $p \not \mid a$. Hence: $$ 1^{p-1}+2^{p-1}+\ldots+(p-1)^{p-1} \equiv 1+1+\ldots+1 = p-1 \equiv -1 \pmod{p}$$


6

Example Let $\Gamma$ the set of first-order Peano axioms: no variables free. 1) $\Gamma \vdash \exists x (x = 0)$ --- easily provable 2) $\Gamma, x=0 \vdash x=0$ --- obvious 3) $\Gamma \vdash x=0$ --- from 1) and 2) by $\exists$-elim : wrong ! 4) $\Gamma \vdash \forall x (x=0)$ --- from 3) by $\forall$-intro, 1) $\Gamma, x=0 \vdash x = 0$ 2) $\Gamma,...


6

In algebraic number theory, there are a lot of ways of getting to the main results of class field theory. Here are what I think of as the main results. Of course there are many auxiliary results, which appear either as corollaries of theorems (1) and (2) or are part of their proof, such as Kronecker-Weber theorem, Hilbert class field theorem, existence of ...


6

I would do it slightly differently, but as always people use somewhat different systems for natural deduction. Begin 1) $(P \land \lnot Q) \rightarrow Q$ (ass.) 2) $P$ (ass.) 3) $\lnot Q$ (ass.) 4) $(P \land \lnot Q)$ introduction $\lnot$ from 2,3. 5) $Q$ (modus ponens from 1. and 4.) 6) $\bot$ from $5$ and $3$. 7) $\lnot \lnot Q$ (from introduction $\...


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