# A question about the proper use of certain notation

1. Dec 1, 2015

### xwolfhunter

I'm currently reading a textbook for one of my classes (discrete mathematics), and we're doing set theory right now. This is not a question about how to do mathematics, it's about how to properly express through notation the concept I'm trying to convey. The text invites the reader to come up with a general formula for determining the cardinality of the union of an arbitrary number of sets, so here is what I have:

(Also, I did the best I could on the latex . . . I'm not that familiar with it)

$$\left|\substack{n \\ \\ \Huge{\cup} \\ \\ k=1}\mathrm{S}_k\right|=\sum_{k=1}^{n}\left|\mathrm{S}_k\right| -\left|\mathrm{S}_k \substack{n-1 \\ \\ \Huge{\cap} \\ \\ k=1} \mathrm{S}_{k+1}\right|+ \left|\substack{n \\ \\ \Huge{\cap} \\ \\ k=1}\mathrm{S}_k \right|$$

I'm pretty sure it's standard practice, but if it's not, the bars mean "the cardinality of."

Okay so my question centers around the second term. I'm fairly certain that the way I wrote it is not how you'd write it. Is there a simple "iterate" operator that is like sigma but more general, so I could do something like $\displaystyle \left(\substack{\scriptsize{n-1} \\ \Large{\mathrm{I}} \\ \\ \scriptsize{k=1}} \left| \mathrm{S}_{\small{k}} \cap \mathrm{S}_{\small{k+1}} \right|\right)$ where $\mathrm{I}$ is the iterator? How would I write that?

Edit: And yeah, I'm aware that what I wrote down does not really work. Just had the question about notation.

2. Dec 1, 2015

### Staff: Mentor

I would write it $∩_{i,j}$ or $∪_{i,j}$ $(S_i ∩_{i≠j} S_j)$ resp. depending on what you mean. Your proposed notation isn't quite clear to me, esp. what is meant by "iterator".
The task for finitely many sets of finite many elements is the easy part. It's getting more than tricky if there are arbitrary many sets. That looks to me like an invitation to think about the continuum hypothesis.

Last edited: Dec 1, 2015
3. Dec 1, 2015

### micromass

Staff Emeritus
What does this notation even mean?

4. Dec 1, 2015

### xwolfhunter

Yeah, I don't get it either. I think your notation just kinda floats there like a lump of seaweed.

By "iterator" I meant "algorithm," I suppose. I was basically asking if there is some operator that says "hey, just iterate whatever's in the parenthesis $n$ times and do $x=x+1$ each time." I was asking a well-educated mathematician somewhere to tell me how he would write what's meant by the thing I wrote before: $\displaystyle \substack{\scriptsize{n-1} \\ \Large{\mathrm{I}} \\ \\ \scriptsize{k=1}} \left| \mathrm{S}_{\small{k}} \cap \mathrm{S}_{\small{k+1}} \right|$.

5. Dec 1, 2015

### micromass

Staff Emeritus
So if you're asking for the general form of the inclusion-exclusion formula, then it's this nasty thing:

$$\left|\bigcup_{k=1}^n A_k\right| = \sum_{i=1}^n (-1)^{i+1} \left(\sum_{B\subseteq \{1,...,n\},~|B| = i}\left|\bigcap_{k\in B} A_k\right|\right)$$

6. Dec 1, 2015

### Staff: Mentor

You wrote $$\left|\mathrm{S}_k \substack{n-1 \\ \\ \Huge{\cap} \\ \\ k=1} \mathrm{S}_{k+1}\right|$$
as one cardinal of $n-1$ possible sets $S_k ∩ S_{k+1}$ which does not make sense. So you have to explain what you are going to do with these $n-1$ numbers: add them, or first intersect or unite the sets? If you want to iterate something then explain what and how. And I wonder that you do not consider sets like. e.g. $S_1 ∩ S_3$ or $S_2 ∩ S_n$.

If you want to write down the iteration it might be helpful to consider the following sets:
$V_i = \substack{n \\ \huge{\cup} \\ k = i} S_k$ , $W_i = \substack{i \\ \huge{\cup} \\ k = 1} S_k$ and $T_i = \substack{i \\ \huge{\cap} \\ k = 1} S_k$ , as well as sets like $V_i - W_{i-1}$.

7. Dec 1, 2015

### xwolfhunter

Secondly, the $n-1$ means "iterated (the number of sets minus one) times." There are no numbers to add, intersect, or unite. The iteration description is exactly the same as that of sigma notation. Which you should already be aware of, considering you thought my notation was good enough that you copy-pasted my cobbled-together handmade way of writing it and used it in your post to define your sets.

Thirdly, while I do understand what is defined by $V_i$, $W_i$, and $T_i$, I honestly have no idea how they would be useful.

Fourthly, based on the exact definitions of $V_i$ and $W_i$, I believe that $V_i - W_{i-1}$ is just $V_i$. Am I wrong? I don't get the point of that.

8. Dec 1, 2015

### suremarc

Are you saying that $\mathrm{I}$ is the same as $\sum$? What operation is being iterated for each of the values $k\in\{1,...,n-1\}$? I also am having a hard time understanding precisely what you are trying to write down.
Perhaps you could try describing in words what object you want this term to express?

9. Dec 2, 2015

### Staff: Mentor

I'm having the same problem. It's not clear what operation you (xwolfhunter) are iterating.

10. Dec 2, 2015

### xwolfhunter

Okay . . . I've got this.

The last term in what I wrote represents the cardinality of the intersection of all of the sets. I wanted to have something that iterates through all possible combinations of two sets intersecting, and subtracts the cardinality of each one individually. The concept behind what I wrote down does not do that, for several reasons, which is most likely why its meaning is so inscrutable. My main question is how would the general mathematically-informed population write that? Here is another stab that (I think) is somewhat clearer at conveying what I want:

I have a collection of $n$ sets: $\{\mathrm{S}_1,\mathrm{S}_2,\cdot\cdot\cdot,\mathrm{S}_n\}$.
$$-\sum_{k=1}^{\frac{n\mathrm{!}}{(n-2)\mathrm{!}}}\left|\mathrm{S}_k\cap\mathrm{S}_{k+1}\right|$$
Of course, I have no idea how to iterate through the permutation (also, I'm pretty sure I need a combination, not a permutation, but I don't know the notation for that), so the second part does not do anything useful, but still, I think this more clearly shows what I was trying to express.

11. Dec 2, 2015

### Staff: Mentor

I think this might be what you're shooting for:
$$\sum_{i,~ j = 1,~ i \ne j}^n|S_i \cap S_j|$$

12. Dec 2, 2015

### micromass

Staff Emeritus
Or as I said above $\sum_{B\subseteq \{1,...,n\}, |B|= 2} \left|\bigcap_{k\in B} S_k\right|$

13. Dec 2, 2015

### suremarc

I like this expression. Since sets have no intrinsic ordering, it ignores the "order" associated with the enumerated indices, in this case $i$ and $j$.

14. Dec 3, 2015

### jbriggs444

Nitpick: This appears to double-count each pair.

15. Dec 3, 2015

### Staff: Mentor

$$\sum_{i = 1, ~j = 2, ~i < j}^n|S_i \cap S_j|$$
If you were dealing with $S_1, S_2, S_3, S_4$, the above would give the magnitudes of $S_1 \cap S_2, S_1 \cap S_3, S_1 \cap S_4, S_2 \cap S_3, S_2 \cap S_4$, and $S_3 \cap S_4$.