0
votes
1answer
23 views

Help explain the set being constructed in this Cantor-Schroder-Berstein proof

The Cantor-Schroder-Bernstein theorem states that: Suppose $A$ and $B$ are sets. If $|A|\le |B|$ and $|B|\le |A|$, then $|A|=|B|$ Proof: So, $|A|\le|B|$ implies we can choose an injection ...
2
votes
1answer
36 views

How to prove this version of the Cantor-Schroder-Bernstein theorem?

My text states the Cantor-Schroder-Bernstein theorem as follows: Suppose that $X$ and $Y$ are non-empty sets such that $|X|>|Y|$. Then, any function $f:X\rightarrow Y$ is not an injection, i.e. ...
1
vote
2answers
45 views

Help explain proof that $\mathbb{Q}$ is denumerable

A set $X$ is said to be denumerable if there is a bijection $\mathbb{Z}^+\rightarrow X$ Statement to prove: The of rationals $\mathbb{Q}$ is denumerable. Proof: Define $f:\mathbb{Q} ...
1
vote
2answers
23 views

How to prove that this function of two variables is a surjection?

Let: $A=\{a_1,a_2,\dots,a_m, \dots\}$ $B=\{b_1,b_2,\dots,b_n,\dots\}$ Define $f:A\times B \rightarrow \mathbb{Z}^+$ as: $(a_m,b_n) \mapsto \frac{1}{2}(m+n-2)(m+n-1)+n$ How do I show that $f$ is ...
1
vote
1answer
26 views

Help to prove this inductively defined function is surjective

Suppose that $A$ is a infinite subset of $\mathbb{Z}^+$. We construct a bijection $f:\mathbb{Z}^+ \rightarrow A$ and define $f(n)$ inductively as follows: Base case: Let $f(1)$ be the least element ...
0
votes
2answers
15 views

Prove if $g \circ f$ is $1-1$ and $f$ is onto, show that $g$ is $1-1$

Let $f: A \rightarrow B$ and $g: B \rightarrow C$. $g \circ f: A \rightarrow C$. But where do I use the fact that $f$ is onto?
0
votes
0answers
15 views

Check proof of union of denumerable sets is denumerable too

I need to prove: If $A$ and $B$ are denumerable sets then so is their union $A\cup B$. In this case, denumerable is defined as: A set $X$ is said to be denumerable if there is a bijection ...
1
vote
2answers
52 views

Proof - Inverse of linear function is linear

This is my first proof related to linear functions. It refers to the linear-algebra-$\textit{linear}$ (not the calculus-$\textit{linear}$). Please comment. Theorem The inverse of a linear bijection ...
1
vote
3answers
60 views

How to prove that a set is infinite iff it is Dedekind infinite?

I need to prove the following: A set $X$ is infinite if and only if it is equipotent to a proper subset of itself Here, $X$ is defined to be infinite if $|X|$ is not a non-negative integer or ...
0
votes
1answer
41 views

How to prove a function from a set of triples to $\mathcal{P}_3(\mathbb{N}_7)$ is a bijection?

Let $Y=\{y_1, y_2, y_3, y_4,y_5\}$ The function from the set of triples $(y_{i_1},y_{i_2},y_{i_3})$ where $i_1 \le i_2 \le i_3$ to $\mathcal{P}_3(\mathbb{N}_7)$ is a bijection given by ...
0
votes
1answer
30 views

How to handle a function from a set of functions to another set of functions?

Given sets $X$ and $Y$ we denote the set of functions from $X$ to $Y$ by $\text{Fun}(X,Y)$. Let: $k,n \in \mathbb{Z}^+$ $X_1 = \{x_1,x_2\dots, x_{k+1}\}$ $Y = \{y_1, y_2, \dots , y_n\}$ Then, ...
2
votes
2answers
57 views

Surjectivity of a piecewise function $f:(-1,1)\to \mathbb R$

Function $f$ is defined as $f: (-1, 1) \to \mathbb{R}$. $$ f(x) = \begin{cases} -x/(x-1),&x\geq 0 \\ x/(x+1),&x \leq 0 \end{cases} $$ Let $y \in \mathbb{R}$. How would I prove that there ...
1
vote
1answer
54 views

