Metamath Proof Explorer

Theorem disjxwwlksn

Description: Sets of walks (as words) extended by an edge are disjunct if each set contains extensions of distinct walks. (Contributed by Alexander van der Vekens, 29-Jul-2018) (Revised by AV, 19-Apr-2021) (Revised by AV, 27-Oct-2022)

		Ref	Expression
	Hypotheses	wwlksnexthasheq.v	$⊢ V = Vtx (G)$
		wwlksnexthasheq.e	$⊢ E = Edg (G)$
	Assertion	disjxwwlksn	$⊢ \underset{y \in N WWalksN G}{Disj} \{x \in Word V \| (x prefix N = y \land y (0) = P \land \{lastS (y), lastS (x)\} \in E)\}$

Proof

Step	Hyp	Ref	Expression
1		wwlksnexthasheq.v	$⊢ V = Vtx (G)$
2		wwlksnexthasheq.e	$⊢ E = Edg (G)$
3		simp1	$⊢ (x prefix N = y \land y (0) = P \land \{lastS (y), lastS (x)\} \in E) \to x prefix N = y$
4	3	a1i	$⊢ x \in Word V \to ((x prefix N = y \land y (0) = P \land \{lastS (y), lastS (x)\} \in E) \to x prefix N = y)$
5	4	ss2rabi	$⊢ \{x \in Word V \| (x prefix N = y \land y (0) = P \land \{lastS (y), lastS (x)\} \in E)\} \subseteq \{x \in Word V \| x prefix N = y\}$
6	5	rgenw	$⊢ \forall y \in (N WWalksN G) \{x \in Word V \| (x prefix N = y \land y (0) = P \land \{lastS (y), lastS (x)\} \in E)\} \subseteq \{x \in Word V \| x prefix N = y\}$
7		disjwrdpfx	$⊢ \underset{y \in N WWalksN G}{Disj} \{x \in Word V \| x prefix N = y\}$
8		disjss2	$⊢ \forall y \in (N WWalksN G) \{x \in Word V \| (x prefix N = y \land y (0) = P \land \{lastS (y), lastS (x)\} \in E)\} \subseteq \{x \in Word V \| x prefix N = y\} \to (\underset{y \in N WWalksN G}{Disj} \{x \in Word V \| x prefix N = y\} \to \underset{y \in N WWalksN G}{Disj} \{x \in Word V \| (x prefix N = y \land y (0) = P \land \{lastS (y), lastS (x)\} \in E)\})$
9	6 7 8	mp2	$⊢ \underset{y \in N WWalksN G}{Disj} \{x \in Word V \| (x prefix N = y \land y (0) = P \land \{lastS (y), lastS (x)\} \in E)\}$