Explanation of proof of why connectedness is not conjunctively local of any order $k$ I was reading Minsky's and Papert's book on perceptrons and I was reading theorem 0.6.1 and I was having a hard time understanding it. The theorem was about proving that the property "connected" was not a local property i.e. that you somehow had to see the whole picture to know if something was connected or not. In particular their prove shows that "connected" is not a conjunctively local property of any order (for definition of conjunctively local see appendix at the end of this question).

In particular goes as follows:

Suppose that $\psi_{CONNECTED}$ has order K. Then to distinguish between these two $k+1$-wide figures:



there must be some $\varphi_0$ such that $\varphi_0(X_0) = 0$, because $X_0$ is not connected. All $\varphi$'s have value 1 on $X_1$, which is connected. Now $ \varphi_0$ can depend on at most $k$ points, so there must be at least one middle square, say $S_j$, that does not contain one of these points. 

This last sentence is the one that does not make sense to me. Why does there must be at least one middle square that does not contain one of these points? I don't understand this. When it says "these points" what does that mean? Why are we talking about the middle points? Why does that matter? Also, the sentence as a whole doesn't make sense to me nor its purpose.

Like the first two properties make sense:


of course there must exist a $\varphi_0$ that rejects $X_0$, since $\psi_{CONNECTED}$ can only work properly if all of its predicates say YES if and only if the shape is connected. Since $X_0$ is not connected then some predicate must reject it. That is clear.
For a similar reason its obvious that all the predicates say YES on $X_1$ since its connected. More precisely, that is the definition of connected according to $\psi_{CONNECTED}$, that all its predicates say YES. Since $X_1$ is connected then all its predicates must say YES.
Last part that does make sense before my brain gets confused is that of course $\varphi_0$ can depend on at most $k$ points. This is obvious from the definition of $\psi_{CONNECTED}$. i.e. we assume $\psi_{CONNECTED}$ is conjunctively local of order $k$ so all of the predicates $\varphi$ can only see $k$ points.


however, the existence of $S_j$ doesn't make sense to me and thus, the remaining of the proof remains a mystery to me. If anyone can clarify that and the remains of the proof that would be fantastic!

Also, for completion, the whole proof is provided in the appendix2.



Appendix::

Recall the definition of Conjunctively local:

A predicate $\psi$ is conjunctively local of order k if it can be computed by independently computing a set of functions $\varphi_1(X)$...$\varphi_n(X)$ and then combined by the results of another function $\Omega$ of n argument by a set $\Phi $ of predicates $\varphi$ such that each $\varphi$ depends no more than $k$ points on a 2D Euclidean plane $R$ and:
$$
\psi(X) = \begin{cases} 
1 \text{ if } \varphi(X) = 1 \text{ for every } \varphi \text{ in } \Phi \\ 
0 \text{ otherwise. } 
\end{cases}
$$

or directly from Minsky's and Papert's book:







Appendix 2:

Proof of theorem 0.6.1
The predicate $\varphi_0$ depends on at most $k$ points. There are $k+1$ middle squares. So $\varphi_0$ cannot depend on all of them. That is, there is a middle square that $\varphi_0$ does not depend on. Therefore, if we add that square, the value of $\varphi_0$ doesn't change, and so $\psi$ is still 0, even though the figure is now connected.