Are there some good overviews of basic facts about images and inverse images of sets under functions?
[Math] Overview of basic results about images and preimages
elementary-set-theoryfaqfunctionsonline-resourcesreference-request
Related Solutions
$\newcommand{\alnul}{\aleph_0}\newcommand{\mfr}[1]{\mathfrak{#1}}\newcommand{\Ra}{\Rightarrow}\newcommand{\card}[1]{\left|#1\right|}\newcommand{\powerset}[1]{\mathcal P(#1)}\newcommand{\Lra}{\Leftrightarrow}\newcommand{\Zobr}[3]{#1\colon#2\to#3}$I have no doubt that you there are many useful online resources for these, but many such identities are available here at MSE, together with their proofs.
I'll give a list of some basic results on cardinal arithmetics and I'll add links to results, which have proofs here at MSE. I am making this CW, so feel free to add more identities and pointers to further useful questions and answers.
In the identities bellow, $a$, $b$, $c$ denote arbitrary cardinals, $X$ is an arbitrary set, $\alnul$ is the cardinality of $\mathbb N$ and $\mfr c=2^{\alnul}$. Cardinality of a set $X$ is denoted by $\card X$ and $\powerset X$ is the notation of the power set of $X$.
Equality of cardinal numbers is defined as follows: $$|A|=|B| \Lra \text{ there exists a bijection }\Zobr fAB.$$ Inequality of cardinal numbers is defined as follows: $$|A|\le|B| \Lra \text{ there exists an injective function }\Zobr fAB.$$ The definitions of the operations on cardinal numbers (addition, multiplication, exponentiation) can be found e.g. in this answer.
Validity of Axiom of Choice is assumed. If you want to learn about cardinals without AC, you can have a look e.g. at this question: Defining cardinality in the absence of choice
- $a\le b$ $\land$ $b\le c$ $\Ra$ $a\le c$
This follows from the fact that composition of two injective maps is injective
- $a\le b \land b\le a \Ra a=b$
This is just a reformulation of Cantor-Bernstein's theorem.
- For any two sets $A$, $B$ we have $|A|\le|B|$ $\lor$ $|B|\le|A|$. I.e. any two sets/any two cardinal numbers are comparable.
Note: Proof of this result uses the Axiom of Choice. For the role of AC in this result see here: Is the class of cardinals totally ordered? and For any two sets $A,B$ , $|A|\leq|B|$ or $|B|\leq|A|$ and Proving $(A\le B)\vee (B\le A)$ for sets $A$ and $B$.
- $|A|\le|B| \Lra (\text{there exists a surjective function }\Zobr fBA \text{ or $A$ is empty}).$
There exists an injection from $X$ to $Y$ if and only if there exists a surjection from $Y$ to $X$.
Note: Proof of this result uses the Axiom of Choice.
- $\card{\powerset X}=2^{\card X}$
See e.g. How to show equinumerosity of the powerset of $A$ and the set of functions from $A$ to $\{0,1\}$ without cardinal arithmetic? or Finding a correspondence between $\{0,1\}^A$ and $\mathcal P(A)$ or this answer. The question What is the set of all functions from $\{0, 1\}$ to $\mathbb{N}$ equinumerous to? deals with a special case, but it can be easily generalized.
- $a+b=b+a$
This follows simply from commutativity of union: $A\cup B=B\cup A$.
- $a+(b+c)=(a+b)+c$
This follows from associativity of union: $A\cup(B\cup C)=(A\cup B)\cup C$.
- $b\le c \Ra a+b\le a+c$
This is (after adding some details) basically the same thing as the implication $B\subseteq C$ $\Ra$ $A\cup B\subseteq A\cup C$. See Does $a \le b$ imply $a+c\le b+c$ for cardinal numbers?
- $ab=ba$
A bijection $A\times B\to B\times A$ can be given by $(x,y)\mapsto (y,x)$.
- $a(bc)=(ab)c$
A bijection between $A\times(B\times C)$ and $(A\times B)\times C$ can be given by $(x,(y,z))\mapsto ((x,y),z)$. See here: A bijection between $X \times (Y \times Z)$ and $ (X \times Y) \times Z$
- $a(b+c)=ab+ac$
This follows from the fact that $A\times(B\cup C)=A\times B\cup A\times C$.
- $b\le c \Ra ab\le ac$
See e.g. Proof of cardinality inequality: $m_1\le m_2$, $k_1\le k_2$ implies $k_1m_1\le k_2m_2$ or Will $\kappa_1, \kappa_2, m$ cardinals. Given $\kappa_1 \leq \kappa_2$. prove: $\kappa_1 \cdot m \leq \kappa_2 \cdot m$
- $a^2=a\cdot a$
See e.g. this answer
- $a\le b \Ra a^c\le b^c$
See e.g. this answer.
- $a\le b \land c\ne 0 \Ra c^a\le c^b$
See e.g. this question.
Note that this is not true for $c=0$, since $0^0=1$. (The set $\emptyset^\emptyset=\{\emptyset\}$ has one element.) The set $\emptyset^\emptyset$ and its cardinality is also discussed here.
- $a^{b+c}=a^b\cdot a^c$
See e.g. Let $A,B,C$ be sets, and $B \cap C=\emptyset$. Show $|A^{B \cup C}|=|A^B \times A^C|$ and Notation on proving injectivity of a function $f:A^{B\;\cup\; C}\to A^B\times A^C$.
- $(a^b)^c=a^{bc}$
See e.g. How to show $(a^b)^c=a^{bc}$ for arbitrary cardinal numbers?
- $(ab)^c=a^c\cdot b^c$
See e.g. Equinumerousity of operations on cardinal numbers and How to prove $|{^A}{(K \times L)}| =_c |{^A}{K} \times {^A}{L}|$?
- $a^b\le 2^{ab}$
See e.g. this answer
- $a<2^a$
This is Cantor's theorem. The question Is the class of subsets of integers countably infinite? deals with the special case $a=\alnul$, but there are answers which discuss the more general result or can be easily generalized. See also Understanding the proof for $ 2^{\aleph_0} > \aleph_0$. This question asks about the general result: Cardinality of a set A is strictly less than the cardinality of the power set of A
- $\alnul+\alnul=\alnul$
See e.g. Let $X$ and $Y$ be countable sets. Then $X\cup Y$ is countable
$a\ge\alnul \Ra \alnul+a=a$
$\alnul\cdot\alnul=\alnul$
See e.g. Bijecting a countably infinite set $S$ and its cartesian product $S \times S$, How does one get the formula for this bijection from $\mathbb{N}\times\mathbb{N}$ onto $\mathbb{N}$?, The cartesian product $\mathbb{N} \times \mathbb{N}$ is countable and Proving the Cantor Pairing Function Bijective
The following result is, to some extent, related to the following:
- Union of countably many countable sets is countable.
It is worth mentioning that proof of this uses Axiom of Choice. See Prove that the union of countably many countable sets is countable.
- $\alnul^{\alnul}=2^{\alnul}=\mfr c$
See e.g. Is $\aleph_0^{\aleph_0}$ smaller than or equal to $2^{\aleph_0}$? or What is $\aleph_0$ powered to $\aleph_0$? or What's the cardinality of all sequences with coefficients in an infinite set? (One of the answers to this question also discusses powers of the form $\aleph_\alpha^{\aleph_\beta}$ in general.
- If $a$ is infinite cardinal, then $a^2=a$.
See e.g. About a paper of Zermelo
Note: Proof of this result uses the Axiom of Choice. See also: For every infinite $S$, $|S|=|S\times S|$ implies the Axiom of choice
- If $b$, $c$ are infinite cardinals, then $b+c=bc=\max\{b,c\}$.
Note: This is a consequence of the preceding result, so it relies on the Axiom of Choice too.
I have no doubt that many resources about Cauchy functional equations and its relatives are available. But many properties of them have been shown in MSE posts, I will try to provide here list of links to the questions I am aware of. I have made this post CW, feel free to add more links and improve this answer in any way. Several links have been collected also in this post: Functional Equation $f(x+y)=f(x)+f(y)+f(x)f(y)$ $\newcommand{\R}{\mathbb{R}}\newcommand{\Q}{\mathbb{Q}}\newcommand{\Zobr}[3]{{#1}\colon{#2}\to{#3}}$
Cauchy's additive functional equation
We are interested in functions $\Zobr f{\R}{\R}$ such that $$f(x+y)=f(x)+f(y) \tag{0}\label{0}$$ holds for each $x,y\in\R$.
- If $f$ is a solution of \eqref{0} and $q$ is a rational number, then $f(qx)=qf(x)$ holds for each $x\in\R$.
See e.g. If $f(x + y) = f(x) + f(y)$ showing that $f(cx) = cf(x)$ holds for rational $c$
- Every continuous solution $\Zobr f{\R}{\R}$ of \eqref{0} has the form $f(x)=cx$ for some constant $c\in\R$.
See e.g. this question: I want to show that $f(x)=x.f(1)$ where $f:R\to R$ is additive. or I need to find all functions $f:\mathbb R \rightarrow \mathbb R$ which are continuous and satisfy $f(x+y)=f(x)+f(y)$
- If $\Zobr f{\R}{\R}$ is a solution of \eqref{0} which is continuous at some point $x_0$, then it is continuous everywhere.
See e.g. Proving that an additive function $f$ is continuous if it is continuous at a single point
- If a solution $f$ of \eqref{0} is bounded on some interval, then $f(x)=cx$ for some $c\in\R$.
One part of this question is about the proof that locally bounded solution of \eqref{0} is necessarily continuous: Real Analysis Proofs: Additive Functions
- Every monotonic solution $\Zobr f{\R}{\R}$ of \eqref{0} has the form $f(x)=cx$ for some constant $c\in\R$.
See e.g. this question: Suppose $f(x)$ is linear i.e. $f(x + y) = f(x) +f(y) $ and monotone on $[-\infty, +\infty]$, then $f(x) = ax$, a real.
- If we have the equation \eqref{0} for function $\Zobr f{[0,\infty)}{[0,\infty)}$, then every solution is of the form $f(x)=cx$.
See If $f:[0,\infty)\to [0,\infty)$ and $f(x+y)=f(x)+f(y)$ then prove that $f(x)=ax$
- There exist non-continuous solutions of \eqref{0}.
See non-continuous function satisfies $f(x+y)=f(x)+f(y)$, Do there exist functions satisfying $f(x+y)=f(x)+f(y)$ that aren't linear?, On sort-of-linear functions, Many other solutions of the Cauchy's Functional Equation
NOTE: The proof of this fact needs at least some form of Axiom of Choice - it is not provable in ZF.
For the role of AC in this result, see this MO thread, and theses questions: Cauchy functional equation with non choice, A question concerning on the axiom of choice and Cauchy functional equation, Is there a non-trivial example of a $\mathbb Q-$endomorphism of $\mathbb R$?, What is $\operatorname{Aut}(\mathbb{R},+)$?
- The graph $G(f)=\big\{\big(x,f(x)\big)\big| x\in\R\big\}$ is a dense subset of $\R^2$ for every non-continuous solution of \eqref{0}.
See e.g. Graph of discontinuous additive function is dense in $ \mathbb R ^ 2 $
- Every anti-differentiable solution $\Zobr f{\R}{\R}$ of \eqref{0} has the form $f(x)=cx$ for some constant $c\in\R$.
See e.g. Solution of Cauchy functional equation which has an antiderivative
- Every locally integrable solution $\Zobr f{\R}{\R}$ of \eqref{0} has the form $f(x)=cx$ for some constant $c\in\R$.
See e.g. How to prove $f(x)=ax$ if $f(x+y)=f(x)+f(y)$ and $f$ is locally integrable
- Every Lebesgue measurable solution $\Zobr f{\R}{\R}$ of \eqref{0} has the form $f(x)=cx$ for some constant $c\in\R$.
See e.g. Additivity + Measurability $\implies$ Continuity or Show that $f(x+y)=f(x)+f(y)$ implies $f$ continuous $\Leftrightarrow$ $f$ measurable or Measurable Cauchy Function is Continuous or Prove that if a particular function is measurable, then its image is a rect line or Proving that $f$ is measurable with $f(x+y)= f(x)+f(y)$ then $f(x) =Ax$ for some $A\in\Bbb R$?.
Related equations
There are several functional equations that are closely related to Cauchy equation. They can be reduced to it by some methods or solved by very similar methods as the Cauchy equation.
Cauchy's exponential functional equation
$$f(x+y)=f(x)f(y) \tag{1}\label{1}$$
- If $f$ is a solution of \eqref{1}, then either $f=0$ (i.e., $f$ is constant function equal to zero) or $f(x)>0$ for each $x\in\R$.
See e.g. Is there a name for function with the exponential property $f(x+y)=f(x) \cdot f(y)$? and A non-zero function satisfying $g(x+y) = g(x)g(y)$ must be positive everywhere
If $f$ is a solution of \eqref{1}, $x\in\Q$ and if we denote $a=f(1)$, then $f(x)=a^x$.
Every continuous solution of \eqref{1} has the form $f(x)=a^x$ for some $a\ge 0$.
See e.g. continuous functions on $\mathbb R$ such that $g(x+y)=g(x)g(y)$ or How do I prove that $f(x)f(y)=f(x+y)$ implies that $f(x)=e^{cx}$, assuming f is continuous and not zero?
- If a solution of \eqref{1} is continuous at $0$, then it is continuous everywhere.
- There are non-continuous solutions of \eqref{1}.
They can be obtained from non-continuous solutions of \eqref{1}.
- If a solution of \eqref{1} is differentiable at $0$, then it is differentiable everywhere and $f'(x)=f(x)f'(0)$.
See Prove that $f'$ exists for all $x$ in $R$ if $f(x+y)=f(x)f(y)$ and $f'(0)$ exists and Differentiability of $f(x+y) = f(x)f(y)$ There are also posts searching for differentiable solutions: Solution for exponential function's functional equation by using a definition of derivative
Cauchy's logarithmic functional equation
$$f(xy)=f(x)+f(y) \tag{2}\label{2}$$
See Examples of functions where $f(ab)=f(a)+f(b)$ and Is the product rule for logarithms an if-and-only-if statement?
Cauchy's multiplicative functional equation
$$f(xy)=f(x)f(y) \tag{3}\label{3}$$
- Every continuous solution of \eqref{3} has the form $f(x)=x^a$
See If $f(xy)=f(x)f(y)$ then show that $f(x) = x^t$ for some t
- A solution of \eqref{3} which is continuous at $1$ is continuous for each $x>0$.
See Functional equation $f(xy)=f(x)+f(y)$ and continuity
- If a function fulfills both \eqref{0} and \eqref{3}, then either $f(x)=0$ or $f(x)=x$ (i.e., it is either zero function or the identity).
Notice that we do not require continuity here. See Functional equations $f(x+y)= f(x) + f(y)$ and $f(xy)= f(x)f(y)$
Best Answer
I have no doubt that you there are many useful online resources for these, but many such results are available here at MSE, together with their proofs.
I'll give a list of some basic results about images and preimages links to the posts, which have proofs here at MSE. I am making this CW, so feel free to add more identities and pointers to further useful questions and answers. $\newcommand{\Map}[3]{{#1}\colon{#2}\to{#3}}\newcommand{\Img}[2]{{#1}[#2]}\newcommand{\Pre}[2]{{#1}^{-1}[#2]}$
If $\Map fXY$ is a function and $A\subseteq X$ and $B\subseteq Y$ are some set then the set $$\Img fA=\{f(x); x\in A\}$$ is called the image of the subset $A$ and the set $$\Pre fB=\{x; f(x)\in B\}$$ is called the preimage or inverse image of the subset $B$.
In the other words, we have $$y\in\Img fA \Leftrightarrow (\exists x\in A)f(x)=y$$ and $x\in\Pre fB \Leftrightarrow f(x)\in B$.
In the notation below we always assume $A,A_i\subseteq X$ and $B,B_i\subseteq Y$.
see Proving that $C$ is a subset of $f^{-1}[f(C)]$ In fact, the equality is equivalent to the fact that $f$ is injective: Show $S = f^{-1}(f(S))$ for all subsets $S$ iff $f$ is injective or Is $f^{-1}(f(A))=A$ always true? Some counterexamples to the equality can be found in answers to Why $f^{-1}(f(A)) \not= A$
For the first part see: Need help for proving that: $f(f^{-1}(A)) ⊆ A$ For the second part, see Demonstrate that if $f$ is surjective then $X = f(f^{-1}(X))$ or Prove $F(F^{-1}(B)) = B$ for onto function.
See, for example, Prove $f(S \cup T) = f(S) \cup f(T)$
or Functions-Set Theory Proof that $f(C \cup D) = f(C) \cup f(D)$
or How do I prove the following: $f(S\cup T) = f(S) \cup f(T)$
or Maps - question about $f(A \cup B)=f(A) \cup f(B)$ and $ f(A \cap B)=f(A) \cap f(B)$
or Unions and Functions on Sets
or The preimage of a subset
See Show that $\bigcup_i f(A_i) = f(\bigcup_i A_i)$
See, for example Is this a valid proof of $f(S \cap T) \subseteq f(S) \cap f(T)$?
or Is this proof correct for : Does $F(A)\cap F(B)\subseteq F(A\cap B) $ for all functions $F$?
or Prove $f(S \cap T) \subseteq f(S) \cap f(T)$
or Do we have always $f(A \cap B) = f(A) \cap f(B)$?
or Maps - question about $f(A \cup B)=f(A) \cup f(B)$ and $ f(A \cap B)=f(A) \cap f(B)$
or Verifying a proposition on image and preimage: $f(A\cap B)\subseteq f(A)\cap f(B)$ and $f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D)$
or How to prove this? "For all sets $A,B\subseteq D$ and functions $f:D\mapsto R$, we have $f(A\cap B)\subseteq(f(A)\cap f(B))$."
or $f(A \cap B)\subset f(A)\cap f(B)$, and otherwise?
The part about injective functions can be found in Conditions Equivalent to Injectivity or in Proving: $f$ is injective $\Leftrightarrow f(X \cap Y) = f(X) \cap f(Y)$
A counterexample showing that equality is not true in general can be found here: Do we have always $f(A \cap B) = f(A) \cap f(B)$?
In fact, if this equality is true for all subsets $A_1,A_2\subseteq X$, then $f$ must be injective, see To prove mapping f is injective and the other f is bijective
See: Inverse image of a union equals the union of the inverse images and Proof for Image of Indexed Collection of Sets?
See, for example: What are the strategies I can use to prove $f^{-1}(S \cap T) = f^{-1}(S) \cap f^{-1}(T)$?
or how to prove $f^{-1}(B_1 \cap B_2) = f^{-1}(B_1) \cap f^{-1}(B_2)$
or Verifying a proposition on image and preimage: $f(A\cap B)\subseteq f(A)\cap f(B)$ and $f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D)$
See: Proving set equalities
See: Show that $f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)$
See: Union of preimages and preimage of union
We can also ask whether image and preimage preserve difference:
See Proving $f(C) \setminus f(D) \subseteq f(C \setminus D)$ and disproving equality. Equality holds for injective functions, see If $f$ is 1-1, prove that $f(A\setminus B) = f(A)\setminus f(B)$. In fact, validity of the equality $\Img fA\setminus\Img fB = \Img f{A\setminus B}$ characterizes injectivity: Does $f(X \setminus A)\subseteq Y\setminus f(A), \forall A\subseteq X$ imply $f$ is injective ?.
See Proof of $f^{-1}(B_{1}\setminus B_{2}) = f^{-1}(B_{1})\setminus f^{-1}(B_{2})$. As a consequence of this we get that the preimage of complement is complement of the preimage, see here: How to approach proving $f^{-1}(B\setminus C)=A\setminus f^{-1}(C)$?, Show that for any subset $C\subseteq Y$, one has $f^{-1}(Y\setminus C) = X \setminus f^{-1}(C)$ and Show $f^{-1}(A^c)=(f^{-1}(A))^c$
The image and inverse image for composition of maps can be expressed in a very simple way. For $\Map fXY$, $\Map gYZ$ and $A\subseteq X$, $C\subseteq Z$ we have
See Show that $(g \circ f)^{-1}(C) = g^{-1}(f^{-1}(C)).$ and Prove that if $Z\subseteq Y$, then $(g\circ f)^{-1}(Z)=f^{-1}(g^{-1}(Z)).$