Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a doubt about how to write a statement in rigorous logical notation.

I have a graph whose nodes are partitioned in some subsets $V_1,...,V_k$ and I have a function $Z:V\rightarrow \mathbb N$ that assign a different and unique number to each subset. I want to formalize in logical notation the definition of $Z$. My first attempt is the following: $$ \forall j \in [\ell], \ \forall u,v \ \in V_j : Z(u) = Z(v) , \ \mbox{ and } \ \forall i\neq j \in [\ell] , \forall v \in V_i \ , \forall u \in V_j \ : Z(v) \neq Z(u) $$ Is it right? My doubt is about the use of the colon, that as far as I know means "such that", but here I'm using it in the meaning of "then it holds" because sometimes I saw it being used in this way.

Another way to write it, based on the notation I've seen on some Computer Science books, could be: $$\forall j \in [\ell]\left[ u,v \ \in V_j \implies Z(u) = Z(v)\right] \ \mbox{ and } \ \forall i\neq j \in [\ell] \left[ v \in V_i \ , u \in V_j \ \implies Z(v) \neq Z(u)\right]$$ where the square parenthesis are used to specify what formula is quantified by the symbols before the parenthesis. Is this correct? If both are, are them equivalent and which one is better? Is there another way you can suggest?

share|cite|improve this question
up vote 1 down vote accepted

I would not write it formally: that simply obscures the meaning. I would probably describe it in one of the following ways or some minor variant thereof.

  1. $\big\{V_k:k\in[\ell]\big\}$ is a partition of $V$, $\varphi:[\ell]\to\Bbb N$ is an injection, and $Z:V\to\Bbb N$ is defined by setting $Z(v)=\varphi(k)$ if and only if $v\in V_k$.

  2. $\big\{V_k:k\in[\ell]\big\}$ is a partition of $V$. For $u,v\in V$ write $u\sim v$ if and only if there is a $k\in[\ell]$ such that $u,v\in V_k$; clearly $\sim$ is an equivalence relation. Then $Z:V\to\Bbb N$ is a function such that $Z(u)=Z(v)$ if and only if $u\sim v$.

If you absolutely must describe this characteristic of $Z$ in formal symbolic terms:

$$\forall k\in[\ell]\,\forall u,v\in V_k\Big(Z(u)=Z(v)\Big)\land\forall i,k\in[\ell]\left(i\ne k\to\forall u\in V_i\,\forall v\in V_k\Big(Z(u)\ne Z(v)\Big)\right)$$

is along the lines that you already had in mind, but

$$\forall i,k\in[\ell]\,\forall u\in V_i\,\forall v\in V_k\Big(Z(u)=Z(v)\leftrightarrow i=k\Big)$$

is shorter, simpler, and easier to read.

share|cite|improve this answer
I think you meant $Z(u) = Z(v) \leftrightarrow i = k$ – roliu Jan 28 '13 at 19:59
@roliu: I sure did; thanks! – Brian M. Scott Jan 28 '13 at 20:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.