Mathbox for Thierry Arnoux < Previous   Next > Nearby theorems Mirrors  >  Home  >  MPE Home  >  Th. List  >   Mathboxes  >  ssrelf Structured version   Visualization version   GIF version

Theorem ssrelf 29397
 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.
StepHypRef Expression
1 eqrelrd2.3 . . . 4 𝑥𝐴
2 eqrelrd2.5 . . . 4 𝑥𝐵
31, 2nfss 3588 . . 3 𝑥 𝐴𝐵
4 eqrelrd2.4 . . . . 5 𝑦𝐴
5 eqrelrd2.6 . . . . 5 𝑦𝐵
64, 5nfss 3588 . . . 4 𝑦 𝐴𝐵
7 ssel 3589 . . . 4 (𝐴𝐵 → (⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵))
86, 7alrimi 2080 . . 3 (𝐴𝐵 → ∀𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵))
93, 8alrimi 2080 . 2 (𝐴𝐵 → ∀𝑥𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵))
10 eleq1 2687 . . . . . . . . . . 11 (𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧𝐴 ↔ ⟨𝑥, 𝑦⟩ ∈ 𝐴))
11 eleq1 2687 . . . . . . . . . . 11 (𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧𝐵 ↔ ⟨𝑥, 𝑦⟩ ∈ 𝐵))
1210, 11imbi12d 334 . . . . . . . . . 10 (𝑧 = ⟨𝑥, 𝑦⟩ → ((𝑧𝐴𝑧𝐵) ↔ (⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵)))
1312biimprcd 240 . . . . . . . . 9 ((⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → (𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧𝐴𝑧𝐵)))
14132alimi 1738 . . . . . . . 8 (∀𝑥𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → ∀𝑥𝑦(𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧𝐴𝑧𝐵)))
154nfcri 2756 . . . . . . . . . . . 12 𝑦 𝑧𝐴
165nfcri 2756 . . . . . . . . . . . 12 𝑦 𝑧𝐵
1715, 16nfim 1823 . . . . . . . . . . 11 𝑦(𝑧𝐴𝑧𝐵)
181719.23 2078 . . . . . . . . . 10 (∀𝑦(𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧𝐴𝑧𝐵)) ↔ (∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧𝐴𝑧𝐵)))
1918albii 1745 . . . . . . . . 9 (∀𝑥𝑦(𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧𝐴𝑧𝐵)) ↔ ∀𝑥(∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧𝐴𝑧𝐵)))
201nfcri 2756 . . . . . . . . . . 11 𝑥 𝑧𝐴
212nfcri 2756 . . . . . . . . . . 11 𝑥 𝑧𝐵
2220, 21nfim 1823 . . . . . . . . . 10 𝑥(𝑧𝐴𝑧𝐵)
232219.23 2078 . . . . . . . . 9 (∀𝑥(∃𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧𝐴𝑧𝐵)) ↔ (∃𝑥𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧𝐴𝑧𝐵)))
2419, 23bitri 264 . . . . . . . 8 (∀𝑥𝑦(𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧𝐴𝑧𝐵)) ↔ (∃𝑥𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧𝐴𝑧𝐵)))
2514, 24sylib 208 . . . . . . 7 (∀𝑥𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → (∃𝑥𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → (𝑧𝐴𝑧𝐵)))
2625com23 86 . . . . . 6 (∀𝑥𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → (𝑧𝐴 → (∃𝑥𝑦 𝑧 = ⟨𝑥, 𝑦⟩ → 𝑧𝐵)))
2726a2d 29 . . . . 5 (∀𝑥𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → ((𝑧𝐴 → ∃𝑥𝑦 𝑧 = ⟨𝑥, 𝑦⟩) → (𝑧𝐴𝑧𝐵)))
2827alimdv 1843 . . . 4 (∀𝑥𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → (∀𝑧(𝑧𝐴 → ∃𝑥𝑦 𝑧 = ⟨𝑥, 𝑦⟩) → ∀𝑧(𝑧𝐴𝑧𝐵)))
29 df-rel 5111 . . . . 5 (Rel 𝐴𝐴 ⊆ (V × V))
30 dfss2 3584 . . . . 5 (𝐴 ⊆ (V × V) ↔ ∀𝑧(𝑧𝐴𝑧 ∈ (V × V)))
31 elvv 5167 . . . . . . 7 (𝑧 ∈ (V × V) ↔ ∃𝑥𝑦 𝑧 = ⟨𝑥, 𝑦⟩)
3231imbi2i 326 . . . . . 6 ((𝑧𝐴𝑧 ∈ (V × V)) ↔ (𝑧𝐴 → ∃𝑥𝑦 𝑧 = ⟨𝑥, 𝑦⟩))
3332albii 1745 . . . . 5 (∀𝑧(𝑧𝐴𝑧 ∈ (V × V)) ↔ ∀𝑧(𝑧𝐴 → ∃𝑥𝑦 𝑧 = ⟨𝑥, 𝑦⟩))
3429, 30, 333bitri 286 . . . 4 (Rel 𝐴 ↔ ∀𝑧(𝑧𝐴 → ∃𝑥𝑦 𝑧 = ⟨𝑥, 𝑦⟩))
35 dfss2 3584 . . . 4 (𝐴𝐵 ↔ ∀𝑧(𝑧𝐴𝑧𝐵))
3628, 34, 353imtr4g 285 . . 3 (∀𝑥𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → (Rel 𝐴𝐴𝐵))
3736com12 32 . 2 (Rel 𝐴 → (∀𝑥𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵) → 𝐴𝐵))
389, 37impbid2 216 1 (Rel 𝐴 → (𝐴𝐵 ↔ ∀𝑥𝑦(⟨𝑥, 𝑦⟩ ∈ 𝐴 → ⟨𝑥, 𝑦⟩ ∈ 𝐵)))
 Colors of variables: wff setvar class Syntax hints:   → wi 4   ↔ wb 196  ∀wal 1479   = wceq 1481  ∃wex 1702  Ⅎwnf 1706   ∈ wcel 1988  Ⅎwnfc 2749  Vcvv 3195   ⊆ wss 3567  ⟨cop 4174   × cxp 5102  Rel wrel 5109 This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1720  ax-4 1735  ax-5 1837  ax-6 1886  ax-7 1933  ax-9 1997  ax-10 2017  ax-11 2032  ax-12 2045  ax-13 2244  ax-ext 2600  ax-sep 4772  ax-nul 4780  ax-pr 4897 This theorem depends on definitions:  df-bi 197  df-or 385  df-an 386  df-3an 1038  df-tru 1484  df-ex 1703  df-nf 1708  df-sb 1879  df-clab 2607  df-cleq 2613  df-clel 2616  df-nfc 2751  df-ral 2914  df-v 3197  df-dif 3570  df-un 3572  df-in 3574  df-ss 3581  df-nul 3908  df-if 4078  df-sn 4169  df-pr 4171  df-op 4175  df-opab 4704  df-xp 5110  df-rel 5111 This theorem is referenced by:  eqrelrd2  29398
 Copyright terms: Public domain W3C validator