Set of Propositional Formulae with no equivalent independent subset A set of propositional formula $X$ is said to be equivalent to $Y$ if for any formula $\alpha$, $X \models \alpha$ iff $Y \models \alpha$. Also, $X$ is said to be dependent if there exists $\alpha \in X$ and $X \setminus \{ \alpha \} \models \alpha$. A set is independent if it is not dependent.

Consider a set of propositional atoms indexed with rational numbers, $\left \{ p_i \mid i \in \mathbb{Q}\right \}$. Now, consider the following set of formulae $\left \{ p_i \implies p_j \mid i < j \right \} $.
Now, is it the case that this set has no independent equivalent subset?

I am tempted to think that this is indeed the case and I try to start arguing like this, but I cannot seem to complete the argument.


*

*This set itself is dependent: Given $i < k < j$, we have $\left \{ p_i \implies p_k, p_k \implies p_j \right \} \models p_i \implies p_j$

*Suppose that there was an equivalent subset $S$ . We show that it cannot be independent. Firstly, this set cannot be empty. So, say it has to have some $p_i \implies p_j \in S$ and also for every $k$ between $i$ and $j$, we should be able to infer $p_i \implies p_k$ as well as $p_k\implies p_j$ from $S$. But ... 

 A: You've started correctly, and it's definitely true that $S\models p_i\rightarrow p_k$ and $S\models p_k\rightarrow p_j$. The trouble is that to conclude that $S$ is not independent, you need to show that $S'\models p_i\rightarrow p_k$ and $S'\models p_k\rightarrow p_j$, where $S' = S\setminus \{p_i\rightarrow p_j\}$.
One way to finish the proof is to use the following lemma. 
Let $P$ be a set of propositional variables. Suppose $\Sigma$ is a set of propositional formulas, where every formula in $\Sigma$ has the form $(p\rightarrow p')$, where $p,p'\in P$ are propositional variables from a set $P$. We say $\Sigma$ links $q$ to $q'$ if there is a sequence $p_1,\dots,p_n\in P$ for some $n\geq 1$, such that $p_1 = q$, $p_n = q'$, and $(p_i\rightarrow p_{i+1})\in \Sigma$ for all $1\leq i< n$. Note that in the case $n = 1$, the definition says that $\Sigma$ links $q$ to $q$ for any $q\in P$. 
Lemma: $\Sigma\models q\rightarrow q'$ if and only if $\Sigma$ links $q$ to $q'$. 
In other words, the preorder $\leq$ on the propositional variables defined by $q\leq q'$ iff $\Sigma\models q\rightarrow q'$ is exactly the reflexive and transitive closure of the relation $R$ on the propositional variables defined by $pRp'$ iff $(p\rightarrow p')\in \Sigma$. 
Proof: If $\Sigma$ links $q$ to $q'$, then it is clear that $\Sigma\models q\rightarrow q'$. For the converse, suppose $\Sigma\models q\rightarrow q'$. We define an interpretation of the proposition variables in $P$ by setting $p$ true if and only if $\Sigma$ links $q$ to $p$. Note that this interpretation makes $\Sigma$ true. Why? For all $(p\rightarrow p')\in \Sigma$, if $\Sigma$ links $q$ to $p$, then $\Sigma$ links $q$ to $p'$, by adding $p'$ to the end of the witnessing sequence. This interpretation also makes $q$ true, since $\Sigma$ links $q$ to $q$. So since $\Sigma\models q\rightarrow q'$, this interpretation makes $q'$ true. By definition, we conclude that $\Sigma$ links $q$ to $q'$. 

Now let's apply this to your problem. Suppose for contradiction that $\Sigma$ were an equivalent independent subset of your set $\{p_i\rightarrow p_j\mid i<j\text{ in }\mathbb{Q}\}$. As you argued, $\Sigma$ is nonempty, so there is some $(p_i\rightarrow p_j) \in \Sigma$. Now pick some $i<k<j$. Since $\Sigma$ is equivalent to the original set, $\Sigma\models p_i\rightarrow p_k$ and $\Sigma\models p_k\rightarrow p_j$. 
By the lemma, $\Sigma$ links $p_i$ to $p_k$ and $p_k$ to $p_j$. Let $\Sigma'$ be the finite number of formulas in $\Sigma$ contributing to these links. The key point is that $(p_i\rightarrow p_j)\notin \Sigma'$, since for every $(q\rightarrow q')\in \Sigma'$, either $q$ and $q'$ are both indexed by rationals $\leq k$ or both by rationals $\geq k$. 
Then $\Sigma'\models p_i\rightarrow p_k$ and $\Sigma'\models p_k\rightarrow p_j$, so $\Sigma'\models p_i \rightarrow p_j$. This shows that $\Sigma$ is not independent. 
