anonymous
  • anonymous
Let \(k\) be a positive integer with \(k \leq |S_n|\). The symmetric group \(S_n\) acts on the set B consisting of all k-element subsets of \({1, \ldots , n}\) by \(\sigma \cdot {a_1, \ldots, a_k}={\sigma(a_1),\ldots,\sigma(a_k)}\). Determine for which values of \(k\) the actions of \(S_n\) on k-element subsets is faithul
Meta-math
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
Let k be a positive integer with \(k \leq n\). The symmetric group \(S_n\) acts on the set \(B\) consisting of all \(k\)-element subsets of \(\{1,…,n\}\) by \(\sigma⋅\{a_1,\ldots,a_k\}=\{σ(a1),\ldots,σ(ak)\}\). Determine for which values of \(k\) the actions of \(S_n\) on \(k\)-element subsets is faithul
anonymous
  • anonymous
Egh, I can't type: \(\{\sigma(a_1), \ldots , \sigma(a_k)\}\)
anonymous
  • anonymous
\(S_n\) is a group and it's operation is symmetric?

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

anonymous
  • anonymous
\(S_n\) is the symmetric group of the set \(\{1, \ldots, n\}\)
anonymous
  • anonymous
I know that if k = n, the operation is not faithful since any permutation will still give the n-element subset, and that if k = 1 it i's trivially faithful, but I'm stuck on proving whether or not it's faithful for 1 < k < n
anonymous
  • anonymous
How would it not be faithful?
anonymous
  • anonymous
An action is faithful if different elements of \(S_n\) induce different permutations of B, and if k = n, there is only one n-element subset, which every element of S_n maps to. ie if for different \(g, h \in S_n\), \(g\cdot x\neq h\cdot x\) for some \(x \in B\)
anonymous
  • anonymous
Hmmm, one thing I can say is that the set of all subsets is the power set and it has cardinality \(2^k\)
anonymous
  • anonymous
So is \(S_n\) full of \(n\) mappings which will permute the elements in \(B\)?
anonymous
  • anonymous
\(S_n\) is the set of n! distinct permutations of the set \(\{1, 2, ..., n\}\) it acts on B by permuting it's elements ie: if we have the permutation (1 2 3) (1 gets send to 2, 2 to 3, 3 to 1) act on {1, 2} we get \((1\,\,2\,\,\,3) \cdot \{1,2\}=\{2, 3\}\)
anonymous
  • anonymous
Should it result in \(\{3,1\}\)?
anonymous
  • anonymous
the action is defined as \(\sigma \cdot \{a_1, ... , a_k\} = \{\sigma(a_1), ... ,\sigma(a_k)\}\) so in the case that \(\sigma =\)(1 2 3), \(\sigma \cdot \{1, 2\}=\{\sigma(1), \sigma(2)\}=\{2, 3\}\)
anonymous
  • anonymous
Okay, I think I get that much now.
anonymous
  • anonymous
I've seen this before, but the notation we use for permutation was maybe backwards.
anonymous
  • anonymous
The number of \(k\) element subsets in \(n\) is \(\binom nk\)
anonymous
  • anonymous
It's faithful if no two permutations produce equivalent sets?
anonymous
  • anonymous
Consider what happens with some concrete examples or concrete permutations.
anonymous
  • anonymous
now if k =1, there exists two permutations \(\sigma\) and \(\tau\) such that \(\sigma(a) \neq \tau(a)\) if we let \(x = \{a\}\) (which is a subset of {1, ..., n} of cardinality 1) then without loss of generality we have \(\sigma \cdot x \neq \tau \cdot x\), so action is trivial if k is one, if k = n, then there is only one subset of {1, ..., n} namely that set itself so every permutation will give you that subset. now I think for 1 < k < n I will have to show that the permutation representation is injective. I think if we let \(\sigma, \tau\) be different permutations again, then without loss of generality \(\sigma(a_1) = x, \tau(a_2) = x\) then we can choose a subset z of cardinality k so that x and \(a_1\) are in the subset, but \(a_2\) isn't (since k < n, we have at least 1 element not in the subset), then \(\sigma \cdot z \neq \tau \cdot z\), since \(\sigma \cdot z\) contains x, and \(\tau \cdot z\) doesn't, so the action is faithful if k
anonymous
  • anonymous
I think this works :D
anonymous
  • anonymous
There only needs to be two distinct permutations which don't result in the same subset?
anonymous
  • anonymous
No, for any two distinct permutations there must be a subset so that \(\sigma \cdot x \neq \tau \cdot x\). In this proof i think i managed to show that we can always construct at least 1 subset of length k which does this
anonymous
  • anonymous
So if I get this right: If the permutations are distinct, there has to be an output where the permutations have a different input to output it. You then find a subset which has the input for one of the permutations but lacks the needed input for the second permutation. Thus there is an output which one has and the other doesn't.
anonymous
  • anonymous
yes
anonymous
  • anonymous
and such a subset always exists, since there is at least 1 element from {1, ..., n} not in the subset
anonymous
  • anonymous
You can ensure an excluded input is excluded, and you can also ensure the necessarily included input gets included?
anonymous
  • anonymous
Yes, since we only consider 2 elements, a1 and x, and for 1 < k < n, k is at least 2 :)
anonymous
  • anonymous
What if a1 and a2 are greater than k, does that matter?
anonymous
  • anonymous
Not really, since k is just how much elements are in the subset
anonymous
  • anonymous
ie if we have k = 2, and two permutations \(\sigma(7) = 8\) and \(\tau(8)=8\) then we choose a subset which doesn't have 7 in it, but contains 8 and any other element, say 5 so we get {5, 8} now even if the 2 permutations map 5 to the same element, 8 still gets mapped to a different one
anonymous
  • anonymous
two permutations such that*
anonymous
  • anonymous
Thanks for the help by the way, trying to explain it to someone else always helps it seems :)

Looking for something else?

Not the answer you are looking for? Search for more explanations.