Help prove $f:X \rightarrow Y$ is an injection $\Leftrightarrow$ $f:X\rightarrow Y$ is a surjection when $|X|=|Y|$

I need to prove: Given non-empty finite sets $X$ and $Y$ with $|X| = |Y|,$ a function $X\rightarrow Y$ is an injection if and only if it is a surjection. The hint given is to use the pigeonhole ...
0
votes
1answer
45 views

Help to prove the existance of a function

Let $f:X \rightarrow Y$ be a function. Prove that there exists a function $g:Y \rightarrow X$ such that $f \circ g = I_Y$ if and only if $f$ is a surjection. I need help on proving the following: ...
0
votes
1answer
55 views

Help to clarify inductive step for proof of $\mathbb{N_m} \rightarrow \mathbb{N}_n\Rightarrow m\le n$

The statement to prove is: If there exists an injection $\mathbb{N_m} \rightarrow \mathbb{N}_n$ then $m\le n$ The solution says to prove by induction on $n$. I just need help on the inductive ...
0
votes
1answer
44 views

How to prove that a given map is an injection?

Let $g:\mathbb{N_{m_1-1}}\rightarrow \mathbb{N}_{m_1}$, where: $$g(i) = \left\{ \begin{align} i & \text {, for } i<i_0 \\ i+1 & \text{, for } i \ge i_0 \end{align}\right.$$ and $i_0 ...
1
vote
1answer
63 views

How to prove that $f:\mathbb{N}\rightarrow X$ where $f$ maps to an element in a set, is a bijection?

Let $X$ and $Y$ be disjoint finite sets, $|X|=n$ and $|Y|=m$, so that we have the following bijections: $f:\mathbb{N}_n \rightarrow X$ and $g:\mathbb{N}_m \rightarrow Y$ I need to prove that ...
0
votes
2answers
71 views

If a converse of an implication is false, does this mean that the proof of that implication will always have an implication that is not reversible?

Let $f:X \rightarrow Y$ be a function and $B_1, B_2 \in \mathcal{P}(Y)$. Prove that $B_1 \subseteq B_2 \Rightarrow \overleftarrow{f}(B_1) \subseteq\overleftarrow{f}(B_2)$. My attempt: $\begin{align} ...
2
votes
2answers
32 views

Help to prove $f$ is surjective $\Leftrightarrow \forall y \in Y, (X \times \{y\} \cap G_f ) \ne \emptyset $

Let $f:X \rightarrow Y$ be a function with graph $G_f \subseteq X \times Y$. Prove that $f$ is surjective if and only if $\forall y \in Y, (X \times \{y\} \cap G_f ) \ne \emptyset $ I have some ...
1
vote
4answers
34 views

Lowest possible value of a function with derivative greater than 2

I have the following two problems, and want to attempt to solve them with Mathematical rigour(which I don't yet possess): Suppose that $f$ is differentiable on $[1,4]$ and is such that $f(1) = 10$ ...
1
vote
3answers
34 views

Help with this function proof

If a function is bijective then its inverse is unique. I came across this in my textbook and was wondering how it is proved. Thank you.
1
vote
1answer
131 views

Proving the chain rule by first principles

I'm currently trying to prove: $(f(g))'(a)=f'(g(a))*g'(a)$ I have been given a proof which manipulates: $f(a+h)=f(a)+f'(a)h+O(h)$ where $O(h)$ is the error function. However, I would like to have a ...
0
votes
2answers
47 views

Show that $A^{(x,y)}$ is countable.

Question: Let $A$ be a countable set $A^{(x,y)}$ the set of all functions from $(x,y)$ to $A$. Show that $A^{(x,y)}$ is countable. My attempt: By proposition 7.1.2iii, $\mid B \mid^{\mid A \mid}$ ...
0
votes
3answers
295 views

Proving a function is a one to one correspondence

I understand that to show a function is a one to one correspondence, you have to show that the function is both one to one and onto. Proving a function is one to one seems simple enough. However for ...
4
votes
3answers
245 views

Do you need to find the domain of a function to prove injectivity?

I teach math and have had this debate with a fellow teacher. I believe the domain of a function is really not important to determine if a function is or is not injective if there is no "real life" ...
2
votes
4answers
111 views

$f:X\to Y$, $A,B,\subseteq X$. Show that $f(A\setminus B)=f(A)\setminus f(B)$ iff $f(A\setminus B)\cap f(B) =\emptyset$

I tried to prove this but I am not sure if its correct. Please help me out with any tips or advice on how to improve. Here it is: First let $f(A\setminus B)\cap f(B)=\emptyset$. Now $$f(A\setminus ...
0
votes
1answer
33 views

$h \circ g $ is 1-1 and onto $g$ is 1-1 and onto $h$ is onto - how to prove that $h$ is 1-1 too?

$h \circ g $ is 1-1 and onto $g$ is 1-1 and onto $h$ is onto I am trying to prove that $h$ is 1-1 too. $h \circ g(x1) $ =$h \circ g(x2) \rightarrow x1=x2 $ And due to the fact that $g$ is ...
0
votes
1answer
48 views

Surjection Equivalence [duplicate]

I'm trying to show that if a function $f:X\to Y$ is surjective it's equivalent to saying that $f \left(f^{-1}(B)\right) = B$ for each $B \subseteq Y$. The definition of surjective that I'm using is ...
1
vote
3answers
160 views

Proof that $\frac{(x+y)-abs(x-y)}{2}$ equivalent to $\min(x,y)$

I plotted the two functions $\frac{(x+y)-abs(x-y)}{2}$ and $min(x,y)$ in the range $[-1, 1]$ and they look the same. The both $min$ and $abs$ functions are defined as expected. ...
0
votes
2answers
85 views

Verification of Proof of a Bijection from A to B

Problem: For $ a,b \in \textbf{R}$ with $ a < b$, prove an explicit bijection of $ A = \{ x : a < x < b \} $ onto $ B = \{ y : 0 < y < 1\} $. My attempt: We consider $ f(x) = ...
0
votes
1answer
49 views

Verification of proof that $f(x) = \frac{x-a}{b-a}$ is bijective over the reals

We consider $ f(x) = \displaystyle \frac{x-a}{b-a} $ for $f: \textbf{R} \rightarrow \textbf{R} $ where $a,b$ are both constants such that $a,b \in \textbf{R} $ and $b-a \neq 0$. Proof that $ f$ is ...
1
vote
1answer
57 views

Method for proving $ f^{-1}(G \cup H) = f^{-1}(G)\cup f^{-1}(H) $

Prove that if $ f: A \rightarrow B $ and $ G,H $ are subsets of $ B $, then $ f^{-1}(G \cup H) = f^{-1}(G)\cup f^{-1}(H) $. My (incorrect) Attempt: Suppose $ x \in f^{-1}(G\cup H) $. Then there ...
1
vote
1answer
28 views

Prove Bijection in roots of unity function

Given $k \in \mathbb{N}, G_k = \{z \in \mathbb{C} |z^k =1 \} $. Probe that if $n$ and $m$ are coprime, the function $f: G_n \times G_m \rightarrow G_{mn}, f(\alpha, \beta) =\alpha\beta$ is bijective. ...
1
vote
1answer
99 views

A polynomial is called a Fermat's polynomial…

A polynomial is called a Fermat polynomial if it can be written as the sum of the squares of two polynomials with integer coefficients. Suppose that $f(x)$ is a Fermat polynomial such that $f(0) = ...
-1
votes
2answers
91 views

prove that $f:X\rightarrow Y$ is surjective if and only if $f(f^{-1}(C))=C$

I need help with proving this: $f:X\rightarrow Y$ is surjective if and only if $f(f^{-1}(C))=C$ $C\subseteq Y$ Thanks.
1
vote
4answers
55 views

check if $f(f^{-1}(D))=D$

I have to check whether $f(f^{-1}(D))=D$. I think this is not true but I'm stuck in my proof. Can somebody help me? Thanks in advance.
0
votes
2answers
396 views

proving whether a function is one-to-one/onto

1) f(n) = 2n + 1 from set of integers to set of integers 2) f(n) = 2[n/2] from set of integers to set of integers [] is floor Could someone demonstrate how I ...
2
votes
0answers
42 views

Prove that $f: \mathbb{N} \rightarrow \mathbb{N}-\left \{ 1 \right \}$ given by $f(x) = x+1$ is $1$-$1$ and onto

$f: \mathbb{N} \rightarrow \mathbb{N}-\{1\}$ given by $f(x) = x+1$ is $1$-$1$ and onto. Proof: ($1$-$1$) Suppose $f(x_{1}) = f(x_{2})$ for $x_{1}, x_{2} \in \mathbb{N}$. Then $x_{1} + 1 = x_{2} + ...
1
vote
2answers
158 views

Prove that the greatest integer function: $\mathbb{R} \rightarrow \mathbb{Z}$ is onto but not $1-1$

Statement: the greatest integer function int: $\mathbb{R} \rightarrow \mathbb{Z}$ is onto but not $1-1$ Proof: let $x \in \mathbb{R}$, then $int(x) \leq x$ and is an element of $\mathbb{Z}$. Since ...
1
vote
1answer
175 views

Prove if $f: A \rightarrow B, g: B \rightarrow C$, and $g \circ f: A\overset{1-1}{\rightarrow}C$, then $f: A \overset{1-1}{\rightarrow} B$

Statement: If $f: A \rightarrow B, g: B \rightarrow C$, and $g o f: A\overset{1-1}{\rightarrow}C$, then $f: A \overset{1-1}{\rightarrow} B$ Here's my proof by contradiction. Proof: Assume $f$ is not ...
0
votes
1answer
58 views

Prove that functions are one-to-one

Given $f: \mathbb{R} \rightarrow \mathbb{R}$, $f(x) = x^{3}$ Proof: Assume $f(m)=f(n)$ for some $m, n \in \mathbb{R}$. Then $m^{3}=n^{3}$, and $m=n$. $f$ is one-to-one. Given $f: \mathbb{R} ...
0
votes
2answers
151 views

How to prove that $f(x,y)=x-y$ is one-to-one?

Given $f: \mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R}, f(x,y) = x-y$. How can I prove that the function is one to one? I know that f(x,y)=x-y is a plane, and just by visualizing it I can see ...
3
votes
1answer
84 views

