I need to prove I formula by induction, but I don't know how to do it.
The problem is :
Given a set S, prove by induction
∀X·X∈F(S)⇒(∀Y ·Y ∈F(S)⇒card(X×Y)=card(X)∗card(Y))
How should I start?
Asked
Active
Viewed 45 times
0
-
what is $F(S)$? – ziggurism Nov 16 '17 at 16:19
-
It is for Finite(S) – Antoine Grandchamp Nov 16 '17 at 16:23
-
finite subsets of $S$? – ziggurism Nov 16 '17 at 16:25
-
Yes, at least that is what I understand – Antoine Grandchamp Nov 16 '17 at 16:26
-
what is your definition of card? – ziggurism Nov 16 '17 at 16:27
-
it returns the cardinality of the set – Antoine Grandchamp Nov 16 '17 at 16:30
-
1It sounds like you are simply trying to prove the rule of product. All this talk about $F(S)$ and such is muddying the statement. A more compact statement is "Given two finite sets $X$ and $Y$ one has $|X\times Y|=|X|\times|Y|$." To prove this, I suggest running double-induction, the outer loop on the number of elements in $X$ and the inner loop on the number of elements in $Y$. To make matters easier, you could assume without loss of generality that $X={1,2,3,4,\dots,x}$ and $Y={1,2,3,\dots,y}$. To fully generalize, use bijections. – JMoravitz Nov 16 '17 at 16:34
-
One of the key observations to make here, is that ${1,2,\dots,x}\times{1,2,\dots,y,y+1} = \left({1,2,\dots,x}\times{1,2,\dots,y}\right)\cup\left({1,2,\dots,x}\times {y+1}\right)$, at which point we can use the rule of sum (or a short proof for that as well) along with our induction hypothesis and a bit of middle-school algebra to get what we wanted. – JMoravitz Nov 16 '17 at 16:39