Difference unexpressable as intersection

In summary: W \vee (C \wedge \neg C) = (W \vee C) \vee (W \vee \ neg C) C \wedge \neg C = (C \wedge \neg C) \vee (C \wedge \neg C)
  • #1
nuuskur
Science Advisor
857
911
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
 
Physics news on Phys.org
  • #2
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
nuuskur said:
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
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
nuuskur said:
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
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
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
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
nuuskur said:
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
nuuskur said:
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.
 

1. What does "Difference unexpressable as intersection" mean?

"Difference unexpressable as intersection" refers to a mathematical concept where two sets of data have no common elements, meaning they cannot be intersected or compared in any way.

2. How is "Difference unexpressable as intersection" used in science?

This concept is often used in fields such as computer science and statistics to help identify and analyze patterns and relationships between different sets of data.

3. Can "Difference unexpressable as intersection" be calculated or measured?

No, since the two sets of data have no common elements, the difference between them cannot be quantified or expressed in any measurable way.

4. What is the significance of "Difference unexpressable as intersection" in research?

Understanding the concept of difference unexpressable as intersection can help researchers identify and analyze complex relationships and patterns within their data, leading to new discoveries and insights.

5. Are there any real-world examples of "Difference unexpressable as intersection"?

Yes, an example of this concept can be seen in the comparison of two completely different species. They may have no common characteristics, making it impossible to express their difference as an intersection.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
1K
  • Set Theory, Logic, Probability, Statistics
2
Replies
40
Views
6K
  • Introductory Physics Homework Help
Replies
10
Views
486
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
2
Replies
55
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
704
  • Programming and Computer Science
Replies
2
Views
1K
Replies
36
Views
4K
Back
Top