MHB The axioms of a vector space are satisfied

[mathmari]

Hey!

We consider the $\mathbb{F}_2$-vector space $(2^M, +, \cap)$, where $M$ is non-empty set and $+ : 2^M\times 2^M \rightarrow 2^M: (X,Y)\mapsto (X\cup Y)\setminus (X\cap Y)$.

I want to show that $(2^M, +, \cap )$ for $\mathbb{K}=\{\emptyset , M\}$ satisfies the axioms of a vector space. I have done the following:

• Associativity: $(X+Y)+Z=[(X\cup Y)\setminus (X\cap Y)]+Z=([(X\cup Y)\setminus (X\cap Y)]\cup Z)\setminus ([(X\cup Y)\setminus (X\cap Y)]\cap Z)$
  
  Is this correct so far? (Wondering)
  
  $ $
  
• Existence of neutral element: The empty set.
  
• Existence of inverse element: The inverse of an element is the set itself.
  
• Commutativity: We have that $X+Y=(X\cup Y)\setminus (X\cap Y)=(Y\cup X)\setminus (Y\cap X)=Y+X$.
  

Are the last 3 ones correct? (Wondering) Then the next axioms that we have to show are multiplicative axioms (with the intersection). Let $k, k_1,k_2\in \mathbb{K}$.

• \begin{align*}(X+Y)\cap k&=[(X\cup Y)\setminus (X\cap Y)]\cap k=[(X\cup Y)\cap k]\setminus [(X\cap Y)\cap k]\\ & =[(X\cap k)\cup (Y\cap k)]\setminus [(X\cap k)\cap (Y\cap k)] =X\cap k+Y\cap k\end{align*} here we use that $(A\cap B)\cap C)=(A\cap C)\cap (B\cap C)$, right? (Wondering)
  
  $ $
  
• $X\cap (k_1+k_1)=X\cap [(k_1\cup k_2)\setminus (k_1\cap k_2)]=[X\cap (k_1\cup k_2)]\setminus [X\cap (k_1\cap k_2)]=[(X\cap k_1)\cup (X\cap k_2)]\setminus [(X\cap k_1)\cap (X\cap k_2)]=X\cap k_1+X\cap k_2$.
  
  Is this correct? (Wondering)
  
  $ $
  
• $X\cap (k_1\cap k_2)=(X\cap k_1)\cap k_2$. So it is satisfied. (Or do we not get that equality immediately? (Wondering) )
  
  $ $
  
• $k\cap 1=k$ where $1$ is in this case $2^M$, or not? (Wondering)

 

[I like Serena]

Hey!

We consider the $\mathbb{F}_2$-vector space $(2^M, +, \cap)$, where $M$ is non-empty set and $+ : 2^M\times 2^M \rightarrow 2^M: (X,Y)\mapsto (X\cup Y)\setminus (X\cap Y)$.

I want to show that $(2^M, +, \cap )$ for $\mathbb{K}=\{\emptyset , M\}$ satisfies the axioms of a vector space. I have done the following:

• Associativity: $(X+Y)+Z=[(X\cup Y)\setminus (X\cap Y)]+Z=([(X\cup Y)\setminus (X\cap Y)]\cup Z)\setminus ([(X\cup Y)\setminus (X\cap Y)]\cap Z)$
  
  Is this correct so far? (Wondering)
  
  $ $
  
• Existence of neutral element: The empty set.
  
• Existence of inverse element: The inverse of an element is the set itself.
  
• Commutativity: We have that $X+Y=(X\cup Y)\setminus (X\cap Y)=(Y\cup X)\setminus (Y\cap X)=Y+X$.
  

Are the last 3 ones correct? (Wondering) Then the next axioms that we have to show are multiplicative axioms (with the intersection). Let $k, k_1,k_2\in \mathbb{K}$.

