The axioms of a vector space are satisfied

Click For Summary

Discussion Overview

The discussion revolves around verifying whether the structure $(2^M, +, \cap)$, where $M$ is a non-empty set and $+ : 2^M\times 2^M \rightarrow 2^M$ is defined as $(X,Y)\mapsto (X\cup Y)\setminus (X\cap Y)$, satisfies the axioms of a vector space over the field $\mathbb{F}_2$. Participants explore various axioms including associativity, existence of neutral and inverse elements, commutativity, and multiplicative properties involving intersection.

Discussion Character

  • Technical explanation
  • Mathematical reasoning
  • Debate/contested

Main Points Raised

  • Some participants assert that the associativity of the operation $+$ is correctly shown, while others seek clarification on the rules needed to demonstrate equality in the associative property.
  • Participants agree that the empty set serves as the neutral element and that the inverse of an element is the set itself.
  • Commutativity is claimed to hold, with participants providing reasoning for this property.
  • There is discussion about the multiplicative axioms, with participants attempting to verify expressions involving intersections and questioning the correctness of their manipulations.
  • Some participants express uncertainty about the multiplicative unity of $\mathbb{K}$ and whether it is indeed $M$, while others suggest that $X \cap M = X$ should hold.
  • Questions arise regarding whether $\mathbb{K}$ can be assumed to be isomorphic to $\mathbb{F}_2$ and what needs to be proven to establish this.
  • Participants discuss the necessity of proving that $\mathbb{K}$ is a field with the defined operations, referencing the unique properties of fields with two elements.

Areas of Agreement / Disagreement

Participants generally agree on some properties being satisfied, such as the existence of a neutral element and the inverse element. However, there remains uncertainty and debate regarding the verification of the associativity and multiplicative axioms, as well as the isomorphism of $\mathbb{K}$ to $\mathbb{F}_2$. The discussion is not resolved, with multiple competing views and questions still present.

Contextual Notes

Participants note that the proof of $\mathbb{K}$ being a field is necessary for the consistency of the problem statement, and they highlight the need to verify that the addition and multiplication tables match those of $\mathbb{F}_2$. There are unresolved questions about the assumptions made regarding the operations and their implications.

Who May Find This Useful

This discussion may be useful for students and researchers interested in vector spaces, set theory, and the properties of fields, particularly in the context of finite fields and combinatorial structures.

mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

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)
 
Physics news on Phys.org
mathmari said:
Hey! :o

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)

mathmari said:
  • $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)
 
Klaas van Aarsen said:
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)
Klaas van Aarsen said:
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)
Klaas van Aarsen said:
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)
 
mathmari said:
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)

mathmari said:
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)

mathmari said:
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)
 
Klaas van Aarsen said:
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)
Klaas van Aarsen said:
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)
 
mathmari said:
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)
 
Klaas van Aarsen said:
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)
 
Last edited by a moderator:
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)
 
Klaas van Aarsen said:
So I think we need to be a bit smart on how to get there. (Sweating)

But how? (Wondering)
 
  • #10
mathmari said:
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)
 
  • #11
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$.
 

Similar threads

MHB Equivalence of Subspace Statements
  • · Replies 9 ·
Replies
9
Views
1K
Undergrad Tough lemma on locally finite refinement
  • · Replies 8 ·
Replies
8
Views
3K
MHB Solve Sets of Form $v+X$ in $\mathbb{R}^2$
  • · Replies 5 ·
Replies
5
Views
2K
MHB Determining Basis and Dimension for Vector Subspaces $U_1$ and $U_2$
  • · Replies 5 ·
Replies
5
Views
2K
MHB Set of 2-dimensional orthogonal matrices equal to an union of sets
  • · Replies 9 ·
Replies
9
Views
2K
Undergrad Localizing single variable quotient polynomial ring at a prime ideal
  • · Replies 6 ·
Replies
6
Views
1K
MHB Proving Convexity: Steps and Conditions for a Set to be Convex
  • · Replies 6 ·
Replies
6
Views
2K
MHB Collection of Subspaces of a Vector Space
  • · Replies 4 ·
Replies
4
Views
2K
MHB Upper and lower bounds for the cardinalities
  • · Replies 17 ·
Replies
17
Views
2K
Undergrad On Borel sets of the extended reals
  • · Replies 2 ·
Replies
2
Views
3K