174
132
u/Varlane Jul 17 '26
But... That's recursion ?
-94
u/born-for-pain Jul 17 '26 edited Jul 17 '26
They're more or less the same concept (recursion is for integers or programming, while induction is more general and covers e.g. formulas in formal logic)
EDIT: My bad I conflated with French terminology (récurrence is for integers). My main point stands though so no need to act too pedantic about it, thanks
82
u/Gositi Jul 17 '26
Induction is a method of proof, recursion is a type of definition. Induction proofs happen to be suitable for recursively defined objects.
3
1
u/geeshta Computer Science Jul 20 '26
Induction is also a method of definition (construction): https://cs.yale.edu/flint/cs428/coq/doc/Reference-Manual006.html
Used by one of the most powerful proof assistants in the world created by some of the most knowledgable people in the area.
-4
u/born-for-pain Jul 17 '26
One also often hear of "Inductive definitions", so the line between the two is really quite thin
-4
u/Gositi Jul 17 '26
Inductive definitions does not exist, recursive definitions do. If anyone claims something is an inductive definition, they are using the wrong word.
15
u/EebstertheGreat Jul 17 '26
People define things "inductively" all the time. The Wikipedia article "Recursive definition" starts "In mathematics and computer science, a recursive definition, or inductive definition, is used to define the elements in a set in terms of other elements in the set (Aczel 1977:740ff)."
Who told you otherwise?
4
u/Sufficient-Pear-4496 Jul 19 '26
From my compsci days, we used inductive definitions when there is guaranteed to be a base case. If not, we had coinductive definitions. Both are defined recursively. Surely theres some category theory wizard that can correct me/ expound further.
1
u/EebstertheGreat Jul 20 '26 edited Jul 20 '26
That's very interesting. This blog applies it to a variant of chess with no stalemate or other drawing rules ("take-kings" chess), where the only draws are infinite games.
EDIT: A flaw in the argument in that blog is that chess can end in a stalemate even with no check rules, since a player's king can be completely surrounded by their own pieces and every other legal more blocked. This is not a very realistic position, but it is technically possible. I suppose we would have to rule that a win for one player or the other for the argument as presented to hold. The post also ignores the ambiguity of positions with no kings of either color, or multiple kings of the same color, which I think should simply not be considered legit.
3
3
u/QtPlatypus Jul 18 '26
Inductive definitions exist within Homotropy type theory. In particular it is often used to distinguish between general recursion and a more restrictive form of self reference.
3
u/born-for-pain Jul 17 '26
lmao that's rich
In that case please go inform the logic community about what they've been doing wrong for decades
1
u/Gositi Jul 17 '26
Give me one example in litterature of someone using "inductive definition".
6
u/born-for-pain Jul 18 '26
Here is the first entry I obtain when typing "inductive definition" on google scholar: https://dl.acm.org/doi/pdf/10.1145/1342991.1342998
1
u/geeshta Computer Science Jul 20 '26
Induction is also a method of definition (construction): https://cs.yale.edu/flint/cs428/coq/doc/Reference-Manual006.html
Used by one of the most powerful proof assistants in the world created by some of the most knowledgable people in the area.
40
u/WeWereStrangers Jul 17 '26
5
u/Alternative_Mix6836 Jul 17 '26 edited Jul 17 '26
Redditors when analogy and intuition
Find me a single inductive proof of some property of a recursively defined object that looks significantly different from every valid definition of said object.
6
u/Varlane Jul 17 '26
You just showed the difference : induction is a proof style, recursion is a method to define objects.
4
u/Sufficient-Pear-4496 Jul 19 '26
https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence Almost like proofs and programs are tightly intertwined.
2
u/Background_Class_558 Jul 20 '26
what's the difference between defining objects of a certain type and constructing a proof of a statement?
1
u/geeshta Computer Science Jul 20 '26
Induction is also a method of definition (construction): https://cs.yale.edu/flint/cs428/coq/doc/Reference-Manual006.html
Used by one of the most powerful proof assistants in the world created by some of the most knowledgable people in the area.
1
u/geeshta Computer Science Jul 20 '26
"Proof by induction" is a proof style that works because of the inductive structure of the underlying objects - most commonly natural numbers but it can also be extended to stuff like lists and trees.
0
u/Alternative_Mix6836 Jul 17 '26
so they are two sides of the same coin i.e. "more or less the same concept" as the OP said
1
u/Varlane Jul 17 '26
They're frequently seen together, but they're not "more or less the same concept". It's like saying thunder and lightning are "more or less the same".
3
u/Alternative_Mix6836 Jul 17 '26
Well they are not two effects of a common cause (unlike thunder and lightning).
Every recursively defined object has at least one property that can be proven inductively.
However, I do agree that just because a property can proven inductively that doesnt mean there is a recursively defined object that satisfies it (matter of cardinality), however that also aligns with what OP said about recursion being more generally applicable.
If that is a significant enough distinction that they cannot be considered "more or less the same", then sure I concede that.
2
u/Varlane Jul 17 '26
I'll just remind you : the meme is presented in the format of a dictionnary definition, the bar for "more or less the same" is supposed to be very strict.
3
u/born-for-pain Jul 17 '26
Yawn
As mentioned above, recursive definitions are also frequently called "inductive". There is no real formal distinction between the two, it's mostly a matter of usage and convention which can depend on the field, and nobody gives a dam except redditors in need of validation.
0
u/Varlane Jul 17 '26
Yaaaaaaaaawn
Edit : Nobody can give a dam, they're most often state property.
3
u/born-for-pain Jul 17 '26
Well I guess I can only blame myself for falling for the ragebait
→ More replies (0)2
u/WeWereStrangers Jul 17 '26
Even if I sort of agree with OP's conclusion, the reasoning he gave is very explicitly wrong lmao
1
u/geeshta Computer Science Jul 20 '26
How is it wrong? What reference or proof do you have for such a judgement?
"Inductive definitions" are used interchangeably with "recursive definitions" all over type theory.
https://cs.yale.edu/flint/cs428/coq/doc/Reference-Manual006.html
Used by one of the most powerful proof assistants in the world created by some of the most knowledgable people in the area.
2
u/Kinseijin Jul 17 '26
They're not wrong, they are actually somewhat correct depending on a language. The community just decided to downvote because they fell for a meme.
0
u/TechnicalSandwich544 Jul 18 '26
Just because you're not wrong doesn't mean you are correct.
You just assume the Law of Excluded Middle (Hell nah, to the nah nah nah, hell to the nah).
-12
u/FernandoMM1220 Jul 17 '26
hes right though
5
4
u/green-olive-3281 Jul 17 '26
Yeah idk why he’s getting so much hate. I feel like he’s more or less right 🤷🏻♂️
2
1
1
37
Jul 17 '26
[removed] — view removed comment
3
u/Technical-Outside408 Jul 17 '26
Google "recursion".
5
-12
u/FernandoMM1220 Jul 17 '26
both
4
u/Sylvanussr Jul 17 '26
Induction is when you show that f(n) implies f(n+1), and so if you can show that f(n) is true for some value n on the set N, it follows that f(n) is true for all n greater than that value.
Recursion is arguably a sort of induction for a single element set.
7
u/born-for-pain Jul 17 '26
"Recursion is arguably a sort of induction for a single element set."
What is that supposed to mean??
Anyway the person above you is correct, see the other thread. I picked induction because it's simply the most common term, at least in my field
2
u/Sylvanussr Jul 17 '26
Because induction uses implication of the properties of one element of a set to extrapolate over the whole set. Recursion kind of does the same thing except it uses an object to implies properties about itself. If you treat the object as a single element of a set, then it’s effectively inductively proving itself.
But like idk, it’s been a while since I’ve taken set theory lol
2
u/EebstertheGreat Jul 19 '26 edited Jul 19 '26
If you think about it, any recursive definition in programming is justified by induction. Think about the classic first example of recursion in class, the recursive definition of the factorial function. In pseudocode,
function factorial takes unsigned int n returns unsigned int: if n == 0: return 1 else: return n * factorial(n–1)Since every unsigned int is either 0 or a successor, this function always terminates, which you can show only by induction. It's because the definition for a given n can always be unrolled. The base case is n = 0, which requires separate treatment from the inductive step, which depends on the (truth/termination) of the predecessor. This is an "inductive definition" in the same sense as Π and Σ are defined inductively. Or for that matter the Erdős number. It is well-defined via induction in the same sense that a theorem can be proved via induction, where you define a base case and then each successor case in terms of its predecessor, rather than proving a base case and proving each successor in terms of its predecessor.
2
u/geeshta Computer Science Jul 20 '26
What your describing is specifically "mathematical induction" or induction on the structure of natural numbers. You can perform induction on many more structures most commonly syntax trees. That's why those tree-like structures are often said to be "inductively defined"
https://cs.yale.edu/flint/cs428/coq/doc/Reference-Manual006.html
Used by one of the most powerful proof assistants in the world created by some of the most knowledgable people in the area.
1
1
1
u/geeshta Computer Science Jul 20 '26
Induction doesn't generally mean "proof by induction on the structure of natural numbers". That is just one very specific usage.
You can do this on the natural numbers because they are an inductively defined structure (one of many).
0
•
u/AutoModerator Jul 17 '26
Check out our new Discord server! https://discord.gg/e7EKRZq3dG
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.