Theorem 32 (Peterson): {1, 2, 3} is the same size as {4, 5, 6}.
Proof:
Let X be the set {1,2,3} and Y be the set {4,5,6}. In order for X to be the same size as Y, a function f must be surjective and injective.
Let f(x) = Y be the function of X into Y. Let f = {(1,4), (2,5), (3,6)}. First we must prove this to be true!
If this is a function, then it must meet the three conditions:
1. f must be a subset of {1,2,3} x {4,5,6}.
The Cartesian product of X into Y is {(1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6)}.
The function f is a subset of the Cartesian product!
2. If p is an element of X, then it should be that p is the first coordinate of an element of f.
This is true because all the elements of X are first coordinates of the elements of f.
3. If (a,b) is an element of f and (a,c) is also an element of f, then b=c.
This condition does not apply because none of the first coordinates of the set are the same.
Therefore, f is a function of X into Y! In order for f to be a one-to-one function of X into Y, the element (a,c) is an element of f and (b,c) is
an element of f, then a=b. Our function f is injective because each element is distinct.
In order for the function f to be surjective, the range of f should be Y. If the set Y is {4,5,6} and the second coordinates of the elements of f
are ( ,4), ( ,5) and ( ,6), then the function is surjective! (X onto Y)
Hence, the sets {1,2,3} and {4,5,6} are the same size. QED
Theorem 33 (Flood): {1, 2} is not the same size as {1}.
True
Proof:
Let x be the set {1,2} and y be the set {1}
For x and y to be the same size the following criteria must be met:
1. There must exist some function f from x into y
2. f must be injective
3. f must be surjective
To discover if the exists a function from x into y we must look at three things:
1. Is f a subset of x into y (possible functions are f = {(1,1)}, {(2,1)}, and {(1,1),(2,1)})
2. if p is an element of x then there is an element of f so that its first coordinate is p (of the possibilities, would have to be {(1,1),(2,1)}
3. if (a,b) is an element of f and (a,c) is an element of f then b = c, {(1,1),(2,1)} satisfies this
So, Let the function f from {1,2} into {1} be f = {(1,1),(2,1)}
First we must test to see if it is injective, or one to one. This means that if there is an element (a,c) and an element (b,c), a = b.
Our function fails this test because 1 does not equal 2, therefore the Theorem is true.
QED
Theorem 34: {x : x is a positive integer} is the same size as {x:x is a negative integer}.
Let B = {x:x is a negative integer}.
Suppose f ={(x,y) y = -x and x is a positive integer}.
If f is a function from A into B it must fulfill the following conditions:
i. f is a subset of AxB
ii. If p is an element of A then p is the first coordinate of an ordered pair.
iii. If (a,b) is in the set f and (a,c) is in the set f, then b=c. Since b=-a and c=-a they are the same.
To determine if A and B are the same size, it must meet these requirement:
i. If (a,c) and (b,c) are in the set then a=b (injective) c=-a and c=-b then a=b
ii. The range of the function is B therefore if q is an element of B then q is the 2nd coordinate in an ordered pair.
QED {x : x is a positive integer} is the same size as {x:x is a negative integer}
Theorem 36 (Flood): If X and Y are sets and X is the same size as Y, then Y is the same size as X.
Proof: Let X and Y be sets so that X is the same size as Y. By definition there is a function f from X into Y so that f is injective and surjective.
Let g be f-1.
Because g is a function from Y into X that is injective and surjective, Y is the same size as X.
QED.
Theorem 39 (Gutierrez): {x:x is a positive integer and x is $\leq$100} is the same size as {x:x is an even positive integer and x is $\leq$200}.
Proof: Let X be the set {x:x is a positive integer and x is $\leq$100} and Y be the set {y:y is an even positive integer and y is $\leq$200}.
Let f be the function {(x,y):y=2*x and x is $\leq$100}
If f is a function from X into Y it must fulfill the following conditions:
i. f is a subset of X$\times$Y
The first condition is met because every element of f is an element of X$\times$Y.
ii. If p is an element of X, then p is the first coordinate of an ordered pair.
The second condition is met because every first coordinate is x, and x is an element of X.
iii. If (a,b) is in the set f and (a,c) is in the set f, then b=c. If a is x then both b and c are 2*x. b=c.
To determine if X and Y are the same size, the following requirements must be met:
i. If (a,c) and (b,c) are in the set, then a=b (injective). c=2*a and c=2*b, therefore a=b. First condition met.
ii. The range of the function is Y, therefore if q is an element of Y then q is the 2nd coordinate in an ordered pair. Second condition met.
QED. {x:x is a positive integer and x is $\leq$100} is the same size as {x:x is an even positive integer and x is $\leq$200}.
Theorem 40: {x:x is a positive integer} is the same size as {x:x is an even positive integer}.
Let A={x:x is a positive integer} and let B={x:x is an even positive integer}.
Suppose f={(x,y) y = 2*x}
If f is a function from A into B it must fulfill the following conditions:
i. f is a subset of AxB
p is an element of A and B, p is any integer (x,y) for the function y=2*x
ii. If p is an element of A then p is the first coordinate of an ordered pair.
A is any positive integer
iii. If (a,b) is in the set f and (a,c) is in the set f, then b=c.
If a is a positive integer, b and c are both twice that integer
To determine if A and B are the same size, it must meet these requirements:
i. If (a,c) and (b,c) are in the set then a=b (injective)
If c is and even positive integer, a and b are borth half that integer
ii. The range of the function is B (surjective)
B is y which is all even positive integers
QED {x : x is a positive integer} is the same size as {x:x is an even positive integer}
Take-home Test
1. Prove true or false: {x : x is a positive integer} is the same size as {x : x is an even positive integer}.
Let X= {x : x is a positive integer} and let Y= {x : x is an even integer}.
Let x be an element in X and let y be an element in Y.
In order for X to be the same size as Y, there must exist a one-to-one function of X onto Y.
f= {(x,y), y= 2x and x is an element of X}
For f to be a function from X into Y the following conditions must be met:
i. f is a subset of XxY
This f fulfills the condition. If p is an element in f then p is in XxY. p consists of an ordered pair (x,y).
ii. If q is an element of X then there is an element of f so that it’s first coordinate is q.
This function f fulfills the condition. Let q be a positive integer then (q,2q) is an element of f.
iii. If (a,b) is in the set f and (a,c) is in the set f, then b=c.
This function f fulfills the condition. a is an element of X, and b=2a and c=2a therefore b=c.
Now that it has been established that f is a function, we must prove that f is a function, we must prove that f is a one-to-one function from X onto Y. This is done by proving that f is injective and surjective. The following requirements must be met:
i. In order for f to be injective or a one-to-one function if (a,c) is a element of f and (b,c) is an element of f then a=b.
c is an element of Y and b=c/2 and a=c/2 therefore b=a.
ii. In order for f to be surjective or a function fron X onto Y, then the range of f is Y.
Let r be any element in Y. In the case of the function f the range of f is r because all values are (q,r) so that no ordered pair is outside of r.
Therefore f is a one-to-one function from X onto Y, proving that X is the same size as Y. QED