3. Let S3 act on the set A={(i,j) : 1≤i,j≤3} by σ((i, j)) = (σ(i), σ(j))....

3. Let S3 act on the set A={(i,j) : 1≤i,j≤3} by σ((i, j)) = (σ(i), σ(j)).

(a) Describe the orbits of this action.

(b) Show this is a faithful action, i.e. that the permutation represen- tation φ:S3 →SA =S9

(c) For each σ ∈ S3, find the cycle decomposition of φ(σ) in S9.

Expert Solution

The solution to (a) is obtained by observing that the orbits of any group action partition the set(on which the group acts).

For (b), it suffices to prove that the kernel of the permutation representation is trivial. The proof is not difficult.

For (c), the solution at first enumerates the set A by {1,2,...9}. Then, the action of every group element on A is analysed and finally, the corresponding cycle decompositions of the induced permutations are obtained.

Colby Messinger answered 2 years ago

An inversion in σ ∈ Sn is a pair (i, j) such that i < j...

An inversion in σ ∈ Sn is a pair (i, j) such that i < j and σ(i) > σ(j). Take σ, τ ∈ Sn and take i < j. - Suppose (i, j) is not an inversion in τ. Show that (i, j) is an inversion in στ if and only if (τ(i), τ(j)) is an inversion in σ. - Suppose (i, j) is an inversion in τ. Show that (i, j) is an inversion in στ if and...

Let L = {aibj | i ≠ j; i, j ≥ 0}. Design a CFG and...

Let L = {aibj | i ≠ j; i, j ≥ 0}. Design a CFG and a PDA for this language. Provide a direct design for both CFG and PDA (no conversions from one form to another allowed).

a symmetric group S5 acts on the set X5 = {(i, j) : i, j ∈...

a symmetric group S5 acts on the set X5 = {(i, j) : i, j ∈ {1, 2, 3, 4, 5}}. S5 will also act on this set. Consider the subgroup H = <(1, 2)(3, 4), (1, 3)(2, 4)>≤ S5. (a) Find the orbits of H in this action. Justify your answers. (b) For each orbit find the stabiliser one of its members. Justify your answers. action is this t.(i,j)=(t(i),t(j))

Let X be a set and A a σ-algebra of subsets of X. (a) What does...

Let X be a set and A a σ-algebra of subsets of X. (a) What does it mean for a function f : X → R to be measurable? [2%] (b) If f and g are measurable and α, β ∈ R show that the function αf + βg is also measurable. [7%] (c) (i) Suppose that f is a measurable function. Is |f| measurable? (Give a proof or a counterexample.) [3%] (ii) Suppose that |f| is a measurable function....

Q3 [17% ] Let X be a set and A a σ-algebra of subsets of X....

Q3 [17% ] Let X be a set and A a σ-algebra of subsets of X. (a) What does it mean for a function f : X → R to be measurable? [2%] If f and g are measurable, show that the function f − g is also measurable. [6%] (b) Let (fn) be a sequence of measurable functions. (i) What does it mean to say that (fn) converges pointwise to a function f? [2%] (ii) If (fn) converges pointwise...

3. Let X = {1, 2, 3, 4}. Let F be the set of all functions...

3. Let X = {1, 2, 3, 4}. Let F be the set of all functions from X to X. For any relation R on X, define a relation S on F by: for all f, g ∈ F, f S g if and only if there exists x ∈ X so that f(x)Rg(x). For each of the following statements, prove or disprove the statement. (a) For all relations R on X, if R is reflexive then S is reflexive....

View S3 as a subset of S5 in the obvious way. For σ, τ ∈ S5,...

View S3 as a subset of S5 in the obvious way. For σ, τ ∈ S5, define σ ∼ τ if στ -1 ∈ S3. (a) Prove that ∼ is an equivalence relation on S5. (b) Find the equivalence class of (4, 5). (c) Find the equivalence class of (1, 2, 3, 4, 5). (d) Determine the total number of equivalence classes

Let S be a non-empty set (finite or otherwise) and Σ the group of permutations on...

Let S be a non-empty set (finite or otherwise) and Σ the group of permutations on S. Suppose ∼ is an equivalence relation on S. Prove (a) {ρ ∈ Σ : x ∼ ρ(x) (∀x ∈ S)} is a subgroup of Σ. (b) The elements ρ ∈ Σ for which, for every x and y in S, ρ(x) ∼ ρ(y) if and only if x ∼ y is a subgroup of Σ.

2. Let S be the set of strings over the alphabet Σ = {a, b, c}...

2. Let S be the set of strings over the alphabet Σ = {a, b, c} defined recursively by (1) λ ∈ S and a ∈ S; and (2) if x ∈ S, then bxc ∈ S. Recall that λ denotes the empty string which has no letters and has length 0. List all strings of S which are length at most seven. 3. Prove the following theorem by induction: For every integer n ≥ 1, 1 · 2 +...

for (i=0; i<n; i++) for (j=1; j<n; j=j*2) for (k=0; k<j; k++) ... // Constant...

for (i=0; i<n; i++) for (j=1; j<n; j=j*2) for (k=0; k<j; k++) ... // Constant time operations end for end for end for Analyze the following code and provide a "Big-O" estimate of its running time in terms of n. Explain your analysis. Note: Credit will not be given only for answers - show all your work: (2 points) steps you took to get your answer. (1 point) your answer.

Question