A nonidentity permutation $sigma$ satisfies $sigma(i)<i$ for some $i$ [closed]
$begingroup$
If a permutation $sigma: Nto N$ is not the identity, prove that there exists an $i in {1,...,n} $ such that $sigma(i)<i$.
abstract-algebra functions permutations
edited Dec 9 '18 at 16:11
Matt Samuel
38k63666
asked Dec 5 '18 at 0:57
cercer
405
$endgroup$
closed as off-topic by caverac, user10354138, Lord Shark the Unknown, Rebellos, Vidyanshu Mishra Dec 5 '18 at 7:27
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – caverac, user10354138, Rebellos, Vidyanshu Mishra
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
If a permutation $sigma: Nto N$ is not the identity, prove that there exists an $i in {1,...,n} $ such that $sigma(i)<i$.
abstract-algebra functions permutations
edited Dec 9 '18 at 16:11
Matt Samuel
38k63666
asked Dec 5 '18 at 0:57
cercer
405
$endgroup$
closed as off-topic by caverac, user10354138, Lord Shark the Unknown, Rebellos, Vidyanshu Mishra Dec 5 '18 at 7:27
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – caverac, user10354138, Rebellos, Vidyanshu Mishra
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
If a permutation $sigma: Nto N$ is not the identity, prove that there exists an $i in {1,...,n} $ such that $sigma(i)<i$.
abstract-algebra functions permutations
edited Dec 9 '18 at 16:11
Matt Samuel
38k63666
asked Dec 5 '18 at 0:57
cercer
405
$endgroup$
If a permutation $sigma: Nto N$ is not the identity, prove that there exists an $i in {1,...,n} $ such that $sigma(i)<i$.
abstract-algebra functions permutations
abstract-algebra functions permutations
edited Dec 9 '18 at 16:11
Matt Samuel
38k63666
asked Dec 5 '18 at 0:57
cercer
405
edited Dec 9 '18 at 16:11
Matt Samuel
38k63666
asked Dec 5 '18 at 0:57
cercer
405
edited Dec 9 '18 at 16:11
Matt Samuel
38k63666
edited Dec 9 '18 at 16:11
Matt Samuel
38k63666
edited Dec 9 '18 at 16:11
Matt Samuel
38k63666
38k63666
asked Dec 5 '18 at 0:57
cercer
405
asked Dec 5 '18 at 0:57
cercer
405
asked Dec 5 '18 at 0:57
cercer
405
405
closed as off-topic by caverac, user10354138, Lord Shark the Unknown, Rebellos, Vidyanshu Mishra Dec 5 '18 at 7:27
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – caverac, user10354138, Rebellos, Vidyanshu Mishra
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by caverac, user10354138, Lord Shark the Unknown, Rebellos, Vidyanshu Mishra Dec 5 '18 at 7:27
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – caverac, user10354138, Rebellos, Vidyanshu Mishra
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
We prove that if $sigma(i)geq i$ for all $i$, then $sigma$ is the identity. We do this by induction on $n$. Clearly it is true if $n=1$. Otherwise, note that $sigma(n)geq n$, hence $sigma(n)=n$ since $n$ is the largest element. Then $sigma$ restricted to $[n-1]$ is a permutation with the same property on the smaller set, hence is the identity.
answered Dec 5 '18 at 1:55
Matt SamuelMatt Samuel
38k63666
$endgroup$
add a comment |
$begingroup$
Suppose the contrary, that $sigma (i)ge i,,forall i$. Then there is a minimum $hat i$ for which $sigma (hat i)gthat i$. Now the only remaining choices for $sigma ^{-1}(hat i)$ are all greater than $hat i$. So if $sigma (k)=hat i$, then $kgtsigma (k)$.
answered Dec 5 '18 at 2:02
Chris CusterChris Custer
12.5k3825
$endgroup$
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
We prove that if $sigma(i)geq i$ for all $i$, then $sigma$ is the identity. We do this by induction on $n$. Clearly it is true if $n=1$. Otherwise, note that $sigma(n)geq n$, hence $sigma(n)=n$ since $n$ is the largest element. Then $sigma$ restricted to $[n-1]$ is a permutation with the same property on the smaller set, hence is the identity.
answered Dec 5 '18 at 1:55
Matt SamuelMatt Samuel
38k63666
$endgroup$
add a comment |
$begingroup$
We prove that if $sigma(i)geq i$ for all $i$, then $sigma$ is the identity. We do this by induction on $n$. Clearly it is true if $n=1$. Otherwise, note that $sigma(n)geq n$, hence $sigma(n)=n$ since $n$ is the largest element. Then $sigma$ restricted to $[n-1]$ is a permutation with the same property on the smaller set, hence is the identity.
answered Dec 5 '18 at 1:55
Matt SamuelMatt Samuel
38k63666
$endgroup$
add a comment |
$begingroup$
We prove that if $sigma(i)geq i$ for all $i$, then $sigma$ is the identity. We do this by induction on $n$. Clearly it is true if $n=1$. Otherwise, note that $sigma(n)geq n$, hence $sigma(n)=n$ since $n$ is the largest element. Then $sigma$ restricted to $[n-1]$ is a permutation with the same property on the smaller set, hence is the identity.
answered Dec 5 '18 at 1:55
Matt SamuelMatt Samuel
38k63666
$endgroup$
We prove that if $sigma(i)geq i$ for all $i$, then $sigma$ is the identity. We do this by induction on $n$. Clearly it is true if $n=1$. Otherwise, note that $sigma(n)geq n$, hence $sigma(n)=n$ since $n$ is the largest element. Then $sigma$ restricted to $[n-1]$ is a permutation with the same property on the smaller set, hence is the identity.
answered Dec 5 '18 at 1:55
Matt SamuelMatt Samuel
38k63666
answered Dec 5 '18 at 1:55
Matt SamuelMatt Samuel
38k63666
answered Dec 5 '18 at 1:55
Matt SamuelMatt Samuel
38k63666
answered Dec 5 '18 at 1:55
Matt SamuelMatt Samuel
38k63666
38k63666
add a comment |
add a comment |
$begingroup$
Suppose the contrary, that $sigma (i)ge i,,forall i$. Then there is a minimum $hat i$ for which $sigma (hat i)gthat i$. Now the only remaining choices for $sigma ^{-1}(hat i)$ are all greater than $hat i$. So if $sigma (k)=hat i$, then $kgtsigma (k)$.
answered Dec 5 '18 at 2:02
Chris CusterChris Custer
12.5k3825
$endgroup$
add a comment |
$begingroup$
Suppose the contrary, that $sigma (i)ge i,,forall i$. Then there is a minimum $hat i$ for which $sigma (hat i)gthat i$. Now the only remaining choices for $sigma ^{-1}(hat i)$ are all greater than $hat i$. So if $sigma (k)=hat i$, then $kgtsigma (k)$.
answered Dec 5 '18 at 2:02
Chris CusterChris Custer
12.5k3825
$endgroup$
add a comment |
$begingroup$
Suppose the contrary, that $sigma (i)ge i,,forall i$. Then there is a minimum $hat i$ for which $sigma (hat i)gthat i$. Now the only remaining choices for $sigma ^{-1}(hat i)$ are all greater than $hat i$. So if $sigma (k)=hat i$, then $kgtsigma (k)$.
answered Dec 5 '18 at 2:02
Chris CusterChris Custer
12.5k3825
$endgroup$
Suppose the contrary, that $sigma (i)ge i,,forall i$. Then there is a minimum $hat i$ for which $sigma (hat i)gthat i$. Now the only remaining choices for $sigma ^{-1}(hat i)$ are all greater than $hat i$. So if $sigma (k)=hat i$, then $kgtsigma (k)$.
answered Dec 5 '18 at 2:02
Chris CusterChris Custer
12.5k3825
answered Dec 5 '18 at 2:02
Chris CusterChris Custer
12.5k3825
answered Dec 5 '18 at 2:02
Chris CusterChris Custer
12.5k3825
answered Dec 5 '18 at 2:02
Chris CusterChris Custer
12.5k3825
12.5k3825
add a comment |
add a comment |
