Linked Questions

7
votes
1answer
272 views

Are there any proofs that only exist by induction? [duplicate]

I've come to learn more about induction recently for proving things, and one thing stands out to me. It seems like you could just data-mine patterns and guess a relationship you think might be ...
1
vote
1answer
321 views

Is Proof By Induction Necessary? [duplicate]

Are there any theorems that can only be proved by induction? Induction seems to be proof by technicality.
2
votes
0answers
71 views

Does it make sense to claim that something cannot be proven without induction? [duplicate]

Often we have questions on this site which ask for a proof of some result without induction.1 It seems that when such a question is posted, it is quite well-understood what is meant by proof avoiding ...
7
votes
3answers
678 views

How to verify satisfialibility in a model? (Confusions with Gödel's Completeness Theorem)

I just cannot believe that Gödel's Completeness Theorem is right. Let say we fixed some first order logic with some structure. Theorem claims that for any sentence $P$ in this logic we have that $$\...
10
votes
3answers
2k views

Can we prove that odd and even numbers alternate without using induction?

It is a simple exercise to prove using mathematical induction that if a natural number n > 1 is not divisible by 2, then n can be written as m + m + 1 for some natural number m. (Depending on your ...
3
votes
2answers
322 views

expressability of finite and infinite ramsey theorems in Peano arithmetic

Finite Ramsey theorem: $ \def\nn{\mathbb{N}} $ For any $e,k,r \in \nn$, there exists a least natural number $m=R(e,r,k)$ so that, for any set $M$ with cardinality at least $m$, with each of the $e$-...
5
votes
1answer
379 views

How can know if a proof technique can actually prove something? Specifically, induction

Induction is an incredible tool to prove some propositions. Although it seems that these propositions require some level of simplicity for us to be able prove them using only induction. If we wanted, ...
3
votes
2answers
128 views

Is this mathematical induction or not, and does it matter? And what known proofs have this form?

Suppose one proves that for all $n\in\{1,2,3,\ldots\},$ $a_n=a_1$ by means of showing that for every value of $n$ we have $a_{n+1} = a_n,$ the proof being the same for all values of $n.$ If one puts ...
0
votes
1answer
138 views

Overspill in computable nonstandard models

Tennenbaums' theorem does not apply to Robinson Arithmetic ($Q$). There is a computable, nonstandard model of $Q$ "consisting of integer-coefficient polynomials with positive leading coefficient, plus ...
4
votes
1answer
144 views

Arithmetic systems without Induction

It's often said that AC is a controversial axiom and so often in my math classes when it is used a brief comment is made to the effect of "we can prove this without Zorn's Lemma but it's more work". ...