3
votes
1answer
44 views

Elementary set problem

Let $A$ be a set and $f$ a function $f:A \to A$. A set $B$ is called "solid" in $A$ if and only if $f(B) \subseteq B$. Prove that a set $A$ is finite if and only if there is a function $f:A\to A$ ...
1
vote
3answers
68 views

Set notation and mappings question

Good evening. I have a question. Suppose I have two sets, $A=\{1,2,3,4\}$ and $B=\{5,6\}$. I want to write the notation for a function that takes each element in $A$ and assigns to it a value in $B$. ...
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 ...
0
votes
3answers
34 views

Powerset bijection problem

Please do not provide a full answer for this. Let $2^{S} = \{f : S \rightarrow \{0, 1\}\}$. For $A \subseteq S$, define $\chi_{A}\in2^{S}$ by $$\chi_{A}(s) = \begin{cases} 0 & \text{if } s ...
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
49 views

Proving that the given function $F:\mathbb N\times \mathbb N\to\mathbb N$ is bijective

Consider the function $F:\mathbb N\times\mathbb N\to \mathbb N$ defined by $$F(a,b)=\frac{(a+b-2)(a+b-1)}{2} +a$$ How can I prove that it is a bijective function? I proved it using Partial ...
1
vote
0answers
32 views

Question concerning defining a particular class of functions

I have a multiset of real numbers $X \subseteq \mathbb{R} $ and I want to create a class of injective function to map the elements of $X$ to the unit interval(so basically a normalization). However ...
1
vote
2answers
45 views

Cardinality of all injective functions from $\mathbb{N}$ to $\mathbb{R}$.

What is the cardianlity of: $$ A = \left\{ f:\mathbb{N}\to\mathbb{R} : \text{f is injective} \right\} $$ Trying to prove it using Cantor–Bernstein–Schroeder theorem, I have the obvious side: $$A ...
1
vote
1answer
53 views

Why is the set of functions from $\mathbb N$ to $\mathbb Q$ not equal to the power set of $\mathbb N \times \mathbb Q$?

I'm trying to show that $^{\mathbb{N}}\mathbb{Q}$ is not equal to $\mathcal{P}(\Bbb {N} \times \Bbb {Q})$. I think that I would have to show that either $^{\mathbb{N}}\mathbb{Q} ...
-3
votes
1answer
42 views

Why is the set of functions from the naturals to the rationals a subset of $\mathcal P(\mathbb N \times \mathbb Q)$?

Explain why the set of functions from the naturals to the rationals is a subset of $\mathcal{P}(\mathbb{N} \times \mathbb{Q})$? Give an example to show that the set of functions from the naturals to ...
0
votes
1answer
45 views

What is the cardinality?

Let $A=\left\{1,2,\cdots,10\right\}$ Let $f,g:A\to A$. Consider the equivalence relation $$ fRg \iff \exists h:A\to A. f=h\circ g$$ where $h$ is invertible. Now, let $g(x)=5$: Why is $\left| ...
2
votes
1answer
26 views

Notion of surjective functions

I have some issues with fully understanding the concept of surjection. For the proof of $A_{m}$ being a countable set for each m $\in$ N, then the union $A = \bigcup_{m=1}^{\infty} A_{m}$ is ...
3
votes
2answers
61 views

In composition of two mappings, can the outer mapping access the arguments of the inner mapping?

In composition of two mappings, can the outer mapping access the arguments of the inner mapping? Here is an example to illustrate my question and my thought. E.g. $f: \cup_{n \in \mathbb N} \mathbb ...
18
votes
4answers
3k views

Why is an image called an “image”?

Given a function $f : A \to B$, the image, denoted by $\operatorname{Im}f$ is the set of all $f(x)$ where $x \in A$. Why do we call this set the image? When was it first used, and what motivated its ...
2
votes
1answer
48 views

Proving that a relation is an equivalence relation

I am having difficulties proving the relation IS an equivalence relation. Let $f: X\longrightarrow Y$ be a function from a set $X$ onto a set $Y$. Let $R$ be the subset of $X \times X$ consisting ...
5
votes
2answers
114 views

What is $f(f^{-1}(A))$?

Suppose that $f : E \rightarrow F$. What is $f(f^{-1}(A))$? Is it always $A$? $f^{-1}$ is the inverse function. This is not a homework, I'm confused by this statement.
4
votes
2answers
105 views

Proving that the cardinality of a set is even

Let $E$ be a set and $f:E\to E$ be a function such that $f\circ f=Id$. Let $A=\{x\in E, f(x)\neq x\}$. Suppose that $A$ is finite. Prove that the cardinality of $A$ is even. My ...
1
vote
1answer
44 views

Can injective function has an element that maps to nothing?

Can injective function has an element that maps to nothing? I don't think this violate the definition of injective function. If that is the case, is it possible for a function to be bijective but its ...
1
vote
1answer
80 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
77 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
33 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
38 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 ...
2
votes
1answer
58 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
54 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
19 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
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, ...
5
votes
4answers
300 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
34 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
43 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
24 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
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 ...
0
votes
2answers
70 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
34 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
62 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
41 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
39 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
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
1answer
38 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
57 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
115 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
73 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
55 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
46 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
31 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?