0
votes
1answer
12 views

showing that if a function is a bijection, then there exists a an identity function

Let f:x-y be a bijection, show that foi =iof =f where i is identity function. I know that a bijection is one which is bith noe to one and onto. The problems is that the question is so trivial that I ...
2
votes
0answers
21 views

Intuition - Countable iff Surjection iff Injection [Velleman P310 Thm 7.1.5] [duplicate]

Define $I_n = \{1, 2, ..., n \} $. Let $A$ be a nonempty set. TFAE : (i) $A$ is finite (ie: a bijection $h:A\rightarrow I_{N}$ exists) or A is countably infinite (ie: a bijection ...
0
votes
1answer
21 views

For any function $f$, $f(s) \in f(S) \not\implies \Leftarrow s \in S$

This already contains many counterexamples, so I'm not seeking any more of them; I'm interested in learning about my errors with the notation and definitions. Richard Hammack P213 Defintion 12.9: ...
-1
votes
0answers
38 views

Countable iff Surjection iff Injection [Velleman P310 Thm 7.1.5] [on hold]

Define $I_n = \{1, 2, ..., n \} $. Let $A$ be a nonempty set. TFAE : (i) $A$ is finite (ie: a bijection $h:A\rightarrow I_{N}$ exists) or A is countably infinite (ie: a bijection $h:A\rightarrow ...
1
vote
2answers
38 views

Proof strategy - If $g \circ f = id_A$, then f onto $\iff$ g 1-1. [Chartrand 3Ed P239 9.72]

For nonempty sets A and B and functions f : A → B and g : B → A, suppose that $g \circ f =$ the identity function on A. $(♦)$ (d) $(=>)$ Assume that $f$ is onto. This means there exist ...
1
vote
4answers
78 views

$f[A]\cap f[B]\supsetneq f[A\cap B]$ - Where does the string of equivalences fail ? [Chartrand 3E 9.12(b), 9.29]

I only realised that equality may fail in $f[A]\cap f[B]\supseteq f[A\cap B]$ (i.e., that we can have $A,B,f$ for which $f[A]\cap f[B]\neq f[A\cap B]$) after checking the answer. I don't see any ...
0
votes
2answers
48 views

How to prove that if $A\subseteq B$and $|A|=|B|$, then $A=B$

Apart from the question in the title, the other question that related to the first question: Define: $f(X)=${$f(x)|x\in X$}. if $X$ is finite, $f(X)\subset X$ and $f$ is one to one, then $|f(X)|=|X|$, ...
0
votes
1answer
36 views

Bijection and image

Let f: A -> B be a bijection, so f^-1: B -> A is a function. Let X be a subset of A. How do I prove that Im(f)(X) = Preim(f^-1)(X)? Thank you.
2
votes
3answers
49 views

Determining injectivity and surjectivity

Are these functions injective or surjective? Also, how should I go about proving this? The function maps $ℕ×ℕ$ to $ℤ$. $f(a,b) = 4a+5b$ $f(m,n) = m^2-n$ $f(p,q) = 5^p·3^q$ Thanks!
0
votes
1answer
67 views

Surjectivity of Composite Functions

The question I'm asking might be rather simple, but I couldn't find relevant information (maybe it's too trivial?). Here's the question that baffled me. Let $f:X\rightarrow Y$ and $g:Y\rightarrow ...
-1
votes
2answers
30 views

Prove that there is bijection between sets

I need to prove that there is a bijection between these sets: $$A = [0, 1], B = (0, 1/2) ∪ (1/2, 1)$$ I tried to use Cantor–Bernstein–Schroeder theorem but I am lost. Can you help me?
0
votes
2answers
26 views

How to solve this question subset

Answer true or false to each of the following questions. If a statement is true, prove it. If a statement is false, give a counterexample. For all sets $A$,$B$ and $C$: IF $A ⊆ B$ and $A ⊆ C$, Then ...
0
votes
1answer
31 views

Union of preimages [duplicate]

Given $f:X\rightarrow Y$ as a function, the image of $x$ if $f(x)$. The preimage of $y$ is $f^{-1}(y)=\{x\ |\ f(x)=y\}$, with the symbol PreIm$(Y)$ Given the definition, could you prove the following ...
-1
votes
2answers
103 views

Give a Bijection that is in-between 2 intervals and use a formal proof to show that it is a bijection. [duplicate]

∀w,x,y,z ∈ R, w < x and y < z. Given that information, supply a bijection between the two intervals. (w,x) and (y,z) Then after you find the bijection, provide a formal proof that what you found ...
-1
votes
1answer
39 views

What is the place holder glyph for a set?

What glyph do set theorists use to denote an unspecified set? For example, logicians use φ to talk about an unspecified sentence in first order logic. Does set theory have a comparable glyph? Thank ...
0
votes
1answer
29 views

Preparing for exam: recognizing functions in Set Theory

I'm reviewing earlier exams and found this question: ...
4
votes
4answers
108 views

Simple question about the pre-image of a set

Define the pre-image of a set $S \subseteq Y$ under $f$ where $f:X \to Y$ by $f^{-1}(S) = \{ x \in X : f(x) \in S \}$ Let $A = \{ 0 , 1\}, B = \{ 0,1,2,3 \}$. Define $f:A \to B$ by $f:x \mapsto x + ...
-1
votes
1answer
49 views

Let $X \neq \emptyset$, define the relation$A\sim B$ if there exists a bijection $f : A \to B$, Show that $\sim$ is an equivalence relation on $X$.

A question on my last proofs midterm, I know I must prove injectivity and surjectivity, but there aren't really any obvious conditions or descriptions on S that helped me to manipulate it to try and ...
0
votes
0answers
14 views

Did I correctly apprehend this description of a binary function?

From Wikipedia, $f$ is a binary function if there exists $X,Y,Z$ such that $f: X × Y \mapsto Z$ .... ...one may represent a binary function as a subset of the Cartesian product $X × Y × Z$, ...
-1
votes
0answers
66 views

For the non-empty sets A, B and C, let f : A -> B and g : B -> C Prove or disprove the following statements:

(a) If f is onto then g o f is onto. (b) If g is onto then g o f is onto. (c) If f is one-to-one then g o f is one-to-one. (d) If g is one-to-one then g o f is one-to-one This is a question on my ...
-1
votes
2answers
36 views

Consider the function h where $h(x,y) = (x+y,x-y)$, $h : \mathbb N\times \mathbb N\to \mathbb N\times\mathbb N$ [duplicate]

Is the function h onto and one to one? Prove this. Online bonus question on a recent proofs quiz on the topic of one-to-one and onto functions. Gave me a bit of grief (the mapping stuff). Also ...
1
vote
3answers
70 views

Let X and Y be finite non empty sets such that $|X| = |Y|$. Show that a function $f : X \to Y$ is onto if it is one to one.

Hello this is a recent question posted on my course website for bonus marks. I am not exactly an expert at proving bijection (our current topic of study) and the definitions of onto and one-to-one are ...
0
votes
0answers
30 views

Number of functions over a finite un-ordered set

How many different functions are there with the domain as an unordered set with n elements? Should the set be ordered the answer it seems is $n^n$
-1
votes
4answers
70 views

Let $g : \Bbb N \times \Bbb N \to\Bbb N \times \Bbb N$ defined as $g(m,n) = (m + n,m - n)$

Determine if $g$ is injective; surjective; bijective. Question on a recent test regarding one-to-one and onto functions. Was very difficult for me, could not even begin to answer either. This is ...
3
votes
2answers
215 views

Does the bijection of function sets imply bijection of sets?

Let $X,Y$ and $Z$ be sets. Is it true that if the set of functions from $Z$ to $X$ is in bijection to the set of functions from $Z$ to $Y$, then $X$ is in bijection to $Y$? Or are there any subtleties ...
0
votes
2answers
53 views

Is the collection of all functions between two sets a set?

Can we say "the set of all functions between two sets" as easily as we could say "the set of all real numbers", for example?
2
votes
1answer
59 views

Is there any interesting interpretation of the set of all functions between two sets?

Is there any way to interpret the set of all functions from a set $X$ to a set $Y$? There is an interpretation of it as the cartesian product of $X$-many copies of $Y$, but I am asking for a more ...
0
votes
1answer
54 views

Show that $f$ is right invertible.

Lete $f:A\to B$ be a surjective map. Show that $f$ is right invertible. To prove this we need to construct a map $h:B\to A$ such that $f(h)=i_B$. Now as $f$ surjective so for each $b\in B$ ...
1
vote
1answer
31 views

What is the inverse of this two-case function?

Given the function $f: \mathbb{Z} \to \mathbb{Z}$ defined by $$ f(n) = \begin{cases} n+2 \mbox{ if $n$ is even }\\ 2n+1 \mbox{ if $n$ is odd } \end{cases} $$ find the inverse or show that no ...
0
votes
1answer
27 views

Dedekind cuts and cardinailty

On wikipedia, it is stated that the set $$f(x)=\{q\in\mathbb{Q}|q\leq x\}$$ is an inclusion map. If I define $a,b$ $\in\mathbb{R}$ such that $a\ne b$ and don't see how $\{q\in\mathbb{Q}|q\leq a\}\ne ...
2
votes
1answer
31 views

Some confusion in notation of Bernstein-Schroeder Theorem

Here on page 232-233 the author offers a proof of the Bernstein-Schroeder Theorem. He uses the subset $$\bigcup_{k=0}^\infty(g\circ f)^k(A-g(B))\subseteq A$$ and I'm not exactly sure how to parse ...
1
vote
1answer
65 views

Is there a notion of property of a mathematical object?

I have an alphabet or set of symbols $\Sigma$ from which I can build sequences of symbols in $\Sigma^+$ (think of sentences of characters). Now I have a function ...
1
vote
3answers
63 views

Show that $\alpha$ is a bijection.

Let $X$ be a set and consider the function, $\alpha : \mathcal P \left({X}\right) \rightarrow \mathcal P \left({X}\right)$ such that for all $S \in \mathcal P \left({X}\right), \alpha (S) = X ...
1
vote
4answers
136 views

The set of natural number functions is uncountable

I thought the set of natural number functions would be of the same cardinality as the countably infinite product of $\mathbb{N}$, which is countable. Each natural number function can be identified ...
-3
votes
2answers
104 views

Give an example of a function $f: \mathbb{N}\rightarrow\mathbb {N}$ with the property that there exist a function $g:\mathbb{N}\rightarrow\mathbb {N}$

Question: Give an example of a function $f: \mathbb{N}\rightarrow\mathbb {N}$ with the property that there exist a function $g:\mathbb{N}\rightarrow\mathbb {N}$ such that the composition ($g \circ f$) ...
-5
votes
3answers
126 views

Give an example of a function $f: \mathbb{N} \rightarrow \mathbb{N}$ with the property that there exists [closed]

Give an example of a function $f: \mathbb{N} \rightarrow \mathbb{N}$ with the property that there exists a function $g: \mathbb{N} \rightarrow \mathbb{N}$ such that the composition $g \circ f$ is the ...
0
votes
2answers
33 views

Proof of a bijection to the set of subsets?

For part of a proof I wanted to show that $f: \{1,2\} \to \mathcal{S}(X)$ is a bijection, where $\mathcal{S}(X)$ is the set of subsets of $X$, which in this case I know to be $\{\emptyset , X\}$. So I ...
0
votes
1answer
22 views

How large is the set, that is generated by an unrestricted number of operations on elements of $F$?

Given $F$, a set of functions of one unknown $x$: $$ F=\{c,x, \exp(x),\ln(x) \}, $$ where $c$ is a constant term. Further, given the following operations on functions: Addition $f+g$ Multiplication ...
0
votes
3answers
56 views

What is a set of functions?

I know that you can find the number of functions that map $A \to B$ through $|B|^{|A|}$, but I don't understand how this works? If $A={1,2,3}$ and $B={h,t}$, and for every element in $B$, there are ...
1
vote
3answers
30 views

Equal Cardinality

Let X be any set(it could be finite or infinite),and let T={0,1}. Prove that |𝓟(X)| = |F(X,T)| where 𝓟(X) is the power set of X and F(X , T) is the set of all functions from X to T. So, I have ...
2
votes
2answers
126 views

One to One Correspondence between the Set of All functions

Denote by $F(X , Y)$ the set of all functions from $X$ to $Y$. For sets $A$, $B$, and $C$ prove that: B) $F(C , F(B , A))$ is in one-to-one correspondence with $F(B \times C , A)$. Let's give this ...
2
votes
2answers
97 views

Functions and Set Theory [duplicate]

Denote by $F(X,Y)$ the set of all functions from $X$ to $Y$. For sets $A$, $B$, and $C$ prove that a. $F(C,A\times B)$ is in one-to-one correspondence with $F(C,A)\times F(C,B$). Let's give this ...
2
votes
1answer
49 views

What is opposite inclusion?

This is my first time posting on this form, however I think I have what is a simple question. In my Linear Algebra homework assignment my professor has asked me to prove $f(A\cap B)\subset f(A)\cap ...
2
votes
3answers
343 views

Prove a function is one-to-one and onto

I need some help proving the following function is one-to-one and onto for $\mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$. $F(i, j) = {i + j - 1 \choose 2} + j$ I know you guys like to see ...
2
votes
1answer
58 views

Bijective function proof in $R\times R$ and $Z\times N$

How can I verify if these functions are bijective? $ f_4:\Bbb{R^2} \rightarrow \Bbb{R^2}, \ (x,\ y)\mapsto (x+y,\ x-y)$ $ f_5:\Bbb{Z} \times \Bbb{N^*} \rightarrow \Bbb Q, \ (p,\ q)\mapsto p + ...
2
votes
1answer
72 views

Prove: if $A$ is infinite set and $B$ is finite set then $\left| {A - B} \right| = \left| A \right|$

Prove: if $A$ is infinite set and $B$ is finite set then $\left| {A - B} \right| = \left| A \right|$ Well, one way to show it, is to find an injective function, for both directions. First, ...
1
vote
2answers
22 views

What $P(E)\sim (E \to \{ 0,1\} )$ mean?

i was asked to prove: $P(E)\sim (E \to \{ 0,1\} )$. the left-hand side is the set of all subsets of $E$. (Right?) What about the right-hand side? Thanks.
0
votes
2answers
55 views

Determine if injective or surjective

I need to work out if the following function is surjective or injective. I'm unsure as I've just started learning it. $$h: \mathbb N \rightarrow \mathbb N,\quad h(x) = x^2 + 10$$
0
votes
1answer
31 views

Could someone check this proof for me?

The problem (and a definition first): The following definition explained Let $U \subseteq \mathbb{N}$. We say that a function $x: \{0,1\}^U\to \{0,1\}$ is a $xor$ on the set $U$ if the following ...
0
votes
2answers
65 views

Bijections and composite functions

Let $X$ be a set and let $f : X$ $\longrightarrow$ $X$ be a function. Show that $f$ is a bijection if and only if there is a function $g : X$ $\longrightarrow$ $X$ such that $f(g(x)) = g(f(x)) = x$ ...