Theorem ssrelf 32707

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 3908	. . 3 ⊢ Ⅎ𝑥 𝐴 ⊆ 𝐵
4		eqrelrd2.4	. . . . 5 ⊢ Ⅎ𝑦𝐴
5		eqrelrd2.6	. . . . 5 ⊢ Ⅎ𝑦𝐵
6	4, 5	nfss 3908	. . . 4 ⊢ Ⅎ𝑦 𝐴 ⊆ 𝐵
7		ssel 3909	. . . 4 ⊢ (𝐴 ⊆ 𝐵 → (⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵))
8	6, 7	alrimi 2225	. . 3 ⊢ (𝐴 ⊆ 𝐵 → ∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵))
9	3, 8	alrimi 2225	. 2 ⊢ (𝐴 ⊆ 𝐵 → ∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵))
10		eleq1 2827	. . . . . . . . . . 11 ⊢ (𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 ↔ ⟨𝑥, 𝑦⟩ ∈ 𝐴))
11		eleq1 2827	. . . . . . . . . . 11 ⊢ (𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐵 ↔ ⟨𝑥, 𝑦⟩ ∈ 𝐵))
12	10, 11	imbi12d 345	. . . . . . . . . 10 ⊢ (𝑧 = ⟨𝑥, 𝑦⟩ → ((𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵) ↔ (⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵)))
13	12	biimprcd 251	. . . . . . . . 9 ⊢ ((⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → (𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
14	13	2alimi 1819	. . . . . . . 8 ⊢ (∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → ∀𝑥∀𝑦(𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
15	4	nfcri 2893	. . . . . . . . . . . 12 ⊢ Ⅎ𝑦 𝑧 ∈ 𝐴
16	5	nfcri 2893	. . . . . . . . . . . 12 ⊢ Ⅎ𝑦 𝑧 ∈ 𝐵
17	15, 16	nfim 1903	. . . . . . . . . . 11 ⊢ Ⅎ𝑦(𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)
18	17	19.23 2223	. . . . . . . . . 10 ⊢ (∀𝑦(𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)) ↔ (∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
19	18	albii 1826	. . . . . . . . 9 ⊢ (∀𝑥∀𝑦(𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)) ↔ ∀𝑥(∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
20	1	nfcri 2893	. . . . . . . . . . 11 ⊢ Ⅎ𝑥 𝑧 ∈ 𝐴
21	2	nfcri 2893	. . . . . . . . . . 11 ⊢ Ⅎ𝑥 𝑧 ∈ 𝐵
22	20, 21	nfim 1903	. . . . . . . . . 10 ⊢ Ⅎ𝑥(𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)
23	22	19.23 2223	. . . . . . . . 9 ⊢ (∀𝑥(∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)) ↔ (∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
24	19, 23	bitri 276	. . . . . . . 8 ⊢ (∀𝑥∀𝑦(𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)) ↔ (∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
25	14, 24	sylib 219	. . . . . . 7 ⊢ (∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → (∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
26	25	com23 86	. . . . . 6 ⊢ (∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → (𝑧 ∈ 𝐴 → (∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → 𝑧 ∈ 𝐵)))
27	26	a2d 29	. . . . 5 ⊢ (∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → ((𝑧 ∈ 𝐴 → ∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩) → (𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
28	27	alimdv 1923	. . . 4 ⊢ (∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → (∀𝑧(𝑧 ∈ 𝐴 → ∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩) → ∀𝑧(𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵)))
29		df-rel 5625	. . . . 5 ⊢ (Rel 𝐴 ↔ 𝐴 ⊆ (V × V))
30		df-ss 3900	. . . . 5 ⊢ (𝐴 ⊆ (V × V) ↔ ∀𝑧(𝑧 ∈ 𝐴 → 𝑧 ∈ (V × V)))
31		elvv 5693	. . . . . . 7 ⊢ (𝑧 ∈ (V × V) ↔ ∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩)
32	31	imbi2i 337	. . . . . 6 ⊢ ((𝑧 ∈ 𝐴 → 𝑧 ∈ (V × V)) ↔ (𝑧 ∈ 𝐴 → ∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩))
33	32	albii 1826	. . . . 5 ⊢ (∀𝑧(𝑧 ∈ 𝐴 → 𝑧 ∈ (V × V)) ↔ ∀𝑧(𝑧 ∈ 𝐴 → ∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩))
34	29, 30, 33	3bitri 298	. . . 4 ⊢ (Rel 𝐴 ↔ ∀𝑧(𝑧 ∈ 𝐴 → ∃𝑥∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩))
35		df-ss 3900	. . . 4 ⊢ (𝐴 ⊆ 𝐵 ↔ ∀𝑧(𝑧 ∈ 𝐴 → 𝑧 ∈ 𝐵))
36	28, 34, 35	3imtr4g 297	. . 3 ⊢ (∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → (Rel 𝐴 → 𝐴 ⊆ 𝐵))
37	36	com12 32	. 2 ⊢ (Rel 𝐴 → (∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → 𝐴 ⊆ 𝐵))
38	9, 37	impbid2 227	1 ⊢ (Rel 𝐴 → (𝐴 ⊆ 𝐵 ↔ ∀𝑥∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵)))

Syntax hints:   → wi 4   ↔ wb 207  ∀wal 1545   = wceq 1547  ∃wex 1786  Ⅎwnf 1790   ∈ wcel 2119  Ⅎwnfc 2886  Vcvv 3431   ⊆ wss 3883  ⟨cop 4561   × cxp 5616  Rel wrel 5623

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1802  ax-4 1816  ax-5 1917  ax-6 1974  ax-7 2015  ax-8 2121  ax-9 2129  ax-10 2152  ax-11 2168  ax-12 2189  ax-ext 2711  ax-sep 5218  ax-pr 5362

This theorem depends on definitions:  df-bi 208  df-an 397  df-or 854  df-3an 1094  df-tru 1550  df-ex 1787  df-nf 1791  df-sb 2074  df-clab 2718  df-cleq 2731  df-clel 2814  df-nfc 2888  df-ral 3054  df-rab 3392  df-v 3433  df-un 3888  df-in 3890  df-ss 3900  df-sn 4556  df-pr 4558  df-op 4562  df-opab 5135  df-xp 5624  df-rel 5625

This theorem is referenced by:  eqrelrd2  32708