- #1

- 600

- 393

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

- Thread starter nuuskur
- Start date

- #1

- 600

- 393

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

- #2

- 323

- 56

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

Start with Basic Concepts.

- #3

Stephen Tashi

Science Advisor

- 7,581

- 1,470

That's an interesting question. It is not answered systematically by introductory treatments of set theory.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?

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

[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

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:Given A, B - as an example I would have something like:

[itex]A\setminus B \Rightarrow . . . \Rightarrow A\cap B\cap C\cap ... [/itex]

[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

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

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]

- #8

- 600

- 393

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

[itex] B^c [/itex] is the complement of the set [itex] B [/itex]

I can understand the logic part, but not the notation I just mentioned.

Thanks for the explanation.

- #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.

If the set [itex] S [/itex] is not constructed as you indicated, I don't understand what statement is to be proven or disproven.nobody says that the set S has to be constructed as given.

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.

- Last Post

- Replies
- 15

- Views
- 5K

- Last Post

- Replies
- 12

- Views
- 3K

- Last Post

- Replies
- 20

- Views
- 7K

- Last Post

- Replies
- 4

- Views
- 5K

- Last Post

- Replies
- 4

- Views
- 2K

- Replies
- 3

- Views
- 2K

- Last Post

- Replies
- 3

- Views
- 2K

- Last Post

- Replies
- 24

- Views
- 16K

- Last Post

- Replies
- 6

- Views
- 19K

- Last Post

- Replies
- 5

- Views
- 3K