3
$\begingroup$

enter image description here

My Attempt:

(a) $S_n$ is transitive on $\{1,2,\dots,n\}$ and for any $(i,j)\in G_a,~(i,j)i=j$ whence $G_a$ is transitive on $\{1,2,\dots,n\}-\{a\}.$

(b) Without loss of generality let $|A|\ge2.$

  • Case I: $|A|=2$ or $3$ then $|A-\{a\}|=1$ or $2$ whence the blocks became trivial. So $G$ become primitive in this case.

  • Case II: $|A|\ge4$ then $|A-\{a\}|\ge3.$ $A-\{a\}$ can't have a nontrivial block $B$ since for any $i\in \{A-a\}-B$ and $j\in B,$ $(i,j)\in G_a$ and $(i,j)(B)$ is neither equal or disjoint with $B.$ Hence the result.

$D_8$ is not doubly transitive: Label the four vertices as $1,2,3,4$ consequetively. Consider the action of $G_4,$ the stabilizer of $4,$ on $\{1,2,3\}.$ Then $\{1,3\}$ is a nontrivial block since $G_4$ contains only the reflection about the line of symmetry passing through $4$ and the identity.

My Questions:

  1. Is my attempt correct?

  2. Do we define 'blocks' (and hence 'primitive') only when $A$ is finite? (Even though in this exercise I never used finiteness of $A$ this question comes into my mind from their definition as given in Dummit-Foote text:

enter image description here

$\endgroup$
  • $\begingroup$ Here's an equivalent definition of doubly transitive you might find interesting: $G$ is doubly transitive on $A$ if for every $a,b,c,d\in A$ there exists a $g$ in $G$ such that $ga=b$ and $gc=d$. We can use this to extend to notion to $k$-wise transitivity. If a group acts on a set of $n$ elements $n$-wise transitively, then that group contains (isomorphically) $S_n$ as a subgroup. $\endgroup$ – Stella Biderman Mar 26 '17 at 13:56
1
$\begingroup$

(a) The wording here is backwards. One doesn't begin with "for any $(ij)\in G_a$..." Instead, one begins with "for any $i,j\in \{1,\cdots,n\}-\{a\}$" (followed by "$(ij)$ sends $i$ to $j$").

(b) For case II you have a good idea but a few major misunderstandings.

  1. The statement of double transitivity is that given any $i,j\in\{1,\cdots,n\}-\{a\}$, there exists a $\pi\in G_a$ with $\pi(i)=j$. However, there is nothing that says $\pi$ is specifically the transposition $(ij)$, it could be any of the many permutations that send $i$ to $j$. Indeed, if $G$ contained every transposition $(ij)$ then it would be the full symmetric group $S_n$.

  2. If $B$ and $B'$ are blocks of an action of $G$, it's perfectly possible for an element $g\in G$ to send an element of $B$ to an element of $B'$. In particular, in your reasoning it does not follow that $(ij)B$ is not disjoint from $B$. For example, say we have two sets $X$ and $Y$ of the same size. We can consider a group $G$ comprised of permutations of $X\sqcup Y$ with either $f(X)=X$ and $f(Y)=Y$ or else $f(X)=Y$ and $f(Y)=X$. Then $X$ and $Y$ are blocks and there are elements of $G$ that send elements from one block to another.

  3. The exercise is not asking you to argue $G_a$ acts primitively on $\{1,\cdots,n\}-\{a\}$ (indeed, that action may not be primitive). It's asking you to argue $G$ acts on $\{1,\cdots,n\}$ primitively.

So here's how you get your idea to work.

Suppose there is a nontrivial partition. Let $B$ be a block of $\{1,\cdots,n\}$. Then $|B|\ge2$, since if $|B|=1$ it would be a singleton, then applying elements of $G$ gives every other singleton subset (since $G$ acts transitively), telling us this is a trivial partition, a contradiction.

Pick two elements $a,a'\in B$ and another element $b\not\in B$. Then, because $G$ acts doubly transitively, there is a $\pi\in G$ with $\pi(a)=a$ and $\pi(a')=b$. Therefore $\pi(B)$ intersects $B$ nontrivially (since both contain $a$) but is not equal to it (since $\pi(B)$ contains $b$ whereas $B$ doesn't), a contradiction.


Here is some extra commentary to make sense of the notion of primitivity.

First, some elementary set theory. The notions of equivalence relations, set partitions, and onto functions are all more or less equivalent:

  • Given an equivalence relation $\sim$ on a set $X$, we get a set partition $X/\sim$ of $X$ into equivalence classes, and an onto function $X\to X/\sim$ which sends an element to its equivalence class.
  • Given a set partition $\Gamma$ of a set $X$, we can create an equivalence relation $\sim$ defined by $x\sim y$ if and only if $x,y$ are in the same cell $\gamma\in \Gamma$, and we get an onto function $X\to\Gamma$ where an element is sent to the unique cell it resides in.
  • Given an onto function $f:X\to Y$, we get an equivalence relation $\sim$ defined by $x\sim x'$ whenever $f(x)=f(y)$, and $X$ may be partitioned into fibers (preimages of singletons, i.e. the subsets $f^{-1}(y)\subseteq X$ for $y\in Y$).

If you're familiar with the idea of a category, for a given group $G$, there is a category of $G$-sets. If you're not familiar, don't worry about it. Given two $G$-sets $X,Y$, a $G$-set homomorphism is a map $f:X\to Y$ which respects the group action, that is $f(gx)=gf(x)$ for all $x\in X$ and $g\in G$. (One also describes $f$ as equivariant or intertwining.)

A congruence relation $\sim$ on a $G$-set $X$ is an equivalence relation $\sim$ with the added condition that $x\sim y$ implies $gx\sim xy$ for all $x,y\in X$ and $g\in G$. Given any subset $A\subseteq X$, one may apply $g\in G$ to it pointwise, yielding $gA=\{ga:a\in A\}$. A $G$-stable partition of $X$ is a set partition $\Gamma$ with the property that $\gamma\in \Gamma$ implies $g\gamma\in\Gamma$.

Just as in the set-theoretic situation, there is an equivalence between congruence relations on $X$, $G$-stable partitions of $X$, and onto $G$-set homomorphisms out of $X$. Then the primitivity condition on $X$, usually stated in terms of partitions (where the cells are called blocks), can be translated to the statement that $X$ has no nontrivial homomorphic images. Thus, they are the analogue of simple groups in the category of $G$-sets.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.