So I'm very, very new to group theory (I've know about it's existence for about a week now) and I'm a bit confused. I thought that for every set $S$, $$(\{x\in\mathcal{P}(S)\ |\ |x|\leq0.5|S|\},\cup)$$ Is a group. So I checked the axioms.

It is obvious that: $$\forall A,B\subset S\ :\ A\cup B\subset S$$ with $|A\cup B|\leq |A|$ and $|A\cup B|\leq |B|$, but $|A\cup B|\geq 0$. So we have closure.

Now: $$\forall S\ :\ \emptyset\in\mathcal{P}(S)\wedge|\emptyset|=0\leq0.5|\mathcal{P}(S)|$$ $$\forall S\ :\ S\cup\emptyset=S$$ So $\emptyset$ is our identity element.

We know that the union is associative.

$S$ contains $|S|$ unique elements, but all elements of $\{x\in\mathcal{P}(S)\ |\ |x|\leq0.5|S|\}$ contains at most $0.5|S|$ unique elements, which means that: $$\forall a \in\{x\in\mathcal{P}(S)\ |\ |x|\leq0.5|S|\}\ :\ (\exists b \in \{x\in\mathcal{P}(S)\ |\ |x|\leq0.5|S|\}\ :\ a\cup b = \emptyset)$$ Hence, we have inverses.

All axioms are checked, so $(\{x\in\mathcal{P}(S)\ |\ |x|\leq0.5|S|\},\cup)$ should be a group for every set $S$.

Now here's my problem; the cancellation law doesn't work and elements have multiple different inverses. It looks like the proofs of both the cancellation law and the unique inverse law are independent of the operation and only need the four axioms.

So where did I go wrong?

  • $\begingroup$ Every set $S$? I think you're dealing with rather specific $S$'s here. (Subsets of the reals, perhaps?) $\endgroup$ – Justin Benfield Aug 2 '16 at 13:30
  • 1
    $\begingroup$ It's not a group, but you can use symmetric difference (union minus intersection) as a group operation. $\endgroup$ – Mark Aug 2 '16 at 13:30
  • $\begingroup$ @JustinBenfield: The operation $|\cdot|$ is being applied to sets, not their elements. $\endgroup$ – joriki Aug 2 '16 at 13:31
  • $\begingroup$ @joriki Then how does $|x|\leq 0.5|S|$ make sense? Is my thinking correct that $|\cdot |$ applied to sets means cardinality? What about $x$? $\endgroup$ – Justin Benfield Aug 2 '16 at 13:34
  • $\begingroup$ @JustinBenfield: $x$ is an element of the power set $\mathcal P(S)$, so it's a set to which the cardinality operator applies. $\endgroup$ – joriki Aug 2 '16 at 13:36

Let $G := \{A \subset S : 2|A| \leq |S|\}$ be the set you're talking about.

$\cup$ is union, and $\cap$ is intersection. You seem to have mixed these up a lot:

  • Both $\cup$ and $\cap$ are associative on $\mathcal{P}(S)$, however only $\cap$ is actually defined on $G$. $\cup$ is not a valid operation on $G$.

  • $\emptyset$ is the neutral element of $\cup$, but not $\cap$.

  • Clearly for any $A \in G$ there exists $B \in G$ such that $A \cap B = \emptyset$. However this is irrelevant since $\emptyset$ is not the neutral element of $\cap$.


You don’t have closure. Let $G=\left\{x\in\wp(S):|x|\le\frac12|S|\right\}$, and let $a,b\in G$. It’s not enough that $a\cup b\subseteq S$: you need to have $a\cup b\in G$. If $S=\{0,1\}$, $a=\{0\}$, and $b=\{1\}$, then $a\cup b=\{0,1\}\notin G$.

You are correct that $\varnothing$ is an identity element for union.

You don’t have inverses: if $\varnothing\ne x\in G$, there is no $y\in G$ such that $x\cup y=\varnothing$: $x\cup y$ always contains every element of $S$ that is already in $x$.

Added: By the way, you can use $\triangle$ (symmetric difference): for any set $S$, $\langle\wp(S),\triangle\rangle$ is an Abelian group in which every element except $\varnothing$, the identity, has order $2$.

  • 1
    $\begingroup$ I see. Thank you for your explanation. I am confusing the union with the intersection in my closure proof. $\endgroup$ – Mastrem Aug 2 '16 at 13:32
  • $\begingroup$ @Mastrem: You’re welcome. $\endgroup$ – Brian M. Scott Aug 2 '16 at 13:34

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.