1
vote
1answer
75 views

how to show a function is bijection

I have taken two numbers $p$ and $r$ where $p,r\in A = \{0,1,\ldots,4i + 1\}$ where $i\geq 1$ and $q\in B = \{0,1,\ldots,n-1\}$. Let $X$ contains all elements obtained by cartesian product of $A$ and ...
2
votes
3answers
73 views

Is this proof correct? Injective function $ f: A \rightarrow B \iff $ function $ g: B \rightarrow A $ is surjective

I've begun a course in "Real Analysis" recently and I have this trivial exercise. Could someone check if my proof is correct? Proposition: There exists Injective function $ f: A \rightarrow B \iff $ ...
0
votes
2answers
32 views

If a mapping and it's inverse are both one to one, then must the mapping be bijective?

If $\sigma$: $A$ $\rightarrow$ $B$ was a mapping which was one to one, and had an inverse $\sigma$$^{-1}$: $B$ $\rightarrow$ $A$ which is also one to one, then are they both bijective mappings? I'm ...
0
votes
2answers
37 views

How to show the surjectivity of $f(x)=x^5$ on $\mathbb R$?

Sasy $f:\mathbb R\to\mathbb R$ define by $f(x)=x^5$ This is definitely injective as $x_1^5=x_2^5 \implies x_1=x_2$ I say it is surjective because for all really $x$ there is all real $y$, $x \in ...
1
vote
1answer
45 views

Intersection of Images of a function

I'm trying to understand intuitively why the image ( under some function ) of the intersection of subsets of the domain of that function is only contained ( and not equal ) to the intersection of the ...
0
votes
0answers
52 views

Elementary Pigeonhole Principle Question

Is my reasoning here correct? If not, advice would be appreciated. Thank you for your time! We assume that $A$ is finite and $f: A \rightarrow A$. We show that $f$ is one-to-one iff $ran \ f = A$. ...
1
vote
1answer
18 views

One set of functions larger than another set of functions?

This summer I've been slowly working through Halmos's Naive Set Theory. I'm not that far, but I know what lies ahead, which is proving that one infinite set is larger than another (the reals larger ...
0
votes
1answer
29 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, ...
5
votes
4answers
297 views

Can functions be defined by relations?

So let us say that for whatever reasons, we are not allowed to use function symbols in first-order logic. Then can we define and use a function only by relations?
0
votes
1answer
32 views

Finding the “canonical decomposition” of a function — I don't know if I'm doing it right

I've been told to identify the terms in the canonical decomposition of the function r |-> exp(2*pi*i*r) from R -> C. I've been able to give an answer, but I think i might have misinterpreted the ...
0
votes
2answers
42 views

Combinaision of two functions

Let us denote $X_0 = \{x, y\}$ and $X_1 = \{a, b\}$ two disjoint sets of variables; let us denote $V$ a set of values. I have two functions $f_0 : X_0 \rightarrow V$ and $f_1 : X_1 \rightarrow V$, ...
0
votes
0answers
22 views

Is there accepted notation and/or terminology for the smallest cover of $S$ with cells from $P$?

