Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Difference unexpressable as intersection

  1. Jan 26, 2015 #1
    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.

  2. jcsd
  3. Jan 26, 2015 #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:


    Start with Basic Concepts.
  4. Jan 27, 2015 #3

    Stephen Tashi

    User Avatar
    Science Advisor

    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].
  5. Jan 27, 2015 #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?
  6. Jan 27, 2015 #5

    Stephen Tashi

    User Avatar
    Science Advisor

    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]
  7. Jan 27, 2015 #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.
  8. Jan 27, 2015 #7

    Stephen Tashi

    User Avatar
    Science Advisor

    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]
  9. Jan 27, 2015 #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.
  10. Jan 27, 2015 #9

    Stephen Tashi

    User Avatar
    Science Advisor

    [itex] B^c [/itex] is the complement of the set [itex] B [/itex]
  11. Jan 27, 2015 #10

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook