Quote: "Imagine a set of numbers x1, x2, x3, ... xN, ie. a set of n different numbers, let's assume that they are all equal, as in, any set of size n has all the numbers equal, so x1 = x2 = ... = xN
"
CASE 1.1:
-----------
Let the set A = {x1, x2, x3 ... xN}
You initally start with the assumption that the set A contains all numbers different.
You then state that the same set A has all numbers equal.
In symbolic logic terms your first assumption can be expressed as
(A) ^ (~A) ... (1)
where ^ is the logical AND operator and ~ is the logical NOT operator
Statement (1) is known as a contradiction.
You cannot extend your proof beyond this first statement because it has a truth value FALSE
If you now start of with the assumption that the set A has all numbers EQUAL, we have
for x1 = x2 = x3 = ... = xN = K where K is a constant
Set A then reduces to A = {K, K, K ... K} where all N elements of the set have the value K ...(2)
Since set theory requires that no two elements in a set can have the same value the set A further reduces to A = {K}
The cardinal number of the set A is 1 - where the cardinal number is the number of elements in the set.
("size of the set" is an improper way to describe the number of elements of a set)
Quote: "Now consider a set one bigger than that (size n+1) - x1, x2, x3, ... xN, xN + 1, we can split this into two sets of size n: x1, x2, ... xN - and - x2, x3, ... xN + 1, so we have, x1 = x2 = ... = xN and x2 = x3 = ... = xN + 1, which means that x1 = x2 = x3 = ... = xN = xN + 1.
"
If you now consider another set B = {x1, x2, x3 ... xN, xN+1}
and obtain subsets B1 = {x1, x2, x3 ... xN} and B2 = {x2, x3, x4 ... xN+1}
using the same logic as in statement (2), we have
B = {K}
i.e. The inductive proof immediately collapses, if you assume that the numbers are all equal because you get the same result for N =1, N=2, ......
viz. the sets B1 and B2 are not subsets of B of cardinal number N , where B has a cardinal number N+1
All three sets B, B1, B2 have a single element K and all therefore have the cardinal number 1
But we know that for a set containing any single element, that element has to be equal to itself.
You have therefore NOT PROVED by Induction that a set of N equal numbers, would result in a set of N+1 equal numbers, but that every number is equal to itself, which is a tautology in any case.
The inductive proof is therefore not valid for the set of EQUAL numbers for all values of N.
CASE 1.2
-------------
If you now abort the set theoretic notation and just state the problem as
If x1 = x2 = ... = xN, then by induction it is true for all N
When you arrive at the statement x1 = x2 = ... xN+1
and further break this into two equations
x1 = x2 = ... xN and x2 = x3 = ... xN+1
it is true then that x1 = x2 = ... xN+1 and the inductive proof is valid for EQUAL numbers for all values of N and not for the SET OF EQUAL numbers for all values of N.
(Note that in this case the proof does not collapse even for N=1 because x1 = x2)
CASE 2:
-----------
If we now start with the assumption that A is a set of N numbers that are DIFFERENT
the inductive proof holds true.
It is also not true in this case that for N = 2 the subsets B1 and B2 do not intersect.
For N = 2, B = {x1, x2, x3}
B1 = {x1, x2} and B2 = {x2, x3}
As you can see B1 and B2 intersect at the element x2
In fact B1 and B2 intersect for all values of N >= 2
For N = 1 we have B = {x1, x2} , B1 = {x1} and B2 = {x2}
But since we originally assumed that x1 and x2 are different numbers, the proof by induction holds for the set of N numbers that are different, because x1 does not have to be equal to x2, and the sets do not therefore have to intersect, since we no longer have to show that x1 = x2
The conclusion is that for any set of N numbers that are different, by induction, any set of N+1 numbers will be DIFFERENT
The inductive proof is valid for the set of DIFFERENT numbers for all values of N.
CASE 3:
-----------
If you however decide to prove by induction the CONTRADICTION that the set of N different numbers that are all equal , would result in a set of N+1 different numbers that are all equal, you would first have to prove that 1 = 2 , for the inital case and then proceed further by induction. This is because CASE1.1 and CASE2 show that the method of proof by induction fails.
This brings us back to having to establish whether the first proof is valid.
viz.
a = b
...
a(b-a) = (b-a)(b+a) ...(3)
...
Note that in equation (3) the bracket term evaluates to 0, since a = b
To cancel the factor (a-b) on both sides of the equation we have to multiply both sides by the multiplicative inverse of (a-b), viz. 1/(a-b)
But since a-b = 0 , we are attempting to multiply both sides of the equation by the multiplicative inverse of 0. This is not possible as 1/0 is undefined. We therefore cannot proceed beyond equation (3)
with the proof.
We therefore cannot prove that 1 = 2, 2 = 3 and so on.
If we cannot prove for the inital case that 1 = 2 , we cannot proceed to prove by induction that the set of N different numbers that are all equal, would be true for the case N+1 also, since the inital case for 1 = 2 has not been established.
CONCLUSION:
---------------------
From CASE1, CASE2 and CASE3 we have not shown anywhere that the set of N DIFFERENT numbers are all EQUAL. How can we then, using proof by induction, extend an argument that isn't true in the first place.
