1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A question about the proper use of certain notation

  1. Dec 1, 2015 #1
    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)

    [tex]
    \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|[/tex]

    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. jcsd
  3. Dec 1, 2015 #2

    fresh_42

    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
  4. Dec 1, 2015 #3

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    What does this notation even mean?
     
  5. Dec 1, 2015 #4
    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|##.
     
  6. Dec 1, 2015 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

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

    [tex]\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)[/tex]
     
  7. Dec 1, 2015 #6

    fresh_42

    Staff: Mentor

    You wrote [tex]\left|\mathrm{S}_k \substack{n-1 \\ \\ \Huge{\cap} \\ \\ k=1} \mathrm{S}_{k+1}\right|[/tex]
    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} ##.
     
  8. Dec 1, 2015 #7
    Firstly, as I said in my first post, I am not asking about the math, I'm asking about the notation.

    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.
     
  9. Dec 1, 2015 #8
    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?
     
  10. Dec 2, 2015 #9

    Mark44

    Staff: Mentor

    I'm having the same problem. It's not clear what operation you (xwolfhunter) are iterating.
     
  11. Dec 2, 2015 #10
    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\}##.
    [tex]-\sum_{k=1}^{\frac{n\mathrm{!}}{(n-2)\mathrm{!}}}\left|\mathrm{S}_k\cap\mathrm{S}_{k+1}\right|[/tex]
    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.
     
  12. Dec 2, 2015 #11

    Mark44

    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|$$
     
  13. Dec 2, 2015 #12

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Or as I said above ##\sum_{B\subseteq \{1,...,n\}, |B|= 2} \left|\bigcap_{k\in B} S_k\right|##
     
  14. Dec 2, 2015 #13
    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##.
     
  15. Dec 3, 2015 #14

    jbriggs444

    User Avatar
    Science Advisor

    Nitpick: This appears to double-count each pair.
     
  16. Dec 3, 2015 #15

    Mark44

    Staff: Mentor

    How about this?
    $$\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##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: A question about the proper use of certain notation
Loading...