Let $X$ denote a set. Then for $S \subseteq X$ and $P$ a partitioning of $X$, define $P \diamond S$ as the smallest cover of $S$ with cells from $P$. Explicitly: $$P \diamond S = \bigcup\{Q \in P ...
2
votes
2answers
52 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 ...
0
votes
2answers
63 views

Explanation of the formula $f^{-1}(Y)=\{x \in A |f(x) \in Y\}$ for the preimage of a set

So I found a Definition in the book that goes like this to find the pre-image of a set: $$f^{-1}(Y)=\{x \in A |f(x) \in Y\}$$ Example of the theorem being used: Let $A = \{1,2,3,4,5,6\}$ and ...
0
votes
2answers
31 views

Relations on set A and conditions of existence of descending chains

I am reading through the Elements of Set theory by Herbert Enderton and even though I have passed this exercise long ago,the more I look at my solution the less I believe it. Problem goes like this: ...
4
votes
1answer
59 views

Proof that there is a bijection, if there are injective maps in both directions

Let $A$ and $B$ be two sets. Let $f:A\to B$ be injective such that $Im(f) \subsetneq B$. Let $g:B\to A$ be injective such that $Im(g) \subsetneq A$. Obviously $A$ and $B$ are not finite sets. Can ...
2
votes
2answers
77 views

Proof for Surjections

I'm reading through Basic Algebra I (which I enjoy so far. Thoughts on this for self-studying?) and am having a difficult time proving surjection. I believe I understand the concept, but when it comes ...
0
votes
1answer
35 views

How to deduce number of unordered distinct pairs using set operations and bijections

In (b) of the example, we are ask to calculate the number of ordered pairs of distinct positive integers. I like the first method's answer (using bijections, set operations) because it clearly shows ...
1
vote
0answers
47 views

Two definitions of functions

In literature on logic and set theory, there seem to be two different definitions of functions, one more general than the other. First of all, a function $f\colon X\to Y$ consists of three element ...
0
votes
2answers
92 views

Showing that $A\rightarrowtail A \times \{x\}$ is a bijection

$A\rightarrowtail A \times \{x\}$ where $A$ is any set and $\{x\}$ is an arbitrary one-object set. How would I show the following is a bijection ( one to one and onto)? I know if I turn it into a ...
2
votes
2answers
34 views

Composition of injections (proof)

I'm trying to prove that composition of injections is an injection. I want to know if this is a good proof: Composition of injections is an injection. Let $f:S_1\rightarrow S_2$ and ...
6
votes
3answers
128 views

Functions with different codomain the same according to my book?

My book gives the following definition: A function $f$ from $A$ to $B$ is defined as $f\subseteq A\times B$ such that if $(a,b)\in f$ and $(a,b_1)\in f$ then $b=b_1$ and there exists a $(a,b)\in ...
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 ...
2
votes
2answers
31 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
1answer
36 views

I need help proving this theorem (composition of functions)

This is the statement: If $f$ and $g$ are functions, the composition $g\circ f$ is a function with $$D(g\circ f)=\{x\in D(f):f(x)\in D(g)\}$$ $$R(g\circ f)=\{g(f(x)):x\in D(g\circ f)\}$$ The ...
1
vote
2answers
56 views

Problem Involving a Generalized Cartesian Product

Let $I$ be a set, and for each $i \in I$, let $U_i$ and $V_i$ be sets. Furthermore, suppose for each $i \in I$, there is a bijection $f_i:U_i \to V_i$. Prove that there is a bijection $g:\prod_{i \in ...
0
votes
3answers
74 views

What would make a function reflexive, transitive, and/or symmetric?

A binary relation $R$ is a subset of the Cartesian product between two sets $X$ and $Y$, containing a set of ordered pairs $\{(x,y) : x \in X, y \in Y\}$. $R$ is a function if each element of $X$ is ...
4
votes
2answers
64 views

Suppose $f: X \rightarrow Y$, and is one-to-one, and let $A \subseteq X$, prove that $f^{-1}[f[A]] = A$. [duplicate]

Suppose $f: X \rightarrow Y$, and is one-to-one, and let $A \subseteq X$, prove that $f^{-1}[f[A]] = A$. EDIT: Actually, this identity should hold even if $f$ is not one-to-one (injective), right? ...
0
votes
1answer
50 views

Understanding the difference between relations and functions.

$R=\{(1,2),(1,3)\}$ is a relation but not function. The logic for this is that if the first element of every ordered pair must remain different, then it is said to be function. Otherwise, it's just ...
2
votes
1answer
45 views

Does something that is injective, surjective or bijective imply that it is a function?

As the title says. Sorry it seems like a silly question but it's something I've been wondering because it seems like sometimes the word "function" is omitted, but other times it is included
0
votes
4answers
30 views

Empty preimage of an intersection implies empty intersection of the preimages

Assume $f:A\to A'$ is a function, $B\subset A'$, $C\subset A'$, and $f^{-1}(B\cap C)=\emptyset$ How can we see that $f^{-1}(B)\cap f^{-1}(C)=\emptyset$?
1
vote
3answers
73 views

Why do we define functions to be set theoretic objects?

Why do we define functions to be set theoretic objects? Functions are so intuitive, why do we define it in complicated set theory language?
9
votes
3answers
254 views

Why is this proof of $\mathbb{N}\times\mathbb{N}$ being countable not formal?

My copy of Introduction to Real Analysis: Bartle and Sherbert gives: Theorem: The set $\mathbb{N}\times\mathbb{N}$ is countable. Informal Proof: Recall that $\mathbb{N}\times\mathbb{N}$ ...
0
votes
1answer
42 views

Confused about images, reverse images.

I am confused over a seemingly simple practice question which I will post below. I am confused over the concept as well, but this question just helps to show what it is I am not understanding. ...
0
votes
2answers
51 views

Converting a set to a tuple?

Okay, so, let's say I have a set: $\{0,1,2,3\}$ And I want to convert it to a tuple: $(0,1,2,3)$ How would I do this? Would it be as simple as: $f(\{0,1,2,3\}) = (0,1,2,3)$ ??
0
votes
2answers
41 views

Prove that $f(m,n) = 2^m(2n +1 ) -1 $ is a bijection

Basically this proves that set of natural numbers is equinumerous to its cartesian product with itself. f I have tried proving injectivity and surjectivity.Here is what I have done so far. To prove ...
1
vote
0answers
41 views

bijective function $h:\mathbb{N}\rightarrow A\cup B$ from bijective functions $f:\mathbb{N}\rightarrow A$, $g:\mathbb{N}\rightarrow B$

Let $A,B\subseteq \mathbb{N}$ and let $f:\mathbb{N}\rightarrow A$, $g:\mathbb{N}\rightarrow B$ be bijective functions. What are ways to construct a bijective function $$h:\mathbb{N}\rightarrow A\cup ...
0
votes
0answers
14 views

For which sets, $X$ the relation is a partial function

Given $T=\left\{\ \left<A,B\right> \in (P(X))^2 | A\subseteq B \right\}$ For which sets, $X$, the relation $(P(X))^2-T \cap (P(X))^2-T^{-1}$ is a partial function? Here's my solution: ...
2
votes
1answer
23 views

Domain of a composite function

I was given the question: Find the domain of the function $f(x)=\ln(\ln(\ln x))$ I found the answer by inspection: $\qquad D(\ln x)=(0,\infty)$ $\therefore\quad D(\ln(\ln x))=(1,\infty)$ ...
1
vote
1answer
16 views

Proving equality of functions using their restrictions

I have been going through Elementary Set Theory by Enderton and once again I am stuck on an exercise, which goes like this (p.88, exercise 27): Assume that $A$ is a set, $G$ is a function, and ...
0
votes
0answers
16 views

Bijective Functions between Multiple Dimensions [duplicate]

Do bijective functions exist that map from a function of one dimension to a function of another dimension? For example, does there exist a function $f : \mathbb{R^2} \rightarrow \mathbb{R^3}$ that is ...
3
votes
1answer
45 views

Preimage simple problem

Which one is correct and which one is wrong ? $f^{-1}[Y \cap Y^{'}] \subseteq f^{-1}[Y] \cap f^{-1}[Y^{'}]$ $f^{-1}[Y] \cap f^{-1}[Y^{'}] \subseteq f^{-1}[Y \cap Y^{'}]$ Here is my solution: ...
0
votes
1answer
84 views

Can a bijection be constructed between $\mathbb{Q}$ and $\mathbb{R}$

Can a bijection be constructed between $\mathbb{Q}$ and $\mathbb{R}$, such that $f:\mathbb{Q} \to \mathbb{R}$ is a bijective function? I understand that there exists no bijection between $\mathbb{N}$ ...
1
vote
1answer
23 views

Injective/Surjection/Bijection

How would you handle the h(x) case to see if it is surjective or injective? Also, how would you prove/disprove that it is a bijection. I know you have to show if it is injective and surjective, but ...
0
votes
2answers
49 views

Proving a Function

Consider the function $f\colon[0,+\infty)\to X$ where $f(x) = 3\sqrt{x+5}-1$. (a) Determine a set $X$ for which $f$ is onto, and then prove that $f$ is onto using your $X$. Really stuck and ...
0
votes
3answers
26 views

Existence of a one-to-one function (injection) from one finite set to another

Consider two finite sets, $A$ and $B$. Is it fine to say that “an injection $f \colon A \rightarrow B$ exists if and only if $|A| \leq |B|$”? If it is, could you please suggest as to how I might ...
1
vote
1answer
54 views

Is injective function $f:A \to A$ always surjective?

Ok so while browsing a book(namely Herbert Endertons book "Elements of set theory") I have stumbled upon a curiosity which provoked me to try to prove this.Here is how I went about it,but I do not ...
2
votes
2answers
20 views

A problem of diagram chasing

Consider the following diagram of functions between sets: I know that the $4$ inner triangles (i.e. $\{X,X',Z\}$,$\{X',Y',Z\}$...) are all commutative diagrams and moreover that $f_1$ and $f_3$ ...
1
vote
0answers
19 views

Show that $F(B)=B$and $F(C)=C$ if $F: \mathcal{P}A \to \mathcal{P}A$ and that $F$ has the monotonicity property [duplicate]

Assume that $F: \mathcal{P}A \to \mathcal{P}A$ and that $F$ has the monotonicity property: $$X \subseteq Y \subseteq A \implies F(X) \subseteq F(Y)$$ Define $$B = \bigcap \{ X \subseteq A | F(X) ...
0
votes
0answers
17 views

How to write the condition for Image of a function?

If $\Omega_l$ is $\Omega$ with $|x|<l$ and if $\Omega_S$ is the image of $z$ under mapping how we will write the condition for it. Am I right if I write $\Omega_S$ is $\Omega$ with $|S|<l$ or ...