Tag Info

Hot answers tagged

45

Write the axioms of number theory as $P^-+\mathrm{Ind}$, where $P^-$ is the ordered semiring axioms (no induction), and $Ind$ is the axiom (scheme) of induction. Then a theorem requires some induction if it is not provable by $P^-$ alone - that is, if we can find a model of $P^-$ in which the theorem is not true. (This is Goedel's completeness theorem.) So ...


23

Here is a "proof" of a famous identity by Ramanujan: $$\sqrt{1+\sqrt{1+2\sqrt{1+3{\sqrt{1+4\sqrt{\dots}}}}}}=2.$$ Claim: Let us prove this more general result for all $n\geq 0$: $$\sqrt{1+n\sqrt{1+(n+1)\sqrt{1+(n+2)\sqrt{1+(n+3)\sqrt{\ldots}}}}}=n+1.$$ Base case: When $n=0$, we have $\sqrt{1+0\sqrt{\dots}}=0+1$, and this is true. Inductive step: Assume ...


8

Claim: For every $n\in\mathbb{Z^+}$, if $x,y\in\mathbb{Z^+}$ with $\max(x,y)=n$, then $x=y$. Base case: Suppose that $n=1$. If $\max(x,y)=1$ and $x,y\in\mathbb{Z^+}$, then $x=1$ and $y=1$. Inductive step: Let $k\in\mathbb{Z^+}$. Assume that whenever $\max(x,y)=k$ and $x,y\in\mathbb{Z^+}$, then $x=y$. Now let $\max(x,y)=k+1$, where $x,y\in\mathbb{Z^+}$. ...


7

A nice example from the area of computer science would be John C. Reynolds "Polymorphism is not set-theoretic" (available here: https://hal.inria.fr/inria-00076261/document). The point is that second-order $\lambda$-calculus does not have set-theoretic models (there is a rather natural definition in the paper of what it means to be "set-theoretic"). The ...


6

Does the following standard proof of the Brouwer fixed point theorem for the two-dimensional disk $D$ count? Theorem. Any continuous map $f : D \to D$ has a fixed point. Proof. If $f$ had no fixed point, the map $g : D \to \partial D$ given by $g(x) = \partial D \cap ($ray from $f(x)$ to $x)$ would be a retraction of $D$ onto $\partial D$, that is, $g ...


6

Here is one published by Knuth. Claim: $$\underbrace{\frac1{1\cdot2}+\frac1{2\cdot3}+\ldots}_{n\text{ terms}}=\frac32-\frac1n$$ Base case: For $n=1$, we have $\frac32-\frac11=\frac1{1\cdot2}$ Inductive step: $$\left(\frac1{1\cdot2}+\ldots+\frac1{(n-1)\cdot n}\right)+\frac1{n\cdot(n+1)}=\frac32-\frac1n+\frac1{n\cdot(n+1)}$$ ...


6

One example is Sylver's Coinage played like so: Player's alternate selecting positive integers ($1, 2, 3, 4\dots$). The rule is that no number is allowed to be expressed as sum (with possible duplicates) of the previous. For example, say $\{4, 8, 5, 7\}$ ($8$ would have had to been said before $4$) was previously said. Then $6$ could be said, but $14$ could ...


4

One example is the ring game, which is defined here - in essence, the game (or a slight variant thereon) can be described as: Start with a Noetherian ring $R$. At each turn, replace $R$ with a quotient thereof. If a player can make no legal moves (i.e. $R$ is a field, thus has no proper quotients). One can notice that if we play this on $\mathbb Z$, ...


4

Here are two proofs that both involve recognizing that a big category is the ind- or pro-category of a smaller category, and then proving something about the smaller category to get it for the bigger category. Theorem: The Pontryagin dual $\text{Hom}(A, S^1)$ of a torsion abelian group $A$ is a profinite abelian group and vice versa; these two maps are ...


4

Here is one example, very classical probably. I hope it counts for your purposes! Proposition. The fundamental group of a topological group $(G,\ast,e)$ is abelian. Proof. The fundamental group $\pi_{1}$ is a functor from topological spaces to groups which preserves products, so that it sends group objects into group objects. A topological group is a ...


4

How about the following: Given collections $\{a_i\}$ and $\{b_i\}$ of real numbers, then for all $n$: $\sum_{i=1}^n a_i + \sum_{i=1}^nb_i=\sum_{i=1}^n(a_i+b_i)$. If that is what you are looking for then I'm sure you can come up with millions of other such examples.


3

The Baire Category Theorem is equivalent to the Axiom of Dependent Choice, and therefore you would not expect to be able to find what you call a neat proof. It may if course not be exactly what you are looking for, precisely because induction alone is not enough to prove the theorem.


2

For each non-negative integer $n$, let $S(n)$ be the statement $S(n) : n=0.$ Claim: Every non-negative integer is equal to $0$. Base case: $S(0)$ is clearly true. Inductive step: Fix some $k\geq 0$ and assume that $S(0),\ldots, S(k)$ are true. To prove that $S(k+1)$ is true, observe that $S(k)$ says $k=0$ and $S(1)$ says $1=0$; hence, we have that ...


2

Let me provide a few references about the $p$-Laplace operator. Some open problems concerning $p$-Laplacian are listed in Abstracts of Mini-Workshop "The p-Laplacian Operator and Applications", 2013, on the pages 476-480. (Problem 3 about Nodal line of second $p$-eigenfunction is explained also here, p. 10.) Other open problems like a unique continuation ...


2

Claim: For every non-negative integer $n, 5n=0$. Base case: $5\cdot 0=0$. Inductive step: Suppose that $5j=0$ for all non-negative integers $j$ with $0\leq j\leq k$. Write $k+1=i+j$, where $i$ and $j$ are natural numbers less than $k+1$ (I am considering the natural numbers to include $0$). By the induction hypothesis, $5(k+1)=5(i+j)=5i+5j=0+0=0$. Flaw: ...


2

Higman's game$^*$ Using finite words on a fixed finite alphabet, two players take turns, in each turn specifying a word that contains no already-specified word as a subsequence. The game terminates when a player (declared the loser) is unable to specify a word, and the other player is declared the winner. By Higman's Lemma, every such game must eventually ...


2

The Hydra problem can be converted in a game with several players. The first player chooses the hydra. Players take turns cutting heads.


1

A ring $R$ with exactly two non-maximal ideals, $\{0\}$ and $R$, is either a local ring that's not a field or a product of two fields.


1

A commutative ring is connected (no nontrivial idempotents) iff $\{0\}$ and $R$ are the only finitely generated idempotent ideals. Near misses: A commutative ring is semisimple iff $R$ is the only essential ideal. A commutative ring has trivial Jacobson radical if $\{0\}$ is the only superfluous ideal. A commutative ring is reduced iff $\{0\}$ is the ...


1

Finite groups: The cyclic groups; the dihedral groups; the symmetric groups; the alternating groups; the quaternion group.


1

Graph Theory: the complete graphs; the complete bipartite graphs; trees; the Petersen graph.


1

The Jacobson radical. Take a noncommutative ring $R$ with 1. Any left ideal is either contained in another or is maximal. The elements common to all maximal left ideals, i.e. $$ J = \bigcap_i M_i, $$ is a group in two ways: It is an abelian group because it is an ideal (inherits group additivity from $R$, pretty obvious). It is group under circle ...


1

You might be interested in "Uncle Petros and Goldbach's Conjecture", a 1992 novel by Greek author Apostolos Doxiadis. This book has got a good story, and also discusses mathematical problems and some recent history of mathematics. http://www.amazon.co.uk/gp/aw/d/0571205119/ref=redir_mdp_mobile/278-8223441-9186456


1

I don't know if this fits as an answer, but I think that Michael Barr's existence of free groups is a nice application of some basic category theory.


1

You can prove the Poincare Lemma by reducing categorically/homotopy-theoretically to the case of a point. Proof: (re-)state the Poincare lemma (every closed form on a contractible subdomain of $\mathbb{R}^n$ is exact) as a statement about De Rham cohomology, and prove that the De Rham cohomology functor sends homotopy equivalences to isomorphisms. I seem to ...



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