ILE Home Intuitionistic Logic Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  ILE Home  >  Th. List  >  xporderlem GIF version

Theorem xporderlem 5877
Description: Lemma for lexicographical ordering theorems. (Contributed by Scott Fenton, 16-Mar-2011.)
Hypothesis
Ref Expression
xporderlem.1 𝑇 = {⟨𝑥, 𝑦⟩ ∣ ((𝑥 ∈ (𝐴 × 𝐵) ∧ 𝑦 ∈ (𝐴 × 𝐵)) ∧ ((1st𝑥)𝑅(1st𝑦) ∨ ((1st𝑥) = (1st𝑦) ∧ (2nd𝑥)𝑆(2nd𝑦))))}
Assertion
Ref Expression
xporderlem (⟨𝑎, 𝑏𝑇𝑐, 𝑑⟩ ↔ (((𝑎𝐴𝑐𝐴) ∧ (𝑏𝐵𝑑𝐵)) ∧ (𝑎𝑅𝑐 ∨ (𝑎 = 𝑐𝑏𝑆𝑑))))
Distinct variable groups:   𝑥,𝐴,𝑦   𝑥,𝐵,𝑦   𝑥,𝑅,𝑦   𝑥,𝑆,𝑦   𝑥,𝑎,𝑦   𝑥,𝑏,𝑦   𝑥,𝑐,𝑦   𝑥,𝑑,𝑦
Allowed substitution hints:   𝐴(𝑎,𝑏,𝑐,𝑑)   𝐵(𝑎,𝑏,𝑐,𝑑)   𝑅(𝑎,𝑏,𝑐,𝑑)   𝑆(𝑎,𝑏,𝑐,𝑑)   𝑇(𝑥,𝑦,𝑎,𝑏,𝑐,𝑑)

