Etydhv

How to reply this mail from potential PhD professor?

Is induction neccessary for proving that every injective mapping of a finite set into itself is a mapping onto itself?

Did we get closer to another plane than we were supposed to, or was the pilot just protecting our delicate sensibilities?

Should I replace my bicycle tires if they have not been inflated in multiple years

Is one octave above tonic also considered as tonic?

Why do money exchangers give different rates to different bills?

I may be a fraud

What are the spoon bit of a spoon and fork bit of a fork called?

Where can I go to avoid planes overhead?

What happens to matryoshka Mordenkainen's Magnificent Mansions?

Has any spacecraft ever had the ability to directly communicate with civilian air traffic control?

Pressure inside an infinite ocean?

A non-technological, repeating, phenomenon in the sky, holding its position in the sky for hours

Can I get a paladin's steed by True Polymorphing into a monster that can cast Find Steed?

Enumerate Derangements

What is a "listed natural gas appliance"?

Reconstruct a matrix from its traces

How could a planet have most of its water in the atmosphere?

In a vacuum triode, what prevents the grid from acting as another anode?

How to give very negative feedback gracefully?

Why wasn't the Night King naked in S08E03?

In Endgame, why were these characters still around?

Pressure to defend the relevance of one's area of mathematics

Why was the battle set up *outside* Winterfell?

Is induction neccessary for proving that every injective mapping of a finite set into itself is a mapping onto itself?

