Our server costs ~$56 per month to run. Please consider donating or becoming a Patron to help keep the site running. Help us gain new members by following us on Twitter and liking our page on Facebook!
February 1, 2017 at 8:42 pm (This post was last modified: February 1, 2017 at 10:31 pm by Kernel Sohcahtoa.)
Consider the function θ: P(ℤ) → P(ℤ) defined as θ(X)=X^c (note ℤ is the set of all integers). We can also rephrase this as the function θ from the power set of ℤ to the power set of ℤ is defined as the function θ whose input set X produces an output set equal to the complement of X (or X^c). Now determine if θ is injective, surjective, and bijective. This problem was retrieved via Hammack, Richard. (2013) Book of Proof, 2nd ed. Virginia commonwealth University: published by Richard Hammack, pg 205.
Definitions and Terms
Injective, surjective, and bijective functions.
Suppose we have a function f: A→B.
To show that f is injective, we must show that if x does not equal y for any x,y in A, then this implies that f(x) does not equal f(y) in B. An easier way to show if f is injective is if we take the contrapositive of the approach stated above, which is if f(x)=f(y) then x=y. Thus, we can show that f is injective if we can demonstrate that f(x)=f(y) implies that x=y.
To show that f is surjective. We need to find an a in A or a ∈ A for which f(a)=b∈B. In other words, for every b output that is in the range of B, we must be able to link them to some a input in A which yields f(a)=b.
To show if a function is bijective, we will need to show that f is both injective and surjective. For example, the function f: ℤ→ℤ defined as f(x)=x is a bijective function, as every x value will have exactly one y value in the range (injective), which means that every y value in the range can be mapped to some x value in the domain (surjective); whereas the function f: ℕ→ℤ defined as f(x)=x would be injective and not surjective.* Clearly, every x value in the domain will have exactly one y value in the range, so f is injective. However, Let -2∈ ℤ. Then there is no x∈ ℕ which produces -2∈ℤ. Hence, f is not surjective.
*note ℕ is the set of all natural numbers or the set of all positive integers
The complement
Suppose we have some set S that is a subset of some universal set U. Then the complement of S or S^c is the set containing all of the elements that are not in S or U − S.
The law of double complements
(x^c)^c=x
The Power Set
Suppose that we have some set S. The power set of S or P(S) is the set that contains all of the subsets of S. For example, let S={a,b}. Since S contains two elements (or, it’s cardinality or order is 2) then we can determine the number of elements in the power set from the following equation: the order of P(S) equals 2^n, where n represents the order of the set S. Thus, in our example, the number of elements in P(S) is 2^2=4. These elements would be ∅ (the empty set), {a}, {b}, {a,b}.* Hence, P(S)={ ∅, {a}, {b}, {a,b}}.
*please note that a (or b for that matter) is an element of S but it is not an element of P(S). Remember that P(S) is the set containing all of the subsets of S; thus, the elements of P(S) are the various subsets in S. As a result, {a} or the set containing a, would be an element in P(S).
Proof (My attempt)
i)Let X and Y be two subsets of ℤ or X,Y ⊆ ℤ. Then X and Y are two elements in P(ℤ) or X,Y ∈ P(ℤ). Now, if θ(X)= θ(Y), then this means that X^c=Y^c. Now, from the law of double complements, we can take the complement of both sides of the equation which yields (X^c)^c=(Y^c)^c or X=Y. So, θ is injective.
ii)Let X⊆ ℤ. Then X ∈ P(ℤ). Now suppose a is an element in X. Now, this means that the set containing a or {a} is in P(X). Since P(X) is the set of all subsets in X, then P(X) is a subset of P(ℤ) or the set containing all of the subsets in ℤ; thus, {a} is also an element in P(ℤ). Now, since θ(X)=X^c, this means that inputting X ∈ P(ℤ) into θ will produce an output set equal to X^c∈ P(ℤ) containing all of those elements that are not in X or ℤ−X. Consequently, θ would not be able to produce {a}. However, we have established that {a}∈ P(ℤ). Therefore, there is no X for which θ(X)={a}. Hence, θ is not surjective.
iii) From parts one and two, we can conclude that θ is injective but not surjective, which means that θ is not a bijective function.