1
$\begingroup$

I have a set of sets $G = \{D_{0,0}\,D_{0,1}\,D_{0,2}\,D_{1,0},...,D_{n,0}\,D_{n,m}\} $

What I know want to express is a constraint that for each set in $ G $, if $ x \in D_{0,0} $ then the statement $ y \in D_{0,1} $ can't be true. So basically, if the set with index 0 has the element $x$ in it, the set with index 1 is not allowed to have an element y. Now the problem is, that I want to have this constraint for all the possible combinations.

$ D_{0,0} $ and $ D_{0,1} $, $ D_{0,1} $ and $ D_{0,2} $, $ D_{1,0} $ and $ D_{1,1} $, and so on. In programming this would basically be a nested for loop. But how would I express something like that in Mathematics?

What I have so far is this: I count all the violations, and if they are 0, it is correct. Is this possible in Mathematics?

$\sum_{i = 1}^{n} \sum_{j = 1}^{m-1} x \in D_{i,j}\wedge y \in D_{i,j+1})=0 $

$\endgroup$
2
  • $\begingroup$ The index pattern is unclear; it seems that the number of sets with a given first index depends on the index if there are only three sets with first index $0$, but looking at the sum you wrote, that's not the case. $\endgroup$
    – fuglede
    Nov 18, 2014 at 10:33
  • $\begingroup$ But if all sets with a given first index i have, m elements for the second index. Would the sum then be correct? If yes, how would I need to add this information? If no, how can I change my sum, so it makes sense? $\endgroup$
    – nino
    Nov 18, 2014 at 10:40

1 Answer 1

Reset to default
1
$\begingroup$

One thing that's a bit unfortunate is that for two statements $P$ and $Q$, $P \wedge Q$ denotes another statement and not a number like $0$ and $1$, so trying to sum such things to get a number is problematic (compare it with programming languages where boolean True and 1 are different). Now you could augment your summand with a function which you define to take the values 0 and 1 on false and true statements respectively, but that's maybe a little weird.

In your situation, you're in luck though: implementing the constraint of elements belong to certain sets is so common that there's standard notation for it, the underlying notion being that of an indicator function: if $A$ is a subset of some set $X$, then the indicator function $1_A$ takes the value $1$ on elements of $A$ and $0$ on elements in $X \setminus A$.

Suppose now that you have two elements $x , y \in X$ and two subsets $A$ and $B$ of $X$. Then the product $1_A(x)1_B(y)$ is equal to $1$ if both $x \in A$ and $y \in B$, and otherwise it's zero.

$\endgroup$
4
  • $\begingroup$ I thought that this was a problem, as true is not the same as 1. So what you say is, that $ (\sum_{i = 1}^{n} \sum_{j = 1}^{m-1} 1_{\{d1\}} D_{i,j} 1_{\{d2\}} D_{i,j+1})=0 $ would be correct? $\endgroup$
    – nino
    Nov 18, 2014 at 11:16
  • $\begingroup$ Hm, I'm not sure what you mean by $d1$ and $d2$. But you could write $1_{D_{i,j}}(x)1_{D_{i,j+1}}(y)$. Another thing that confused me about your sum was that from your description, it seems like you did /not/ want $y$ to be in that particular set. $\endgroup$
    – fuglede
    Nov 18, 2014 at 11:36
  • $\begingroup$ Oh of course, the $d1$ and $d2$ was a copy&paste error. Your second assumption is correct. If x is in the first set, then y can not be in second set. If I understood the indicator function correctly that would mean I get a 1 if $x \in A$ and $y \in B$. If I want this to NEVER happen then all product of all indicator functions should always be 0. Isn't this correct? $\endgroup$
    – nino
    Nov 18, 2014 at 12:54
  • 1
    $\begingroup$ As it stands, $1_A(x) 1_B(y) = 0$ if and only if either $x \notin A$ or $y \notin B$. I couldn't quite read off if that was your criterion. $\endgroup$
    – fuglede
    Nov 23, 2014 at 19:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .