Theorem ssrelf 33263

Description: A subclass relationship depends only on a relation's ordered pairs. Theorem 3.2(i) of [Monk1] p. 33. (Contributed by NM, 2-Aug-1994.) (Proof shortened by Andrew Salmon, 27-Aug-2011.) (Revised by Thierry Arnoux, 6-Nov-2017.)

Hypotheses

Ref	Expression
eqrelrd2.1	⊢ Ⅎ𝑥𝜑
eqrelrd2.2	⊢ Ⅎ𝑦𝜑
eqrelrd2.3	⊢ Ⅎ𝑥𝐴
eqrelrd2.4	⊢ Ⅎ𝑦𝐴
eqrelrd2.5	⊢ Ⅎ𝑥𝐵
eqrelrd2.6	⊢ Ⅎ𝑦𝐵

Assertion

Ref	Expression
ssrelf	⊢ (Rel 𝐴 → (𝐴 ⊆ 𝐵 ↔ ∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵)))

Distinct variable group:   𝑥,𝑦

Allowed substitution hints:   𝜑(𝑥, 𝑦)   𝐴(𝑥, 𝑦)   𝐵(𝑥, 𝑦)

Proof of Theorem ssrelf

Dummy variable 𝑧 is distinct from all other variables.

Step	Hyp	Ref	Expression
1		eqrelrd2.3	. . . 4 ⊢ Ⅎ𝑥𝐴
2		eqrelrd2.5	. . . 4 ⊢ Ⅎ𝑥𝐵
3	1, 2	nfss 3905	. . 3 ⊢ Ⅎ𝑥 𝐴 ⊆ 𝐵
4		eqrelrd2.4	. . . . 5 ⊢ Ⅎ𝑦𝐴
5		eqrelrd2.6	. . . . 5 ⊢ Ⅎ𝑦𝐵
6	4, 5	nfss 3905	. . . 4 ⊢ Ⅎ𝑦 𝐴 ⊆ 𝐵
7		ssel 3906	. . . 4 ⊢ (𝐴 ⊆ 𝐵 → (⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵))
8	6, 7	alrimi 2252	. . 3 ⊢ (𝐴 ⊆ 𝐵 → ∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵))
9	3, 8	alrimi 2252	. 2 ⊢ (𝐴 ⊆ 𝐵 → ∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵))
10		eleq1 2851	. . . . . . . . . . 11 ⊢ (𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 ↔ ⟨𝑥, 𝑦⟩ ∈ 𝐴))
11		eleq1 2851	. . . . . . . . . . 11 ⊢ (𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐵 ↔ ⟨𝑥, 𝑦⟩ ∈ 𝐵))
12	10, 11	imbi12d 347	. . . . . . . . . 10 ⊢ (𝑧 = ⟨𝑥, 𝑦⟩ → ((𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵) ↔ (⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵)))
13	12	biimprcd 253	. . . . . . . . 9 ⊢ ((⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → (𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
14	13	2alimi 1844	. . . . . . . 8 ⊢ (∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → ∀𝑥∀𝑦(𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
15	4	nfcri 2917	. . . . . . . . . . . 12 ⊢ Ⅎ𝑦 𝑧 ∈ 𝐴
16	5	nfcri 2917	. . . . . . . . . . . 12 ⊢ Ⅎ𝑦 𝑧 ∈ 𝐵
17	15, 16	nfim 1930	. . . . . . . . . . 11 ⊢ Ⅎ𝑦(𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)
18	17	19.23 2250	. . . . . . . . . 10 ⊢ (∀𝑦(𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)) ↔ (∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
19	18	albii 1851	. . . . . . . . 9 ⊢ (∀𝑥∀𝑦(𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)) ↔ ∀𝑥(∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
20	1	nfcri 2917	. . . . . . . . . . 11 ⊢ Ⅎ𝑥 𝑧 ∈ 𝐴
21	2	nfcri 2917	. . . . . . . . . . 11 ⊢ Ⅎ𝑥 𝑧 ∈ 𝐵
22	20, 21	nfim 1930	. . . . . . . . . 10 ⊢ Ⅎ𝑥(𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)
23	22	19.23 2250	. . . . . . . . 9 ⊢ (∀𝑥(∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)) ↔ (∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
24	19, 23	bitri 278	. . . . . . . 8 ⊢ (∀𝑥∀𝑦(𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)) ↔ (∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
25	14, 24	sylib 221	. . . . . . 7 ⊢ (∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → (∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
26	25	com23 87	. . . . . 6 ⊢ (∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → (𝑧 ∈ 𝐴 → (∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → 𝑧 ∈ 𝐵)))
27	26	a2d 30	. . . . 5 ⊢ (∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → ((𝑧 ∈ 𝐴 → ∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩) → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
28	27	alimdv 1950	. . . 4 ⊢ (∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → (∀𝑧(𝑧 ∈ 𝐴 → ∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩) → ∀𝑧(𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
29		df-rel 5661	. . . . 5 ⊢ (Rel 𝐴 ↔ 𝐴 ⊆ (V × V))
30		df-ss 3900	. . . . 5 ⊢ (𝐴 ⊆ (V × V) ↔ ∀𝑧(𝑧 ∈ 𝐴 → 𝑧 ∈ (V × V)))
31		elvv 5729	. . . . . . 7 ⊢ (𝑧 ∈ (V × V) ↔ ∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩)
32	31	imbi2i 339	. . . . . 6 ⊢ ((𝑧 ∈ 𝐴 → 𝑧 ∈ (V × V)) ↔ (𝑧 ∈ 𝐴 → ∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩))
33	32	albii 1851	. . . . 5 ⊢ (∀𝑧(𝑧 ∈ 𝐴 → 𝑧 ∈ (V × V)) ↔ ∀𝑧(𝑧 ∈ 𝐴 → ∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩))
34	29, 30, 33	3bitri 300	. . . 4 ⊢ (Rel 𝐴 ↔ ∀𝑧(𝑧 ∈ 𝐴 → ∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩))
35		df-ss 3900	. . . 4 ⊢ (𝐴 ⊆ 𝐵 ↔ ∀𝑧(𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵))
36	28, 34, 35	3imtr4g 299	. . 3 ⊢ (∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → (Rel 𝐴 → 𝐴 ⊆ 𝐵))
37	36	com12 33	. 2 ⊢ (Rel 𝐴 → (∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → 𝐴 ⊆ 𝐵))
38	9, 37	impbid2 229	1 ⊢ (Rel 𝐴 → (𝐴 ⊆ 𝐵 ↔ ∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵)))

This proof depends on syntax axioms:   → wi 4   ↔ wb 209  ∀wal 1567   = wceq 1569  ∃wex 1811  Ⅎwnf 1815   ∈ wcel 2146  Ⅎwnfc 2910  Vcvv 3453   ⊆ wss 3899  ⟨cop 4837   × cxp 5652  Rel wrel 5659

This proof depends on axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1827  ax-4 1841  ax-5 1944  ax-6 2001  ax-7 2042  ax-8 2148  ax-9 2156  ax-10 2179  ax-11 2196  ax-12 2215  ax-ext 2735  ax-sep 5251  ax-pr 5394

This proof depends on definitions:  df-bi 210  df-an 402  df-or 862  df-3an 1105  df-tru 1572  df-ex 1812  df-nf 1816  df-sb 2101  df-clab 2742  df-cleq 2755  df-clel 2838  df-nfc 2912  df-ral 3080  df-rex 3090  df-rab 3416  df-v 3455  df-ss 3900  df-in 4093  df-un 4153  df-sn 4588  df-pr 4590  df-op 4838  df-opab 5170  df-xp 5660  df-rel 5661

This theorem is used by:  eqrelrd2  33264