1
vote
2answers
26 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
38 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 ...
3
votes
2answers
39 views

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

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
37 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
41 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
29 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$?
-4
votes
1answer
58 views

To check if the function is onto or not? [closed]

Let $f \colon \mathbb N \to \mathbb N$ given by $$ f(n)=\begin{cases} (n+1)/2 & n \in\mathbb N \text{ odd}\\ n/2& n \in\mathbb N \text{ even} \end{cases} $$ The question is clear as it ...
1
vote
3answers
69 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
4answers
247 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
35 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
46 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)$ ??
-2
votes
0answers
27 views

Question of set theory [duplicate]

Suppose That A is a set that at least have 2 element prove that exist a function form A to A that f is 1-1 and onto that for any x is an element of A,f(x) is not equal with x.
-1
votes
2answers
35 views

What is a preimage of domain's subset? [closed]

Let f: A->B be a function. Now let D be subset of A. What is a preimage of D? Is it empty set? There is no typo. The actual question has D as subset of A and E as subset of B. Then you need to ...
0
votes
2answers
39 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 ...
0
votes
0answers
45 views

Real Analysis - Proving a function is injective

I just need a nudge in the right direction. I know one-to-one (injective) functions but I have never seen it like this: Let $i\colon \mathbb Z\to \mathbb Q$ be defined by $ i(x)=[(x,1)]$ for all ...
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
9 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
20 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
15 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
44 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
73 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
19 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
23 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
52 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
19 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
15 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 ...
6
votes
5answers
523 views

Why is there no function with a nonempty domain and an empty range?