• \begin{align*}(X+Y)\cap k&=[(X\cup Y)\setminus (X\cap Y)]\cap k=[(X\cup Y)\cap k]\setminus [(X\cap Y)\cap k]\\ & =[(X\cap k)\cup (Y\cap k)]\setminus [(X\cap k)\cap (Y\cap k)] =X\cap k+Y\cap k\end{align*} here we use that $(A\cap B)\cap C)=(A\cap C)\cap (B\cap C)$, right? (Wondering)
  
  $ $
  
• $X\cap (k_1+k_1)=X\cap [(k_1\cup k_2)\setminus (k_1\cap k_2)]=[X\cap (k_1\cup k_2)]\setminus [X\cap (k_1\cap k_2)]=[(X\cap k_1)\cup (X\cap k_2)]\setminus [(X\cap k_1)\cap (X\cap k_2)]=X\cap k_1+X\cap k_2$.
  
  Is this correct? (Wondering)
  
  $ $
  
• $X\cap (k_1\cap k_2)=(X\cap k_1)\cap k_2$. So it is satisfied. (Or do we not get that equality immediately? (Wondering) )
  
  $ $

Hey mathmari!

It is all correct so far. (Nod)

• $k\cap 1=k$ where $1$ is in this case $2^M$, or not?

Shouldn't that be $X \cap 1=X$ where $1$ is the multiplicative unity of $\mathbb K$?
What is the multiplicative unity of $\mathbb K$? (Wondering)

Btw, can we assume that $\mathbb K \simeq \mathbb F_2$, or do we need to prove that as well? (Wondering)

 

[mathmari]

It is all correct so far. (Nod)

Ah ok!

For the associativity:
\begin{align*}(X+Y)+Z&=[(X\cup Y)\setminus (X\cap Y)]+Z\\ & =([(X\cup Y)\setminus (X\cap Y)]\cup Z)\setminus ([(X\cup Y)\setminus (X\cap Y)]\cap Z) \end{align*}
\begin{align*}X+(Y+Z)&=X+ [(Y\cup Z)\setminus (Y\cap Z)] \\ & = (X\cup [(Y\cup Z)\setminus (Y\cap Z)])\setminus (X\cap [(Y\cup Z)\setminus (Y\cap Z)])\end{align*}
How can we see that these two are equal? Which rules do we have to use here? I got stuck right now. (Wondering)

Shouldn't that be $X \cap 1=X$ where $1$ is the multiplicative unity of $\mathbb K$?
What is the multiplicative unity of $\mathbb K$? (Wondering)

Oh yes you are right! The elements of $\mathbb{K}$ are $\emptyset$ and $M$, so the multiplicative unity of $\mathbb K$ is $M$ since $X\cap M=X=M\cap X$, right? (Wondering)

Btw, can we assume that $\mathbb K \simeq \mathbb F_2$, or do we need to prove that as well? (Wondering)

Why does this hold? (Wondering)

 

[I like Serena]

Ah ok!

For the associativity:
\begin{align*}(X+Y)+Z&=[(X\cup Y)\setminus (X\cap Y)]+Z\\ & =([(X\cup Y)\setminus (X\cap Y)]\cup Z)\setminus ([(X\cup Y)\setminus (X\cap Y)]\cap Z) \end{align*}
\begin{align*}X+(Y+Z)&=X+ [(Y\cup Z)\setminus (Y\cap Z)] \\ & = (X\cup [(Y\cup Z)\setminus (Y\cap Z)])\setminus (X\cap [(Y\cup Z)\setminus (Y\cap Z)])\end{align*}
How can we see that these two are equal? Which rules do we have to use here? I got stuck right now.

We can write $A\setminus B = A\cap B^C$ can't we? (Thinking)

Oh yes you are right! The elements of $\mathbb{K}$ are $\emptyset$ and $M$, so the multiplicative unity of $\mathbb K$ is $M$ since $X\cap M=X=M\cap X$, right?

(Nod)

Why does this hold? (Wondering)

