It's worth recalling what Martin-Löf wrote in [Intuitionistic type theory]: (But note that Martin-Löf writes "set" for what we would call "type"!)
- What is a set?
- What is it that we must know in order to have the right to judge something to be a set?
- What does a judgement of the form "$A$ is a set" mean?
The first is the ontological (ancient Greek), the second the epistemological (Descartes, Kant, ...) and the third semantical (modern) way of posing essentially the same question. [...] So:
- a set $A$ is defined by prescribing how a canonical element of $A$ is formed as well as how two equal canonical elements of $A$ are formed.
This is the explanation of the meaning of a judgement of the form $A$ is a set.
My own view is that it doesn't make sense to compare sets and types at all – they are entities in very different worlds. The right question to ask is:
What is the difference between a set theory and a type theory?
The answer, which is hinted at by the quote above, is syntax. Set theory is a logical theory, built on top of a preexisting deductive system such as first-order logic, while type theory is a deductive system in its own right. (Well, you could formalise type theory as a certain kind of first-order theory, but I consider that to be a kind of abstraction inversion.)
One of the key differences is that terms in type theories are first-class citizens: they do not denote elements, they are elements. (That is not to say that different terms can't be equal, though – more on that later.) Of course, what one means by "element" also has to be somewhat more general than in set theory, since terms do not have to be closed: for instance, the term $\mathsf{succ} (x)$, in the context $x : \mathbb{N}$, is of type $\mathbb{N}$; so interpreted literally, it says that $\mathbb{N}$ has an "element" $\mathsf{succ} (x)$, the successor of a "variable element" $x$. One way of making concrete sense of this is to employ the notion of "generalised element" from category theory: the "variable element" $x$ is interpreted as the identity function $\mathbb{N} \to \mathbb{N}$, and similarly $\mathsf{succ} (x)$ is interpreted as the successor function $\mathbb{N} \to \mathbb{N}$. This is to be distinguished from (the interpretation of) the closed term $\lambda x : \mathbb{N} . \mathsf{succ} (x)$, which is of type $\mathbb{N} \to \mathbb{N}$ in the empty context. (This, by the way, is one reason why ETCS is considered a set theory and not a type theory – though, granted, it draws heavily from type-theoretic practices.)
A much more subtle difference between set theory and type theory is the treatment of equality. In type theory, it is possible (but not necessary) to distinguish between so-called judgemental equality (denoted by $\equiv$) and propositional equality (denoted by $=$). Judgemental equality concerns equality of terms qua terms: for instance, $1 \equiv \mathsf{succ}(0)$ because the former is an abbreviation for the latter, and (assuming consistency) we never have $x \equiv y$ when $x$ and $y$ are two different variables. This is sometimes called "definitional equality", because one usually deduces judgemental equalities by repeatedly applying definitions ("$\beta$-reduction"). No matter what you call it, judgemental equality is (supposed to be) an external metalinguistic notion, and needless to say, judgemental equality is absent in set theory.
On the other hand, propositional equality concerns semantics. Of course, judgemental equality implies propositional equality, but the converse need not hold. (If it does, then the type theory is said to be extensional.) Here's a somewhat involved example. Let $x$ and $y$ be variables of type $\mathbb{N}$. Then $x + y$ and $y + x$ are terms of type $\mathbb{N}$, defined by induction in the usual way:
\begin{align*}
x + 0 & \equiv x &
x + \mathsf{succ}(y) & \equiv \mathsf{succ}(x + y) \\
y + 0 & \equiv y &
y + \mathsf{succ}(x) & \equiv \mathsf{succ}(y + x)
\end{align*}
Now, by repeatedly applying definitions, one can show that $x + y \equiv y + x$ after substituting closed numerals for $x$ and $y$, so e.g. $2 + 3 \equiv 5 \equiv 3 + 2$. But that does not mean that $x + y \equiv y + x$; in fact, this judgement cannot be derived in intensional type theory! Rather, one has to use induction on $x$ and $y$, and the only kinds of equalities provable by induction are propositional equalities.
I think, to really get a good feel for type theories as a mathematician, one should either go play around with proof assistants like Coq or Agda, or otherwise try to learn what it takes to build a model of intensional type theory. My own understanding was seriously hindered by intuitions drawn from extensional type theory, which is in many ways more like set theory than not.
I think the proof becomes easier if you turn the notation $X-Y$ into $X\cap Y^c$, which means the intersection between $X$ and the complement of $Y$. (They're equivalent.)
I think my main problem is that I don't know how to manipulate $A-(B-C)$. I've reasoned as follows so far: If $x\in A-(B-C)$ then $x\in A$ and $\not\in (B-C)$. Then $x\in A$ and $\not\in$ the part of $B$ that isn't $C$. (I think saying it like this isn't rigorous enough, but correct if if I'm wrong.)
Your interpretation is right, but more precisely, you could say "$x \not\in (B-C)=B \cap C^c$ means that either $x \not\in B$ or $x \notin C^c$, so $x\not\in B$ or $x \in C$." (To not be in the intersection it is enough for $x$ to not be in one of the sets.)
Then there are two cases: $x\in A$ and $x\in B$, so then $x\in C$, since it cannot be in the part of $B$ that isn't $C$.
This sentence is a little unclear. The two cases are
- $x\in A$ and $x \notin B$
- $x\in A$ and $x \in C$.
Case 1: $x\in A$ and $x \notin B$ means that $x\in A-B$, so $x \in (A-B)\cup C$.
Case 2: $x \in C \implies x \in (A-B)\cup C$.
(This is pretty much what you wrote in the sentence following the one I just quoted.)
Note that you didn't really use the hypothesis that $C \subseteq A$ anywhere to prove this inclusion.
Another way to check that $C \subseteq A \implies A-(B-C)=(A-B)\cup C$:
\begin{align} A-(B-C) &= A \cap (B\cap C^c)^c \\
&=A\cap (B^c \cup C)\\
&= (A \cap B^c) \cup (A \cap C) \\
&= (A \cap B^c) \cup C \quad \text{ because $C \subseteq A$}\\
&=(A -B)\cup C
\end{align}
Best Answer
Yes, your guesses are correct (except for “the necessary and sufficient condition for (i) to be correct” — I explain it in my other answer.)
Ad (i):
To prove, that it is not always true, it is sufficient to provide particular sets $A$, $B$, $C$ which don't satisfy the equation (i.e. so called contra example).
So let $A$, $B$, $C$ are as in this table, where are progressively calculated expressions from them:
By comparing rows 5 and 7 we see that the equation is not satisfied.
Ad (ii):
To prove the equality for every sets $A$, $B$, $C$, we need to prove that every element in the set on the left-hand side of the equality
$$A−(B∪C)=(A−B)−C$$
belongs to the right-hand set, and vice versa.
So let
$$x \in A−(B∪C).$$
Then by definition of the set subtraction
$$x \in A, \ \text{but}\ x \notin (B \cup C)$$
But if $x \notin (B \cup C)$, then by definition of the set union
$$\text{neither}\ x \in B, \ \text{nor}\ x \in C$$
which mean — again by definiton of the set subtraction — that
$$x \in (A - B), \ \text{ but }\ x \notin C$$
i.e. — once more by definiton of the set subtraction — that
$$x \in (A - B) - C$$
So we proved that the arbitrary element $x$ of the left-hand side belongs to the right-hand side, too.
The reversed statement we may prove by similar manner.