For bijection $f:A \rightarrow B$, prove that $f^{-1} \circ f = {\text {id}}_{A}$

I have to prove that for a bijection $f:A \rightarrow B$, $f^{-1} \circ f = {\text {id}}_{A}$, where ${\text {id}_A}$ is the identity function of $A$, and we define $f^{-1}: B \rightarrow A$ by ...
4
votes
1answer
104 views

Function Surjectivity Proof

I have this question: Prove that a function $f:X\rightarrow Y$ is surjective iff for any finite set $Z$ and any function $g:Z\rightarrow Y$ there exists a function $h:Z\rightarrow X$ such that ...
0
votes
2answers
414 views

How do I prove that a function grows faster than another? [closed]

I need to prove that one function, say $n$ grows faster than say, $\sqrt{n}$?
0
votes
2answers
59 views

Why does this limit work?

Let $h(x)= (1+1/x)^x$ and $g(x)$ be another function. Now suppose $\lim\limits_{x \to \infty} g(x)= \infty$. Then $\lim\limits_{x \to \infty} h(g(x))$ =$\lim\limits_{x \to \infty} h(x)=e$. I would ...
0
votes
2answers
65 views

Proof that a function is surjective to R

I'm having difficulties proving that the function $$\frac{\sin(\frac1x)}{x^2}$$ is surjective to $\mathbb R$. on the interval $(0,10]$. I tried to use the intermediate theorem, but that of ...
0
votes
1answer
110 views

Prove that the function $f(x)=\frac{1}{x}$ is continuous at the point x=2.

I am looking to prove that the function $f(x)=\frac{1}{x}$ is continuous at the point x=2. So we nee that given any $\epsilon>0,\ \exists\delta>0$ so that $|f(x)-f(2)|<\epsilon\\$ whenever ...
1
vote
3answers
80 views

Prove $f : A\rightarrow B, g: B\rightarrow C$ , and $g\circ f: A \overset{1-1}{\rightarrow}C$, then $f:A\overset{1-1}{\rightarrow}B$

Could anyone please explain how to approach this problem, I'm honestly having a hard time figuring out where to start the problem. I know that I have to show that $\forall x,y\in A$ , if $f(x)=f(y)$, ...
1
vote
1answer
72 views

Can you prove this three-way linear map composition?

OK, this was an example that my prof gave when talking about surjective, injective and bijective functions. I also am curious if I am approaching this the right way. (Everyone here has been a really ...