Difference unexpressable as intersection

[nuuskur]

Is there anywhere to look for proofs that deal in tackling the set theoretic operations - what can and what can't be expressed through another operation?

For example: prove that the difference of 2 (or N) sets cannot be expressed through the intersection operator.
Given A,B we cannot

I'm not exactly sure how to express myself in English in this topic, I hope it's concise enough.

Thanks

 

[alan2]

Any decent introductory analysis book should contain a chapter or two on set theory. If you like free try this set of 3 books:

http://www.trillia.com/products.html

Start with Basic Concepts.

 

[Stephen Tashi]

Is there anywhere to look for proofs that deal in tackling the set theoretic operations - what can and what can't be expressed through another operation?

That's an interesting question. It is not answered systematically by introductory treatments of set theory.

It amounts to a question about logical operations. Elementary set theoretic operations on sets produces a set S. The definitions of the S will be given in terms of the relation "is an element of" between an element and a set and the logical connectives "AND" and "OR", and the logical operator "NOT". For example $A \cap B^c = S$ defines $S$ as $\{x: x \in A\ and\ not\ (x\in B) \}$.

So I think deciding if two set theoretic operations do or don't produce equal sets comes down to showing that two logical expressions are or are not equivalent. That can be done by truth tables or theorems about propositional logic.

For example, let $S_1 = A \cap (B \cup C)$ Let $S_2 = (A\cap B) \cup (A\cap C)$

Abusing notation, let $A$ also stand for the statement $x \in A$ etc.

The question of whether $S_1$ is equal to $S_2$ amounts to asking if the logical expression $A \ and \ (\ B \ or \ C)$ is logically equivalent to the expression $(A \ and\ B ) \ or \ ( A\ and \ C)$.

 

[nuuskur]

Given A, B - as an example I would have something like:
$A\setminus B \Rightarrow . . . \Rightarrow A\cap B\cap C\cap ...$
For the difference of two sets, by definition an element is in A and Not in B - the intersection operator does not allow such exclusion hence a Not statement would never appear thus not satisfying the criteria, but it's such a sloppy explanation. How would I know for sure if there was the difference of N number of sets that can in NO way be expressed as the intersection of any M number of sets?

 

[Stephen Tashi]

Given A, B - as an example I would have something like:
$A\setminus B \Rightarrow . . . \Rightarrow A\cap B\cap C\cap ...$

You don't need a separate symbol for each element, if that's what your are asking. I'm assuming a set S is defined by a logical equivalence of the form:
$x \in S \leftrightarrow x\in... x\in ... x\in$ You don't need a symbol for each element of the set. You only need a symbol for each different set named after the "$x\in ...$

So $A \setminus B$ is defined by the statement $x \in A \ and \ not \ (x \in B)$ and this is abbreviated to $A \ and \ not\ B$

 

[nuuskur]

If we define sets S and T such that $S := S_1\setminus (S_2\setminus (S_3\setminus ... (S_{n-1}\setminus S_n))$ (set difference is not commutative) and $T := T_1\cap T_2\cap T_3\cap ...\cap T_m$ where $n,m\in\mathbb{N}$ are arbitrary. Assuming such m,n exist where S = T, then the two sets contain the same elements.
Let $x\in S$, the objective is to show that $x\in S\Rightarrow x\in T \wedge x\in T\Rightarrow x\in S \Leftrightarrow S = T$ - I know ahead of time that such scenario cannot exist. Would this proof, if finished, be sufficient, though? I am still not satisfied, as it still considers a specific scenario - albeit the n,m are arbitrary, nobody says that the set S has to be constructed as given.

 

[Stephen Tashi]

As an example:

Using $\neg$ for "not"
Using $\wedge$ for "and"
Using $\vee$ for "or"


$A \setminus B$ is determined by the condition $x \in A \wedge \neg (x \in B)$
Abbreviate that to $A \wedge \neg B$

We could note $A \cap B^c$ is the same condition so $A \setminus B = A \cap B^c$

We can do something more elaborate:

Propositional logic tells us $W \Leftrightarrow W \vee (C \wedge \neg C)$

$A \wedge \neg B \Leftrightarrow ( A \wedge \neg B) \vee ( C \wedge \neg C)$

Apply the logical distributive laws:

$\Leftrightarrow ( (A \wedge \neg B) \vee C) \wedge ( (A \wedge \neg B) \vee \neg C)$

$\Leftrightarrow ( ( A \vee C) \wedge (\neg B \vee C) ) \wedge ( ( A \vee \neg C) \wedge (\neg B \vee \neg C) )$

Apply one of DeMorgan's laws :

$\Leftrightarrow ( ( A \vee C) \wedge (\neg B \vee C) ) \wedge ( ( A \vee \neg C) \wedge \neg (B \wedge C) )$


The corresponding result for sets is:

$A \setminus B = ((A \cup C) \cap (B^c \cup C) ) \cap ( (A \cup C^c) \cap (B \cap C)^c)$

 

[nuuskur]

What is this notation $B^c$?
I can understand the logic part, but not the notation I just mentioned.

Thanks for the explanation.

 

[Stephen Tashi]

What is this notation $B^c$?
I can understand the logic part, but not the notation I just mentioned.

Thanks for the explanation.

$B^c$ is the complement of the set $B$

 

[Stephen Tashi]

If we define sets S and T such that $S := S_1\setminus (S_2\setminus (S_3\setminus ... (S_{n-1}\setminus S_n))$ (set difference is not commutative) and $T := T_1\cap T_2\cap T_3\cap ...\cap T_m$ where $n,m\in\mathbb{N}$ are arbitrary. Assuming such m,n exist where S = T, then the two sets contain the same elements.

nobody says that the set S has to be constructed as given.

If the set $S$ is not constructed as you indicated, I don't understand what statement is to be proven or disproven.

If the sets $T_i$ can be any sets then you could let $T_1 = T_2 = T_3 ... = S$. So for the question to be interesting there must some restriction on the sets $T_i$ or some relation between the sets $T_i$ and $S_j$. I think what you have in mind is that each $T_i$ is equal to some finite expression involving the sets $S_j$ and set operations.