findcard

Description: Schema for induction on the cardinality of a finite set. The inductive hypothesis is that the result is true on the given set with any one element removed. The result is then proven to be true for all finite sets. (Contributed by Jeff Madsen, 2-Sep-2009)

	Ref	Expression
Hypotheses	findcard.1	$⊢ x = \emptyset \to (φ \leftrightarrow ψ)$
	findcard.2	$⊢ x = y ∖ \{z\} \to (φ \leftrightarrow χ)$
	findcard.3	$⊢ x = y \to (φ \leftrightarrow θ)$
	findcard.4	$⊢ x = A \to (φ \leftrightarrow τ)$
	findcard.5	$⊢ ψ$
	findcard.6	$⊢ y \in Fin \to (\forall z \in y χ \to θ)$
Assertion	findcard	$⊢ A \in Fin \to τ$

Proof

Step	Hyp	Ref	Expression
1		findcard.1	$⊢ x = \emptyset \to (φ \leftrightarrow ψ)$
2		findcard.2	$⊢ x = y ∖ \{z\} \to (φ \leftrightarrow χ)$
3		findcard.3	$⊢ x = y \to (φ \leftrightarrow θ)$
4		findcard.4	$⊢ x = A \to (φ \leftrightarrow τ)$
5		findcard.5	$⊢ ψ$
6		findcard.6	$⊢ y \in Fin \to (\forall z \in y χ \to θ)$
7		isfi	$⊢ x \in Fin \leftrightarrow \exists w \in ω x \approx w$
8		breq2	$⊢ w = \emptyset \to (x \approx w \leftrightarrow x \approx \emptyset)$
9	8	imbi1d	$⊢ w = \emptyset \to ((x \approx w \to φ) \leftrightarrow (x \approx \emptyset \to φ))$
10	9	albidv	$⊢ w = \emptyset \to (\forall x (x \approx w \to φ) \leftrightarrow \forall x (x \approx \emptyset \to φ))$
11		breq2	$⊢ w = v \to (x \approx w \leftrightarrow x \approx v)$
12	11	imbi1d	$⊢ w = v \to ((x \approx w \to φ) \leftrightarrow (x \approx v \to φ))$
13	12	albidv	$⊢ w = v \to (\forall x (x \approx w \to φ) \leftrightarrow \forall x (x \approx v \to φ))$
14		breq2	$⊢ w = suc v \to (x \approx w \leftrightarrow x \approx suc v)$
15	14	imbi1d	$⊢ w = suc v \to ((x \approx w \to φ) \leftrightarrow (x \approx suc v \to φ))$
16	15	albidv	$⊢ w = suc v \to (\forall x (x \approx w \to φ) \leftrightarrow \forall x (x \approx suc v \to φ))$
17		en0	$⊢ x \approx \emptyset \leftrightarrow x = \emptyset$
18	5 1	mpbiri	$⊢ x = \emptyset \to φ$
19	17 18	sylbi	$⊢ x \approx \emptyset \to φ$
20	19	ax-gen	$⊢ \forall x (x \approx \emptyset \to φ)$
21		peano2	$⊢ v \in ω \to suc v \in ω$
22		breq2	$⊢ w = suc v \to (y \approx w \leftrightarrow y \approx suc v)$
23	22	rspcev	$⊢ (suc v \in ω \land y \approx suc v) \to \exists w \in ω y \approx w$
24	21 23	sylan	$⊢ (v \in ω \land y \approx suc v) \to \exists w \in ω y \approx w$
25		isfi	$⊢ y \in Fin \leftrightarrow \exists w \in ω y \approx w$
26	24 25	sylibr	$⊢ (v \in ω \land y \approx suc v) \to y \in Fin$
27	26	3adant2	$⊢ (v \in ω \land \forall x (x \approx v \to φ) \land y \approx suc v) \to y \in Fin$
28		dif1en	$⊢ (v \in ω \land y \approx suc v \land z \in y) \to (y ∖ \{z\}) \approx v$
29	28	3expa	$⊢ ((v \in ω \land y \approx suc v) \land z \in y) \to (y ∖ \{z\}) \approx v$
30		vex	$⊢ y \in V$
31	30	difexi	$⊢ y ∖ \{z\} \in V$
32		breq1	$⊢ x = y ∖ \{z\} \to (x \approx v \leftrightarrow (y ∖ \{z\}) \approx v)$
33	32 2	imbi12d	$⊢ x = y ∖ \{z\} \to ((x \approx v \to φ) \leftrightarrow ((y ∖ \{z\}) \approx v \to χ))$
34	31 33	spcv	$⊢ \forall x (x \approx v \to φ) \to ((y ∖ \{z\}) \approx v \to χ)$
35	29 34	syl5com	$⊢ ((v \in ω \land y \approx suc v) \land z \in y) \to (\forall x (x \approx v \to φ) \to χ)$
36	35	ralrimdva	$⊢ (v \in ω \land y \approx suc v) \to (\forall x (x \approx v \to φ) \to \forall z \in y χ)$
37	36	imp	$⊢ ((v \in ω \land y \approx suc v) \land \forall x (x \approx v \to φ)) \to \forall z \in y χ$
38	37	an32s	$⊢ ((v \in ω \land \forall x (x \approx v \to φ)) \land y \approx suc v) \to \forall z \in y χ$
39	38	3impa	$⊢ (v \in ω \land \forall x (x \approx v \to φ) \land y \approx suc v) \to \forall z \in y χ$
40	27 39 6	sylc	$⊢ (v \in ω \land \forall x (x \approx v \to φ) \land y \approx suc v) \to θ$
41	40	3exp	$⊢ v \in ω \to (\forall x (x \approx v \to φ) \to (y \approx suc v \to θ))$
42	41	alrimdv	$⊢ v \in ω \to (\forall x (x \approx v \to φ) \to \forall y (y \approx suc v \to θ))$
43		breq1	$⊢ x = y \to (x \approx suc v \leftrightarrow y \approx suc v)$
44	43 3	imbi12d	$⊢ x = y \to ((x \approx suc v \to φ) \leftrightarrow (y \approx suc v \to θ))$
45	44	cbvalvw	$⊢ \forall x (x \approx suc v \to φ) \leftrightarrow \forall y (y \approx suc v \to θ)$
46	42 45	syl6ibr	$⊢ v \in ω \to (\forall x (x \approx v \to φ) \to \forall x (x \approx suc v \to φ))$
47	10 13 16 20 46	finds1	$⊢ w \in ω \to \forall x (x \approx w \to φ)$
48	47	19.21bi	$⊢ w \in ω \to (x \approx w \to φ)$
49	48	rexlimiv	$⊢ \exists w \in ω x \approx w \to φ$
50	7 49	sylbi	$⊢ x \in Fin \to φ$
51	4 50	vtoclga	$⊢ A \in Fin \to τ$

Metamath Proof Explorer

Theorem findcard

Proof