Beginner help at proving two sets are equal

Question

I'm a computer scientist who is a complete noob at proofs.

This was a part of my home exercises but I think I failed totally so I'd love to have some advice how I'm supposed to do this. It's about propositional logic.

The question is:

Let $M$ be the set of all possible valuations. For each propositional formula $A$, define the set

$$[A]=\{v\in M\mid v(A)=1\}.$$ That is, $[A]$ is the set of all valuations which make the formula $A$ true. Show that:

$$[A\wedge B]=[A]\cap[B]$$

My proof:

Let $x∈[A∧B]$. Therefore $x∈A$ and $x∈B$.
Let $y∈[A]∩[B]$. Therefore $y∈A$ and $y∈B$.
Therefore $x$ and $y$ are equal thus the sets are the same.

I think I skipped over some crucial steps like defining the set but for the love of god I can't understand how these proofs work. If someone could strip away all the magic from this and explain it in a way that a pragmatic programmer could understand it I'd be forever grateful. The abstraction level here is just too great for me to figure out the "syntax".

Like for example I can't understand with what set of rules should I establish my deductions? Intersection of sets I guess is so common property that every mathematician is supposed to know it (?) or do I have to reference the law which I'm this conclusion basing? That would at least make sense to me. Eg. "By the rules of set theory intersection of two sets is x and x". Sure a bit wordy but that would finally clear this thing up for me.

I understand axioms are the core properties of the objects and from which all laws/rules deliver from (?) but is it always somewhat assumed that the reader knows those rules/axioms? I wish I could just run this in my code interpreter to see if it's correct or not... :)

Thank you in advance!

Answer 1

Usually the easiest way to show that two sets are equal is to show that each one is a subset of the other. A common proof format is as follows.

Let $x\in LHS$.
...
Therefore $x\in RHS$.
Conversely, let $x\in RHS$.
...
Therefore $x\in LHS$.
We have shown that $LHS\subseteq RHS$ and $RHS\subseteq LHS$, therefore $LHS=RHS$.

In your case I think you are assuming too readily the relation between $\wedge$ and $\cap\,$. Try this.

Let $v\in[A\wedge B]$.
Then by definition $v(A\wedge B)=1$.
Therefore $v(A)=1$ and $v(B)=1$. $(*)$
Hence $v\in[A]$ and $v\in[B]$.
By definition of intersection, $v\in[A]\cap[B]$.
Thus $[A\wedge B]\subseteq[A]\cap[B]$.

In line $(*)$ you may need to fill in some details depending on exactly what you have been taught about valuations. You will also need to prove $[A]\cap[B]\subseteq[A\wedge B]$. Give it a try.

Good luck!