Theorem ssrelrn 5908

Description: If a relation is a subset of a cartesian product, then for each element of the range of the relation there is an element of the first set of the cartesian product which is related to the element of the range by the relation. (Contributed by AV, 24-Oct-2020.)

Assertion

Ref	Expression
ssrelrn	⊢ ((𝑅 ⊆ (𝐴 × 𝐵) ∧ 𝑌 ∈ ran 𝑅) → ∃𝑎 ∈ 𝐴 𝑎𝑅𝑌)

Distinct variable groups:   𝐴,𝑎   𝐵,𝑎   𝑅,𝑎   𝑌,𝑎

Proof of Theorem ssrelrn

Step	Hyp	Ref	Expression
1		elrng 5905	. . . . 5 ⊢ (𝑌 ∈ ran 𝑅 → (𝑌 ∈ ran 𝑅 ↔ ∃𝑎 𝑎𝑅𝑌))
2		ssbr 5192	. . . . . . . . . . 11 ⊢ (𝑅 ⊆ (𝐴 × 𝐵) → (𝑎𝑅𝑌 → 𝑎(𝐴 × 𝐵)𝑌))
3		brxp 5738	. . . . . . . . . . . 12 ⊢ (𝑎(𝐴 × 𝐵)𝑌 ↔ (𝑎 ∈ 𝐴 ∧ 𝑌 ∈ 𝐵))
4	3	simplbi 497	. . . . . . . . . . 11 ⊢ (𝑎(𝐴 × 𝐵)𝑌 → 𝑎 ∈ 𝐴)
5	2, 4	syl6 35	. . . . . . . . . 10 ⊢ (𝑅 ⊆ (𝐴 × 𝐵) → (𝑎𝑅𝑌 → 𝑎 ∈ 𝐴))
6	5	ancrd 551	. . . . . . . . 9 ⊢ (𝑅 ⊆ (𝐴 × 𝐵) → (𝑎𝑅𝑌 → (𝑎 ∈ 𝐴 ∧ 𝑎𝑅𝑌)))
7	6	adantl 481	. . . . . . . 8 ⊢ ((𝑌 ∈ ran 𝑅 ∧ 𝑅 ⊆ (𝐴 × 𝐵)) → (𝑎𝑅𝑌 → (𝑎 ∈ 𝐴 ∧ 𝑎𝑅𝑌)))
8	7	eximdv 1915	. . . . . . 7 ⊢ ((𝑌 ∈ ran 𝑅 ∧ 𝑅 ⊆ (𝐴 × 𝐵)) → (∃𝑎 𝑎𝑅𝑌 → ∃𝑎(𝑎 ∈ 𝐴 ∧ 𝑎𝑅𝑌)))
9	8	ex 412	. . . . . 6 ⊢ (𝑌 ∈ ran 𝑅 → (𝑅 ⊆ (𝐴 × 𝐵) → (∃𝑎 𝑎𝑅𝑌 → ∃𝑎(𝑎 ∈ 𝐴 ∧ 𝑎𝑅𝑌))))
10	9	com23 86	. . . . 5 ⊢ (𝑌 ∈ ran 𝑅 → (∃𝑎 𝑎𝑅𝑌 → (𝑅 ⊆ (𝐴 × 𝐵) → ∃𝑎(𝑎 ∈ 𝐴 ∧ 𝑎𝑅𝑌))))
11	1, 10	sylbid 240	. . . 4 ⊢ (𝑌 ∈ ran 𝑅 → (𝑌 ∈ ran 𝑅 → (𝑅 ⊆ (𝐴 × 𝐵) → ∃𝑎(𝑎 ∈ 𝐴 ∧ 𝑎𝑅𝑌))))
12	11	pm2.43i 52	. . 3 ⊢ (𝑌 ∈ ran 𝑅 → (𝑅 ⊆ (𝐴 × 𝐵) → ∃𝑎(𝑎 ∈ 𝐴 ∧ 𝑎𝑅𝑌)))
13	12	impcom 407	. 2 ⊢ ((𝑅 ⊆ (𝐴 × 𝐵) ∧ 𝑌 ∈ ran 𝑅) → ∃𝑎(𝑎 ∈ 𝐴 ∧ 𝑎𝑅𝑌))
14		df-rex 3069	. 2 ⊢ (∃𝑎 ∈ 𝐴 𝑎𝑅𝑌 ↔ ∃𝑎(𝑎 ∈ 𝐴 ∧ 𝑎𝑅𝑌))
15	13, 14	sylibr 234	1 ⊢ ((𝑅 ⊆ (𝐴 × 𝐵) ∧ 𝑌 ∈ ran 𝑅) → ∃𝑎 ∈ 𝐴 𝑎𝑅𝑌)

Syntax hints:   → wi 4   ∧ wa 395  ∃wex 1776   ∈ wcel 2106  ∃wrex 3068   ⊆ wss 3963   class class class wbr 5148   × cxp 5687  ran crn 5690

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1792  ax-4 1806  ax-5 1908  ax-6 1965  ax-7 2005  ax-8 2108  ax-9 2116  ax-ext 2706  ax-sep 5302  ax-nul 5312  ax-pr 5438

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-3an 1088  df-tru 1540  df-fal 1550  df-ex 1777  df-sb 2063  df-clab 2713  df-cleq 2727  df-clel 2814  df-ral 3060  df-rex 3069  df-rab 3434  df-v 3480  df-dif 3966  df-un 3968  df-ss 3980  df-nul 4340  df-if 4532  df-sn 4632  df-pr 4634  df-op 4638  df-br 5149  df-opab 5211  df-xp 5695  df-cnv 5697  df-dm 5699  df-rn 5700

This theorem is referenced by:  incistruhgr  29111