Proof about two disjoint non-empty sets ## S ## and ## T ##

In summary, we are trying to find a split of the set of numbers from 1 to 22 into two non-empty subsets, S and T, such that the product of any two elements in S is also in S, the product of any two elements in T is also in S, and the product of an element in S and an element in T is in T. After defining S and T as the sets of quadratic residues and non-residues mod 23, it can be shown that these two sets satisfy all the given properties and are the only possible solution.
  • #1
750
199
Homework Statement
The set ## \left \{ 1, 2, ..., 22 \right \} ## is to be split into two disjoint non-empty sets ## S ## and ## T ## in such a way that:
(i) the product (mod ## 23 ##) of any two elements of ## S ## lies in ## S ##;
(ii) the product (mod ## 23 ##) of any two elements of ## T ## lies in ## S ##;
(iii) the product (mod ## 23 ##) of any element of ## S ## and any element of ## T ## lies in ## T ##.
Prove that the only solution is
## S=\left \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \right \} ##,
## T=\left \{ 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22 \right \} ##.
Relevant Equations
If ## A ## and ## B ## are disjoint, then their union ## A\cup B ## contains ## m+k=(p-1)/2 ## integers in the interval ## [1, (p-1)/2] ##.
Proof:

Let ## p ## be an odd prime and ## G=\left \{ 1, 2, ..., p-1 \right \} ## be the set which can be expressed as the
union of two nonempty subsets ## S ## and ## T ## such that ## S\neq T ##.
Observe that ## p-1=22\implies p=23 ##.
Let ## g\in G ##.
Since ## g ## is either an element of ## S ## or ## T ##, it follows that ## g^{2}\in S ##.
This implies that ## S ## contains all quadratic residues modulo ## 23 ##.
Suppose for the sake of contradiction that there exists ## x\in S ## for ## (x|p)=-1 ##.
Note that there exists ## y\in T ##, so we have ## (y|p)=-1 ##.
Thus ## xy\in T ##, but ## (xy|p)=1 ##, which is a contradiction, so ## S ## cannot contain any quadratic non-residues modulo ## 23 ##.
Therefore, the only solution is ## S=\left \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \right \}, T=\left \{ 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22 \right \} ##.
 
Physics news on Phys.org
  • #2
Math100 said:
Homework Statement:: The set ## \left \{ 1, 2, ..., 22 \right \} ## is to be split into two disjoint non-empty sets ## S ## and ## T ## in such a way that:
(i) the product (mod ## 23 ##) of any two elements of ## S ## lies in ## S ##;
(ii) the product (mod ## 23 ##) of any two elements of ## T ## lies in ## S ##;
(iii) the product (mod ## 23 ##) of any element of ## S ## and any element of ## T ## lies in ## T ##.
Prove that the only solution is
## S=\left \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \right \} ##,
## T=\left \{ 5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22 \right \} ##.
Relevant Equations:: If ## A ## and ## B ## are disjoint, then their union ## A\cup B ## contains ...
... ##m+k=22## numbers with ##k\in [1,11]## and ##m\in [11,21].##
Math100 said:
## m+k=(p-1)/2 ## integers in the interval ## [1, (p-1)/2] ##.

Proof:

Let ## p ## be an odd prime and ## G=\left \{ 1, 2, ..., p-1 \right \} ## be the set which can be expressed as the
union of two nonempty subsets ## S ## and ## T ## such that ## S\neq T ##.
Observe that ## p-1=22\implies p=23 ##.
Let ## g\in G ##.
Since ## g ## is either an element of ## S ## or ## T ##, it follows that ## g^{2}\in S ##.
No. This is the wrong way of conclusion. You have to show this after you have defined ##S##.

The idea is as before:

We have a field ##\mathbb{Z}_{23}## with a multiplicative group ##\mathbb{Z}_{23}^*=\{1,2,\ldots,22\}.##
We are looking for a split ##\mathbb{Z}_{23}^*=S \cup T## with ##S,T\neq \emptyset## and ##S\cap T=\emptyset.##
Furthermore, ##S## has to be a multiplicative group: ##S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.##

An assumption would be that ##k=|S|=|T|=m=11## and that ##S## contains all quadratic residues modulo ##23## and ##T## all quadratic non-residues. We already saw in a previous thread that there are equally many quadratic residues as there are quadratic non-residues in ##\mathbb{Z}_{23}^*.##

\begin{align*}
S&:=\{a\in \mathbb{Z}_{23}^*\,|\,a\text{ is a quadratic residue modulo }23\}\\
T&:=\{a\in \mathbb{Z}_{23}^*\,|\,a\text{ is a quadratic non-residue modulo }23\}
\end{align*}
We now have two candidates. Given these two definitions, we must next prove that all properties of ##S## and ##T## are fulfilled.

Math100 said:
This implies that ## S ## contains all quadratic residues modulo ## 23 ##.
See above. The other way around. We set ##S## as this set and have to prove the properties.

##\left(\dfrac{a}{23}\right)=a^{11}\pmod{23}=1## for quadratic residues:
\begin{matrix}
1^{11}\equiv 1\pmod{23}\, & \,2^{11}\equiv 1 \equiv \pmod{23}\, & \,3^{11}\equiv 1\pmod{23}\, & \,4^{11}\equiv 1\pmod{23}\\
6^{11}\equiv 1\pmod{23}\, & \,8^{11}\equiv 1 \equiv \pmod{23}\, & \,9^{11}\equiv 1\pmod{23}\, & \,12^{11}\equiv 1\pmod{23}\\
13^{11}\equiv 1\pmod{23}\, & \,16^{11}\equiv 1 \equiv \pmod{23}\, & \,18^{11}\equiv 1\pmod{23}\, &
\end{matrix}
Thus
\begin{align*}
S&=\left \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \right \}\\
T&=\mathbb{Z}_{23}^*-S.
\end{align*}
We also have ##S,T\neq \emptyset\, , \, S\cap T =\emptyset\, , \,S\cup T =\mathbb{Z}_{23}^*.## From
$$
\left(\dfrac{a}{23}\right)\cdot \left(\dfrac{b}{23}\right)=\left(\dfrac{ab}{23}\right)\, , \,\left(\dfrac{a}{23}\right)=1\,(a\in S)\, , \,\left(\dfrac{a}{23}\right)=-1\,(a\in T)
$$
we get ##S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.##

We finally need to show that this is the only possible decomposition of ##\mathbb{Z}_{23}^*## with the given properties. For that matter, we assume a second decomposition
$$
\mathbb{Z}_{23}^*=A\cup B\, , \,A \cap B=\emptyset\neq A,B\, , \,A\cdot A,B\cdot B\subseteq A,A\cdot B\subseteq B
$$
and show that ##A=S.## (##B=T## follows automatically.)

Can you prove these two statements: ##A=S## and "automatically"?
 
  • Like
Likes WWGD
  • #3
fresh_42 said:
... ##m+k=22## numbers with ##k\in [1,11]## and ##m\in [11,21].##

No. This is the wrong way of conclusion. You have to show this after you have defined ##S##.

The idea is as before:

We have a field ##\mathbb{Z}_{23}## with a multiplicative group ##\mathbb{Z}_{23}^*=\{1,2,\ldots,22\}.##
We are looking for a split ##\mathbb{Z}_{23}^*=S \cup T## with ##S,T\neq \emptyset## and ##S\cap T=\emptyset.##
Furthermore, ##S## has to be a multiplicative group: ##S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.##

An assumption would be that ##k=|S|=|T|=m=11## and that ##S## contains all quadratic residues modulo ##23## and ##T## all quadratic non-residues. We already saw in a previous thread that there are equally many quadratic residues as there are quadratic non-residues in ##\mathbb{Z}_{23}^*.##

\begin{align*}
S&:=\{a\in \mathbb{Z}_{23}^*\,|\,a\text{ is a quadratic residue modulo }23\}\\
T&:=\{a\in \mathbb{Z}_{23}^*\,|\,a\text{ is a quadratic non-residue modulo }23\}
\end{align*}
We now have two candidates. Given these two definitions, we must next prove that all properties of ##S## and ##T## are fulfilled.See above. The other way around. We set ##S## as this set and have to prove the properties.

##\left(\dfrac{a}{23}\right)=a^{11}\pmod{23}=1## for quadratic residues:
\begin{matrix}
1^{11}\equiv 1\pmod{23}\, & \,2^{11}\equiv 1 \equiv \pmod{23}\, & \,3^{11}\equiv 1\pmod{23}\, & \,4^{11}\equiv 1\pmod{23}\\
6^{11}\equiv 1\pmod{23}\, & \,8^{11}\equiv 1 \equiv \pmod{23}\, & \,9^{11}\equiv 1\pmod{23}\, & \,12^{11}\equiv 1\pmod{23}\\
13^{11}\equiv 1\pmod{23}\, & \,16^{11}\equiv 1 \equiv \pmod{23}\, & \,18^{11}\equiv 1\pmod{23}\, &
\end{matrix}
Thus
\begin{align*}
S&=\left \{ 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18 \right \}\\
T&=\mathbb{Z}_{23}^*-S.
\end{align*}
We also have ##S,T\neq \emptyset\, , \, S\cap T =\emptyset\, , \,S\cup T =\mathbb{Z}_{23}^*.## From
$$
\left(\dfrac{a}{23}\right)\cdot \left(\dfrac{b}{23}\right)=\left(\dfrac{ab}{23}\right)\, , \,\left(\dfrac{a}{23}\right)=1\,(a\in S)\, , \,\left(\dfrac{a}{23}\right)=-1\,(a\in T)
$$
we get ##S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.##

We finally need to show that this is the only possible decomposition of ##\mathbb{Z}_{23}^*## with the given properties. For that matter, we assume a second decomposition
$$
\mathbb{Z}_{23}^*=A\cup B\, , \,A \cap B=\emptyset\neq A,B\, , \,A\cdot A,B\cdot B\subseteq A,A\cdot B\subseteq B
$$
and show that ##A=S.## (##B=T## follows automatically.)

Can you prove these two statements: ##A=S## and "automatically"?
Aren't the two statements of ## A=S ## and ## B=T ## ("automatically") the same as proving what's already proven from the first decomposition: ##S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.##? What's different in the second decomposition from the first decomposition? Instead of ## S ## and ## T ##, we have ## A ## and ## B ## now. Or is there another way to prove this?
 
  • #4
Math100 said:
Aren't the two statements of ## A=S ## and ## B=T ## ("automatically") the same as proving what's already proven from the first decomposition: ##S\cdot S\subseteq S\, , \,T\cdot T \subseteq S\, , \,T\cdot S\subseteq T.##? What's different in the second decomposition from the first decomposition? Instead of ## S ## and ## T ##, we have ## A ## and ## B ## now. Or is there another way to prove this?
If ##A=S## then ##B=\mathbb{Z}_{23}^*-A=\mathbb{Z}_{23}^*-S=T.##

But ##A=S## is not automatically the case. E.g. ##A## could be all even numbers, and ##B## all odd numbers. We have to rule out that such a decomposition fulfills the properties. And we have to rule it out for any decomposition with the given properties.

The proof begins with:

Assume ##G:=\mathbb{Z}_{23}^* =A\cup B## with ##A\cap B =\emptyset## and ##A,B\neq \emptyset## and ##A\cdot A \subseteq A\, , \,A\cdot B \subseteq B\, , \,B\cdot B\subseteq A.##

Since ##A\subseteq G=S\cup T## we have ##A=S## in which case we are done, ##A\subset S## or ##A\not\subset S.##

Note that all elements of ##G## are invertible modulo ##23.## This means that for every ##g\in G## and every non-empty, proper subset ##M\subset G## holds ##g\cdot M \subset G,## i.e. ##g\cdot M## is also a non-empty proper subset of ##G.## In other words: left-multiplication in a (multiplicative) group is a bijection.

If ##A\subset S ## then ##B\not\subset T.## There is thus a ##b\in B## that is not in ##T,## i.e. it is contained in ##S.## Thus ##b\cdot B \subseteq A \subseteq S## and ## b\cdot A\subset S\cdot S\subseteq S.## So ##b\cdot G\subseteq S## and ##G\subseteq b^{-1}\cdot S \subset G## which is a contradiction. This disproves ##A\subseteq S.##

Assume ##A\not\subset S.## Then there is a ##a\in A\cap T.## If ##A\subset T## then ##A\cdot A\subseteq A\subset T## and ##A\cdot A\subseteq T\cdot T\subseteq S## which is not possible. Hence ##A\cap T\neq \emptyset \neq A\cap S.## But if ##A## intersects both, ##S## and ##T## non-trivially, so does ##B.##

Hence we must rule out the following situation:
1669081623418.png


Can you do this?
 
  • #5
fresh_42 said:
If ##A=S## then ##B=\mathbb{Z}_{23}^*-A=\mathbb{Z}_{23}^*-S=T.##

But ##A=S## is not automatically the case. E.g. ##A## could be all even numbers, and ##B## all odd numbers. We have to rule out that such a decomposition fulfills the properties. And we have to rule it out for any decomposition with the given properties.

The proof begins with:

Assume ##G:=\mathbb{Z}_{23}^* =A\cup B## with ##A\cap B =\emptyset## and ##A,B\neq \emptyset## and ##A\cdot A \subseteq A\, , \,A\cdot B \subseteq B\, , \,B\cdot B\subseteq A.##

Since ##A\subseteq G=S\cup T## we have ##A=S## in which case we are done, ##A\subset S## or ##A\not\subset S.##

Note that all elements of ##G## are invertible modulo ##23.## This means that for every ##g\in G## and every non-empty, proper subset ##M\subset G## holds ##g\cdot M \subset G,## i.e. ##g\cdot M## is also a non-empty proper subset of ##G.## In other words: left-multiplication in a (multiplicative) group is a bijection.

If ##A\subset S ## then ##B\not\subset T.## There is thus a ##b\in B## that is not in ##T,## i.e. it is contained in ##S.## Thus ##b\cdot B \subseteq A \subseteq S## and ## b\cdot A\subset S\cdot S\subseteq S.## So ##b\cdot G\subseteq S## and ##G\subseteq b^{-1}\cdot S \subset G## which is a contradiction. This disproves ##A\subseteq S.##

Assume ##A\not\subset S.## Then there is a ##a\in A\cap T.## If ##A\subset T## then ##A\cdot A\subseteq A\subset T## and ##A\cdot A\subseteq T\cdot T\subseteq S## which is not possible. Hence ##A\cap T\neq \emptyset \neq A\cap S.## But if ##A## intersects both, ##S## and ##T## non-trivially, so does ##B.##

Hence we must rule out the following situation:
View attachment 317547

Can you do this?
So to rule out the following situation in which you listed above, one example would be ## S\cap B=S ## if ## B=S ##?
 
  • #6
##S=A\, , \,S=B\, , \,T=A\, , \,T=B## are already ruled out. We must basically show that the principal character and the Legendre-symbol are the only two characters (multiplicative functions) with ##\chi^2=1.##

The reason is that ##\mathbb{Z}_{23}^*## has ##22=2 \cdot 11## elements and there is only one normal subgroup of order two. That means such a case as in the picture cannot occur. But why exactly?
 
  • #7
fresh_42 said:
##S=A\, , \,S=B\, , \,T=A\, , \,T=B## are already ruled out. We must basically show that the principal character and the Legendre-symbol are the only two characters (multiplicative functions) with ##\chi^2=1.##

The reason is that ##\mathbb{Z}_{23}^*## has ##22=2 \cdot 11## elements and there is only one normal subgroup of order two. That means such a case as in the picture cannot occur. But why exactly?
I still don't really understand. Can you please tell me why?
 
  • #8
I'm not sure whether the tools I would use are the tools you are expected to use. My plan would be to define
$$
\chi\, : \,\mathbb{Z}_{23}^*=:G \longrightarrow \mathbb{C}^*=\mathbb{C}-\{0\}\; , \;\chi(g)=\begin{cases}1&\text{ if }g\in A\\-1&\text{ if }g\in B\end{cases}
$$
Then
\begin{align*}
\chi(1)&=\chi(1\cdot 1)=\chi(1)\cdot \chi(1)\Longrightarrow \chi(1)=1\Longrightarrow 1\in A\\
\chi(gAg^{-1})&=\chi(g)\chi(A)\chi(g^{-1})=\chi(g)\cdot 1\cdot\chi(g^{-1})=\chi(g\cdot g^{-1})=\chi(1)=1
\end{align*}
This shows that ##A=\operatorname{ker}\chi \trianglelefteq G## is a normal subgroup. The order of any subgroup divides the order of the group. We have only two such prime divisors: ##|G|=22=2\cdot 11.## Hence ##A## has either ##2## or ##11## elements. Now ##B\neq \emptyset## so there is a ##b\in B-\{1\}## such that ##b\cdot A \cup A=G.## The mapping ##a\longmapsto b\cdot a## is a bijection since ##b## is invertible. So ##bA## and ##A## must have equally many elements. Thus, ##|A|=11.##

The exact same considerations can be made for the Legendre symbol. So ##1\in S.## Thus we have an element ##1\in S\,\cap \,A.## So we have two normal subgroups ##A\trianglelefteq G## and ##S\trianglelefteq G## with equally many elements, namely ##11##, that also share one element, namely ##1\in G.## But there is only one cyclic subgroup of ##G## with ##11## elements, ##S=\mathbb{Z}_{11}.## So ##S=A## and ##T=B.##

If you aren't familiar with this basic group theory, then you have to find another way to make sure that there can't be two different partitions of ##G=S\,\cup\,T=A\,\cup \,B.##

My idea: Look at ##3##. Then either ##3\in A## or ##3\in B.## Rule out the latter and show that all powers of ##3## already generate ##S.##
 
  • #9
Forget that complicated stuff above; though it brought me the easier solution.

We have shown everything but uniqueness. We have ##\mathbb{Z}_{23}^*=S\,\cup\,T## partitioned in quadratic residues ##S## and quadratic non-residues ##T##. Now, let us assume that there is another partition ##\mathbb{Z}_{23}^*=A\,\cup\,B## such that ##A\cdot A ,B\cdot B \subseteq A, A\cdot B\subseteq B.## Then ##1=1\cdot 1\in A## and ##A\cdot A\subseteq A.## Moreover, if ##b\in B## then ##b\cdot A\subseteq B## and ##A\,\cup\,B= \mathbb{Z}_{23}^*## because ##A## and ##b\cdot A## have equally many elements, i.e. ##B=b\cdot A.## To show that ##A \trianglelefteq \mathbb{Z}_{23}^* ## is a subgroup, it remains to show that inverses of elements of ##A## are in ##A## again. Suppose ##a^{-1}\in b\cdot A,## i.e. ##A\ni 1=a^{-1}\cdot a=b\cdot a'\cdot a \in B## which is impossible since ##A## and ##B## are disjoint.
\begin{matrix}
3\cdot 3\equiv 9\pmod{23}&3\cdot 9\equiv 4\pmod{23}&3\cdot 4\equiv 12\pmod{23}&3\cdot 12\equiv 13\pmod{23}\\
3\cdot 13\equiv 16\pmod{23}&3\cdot 16\equiv 2\pmod{23}&3\cdot 2\equiv 6\pmod{23}&3\cdot 6\equiv 18\pmod{23}\\
3\cdot 18\equiv 8\pmod{23}&3\cdot 8\equiv 1\pmod{23}
\end{matrix}
If ##3\in B## then ##3^{11}=1\in A\,\cup\,B## which is impossible. So ##\langle 3 \rangle \cong \mathbb{Z}_{11}\subseteq A\trianglelefteq \mathbb{Z}_{23}^*## creates a cyclic subgroup with eleven elements: ##\langle 3 \rangle=A=\{1,2,3,4,6,8,9,12,13,16,18\}=S.##

Sorry, the idea was finally shorter than the solution with all the technical details:
  • ##1\in A##
  • ##B=b\cdot A##
  • ## A^{-1}\subseteq A##
  • ##A\trianglelefteq \mathbb{Z}_{23}^*## is a subgroup.
  • ##\mathbb{Z}_{23}^*=A \,\cup\,B##
  • ##3\in A##
  • ##\langle 3 \rangle = A = S##
 
Last edited:
  • Like
Likes Math100
  • #10
fresh_42 said:
Forget that complicated stuff above; though it brought me the easier solution.

We have shown everything but uniqueness. We have ##\mathbb{Z}_{23}^*=S\,\cup\,T## partitioned in quadratic residues ##S## and quadratic non-residues ##T##. Now, let us assume that there is another partition ##\mathbb{Z}_{23}^*=A\,\cup\,B## such that ##A\cdot A ,B\cdot B \subseteq A, A\cdot B\subseteq B.## Then ##1=1\cdot 1\in A## and ##A\cdot A\subseteq A.## Moreover, if ##b\in B## then ##b\cdot A\subseteq B## and ##A\,\cup\,B= \mathbb{Z}_{23}^*## because ##A## and ##b\cdot A## have equally many elements, i.e. ##B=b\cdot A.## To show that ##A \trianglelefteq \mathbb{Z}_{23}^* ## is a subgroup, it remains to show that inverses of elements of ##A## are in ##A## again. Suppose ##a^{-1}\in b\cdot A,## i.e. ##A\ni 1=a^{-1}\cdot a=b\cdot a'\cdot a \in B## which is impossible since ##A## and ##B## are disjoint.
\begin{matrix}
3\cdot 3\equiv 9\pmod{23}&3\cdot 9\equiv 4\pmod{23}&3\cdot 4\equiv 12\pmod{23}&3\cdot 12\equiv 13\pmod{23}\\
3\cdot 13\equiv 16\pmod{23}&3\cdot 16\equiv 2\pmod{23}&3\cdot 2\equiv 6\pmod{23}&3\cdot 6\equiv 18\pmod{23}\\
3\cdot 18\equiv 8\pmod{23}&3\cdot 8\equiv 1\pmod{23}
\end{matrix}
If ##3\in B## then ##3^{11}=1\in A\,\cup\,B## which is impossible. So ##\langle 3 \rangle \cong \mathbb{Z}_{11}\subseteq A\trianglelefteq \mathbb{Z}_{23}^*## creates a cyclic subgroup with eleven elements: ##\langle 3 \rangle=A=\{1,2,3,4,6,8,9,12,13,16,18\}=S.##

Sorry, the idea was finally shorter than the solution with all the technical details:
  • ##1\in A##
  • ##B=b\cdot A##
  • ## A^{-1}\subseteq A##
  • ##A\trianglelefteq \mathbb{Z}_{23}^*## is a subgroup.
  • ##\mathbb{Z}_{23}^*=A \,\cup\,B##
  • ##3\in A##
  • ##\langle 3 \rangle = A = S##
Don't say sorry, it's okay. I am the one who should apologize, because many stuffs above are things I never learned, I have no knowledge in group theory. So these are all new to me. For example, ##A\trianglelefteq \mathbb{Z}_{23}^*## is a subgroup, I've never seen ## \trianglelefteq ## before. But it's always beneficial to know and learn the new stuffs.
 
Last edited:
  • #11
There seems to be too, a Combinatorial side to this. This may be call a matching or an SDR ( System of Distinct Representatives) .
 
  • #12
Math100 said:
Don't say sorry, it's okay. I am the one who should apologize, because many stuffs above are things I never learned, I have no knowledge in group theory. So these are all new to me. For example, ##A\trianglelefteq \mathbb{Z}_{23}^*## is a subgroup, I've never seen ## \trianglelefteq ## before. But it's always beneficial to know and learn the new stuffs.
The point with the group is the following. I have observed that ##S## is equal to the set of all powers of, say ##3## modulo ##23.## If we have a second partition ##G=A\,\cup\,B## then ##3## is either an element of ##A## or an element of ##B##. The powers of ##3## could hop between ##A## and ##B## all the time.

We show, that ##A## is a group, i.e. it contains the neutral element ##1##, is closed under multiplication, i.e. ##A\cdot A \subseteq A,## a fact that is given by the properties of the partition and is closed under inversion ##A^{-1}\subseteq A## which has to be shown.

Then we show that ##3\in A##. But now we know that ##A## is a group, so all powers of its elements are also within ##A,## no hopping between ##A## and ##B## allowed for powers of elements of ##A##. Hence ##\{3^n\pmod{23}\,|\,n\in \mathbb{N}\} = S \subseteq A.##

I think I have forgotten the final part. We know that ##S\subseteq A## but we need to show ##A\subseteq S## also. Assume that there is an element ##a\in A## which is not in ##S.## Then ##a\in A\,\cup\,T## and ##a\cdot S\subseteq T.## But ##a\cdot S## and ##T## have both ##11## elements, so ##a\cdot S=T.## Thus
$$
G=S\,\cup\,T=S\,\cup\,a\cdot S\subseteq A\,\cup\,a\cdot A\subseteq A
$$
which contradicts ##B\neq \emptyset.## There is therefore no element ##a\in A-S,## i.e. ##A=S.##
 
  • Informative
Likes Math100

1. What is the definition of disjoint sets?

Disjoint sets are sets that have no elements in common. This means that the intersection of the two sets is an empty set.

2. How do you prove that two sets are disjoint?

To prove that two sets are disjoint, you can show that their intersection is an empty set. This can be done by listing out the elements of each set and showing that there are no common elements.

3. Can two non-empty sets be disjoint?

No, two non-empty sets cannot be disjoint. Disjoint sets, by definition, have no elements in common. Therefore, if two sets are non-empty, they must have at least one element in common.

4. What is the importance of proving that two sets are disjoint?

Proving that two sets are disjoint is important in many areas of mathematics, including set theory, topology, and probability. It allows us to make conclusions about the relationship between the two sets and can help us solve problems and make predictions.

5. Can two sets be both disjoint and overlapping?

No, two sets cannot be both disjoint and overlapping. Disjoint sets have no elements in common, while overlapping sets have at least one element in common. These two concepts are mutually exclusive and cannot occur simultaneously.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
14
Views
988
  • Precalculus Mathematics Homework Help
Replies
7
Views
727
  • Precalculus Mathematics Homework Help
Replies
14
Views
847
  • Precalculus Mathematics Homework Help
Replies
3
Views
863
  • Calculus and Beyond Homework Help
Replies
1
Views
511
  • Calculus and Beyond Homework Help
Replies
3
Views
592
  • Precalculus Mathematics Homework Help
Replies
1
Views
912
  • Calculus and Beyond Homework Help
Replies
1
Views
412
  • Calculus and Beyond Homework Help
Replies
1
Views
408
Replies
9
Views
243
Back
Top