Understanding the proof of: If $|A| = kappa$, then $|mathcalP(A)|=2^kappa$.Rigorous proof that surjectivity implies injectivity for finite setsSubsets of countable sets are countableEvery subset of a finite set is finite.. confused why this proof is wrong..Every subset of a finite set is finite (hopefully this would be the last time)Every Subset of a Finite Set is Finite (understanding Cain's proof)Prove that $g^-1hg$ is contained in set of injections with finite non-identities of a set onto itselfA set S is infinite, if and only if S can be put into a one-to-one correspondence with a proper subset of itselfProblem 7 from Topics of Algebra I.N.HersteinProving $anebimpliesa<blorb<a$ for natural numbers beginning with 1 using Peano's Axioms without induction hypothesis

6

$begingroup$

Upon reviewing the basic theorem that the number of elements in a fixed finite set is unique, I tried to determine what part of this proposition is in need of proof. It seems axiomatic. Nonetheless, BBFSK have a very long-winded, and seemingly convoluted discussion of this, and related ideas.

When I attempted to produce my own argument in support of the above proposition, the part which I am not able to state purely in the terminology of mappings (bijection, injection, etc) is that an injection of a finite set into itself is a mapping onto itself. The proof BBFSK give uses induction. After thinking about it for a while, that was the only approach I could come up with.

Is there a rigorous proof of the proposition that every injective mapping of a finite set into itself is a mapping of the set onto itself which does not involve induction?

elementary-number-theory elementary-set-theory induction alternative-proof

share|cite|improve this question

asked 1 hour ago

Steven HattonSteven Hatton

1,115422

$endgroup$

add a comment | 

6

$begingroup$

Upon reviewing the basic theorem that the number of elements in a fixed finite set is unique, I tried to determine what part of this proposition is in need of proof. It seems axiomatic. Nonetheless, BBFSK have a very long-winded, and seemingly convoluted discussion of this, and related ideas.

When I attempted to produce my own argument in support of the above proposition, the part which I am not able to state purely in the terminology of mappings (bijection, injection, etc) is that an injection of a finite set into itself is a mapping onto itself. The proof BBFSK give uses induction. After thinking about it for a while, that was the only approach I could come up with.

Is there a rigorous proof of the proposition that every injective mapping of a finite set into itself is a mapping of the set onto itself which does not involve induction?

elementary-number-theory elementary-set-theory induction alternative-proof

share|cite|improve this question

asked 1 hour ago

Steven HattonSteven Hatton

1,115422

$endgroup$

add a comment | 

$begingroup$

Upon reviewing the basic theorem that the number of elements in a fixed finite set is unique, I tried to determine what part of this proposition is in need of proof. It seems axiomatic. Nonetheless, BBFSK have a very long-winded, and seemingly convoluted discussion of this, and related ideas.

When I attempted to produce my own argument in support of the above proposition, the part which I am not able to state purely in the terminology of mappings (bijection, injection, etc) is that an injection of a finite set into itself is a mapping onto itself. The proof BBFSK give uses induction. After thinking about it for a while, that was the only approach I could come up with.

Is there a rigorous proof of the proposition that every injective mapping of a finite set into itself is a mapping of the set onto itself which does not involve induction?

elementary-number-theory elementary-set-theory induction alternative-proof

share|cite|improve this question

asked 1 hour ago

Steven HattonSteven Hatton

1,115422

$endgroup$

share|cite|improve this question

asked 1 hour ago

Steven HattonSteven Hatton

1,115422

share|cite|improve this question

asked 1 hour ago

Steven HattonSteven Hatton

1,115422

asked 1 hour ago

Steven HattonSteven Hatton

1,115422

asked 1 hour ago

Steven HattonSteven Hatton

1,115422

1 Answer
1

active

oldest

votes

6

$begingroup$

Dedekind proposed to use this property as the definition of "finite set", so that's at least one alternative -- closely in line with your intuition of declaring it to be axiomatic. Unfortunately there are technical problems with that approach. In particular you then need the axiom of choice to prove that induction works for all "finite" cardinalities, which is untidy at the least.

(A set $X$ such that every injection $Xto X$ is a bijection is now called "Dedekind-finite").

In a standard development of set theory, on the other hand, you're out of luck. Here "finite" is defined as "has the same cardinality as an element of $omega$", and $omega$ is (essentially) defined to be the largest set that mathematical induction works for. So in order to prove anything about "finite" you need to have an induction somewhere, because that's the only way to connect to the definition. This induction can be hidden in the proof of another property that you depend on, but that is basically just kicking the buck around. Eventually it has to stop.

---

This comment by Daniel Schepler is also relevant:

There's also the notion of Kuratowski finiteness, which is essentially equivalent to the condition that the power set of $𝑋$ is well-founded under the relation of "strict extension by one element". But then, of course, the natural way to prove nearly anything about Kuratowski finite sets is to use induction on the well-foundedness property...

share|cite|improve this answer

edited 25 mins ago

answered 1 hour ago

Henning MakholmHenning Makholm

245k17314558

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The definition the authors give is that a finite set is one which can be put in one-to-one correspondence with a segment $A_n=left1ge x le nright.$ It appears that what we are saying amounts to "if you count a set of objects, rearrange them, then count them again, you'll get the same number".
  $endgroup$
  – Steven Hatton
  1 hour ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @StevenHatton: That's the same definition as the one Henning provides, because in the "usual" construction of $mathbbN$ as an inductive set, your $A_n$ is exactly equal to $n+1$ (modulo including $0$ in $mathbbN$)...
  $endgroup$
  – Arturo Magidin
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @StevenHatton: To be more explicit; in the "usual" construction as an inductive set, we have $0=varnothing$, $n^+ = ncupn$ for any set $n$, and $mathbbN$ is the smallest set that includes $0$ and such that if $xinmathbbN$ then $x^+inmathbbN$. Then $1=0^+$, $2=1^+$, etc., and in this construction, the set $n$ contains exactly $n$ elements, namely $0,1,2,ldots,n-1$.
  $endgroup$
  – Arturo Magidin
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Bu the way: @Arturo gives the usual textbook definition of $mathbb N$ (a.k.a. $omega$). My characterization as "the largest set induction works for" looks rather different at first, but is nevertheless what the textbook definition achieves. Because $omega$ contains $0$ and all the $x^+$s, induction must fail in any _strictly larger_ set (as $omega$ itself would be a counterexample) -- and being the "smallest set" that satisfies this exactly guarantees that induction will work in $omega$.
  $endgroup$
  – Henning Makholm
  47 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  There's also the notion of Kuratowski finiteness, which is essentially equivalent to the condition that the power set of $X$ is well-founded under the relation of "strict extension by one element". But then, of course, the natural way to prove nearly anything about Kuratowski finite sets is to use induction on the well-foundedness property...
  $endgroup$
  – Daniel Schepler
  30 mins ago
  

  
  
  
  

 | 
show 3 more comments

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3208715%2fis-induction-neccessary-for-proving-that-every-injective-mapping-of-a-finite-set%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

6

$begingroup$

Dedekind proposed to use this property as the definition of "finite set", so that's at least one alternative -- closely in line with your intuition of declaring it to be axiomatic. Unfortunately there are technical problems with that approach. In particular you then need the axiom of choice to prove that induction works for all "finite" cardinalities, which is untidy at the least.

(A set $X$ such that every injection $Xto X$ is a bijection is now called "Dedekind-finite").

In a standard development of set theory, on the other hand, you're out of luck. Here "finite" is defined as "has the same cardinality as an element of $omega$", and $omega$ is (essentially) defined to be the largest set that mathematical induction works for. So in order to prove anything about "finite" you need to have an induction somewhere, because that's the only way to connect to the definition. This induction can be hidden in the proof of another property that you depend on, but that is basically just kicking the buck around. Eventually it has to stop.

---

This comment by Daniel Schepler is also relevant:

There's also the notion of Kuratowski finiteness, which is essentially equivalent to the condition that the power set of $𝑋$ is well-founded under the relation of "strict extension by one element". But then, of course, the natural way to prove nearly anything about Kuratowski finite sets is to use induction on the well-foundedness property...

share|cite|improve this answer

edited 25 mins ago

answered 1 hour ago

Henning MakholmHenning Makholm

245k17314558

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The definition the authors give is that a finite set is one which can be put in one-to-one correspondence with a segment $A_n=left1ge x le nright.$ It appears that what we are saying amounts to "if you count a set of objects, rearrange them, then count them again, you'll get the same number".
  $endgroup$
  – Steven Hatton
  1 hour ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @StevenHatton: That's the same definition as the one Henning provides, because in the "usual" construction of $mathbbN$ as an inductive set, your $A_n$ is exactly equal to $n+1$ (modulo including $0$ in $mathbbN$)...
  $endgroup$
  – Arturo Magidin
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @StevenHatton: To be more explicit; in the "usual" construction as an inductive set, we have $0=varnothing$, $n^+ = ncupn$ for any set $n$, and $mathbbN$ is the smallest set that includes $0$ and such that if $xinmathbbN$ then $x^+inmathbbN$. Then $1=0^+$, $2=1^+$, etc., and in this construction, the set $n$ contains exactly $n$ elements, namely $0,1,2,ldots,n-1$.
  $endgroup$
  – Arturo Magidin
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Bu the way: @Arturo gives the usual textbook definition of $mathbb N$ (a.k.a. $omega$). My characterization as "the largest set induction works for" looks rather different at first, but is nevertheless what the textbook definition achieves. Because $omega$ contains $0$ and all the $x^+$s, induction must fail in any _strictly larger_ set (as $omega$ itself would be a counterexample) -- and being the "smallest set" that satisfies this exactly guarantees that induction will work in $omega$.
  $endgroup$
  – Henning Makholm
  47 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  There's also the notion of Kuratowski finiteness, which is essentially equivalent to the condition that the power set of $X$ is well-founded under the relation of "strict extension by one element". But then, of course, the natural way to prove nearly anything about Kuratowski finite sets is to use induction on the well-foundedness property...
  $endgroup$
  – Daniel Schepler
  30 mins ago
  

  
  
  
  

 | 
show 3 more comments

6

$begingroup$

Dedekind proposed to use this property as the definition of "finite set", so that's at least one alternative -- closely in line with your intuition of declaring it to be axiomatic. Unfortunately there are technical problems with that approach. In particular you then need the axiom of choice to prove that induction works for all "finite" cardinalities, which is untidy at the least.

(A set $X$ such that every injection $Xto X$ is a bijection is now called "Dedekind-finite").

In a standard development of set theory, on the other hand, you're out of luck. Here "finite" is defined as "has the same cardinality as an element of $omega$", and $omega$ is (essentially) defined to be the largest set that mathematical induction works for. So in order to prove anything about "finite" you need to have an induction somewhere, because that's the only way to connect to the definition. This induction can be hidden in the proof of another property that you depend on, but that is basically just kicking the buck around. Eventually it has to stop.

---

This comment by Daniel Schepler is also relevant:

There's also the notion of Kuratowski finiteness, which is essentially equivalent to the condition that the power set of $𝑋$ is well-founded under the relation of "strict extension by one element". But then, of course, the natural way to prove nearly anything about Kuratowski finite sets is to use induction on the well-foundedness property...

share|cite|improve this answer

edited 25 mins ago

answered 1 hour ago

Henning MakholmHenning Makholm

245k17314558

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The definition the authors give is that a finite set is one which can be put in one-to-one correspondence with a segment $A_n=left1ge x le nright.$ It appears that what we are saying amounts to "if you count a set of objects, rearrange them, then count them again, you'll get the same number".
  $endgroup$
  – Steven Hatton
  1 hour ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @StevenHatton: That's the same definition as the one Henning provides, because in the "usual" construction of $mathbbN$ as an inductive set, your $A_n$ is exactly equal to $n+1$ (modulo including $0$ in $mathbbN$)...
  $endgroup$
  – Arturo Magidin
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @StevenHatton: To be more explicit; in the "usual" construction as an inductive set, we have $0=varnothing$, $n^+ = ncupn$ for any set $n$, and $mathbbN$ is the smallest set that includes $0$ and such that if $xinmathbbN$ then $x^+inmathbbN$. Then $1=0^+$, $2=1^+$, etc., and in this construction, the set $n$ contains exactly $n$ elements, namely $0,1,2,ldots,n-1$.
  $endgroup$
  – Arturo Magidin
  1 hour ago
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Bu the way: @Arturo gives the usual textbook definition of $mathbb N$ (a.k.a. $omega$). My characterization as "the largest set induction works for" looks rather different at first, but is nevertheless what the textbook definition achieves. Because $omega$ contains $0$ and all the $x^+$s, induction must fail in any _strictly larger_ set (as $omega$ itself would be a counterexample) -- and being the "smallest set" that satisfies this exactly guarantees that induction will work in $omega$.
  $endgroup$
  – Henning Makholm
  47 mins ago
  
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  There's also the notion of Kuratowski finiteness, which is essentially equivalent to the condition that the power set of $X$ is well-founded under the relation of "strict extension by one element". But then, of course, the natural way to prove nearly anything about Kuratowski finite sets is to use induction on the well-foundedness property...
  $endgroup$
  – Daniel Schepler
  30 mins ago
  

  
  
  
  

 | 
show 3 more comments

$begingroup$

Dedekind proposed to use this property as the definition of "finite set", so that's at least one alternative -- closely in line with your intuition of declaring it to be axiomatic. Unfortunately there are technical problems with that approach. In particular you then need the axiom of choice to prove that induction works for all "finite" cardinalities, which is untidy at the least.

(A set $X$ such that every injection $Xto X$ is a bijection is now called "Dedekind-finite").

In a standard development of set theory, on the other hand, you're out of luck. Here "finite" is defined as "has the same cardinality as an element of $omega$", and $omega$ is (essentially) defined to be the largest set that mathematical induction works for. So in order to prove anything about "finite" you need to have an induction somewhere, because that's the only way to connect to the definition. This induction can be hidden in the proof of another property that you depend on, but that is basically just kicking the buck around. Eventually it has to stop.

---

This comment by Daniel Schepler is also relevant:

There's also the notion of Kuratowski finiteness, which is essentially equivalent to the condition that the power set of $𝑋$ is well-founded under the relation of "strict extension by one element". But then, of course, the natural way to prove nearly anything about Kuratowski finite sets is to use induction on the well-foundedness property...

share|cite|improve this answer

edited 25 mins ago

answered 1 hour ago

Henning MakholmHenning Makholm

245k17314558

$endgroup$

share|cite|improve this answer

edited 25 mins ago

answered 1 hour ago

Henning MakholmHenning Makholm

245k17314558

answered 1 hour ago

Henning MakholmHenning Makholm

245k17314558

answered 1 hour ago

Henning MakholmHenning Makholm

245k17314558