Let $A$ to be a nonempty set and $B= \emptyset$; then $ A \times B$ is a set. And let $F$ be a function $A \to B$. Then $F \subseteq A \times B$. By the axiom of specification, $F$ must exists (if I ...
1
vote
2answers
42 views

Help finding this set

Lets define the following: Let A be a set. A is innumerable if and only if there exists a bijective function from A to $\mathbb{N}$ Proof that there exists an innumerable set $B \subseteq \mathcal P ...
1
vote
2answers
26 views

Bijection and it's inverse

Given $f: X \to Y$ such that $f$ is a bijection prove the existence of a $g:Y\to X$ such that: $f \circ g = 1_Y $ and $g \circ f = 1_X $ Now since $f$ is bijective $\forall y \in Y: \exists!x ...
1
vote
4answers
93 views

If $f \colon A \to B$, $g :\colon B \to C$ and $g\circ f \colon A \to C$ are bijections. Prove that $f $ is 1-1, $g$ is onto.

From what I understand, one-to-oneness means every element in $A$ is mapped to a unique element in $B$. To be onto, means for every $y$ in $B$, there exist at least one $x$ in $A$ from which it can ...
0
votes
2answers
42 views

prove that $f(A) \backslash f(B) \subseteq f(A\backslash B)$

Let $A,B$ be two subsets of a set $X$,and let $f:X \to Y$ be a function.Prove that $f(A) \backslash f(B) \subseteq f(A\backslash B)$ So I first show what these sets are. The set $f(A) \backslash ...
4
votes
2answers
55 views

Assuming that A and B are non-empty, if there is an injective function F : A -> B then there must exist a surjective function g : B -> A

Either give a counter-example, or a proof. A question in my proofs review. From what I understand we must assume each element of A is carried to a unique element of B (i.e. every value of A is ...
1
vote
1answer
27 views

To prove that a specified element belongs to a set under given conditions.

Let $S=\{1,2,\cdots ,n\}$ where $n$ is an odd integer. Let $f$ be a function defined on $\{(i,j): i\in S, j \in S\}$ taking values in $S$ such that $(i) f(s,r)=f(r,s)$ for all $r,s \in S$ $(ii) ...
-1
votes
1answer
30 views

Show a bijection between sets

The question is: prove that there is a bijection between sets A and B for all $n_{1}, n_{2}\in \mathbb N_{> 0}$ and for all $k_{1}, k_{2}\in \mathbb{Z}$ $A = \left\{ {n_{1}q + k_{1}} \mid q\in ...
3
votes
1answer
88 views

Use Cantor-Schroder-Bernstein to prove |X1|=|X2|

If $X_1 = \left\{\text{all functions }f: \mathbb{ R}\rightarrow \mathbb{ R}\right\}$ and $X_2=\left\{\text{all functions }g:\mathbb{R}\rightarrow\mathbb{R}\text{ such that }g(0)=0\right\}$, $a)$ Use ...
0
votes
0answers
45 views

image of intersections of sets and equality with intersection of images.

It can be shown that if $f$ is a map of sets, $f:X\rightarrow Y$ say, that for $A_\lambda \subseteq X, \lambda \in \Lambda$, an indexing set, then: ...
1
vote
0answers
38 views

Cardinality of the set of functions.

Let $\Sigma = \{a_1, a_2, \dots, a_n\}$ - the finite alphabet. We consider the set of functions: $f\colon\Sigma^* \rightarrow \Sigma^* $. How to prove that the cardinality of this set is continuum?
1
vote
0answers
43 views

How do I go about showing the cardinality of two sets are the same?

How do I go about showing that the cardinality of the set of natural numbers and the cardinality of the cartesian product of integers is the same?: |N|=|Z x Z| Directly |N| = Aleph-null and I can ...
-1
votes
1answer
30 views

Prove Every Function is a Relation

In my notes my professor has a question to prove that $\forall m,n \in \Bbb N^+$, $2^{mn}\ge n^m$. There is a suggestion that it can be proved by taking the logarithm of the inequality so that $mn ...
0
votes
1answer
72 views

Beginner proof of image of functions and functions of sets

This is the third time I got my proofs handed back from my teacher. She won't tell me what's wrong except I have to redo it. I am running out of luck and I need help towards the right direction! The ...
1
vote
1answer
45 views

Proving Limits of f(x) and f(a+h) are equal

The question asks me to prove that the equality of these two expressions $\lim_{x\to a} f(x)$ and $\lim_{h \to 0}f(a+h)$ provided their limits exist. My answer: Let $x=a+h$ so this $\lim_{h \to ...
1
vote
1answer
47 views

Proof identity for any function: $F(A) \cap B = F(A \cap F^{-1}(B))$

Let any number $y\in(f(A))\cap B$. We want to show that $y \in f(A \cap f^{-1}(B))$. Then $X \in A$ and $y \in B$. What should I do next?
2
votes
5answers
172 views

Proof strategy for $(\Leftarrow)$: If $g \circ f = id_A$, then $f$ onto $\Leftrightarrow$ $g$ 1-1. [Chartrand 3Ed P239 9.72]

For nonempty sets $A$ and $B$ and functions $f \colon A \to B$ and $g \colon B \to A$, suppose that $g \circ f =$ the identity function on $A$. $(♦)$ (e) $(\Leftarrow)$ Assume that $g$ is ...
0
votes
1answer
52 views

Union of functions

Let $F=\{f(n)\ |\ f:\mathbb N\to\mathbb N\}$ I want to prove that for any $f,g\in F$, there is always an $h\in F$ that is different from $f$ and $g$, and is larger than both of them. I believe that ...
1
vote
2answers
42 views

Conditions on the functions $f,g,h,k$ if $f(x)g(y)=h(x)k(y)$

I was working on this problem, and I thought I'd post my answer so people could see if they have a better one: Spivak Calculus, 4th ed., problem 3-18: Suppose $f,\,g,\,h,\,k$ are functions from ...
0
votes
1answer
46 views

Bijective function with different domain and co-domain element count

To be bijective is to be both injective and surjective. Which in other words, have to have a one-on-one match right? Then how am I supposed to come up with a bijective function if the domain has a ...
1
vote
1answer
80 views

Number of surjective functions from $\{1,2,…,n\}$ to $\{a,b,c\}$

Ok so following questions are given in my text book Let $A = \{1, 2, 3,...., n\}$ and $B =\{a, b, c\}$ then the number of functions form $A$ to $B$ that are onto is. I have no idea how to find ...