Proof of Theorem xporderlem
StepHypRef Expression
1 df-br 3788 . . 3 (⟨𝑎, 𝑏𝑇𝑐, 𝑑⟩ ↔ ⟨⟨𝑎, 𝑏⟩, ⟨𝑐, 𝑑⟩⟩ ∈ 𝑇)
2 xporderlem.1 . . . 4 𝑇 = {⟨𝑥, 𝑦⟩ ∣ ((𝑥 ∈ (𝐴 × 𝐵) ∧ 𝑦 ∈ (𝐴 × 𝐵)) ∧ ((1st𝑥)𝑅(1st𝑦) ∨ ((1st𝑥) = (1st𝑦) ∧ (2nd𝑥)𝑆(2nd𝑦))))}
32eleq2i 2146 . . 3 (⟨⟨𝑎, 𝑏⟩, ⟨𝑐, 𝑑⟩⟩ ∈ 𝑇 ↔ ⟨⟨𝑎, 𝑏⟩, ⟨𝑐, 𝑑⟩⟩ ∈ {⟨𝑥, 𝑦⟩ ∣ ((𝑥 ∈ (𝐴 × 𝐵) ∧ 𝑦 ∈ (𝐴 × 𝐵)) ∧ ((1st𝑥)𝑅(1st𝑦) ∨ ((1st𝑥) = (1st𝑦) ∧ (2nd𝑥)𝑆(2nd𝑦))))})
41, 3bitri 182 . 2 (⟨𝑎, 𝑏𝑇𝑐, 𝑑⟩ ↔ ⟨⟨𝑎, 𝑏⟩, ⟨𝑐, 𝑑⟩⟩ ∈ {⟨𝑥, 𝑦⟩ ∣ ((𝑥 ∈ (𝐴 × 𝐵) ∧ 𝑦 ∈ (𝐴 × 𝐵)) ∧ ((1st𝑥)𝑅(1st𝑦) ∨ ((1st𝑥) = (1st𝑦) ∧ (2nd𝑥)𝑆(2nd𝑦))))})
5 vex 2605 . . . 4 𝑎 ∈ V
6 vex 2605 . . . 4 𝑏 ∈ V
75, 6opex 3986 . . 3 𝑎, 𝑏⟩ ∈ V
8 vex 2605 . . . 4 𝑐 ∈ V
9 vex 2605 . . . 4 𝑑 ∈ V
108, 9opex 3986 . . 3 𝑐, 𝑑⟩ ∈ V
11 eleq1 2142 . . . . . 6 (𝑥 = ⟨𝑎, 𝑏⟩ → (𝑥 ∈ (𝐴 × 𝐵) ↔ ⟨𝑎, 𝑏⟩ ∈ (𝐴 × 𝐵)))
12 opelxp 4394 . . . . . 6 (⟨𝑎, 𝑏⟩ ∈ (𝐴 × 𝐵) ↔ (𝑎𝐴𝑏𝐵))
1311, 12syl6bb 194 . . . . 5 (𝑥 = ⟨𝑎, 𝑏⟩ → (𝑥 ∈ (𝐴 × 𝐵) ↔ (𝑎𝐴𝑏𝐵)))
1413anbi1d 453 . . . 4 (𝑥 = ⟨𝑎, 𝑏⟩ → ((𝑥 ∈ (𝐴 × 𝐵) ∧ 𝑦 ∈ (𝐴 × 𝐵)) ↔ ((𝑎𝐴𝑏𝐵) ∧ 𝑦 ∈ (𝐴 × 𝐵))))
155, 6op1std 5800 . . . . . 6 (𝑥 = ⟨𝑎, 𝑏⟩ → (1st𝑥) = 𝑎)
1615breq1d 3797 . . . . 5 (𝑥 = ⟨𝑎, 𝑏⟩ → ((1st𝑥)𝑅(1st𝑦) ↔ 𝑎𝑅(1st𝑦)))
1715eqeq1d 2090 . . . . . 6 (𝑥 = ⟨𝑎, 𝑏⟩ → ((1st𝑥) = (1st𝑦) ↔ 𝑎 = (1st𝑦)))
185, 6op2ndd 5801 . . . . . . 7 (𝑥 = ⟨𝑎, 𝑏⟩ → (2nd𝑥) = 𝑏)
1918breq1d 3797 . . . . . 6 (𝑥 = ⟨𝑎, 𝑏⟩ → ((2nd𝑥)𝑆(2nd𝑦) ↔ 𝑏𝑆(2nd𝑦)))
2017, 19anbi12d 457 . . . . 5 (𝑥 = ⟨𝑎, 𝑏⟩ → (((1st𝑥) = (1st𝑦) ∧ (2nd𝑥)𝑆(2nd𝑦)) ↔ (𝑎 = (1st𝑦) ∧ 𝑏𝑆(2nd𝑦))))
2116, 20orbi12d 740 . . . 4 (𝑥 = ⟨𝑎, 𝑏⟩ → (((1st𝑥)𝑅(1st𝑦) ∨ ((1st𝑥) = (1st𝑦) ∧ (2nd𝑥)𝑆(2nd𝑦))) ↔ (𝑎𝑅(1st𝑦) ∨ (𝑎 = (1st𝑦) ∧ 𝑏𝑆(2nd𝑦)))))
2214, 21anbi12d 457 . . 3 (𝑥 = ⟨𝑎, 𝑏⟩ → (((𝑥 ∈ (𝐴 × 𝐵) ∧ 𝑦 ∈ (𝐴 × 𝐵)) ∧ ((1st𝑥)𝑅(1st𝑦) ∨ ((1st𝑥) = (1st𝑦) ∧ (2nd𝑥)𝑆(2nd𝑦)))) ↔ (((𝑎𝐴𝑏𝐵) ∧ 𝑦 ∈ (𝐴 × 𝐵)) ∧ (𝑎𝑅(1st𝑦) ∨ (𝑎 = (1st𝑦) ∧ 𝑏𝑆(2nd𝑦))))))
23 eleq1 2142 . . . . . 6 (𝑦 = ⟨𝑐, 𝑑⟩ → (𝑦 ∈ (𝐴 × 𝐵) ↔ ⟨𝑐, 𝑑⟩ ∈ (𝐴 × 𝐵)))
24 opelxp 4394 . . . . . 6 (⟨𝑐, 𝑑⟩ ∈ (𝐴 × 𝐵) ↔ (𝑐𝐴𝑑𝐵))
2523, 24syl6bb 194 . . . . 5 (𝑦 = ⟨𝑐, 𝑑⟩ → (𝑦 ∈ (𝐴 × 𝐵) ↔ (𝑐𝐴𝑑𝐵)))
2625anbi2d 452 . . . 4 (𝑦 = ⟨𝑐, 𝑑⟩ → (((𝑎𝐴𝑏𝐵) ∧ 𝑦 ∈ (𝐴 × 𝐵)) ↔ ((𝑎𝐴𝑏𝐵) ∧ (𝑐𝐴𝑑𝐵))))
278, 9op1std 5800 . . . . . 6 (𝑦 = ⟨𝑐, 𝑑⟩ → (1st𝑦) = 𝑐)
2827breq2d 3799 . . . . 5 (𝑦 = ⟨𝑐, 𝑑⟩ → (𝑎𝑅(1st𝑦) ↔ 𝑎𝑅𝑐))
2927eqeq2d 2093 . . . . . 6 (𝑦 = ⟨𝑐, 𝑑⟩ → (𝑎 = (1st𝑦) ↔ 𝑎 = 𝑐))
308, 9op2ndd 5801 . . . . . . 7 (𝑦 = ⟨𝑐, 𝑑⟩ → (2nd𝑦) = 𝑑)
3130breq2d 3799 . . . . . 6 (𝑦 = ⟨𝑐, 𝑑⟩ → (𝑏𝑆(2nd𝑦) ↔ 𝑏𝑆𝑑))
3229, 31anbi12d 457 . . . . 5 (𝑦 = ⟨𝑐, 𝑑⟩ → ((𝑎 = (1st𝑦) ∧ 𝑏𝑆(2nd𝑦)) ↔ (𝑎 = 𝑐𝑏𝑆𝑑)))
3328, 32orbi12d 740 . . . 4 (𝑦 = ⟨𝑐, 𝑑⟩ → ((𝑎𝑅(1st𝑦) ∨ (𝑎 = (1st𝑦) ∧ 𝑏𝑆(2nd𝑦))) ↔ (𝑎𝑅𝑐 ∨ (𝑎 = 𝑐𝑏𝑆𝑑))))
3426, 33anbi12d 457 . . 3 (𝑦 = ⟨𝑐, 𝑑⟩ → ((((𝑎𝐴𝑏𝐵) ∧ 𝑦 ∈ (𝐴 × 𝐵)) ∧ (𝑎𝑅(1st𝑦) ∨ (𝑎 = (1st𝑦) ∧ 𝑏𝑆(2nd𝑦)))) ↔ (((𝑎𝐴𝑏𝐵) ∧ (𝑐𝐴𝑑𝐵)) ∧ (𝑎𝑅𝑐 ∨ (𝑎 = 𝑐𝑏𝑆𝑑)))))
357, 10, 22, 34opelopab 4028 . 2 (⟨⟨𝑎, 𝑏⟩, ⟨𝑐, 𝑑⟩⟩ ∈ {⟨𝑥, 𝑦⟩ ∣ ((𝑥 ∈ (𝐴 × 𝐵) ∧ 𝑦 ∈ (𝐴 × 𝐵)) ∧ ((1st𝑥)𝑅(1st𝑦) ∨ ((1st𝑥) = (1st𝑦) ∧ (2nd𝑥)𝑆(2nd𝑦))))} ↔ (((𝑎𝐴𝑏𝐵) ∧ (𝑐𝐴𝑑𝐵)) ∧ (𝑎𝑅𝑐 ∨ (𝑎 = 𝑐𝑏𝑆𝑑))))
36 an4 551 . . 3 (((𝑎𝐴𝑏𝐵) ∧ (𝑐𝐴𝑑𝐵)) ↔ ((𝑎𝐴𝑐𝐴) ∧ (𝑏𝐵𝑑𝐵)))
3736anbi1i 446 . 2 ((((𝑎𝐴𝑏𝐵) ∧ (𝑐𝐴𝑑𝐵)) ∧ (𝑎𝑅𝑐 ∨ (𝑎 = 𝑐𝑏𝑆𝑑))) ↔ (((𝑎𝐴𝑐𝐴) ∧ (𝑏𝐵𝑑𝐵)) ∧ (𝑎𝑅𝑐 ∨ (𝑎 = 𝑐𝑏𝑆𝑑))))
384, 35, 373bitri 204 1 (⟨𝑎, 𝑏𝑇𝑐, 𝑑⟩ ↔ (((𝑎𝐴𝑐𝐴) ∧ (𝑏𝐵𝑑𝐵)) ∧ (𝑎𝑅𝑐 ∨ (𝑎 = 𝑐𝑏𝑆𝑑))))
Colors of variables: wff set class
Syntax hints:  wa 102  wb 103  wo 662   = wceq 1285  wcel 1434  cop 3403   class class class wbr 3787  {copab 3840   × cxp 4363  cfv 4926  1st c1st 5790  2nd c2nd 5791
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-mp 7  ax-ia1 104  ax-ia2 105  ax-ia3 106  ax-io 663  ax-5 1377  ax-7 1378  ax-gen 1379  ax-ie1 1423  ax-ie2 1424  ax-8 1436  ax-10 1437  ax-11 1438  ax-i12 1439  ax-bndl 1440  ax-4 1441  ax-13 1445  ax-14 1446  ax-17 1460  ax-i9 1464  ax-ial 1468  ax-i5r 1469  ax-ext 2064  ax-sep 3898  ax-pow 3950  ax-pr 3966  ax-un 4190
This theorem depends on definitions:  df-bi 115  df-3an 922  df-tru 1288  df-nf 1391  df-sb 1687  df-eu 1945  df-mo 1946  df-clab 2069  df-cleq 2075  df-clel 2078  df-nfc 2209  df-ral 2354  df-rex 2355  df-v 2604  df-sbc 2817  df-un 2978  df-in 2980  df-ss 2987  df-pw 3386  df-sn 3406  df-pr 3407  df-op 3409  df-uni 3604  df-br 3788  df-opab 3842  df-mpt 3843  df-id 4050  df-xp 4371  df-rel 4372  df-cnv 4373  df-co 4374  df-dm 4375  df-rn 4376  df-iota 4891  df-fun 4928  df-fv 4934  df-1st 5792  df-2nd 5793
This theorem is referenced by:  poxp  5878
  Copyright terms: Public domain W3C validator