2
votes
2answers
70 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
32 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 ...
0
votes
0answers
43 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 ...
-1
votes
2answers
86 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
33 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
119 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
59 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
30 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
32 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
46 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
58 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
53 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
39 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
43 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
70 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
251 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
36 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
47 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
10 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
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
75 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
24 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
53 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
529 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
97 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
32 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
90 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
46 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 ...