Well, the problem statement says that we have an $\mathbb F_2$-vector space, doesn't it?
That means that our scalars must come from the field $\mathbb F_2$.
And then it said that we were looking at a vector space for $\mathbb K=\{\varnothing, M\}$.
That means that $\mathbb K$ must be a field, mustn't it?
And it should be isomorphic to $\mathbb F_2$ for the problem statement to be consistent.

So I think we should prove that $\mathbb K$ is a field with the given addition and multiplication.
Since there is only one field with 2 elements ($\mathbb F_2$), it should suffice if we can identify $0$ and $1$, and verify that $\mathbb K$ has the same addition table and multiplication table as $\mathbb F_2$. (Nerd)

 

[mathmari]

We can write $A\setminus B = A\cap B^C$ can't we? (Thinking)

So, we get the following:
\begin{align*}(X+Y)+Z&=[(X\cup Y)\setminus (X\cap Y)]+Z\\ & =([(X\cup Y)\setminus (X\cap Y)]\cup Z)\setminus ([(X\cup Y)\setminus (X\cap Y)]\cap Z) \\ & = ([(X\cup Y)\cap (X\cap Y)^c]\cup Z)\setminus ([(X\cup Y)\cap (X\cap Y)^c]\cap Z) \\ & = ([(X\cup Y)\cup Z]\cap [(X\cap Y)^c\cup Z)\setminus ((X\cup Y)\cap (X\cap Y)^c\cap Z) \\ & = ([X\cup Y\cup Z]\cap [(X\cap Y)^c\cup Z)\setminus ((X\cup Y)\cap (X\cap Y)^c\cap Z) \end{align*}
\begin{align*}X+(Y+Z)&=X+ [(Y\cup Z)\setminus (Y\cap Z)] \\ & = (X\cup [(Y\cup Z)\setminus (Y\cap Z)])\setminus (X\cap [(Y\cup Z)\setminus (Y\cap Z)]) \\ & = (X\cup [(Y\cup Z)\cap (Y\cap Z)^c])\setminus (X\cap [(Y\cup Z)\cap (Y\cap Z)^c]) \\ & = ( [X\cup Y\cup Z]\cap [X\cup(Y\cap Z)^c])\setminus (X\cap (Y\cup Z)\cap (Y\cap Z)^c) \end{align*}
right? How could we continue? (Wondering)

Well, the problem statement says that we have an $\mathbb F_2$-vector space, doesn't it?
That means that our scalars must come from the field $\mathbb F_2$.
And then it said that we were looking at a vector space for $\mathbb K=\{\varnothing, M\}$.
That means that $\mathbb K$ must be a field, mustn't it?
And it should be isomorphic to $\mathbb F_2$ for the problem statement to be consistent.

So I think we should prove that $\mathbb K$ is a field with the given addition and multiplication.
Since there is only one field with 2 elements ($\mathbb F_2$), it should suffice if we can identify $0$ and $1$, and verify that $\mathbb K$ has the same addition table and multiplication table as $\mathbb F_2$. (Nerd)

Ah ok! (Nerd)

 

[I like Serena]

So, we get the following:
\begin{align*}(X+Y)+Z&=[(X\cup Y)\setminus (X\cap Y)]+Z\\ & =([(X\cup Y)\setminus (X\cap Y)]\cup Z)\setminus ([(X\cup Y)\setminus (X\cap Y)]\cap Z) \\ & = ([(X\cup Y)\cap (X\cap Y)^c]\cup Z)\setminus ([(X\cup Y)\cap (X\cap Y)^c]\cap Z) \\ & = ([(X\cup Y)\cup Z]\cap [(X\cap Y)^c\cup Z)\setminus ((X\cup Y)\cap (X\cap Y)^c\cap Z) \\ & = ([X\cup Y\cup Z]\cap [(X\cap Y)^c\cup Z)\setminus ((X\cup Y)\cap (X\cap Y)^c\cap Z) \end{align*}
\begin{align*}X+(Y+Z)&=X+ [(Y\cup Z)\setminus (Y\cap Z)] \\ & = (X\cup [(Y\cup Z)\setminus (Y\cap Z)])\setminus (X\cap [(Y\cup Z)\setminus (Y\cap Z)]) \\ & = (X\cup [(Y\cup Z)\cap (Y\cap Z)^c])\setminus (X\cap [(Y\cup Z)\cap (Y\cap Z)^c]) \\ & = ( [X\cup Y\cup Z]\cap [X\cup(Y\cap Z)^c])\setminus (X\cap (Y\cup Z)\cap (Y\cap Z)^c) \end{align*}
right? How could we continue?

We can use $(A\cap B)^c = A^c\cup B^c$ and $(A\cup B)^c = A^c\cap B^c$ can't we? (Thinking)

 

[mathmari]

We can use $(A\cap B)^c = A^c\cup B^c$ and $(A\cup B)^c = A^c\cap B^c$ can't we? (Thinking)

Ah yes!

So, we get:
\begin{align*}(X+Y)+Z&=[(X\cup Y)\setminus (X\cap Y)]+Z\\ & =([(X\cup Y)\setminus (X\cap Y)]\cup Z)\setminus ([(X\cup Y)\setminus (X\cap Y)]\cap Z) \\ & = ([(X\cup Y)\cap (X\cap Y)^c]\cup Z)\setminus ([(X\cup Y)\cap (X\cap Y)^c]\cap Z) \\ & = ([(X\cup Y)\cup Z]\cap [(X\cap Y)^c\cup Z]\setminus ((X\cup Y)\cap (X\cap Y)^c\cap Z) \\ & = ([X\cup Y\cup Z]\cap [(X\cap Y)^c\cup Z])\setminus ((X\cup Y)\cap (X\cap Y)^c\cap Z) \\ & = ([X\cup Y\cup Z]\cap [(X\cap Y)^c\cup Z])\cap((X\cup Y)\cap (X\cap Y)^c\cap Z)^c \\ & = [X\cup Y\cup Z]\cap [(X\cap Y)^c\cup Z]\cap((X\cup Y)\cap (X\cap Y)^c\cap Z)^c \\ & = [X\cup Y\cup Z]\cap [(X\cap Y)^c\cup Z]\cap[(X\cup Y)^c\cup (X\cap Y)\cup Z^c] \\ & = [X\cup Y\cup Z]\cap [X^c\cup Y^c\cup Z]\cap[(X^c\cap Y^c)\cup (X\cap Y)\cup Z^c] \end{align*}
\begin{align*}X+(Y+Z)&=X+ [(Y\cup Z)\setminus (Y\cap Z)] \\ & = (X\cup [(Y\cup Z)\setminus (Y\cap Z)])\setminus (X\cap [(Y\cup Z)\setminus (Y\cap Z)]) \\ & = (X\cup [(Y\cup Z)\cap (Y\cap Z)^c])\setminus (X\cap [(Y\cup Z)\cap (Y\cap Z)^c]) \\ & = ( [X\cup Y\cup Z]\cap [X\cup(Y\cap Z)^c])\setminus (X\cap (Y\cup Z)\cap (Y\cap Z)^c) \\ & = ( [X\cup Y\cup Z]\cap [X\cup(Y\cap Z)^c])\cap (X\cap (Y\cup Z)\cap (Y\cap Z)^c)^c \\ & = ( [X\cup Y\cup Z]\cap [X\cup(Y\cap Z)^c])\cap (X^c\cup (Y\cup Z)^c\cup (Y\cap Z)) \\ & = [X\cup Y\cup Z]\cap [X\cup Y^c\cup Z^c]\cap [X^c\cup (Y^c\cap Z^c)\cup (Y\cap Z)] \end{align*}
Is this correct so far? Which rule do we have to use next? Do we have to simplify the intersections with unions further? (Wondering)

 

[I like Serena]

Well, we should ultimately find the following Venn diagram for $X+Y+Z$:
\begin{tikzpicture}[fill=red!30!white, scale=0.5]
%preamble \usetikzlibrary{shapes,backgrounds}
\begin{scope}
\clip (210:2) circle (3) (-5,-5) rectangle (5,5);
\clip (330:2) circle (3) (-5,-5) rectangle (5,5);
\fill ( 90:2) circle (3);
\end{scope}
\begin{scope}
\clip ( 90:2) circle (3) (-5,-5) rectangle (5,5);
\clip (330:2) circle (3) (-5,-5) rectangle (5,5);
\fill (210:2) circle (3);
\end{scope}
\begin{scope}
\clip ( 90:2) circle (3) (-5,-5) rectangle (5,5);
\clip (210:2) circle (3) (-5,-5) rectangle (5,5);
\fill (330:2) circle (3);
\end{scope}
\begin{scope}
\clip ( 90:2) circle (3);
\clip (210:2) circle (3);
\fill (330:2) circle (3);
\end{scope}
\node at (90:3) {$X$};
\node at (210:3) {$Y$};
\node at (330:3) {$Z$};
\end{tikzpicture}
It should be $X+Y+Z = (X\cap Y\cap Z) \cup (X\cap Y^c\cap Z^c) \cup (X^c\cap Y\cap Z^c) \cup (X^c\cap Y^c\cap Z)$.
Or alternatively $X+Y+Z = (X\cup Y\cup Z) \cap (X\cup Y^c\cup Z^c) \cap (X^c\cup Y\cup Z^c) \cap (X^c\cup Y^c\cup Z)$.

So I think we need to be a bit smart on how to get there. (Sweating)

 

[mathmari]

So I think we need to be a bit smart on how to get there. (Sweating)

But how? (Wondering)

 

[I like Serena]

But how? (Wondering)

Let's try to write everything as a disjunction of conjunctions.
For starters we can write:
$$A+B=(A\cup B)\setminus (A\cap B) = (A\cap B^c) \cup (A^c \cap B) \tag 1$$
So:
$$(X+Y)+Z= ((X+Y)\cap Z^c) \cup ((X+Y)^c \cap Z) \tag 2$$
The first half of (2) expands into a disjunction as:
$$((X+Y)\cap Z^c) = [(X\cap Y^c) \cup (X^c \cap Y)]\cap Z^c
= (X\cap Y^c\cap Z^c) \cup (X^c \cap Y\cap Z^c)$$
The second half of (2) expands as:
$$\begin{align*}((X+Y)^c \cap Z) &= [(X\cap Y^c) \cup (X^c \cap Y)]^c \cap Z
= (X\cap Y^c)^c \cap (X^c \cap Y)^c \cap Z
= (X^c\cup Y) \cap (X \cup Y^c) \cap Z \\
&= [((X^c\cup Y) \cap X) \cup ((X^c\cup Y) \cap Y^c)] \cap Z \\
&= [(Y \cap X) \cup (X^c \cap Y^c)] \cap Z \\
&= (X\cap Y \cap Z) \cup (X^c \cap Y^c \cap Z) \end{align*}
$$
Substitute in (2) to find:
$$(X+Y)+Z = (X\cap Y^c\cap Z^c) \cup (X^c \cap Y\cap Z^c) \cup (X\cap Y \cap Z) \cup (X^c \cap Y^c \cap Z) \tag 3$$
(Whew)

 

[Evgeny.Makarov]

Associativity can indeed be proven by brute force, reducing both sides to disjunction of conjunctions of sets or their complements. The result of simplifying $A_1+\dots+A_n$ should be the disjunction of conjunctions where each conjunction has all $A_i$'s and among them an odd number of $A_i$'s not under complement. So for $n=3$ each conjunction must have either zero or two complements, thus one or three sets without complements. I also prefer omitting $\cap$ and writing $\bar{A}$ for the complement of $A$.