# How to mathematically describe a loop over a set with two indexes.

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$

• 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. Nov 18, 2014 at 10:33
• 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?
– nino
Nov 18, 2014 at 10:40

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.

• 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?
– nino
Nov 18, 2014 at 11:16
• 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. Nov 18, 2014 at 11:36
• 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?
– nino
Nov 18, 2014 at 12:54
• 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. Nov 23, 2014 at 19:40