0

I need some assistance with the following problem:

For $n \in \mathbb{N}$, let $A = \{a^1, a^2,a^3,...,a^n \}$ be a set and let $F$ be the set of all functions $f : A \rightarrow \{0,1 \}$ from $A$ to $\{0, 1\}$. What is the size of $F$? Now, for $P(A)$, the power set of $A$, consider the function $g: F \rightarrow P(A)$, defined as $g(f) = \{a \in A : f(a) = 1\}$. Is $g$ injective? Is $g$ surjective?

I just started to learn Functions and Relations in Mathematical Proof, and I think I still have a little difficulty grasping the core concept of many things in this chapter, so my assumptions maybe all wrong. My questions regarding this problem are the following:

1) "What is the size of $F$?" is it asking how many possible functions there are in $f : A \rightarrow \{0,1 \}$? In this case, I believe it should be $2^n$, since there are $2$ choices $\{0,1\}$ for each function and there are $n$ elements in set $A$.

2)$\mathbf{g(f) = \{a \in A : f(a) = 1\}}$. does $g(f)$ in this case means the composition of $f$ with $g: g \circ f$? I don't really see the point of it in this problem since we are asked to find the in/surjective of "$g$", not $g(f)$?

3) "is g injective?" I have two parts to this question:

a) according to the pigeonhold principle, it's not injective if $|F|>|P(A)|$, in this case, $|F| = |P(A)|$. I remember my prof. vaguely said that if $|A| = |B|$ where $A$ and $B$ are sets then $f : A \rightarrow B$ is bijective. But I have doubts about this, even if the cardinalities of two sets are equal, it's still possible that the function is not one-to-one, eg) $A = \{1,2,3\}, B = \{a,b,c\}, f: A \rightarrow B = \{(1,a),(2,b),(3,a)\}.$ This makes it neither injective nor surjective, so it's definitely not bijective. So I believe that the condition for bijective given that $|A| = |B|$ is that $f: A \rightarrow B$ must be injective in the first place. Is this correct?

b) if my assumption for the above is correct, then how do we determine if "g" is injective?

Thanks

Bergson
  • 1,647
Sam Kay
  • 117

1 Answers1

1

For 2, $F$ is a set of functions and $g$ takes one of these functions as its input. The range of $g$ is $P(A)$ with its value on a given function $f$ being a subset of $A$, which is a member of $P(A)$. There is no composition involved. The questions about whether $g$ is injective or surjective make sense in this context. Are there two functions that have the same image under $g$? Does every element of $P(A)$ have a preimage?

For a function to be injective, the cardinality of the range must be at least as large as the cardinality of the domain. You have that here. You said correctly that there were $2^n$ functions $A \to \{0,1\}$ and the cardinality of $P(A)$ is also $2^n$. You are correct that this does not guarantee that the function is injective. For finite sets if the cardinality of the domain and range are the same, as here, injective, surjective, and bijective are equivalent. If you prove one you prove all three.

To see if $g$ is injective, think about the definition. Is it possible there are two different functions in $F$, call them $f$ and $f'$, such that $g(f)=g(f')$

Ross Millikan
  • 374,822