Difference unexpressable as intersection

  • Thread starter nuuskur
  • Start date
  • #1
600
393
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
 

Answers and Replies

  • #2
323
56
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.
 
  • #3
Stephen Tashi
Science Advisor
7,581
1,470
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 [itex] A \cap B^c = S [/itex] defines [itex] S[/itex] as [itex] \{x: x \in A\ and\ not\ (x\in B) \} [/itex].

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 [itex] S_1 = A \cap (B \cup C) [/itex] Let [itex] S_2 = (A\cap B) \cup (A\cap C) [/itex]

Abusing notation, let [itex] A [/itex] also stand for the statement [itex] x \in A [/itex] etc.

The question of whether [itex]S_1 [/itex] is equal to [itex] S_2 [/itex] amounts to asking if the logical expression [itex] A \ and \ (\ B \ or \ C) [/itex] is logically equivalent to the expression [itex] (A \ and\ B ) \ or \ ( A\ and \ C) [/itex].
 
  • #4
600
393
Given A, B - as an example I would have something like:
[itex]A\setminus B \Rightarrow . . . \Rightarrow A\cap B\cap C\cap ... [/itex]
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?
 
  • #5
Stephen Tashi
Science Advisor
7,581
1,470
Given A, B - as an example I would have something like:
[itex]A\setminus B \Rightarrow . . . \Rightarrow A\cap B\cap C\cap ... [/itex]
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:
[itex] x \in S \leftrightarrow x\in.... x\in .... x\in [/itex] You don't need a symbol for each element of the set. You only need a symbol for each different set named after the "[itex] x\in ....[/itex]

So [itex] A \setminus B [/itex] is defined by the statement [itex] x \in A \ and \ not \ (x \in B) [/itex] and this is abbreviated to [itex] A \ and \ not\ B [/itex]
 
  • #6
600
393
If we define sets S and T such that [itex]S := S_1\setminus (S_2\setminus (S_3\setminus ... (S_{n-1}\setminus S_n))[/itex] (set difference is not commutative) and [itex]T := T_1\cap T_2\cap T_3\cap ...\cap T_m[/itex] where [itex]n,m\in\mathbb{N}[/itex] are arbitrary. Assuming such m,n exist where S = T, then the two sets contain the same elements.
Let [itex]x\in S[/itex], the objective is to show that [itex]x\in S\Rightarrow x\in T \wedge x\in T\Rightarrow x\in S \Leftrightarrow S = T[/itex] - 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.
 
  • #7
Stephen Tashi
Science Advisor
7,581
1,470
As an example:

Using [itex] \neg [/itex] for "not"
Using [itex] \wedge [/itex] for "and"
Using [itex] \vee [/itex] for "or"


[itex] A \setminus B [/itex] is determined by the condition [itex] x \in A \wedge \neg (x \in B) [/itex]
Abbreviate that to [itex] A \wedge \neg B [/itex]

We could note [itex] A \cap B^c [/itex] is the same condition so [itex] A \setminus B = A \cap B^c [/itex]

We can do something more elaborate:

Propositional logic tells us [itex] W \Leftrightarrow W \vee (C \wedge \neg C) [/itex]

[itex] A \wedge \neg B \Leftrightarrow ( A \wedge \neg B) \vee ( C \wedge \neg C) [/itex]

Apply the logical distributive laws:

[itex] \Leftrightarrow ( (A \wedge \neg B) \vee C) \wedge ( (A \wedge \neg B) \vee \neg C) [/itex]

[itex] \Leftrightarrow ( ( A \vee C) \wedge (\neg B \vee C) ) \wedge ( ( A \vee \neg C) \wedge (\neg B \vee \neg C) ) [/itex]

Apply one of DeMorgan's laws :

[itex] \Leftrightarrow ( ( A \vee C) \wedge (\neg B \vee C) ) \wedge ( ( A \vee \neg C) \wedge \neg (B \wedge C) ) [/itex]


The corresponding result for sets is:

[itex] A \setminus B = ((A \cup C) \cap (B^c \cup C) ) \cap ( (A \cup C^c) \cap (B \cap C)^c) [/itex]
 
  • Like
Likes nuuskur
  • #8
600
393
What is this notation [itex]B^c[/itex]?
I can understand the logic part, but not the notation I just mentioned.

Thanks for the explanation.
 
  • #9
Stephen Tashi
Science Advisor
7,581
1,470
What is this notation [itex]B^c[/itex]?
I can understand the logic part, but not the notation I just mentioned.

Thanks for the explanation.
[itex] B^c [/itex] is the complement of the set [itex] B [/itex]
 
  • #10
Stephen Tashi
Science Advisor
7,581
1,470
If we define sets S and T such that [itex]S := S_1\setminus (S_2\setminus (S_3\setminus ... (S_{n-1}\setminus S_n))[/itex] (set difference is not commutative) and [itex]T := T_1\cap T_2\cap T_3\cap ...\cap T_m[/itex] where [itex]n,m\in\mathbb{N}[/itex] 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 [itex] S [/itex] is not constructed as you indicated, I don't understand what statement is to be proven or disproven.

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

Related Threads on Difference unexpressable as intersection

  • Last Post
Replies
15
Views
5K
  • Last Post
Replies
12
Views
3K
  • Last Post
Replies
20
Views
7K
  • Last Post
Replies
4
Views
5K
Replies
4
Views
2K
Replies
3
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
24
Views
16K
Replies
6
Views
19K
Replies
5
Views
3K
Top