1
vote
2answers
19 views

Describe the preimage of the set

I've been stumped on this problem for a while now, unable to find many resources to help me understand how to describe a preimage of a set given a function like this one. Let $f$: $\mathbb Z \to ...
-2
votes
0answers
26 views

1. Determine which of the following functions are injective and which are sur- jective. [closed]

(a)$f:\mathbb{N}→\mathbb{N}, f(x)=3x+2$ (b)$f:\mathbb{Q}→\mathbb{Q}, f(x)=x3+2$ (c)$f:\mathbb{R}→\mathbb{R}, f(x)=−2x+5$ (d)$f:[−π,π]→[−1,1], f(x)=\sin x$. 22 (e)$f:\mathbb{R}→\mathbb{R}$, f(x)= x ...
0
votes
1answer
35 views

Functions involving codomains

Problem: Consider the possible $f: [7]\to[9]$ a) How many have $f(i) $even , for all i? b) How many have rng(f) = {5,6} As far problem a goes, I've only gotten to the answer = 4^7. However I'm not ...
0
votes
0answers
22 views

Determine whether $f$ is a valid function if $f$ (a bit string) is defined as a sequence of $0$ or more bits.

Determine if $f$ is valid from the set of all bit strings to the set of integers if $ f(S) $ is defined as the number of $0$ bits in S. I don't understand where to start. I thought of saying that ...
0
votes
1answer
26 views

How many distinct functions can be defined from set A to P(B)?

A is a set with n elements. B is a set with m elements. How many functions are there from A to P(B)? I am not sure if my thinking is correct. If B is a set with m elements so P(B) = 2^m . Each ...
0
votes
1answer
55 views

How to find the inverse of f?

$ f : A \rightarrow B $ where $ A = B = \left \{4,5,6,7 \right \} $ $ f = \left \{ (4,6),(5,5),(6,7),(7,5) \right \} $ Find $ f^{-1} $ I know how to find the inverse of $ f $ if it were ...
2
votes
2answers
30 views

How to come up with One-To-One and Onto Examples

I'm trying to come up with example functions that are $N \rightarrow N$ for each category: One-to-one but not onto. Onto but not one-to-one. Nether one-to-one nor onto. Both one-to-one and onto. ...
0
votes
1answer
57 views

Use induction to prove that a function is not one to one

Suppose that m and n are positive integers with m > n and f is a function from $\{1, 2,\ldots, m\}$ to $\{1, 2, \ldots , n\}$. Use mathematical induction on the variable n to show that f is not ...
0
votes
3answers
62 views

Is it true that every injective function must be surjective? [duplicate]

I believe it is false, because an injective function never maps elements of the domain to the same element of its codomain, where as the surjective function can map an element of the codomain to any ...
0
votes
1answer
20 views

How to find number of disctinct functions from set A to set B

Let's say there is set A {1, 2, 3} and set B {a, b} While, I know that to find the total number of functions, it's just number of elements from B ^ number of elements from A But I just don't ...
2
votes
1answer
77 views

How to prove a function is not onto?

Let $f : Z\to Z$ be the function defined by $f(x) = 3x + 1$. Prove that $f $ is not onto, using a proof by contradiction. (Choose an integer $n$, and then prove ($\forall m \in Z$)($f(m) ≠ n$) by ...
1
vote
2answers
53 views

How do you solve these recurrence relations for a closed form?

I'm not sure what methods are used to solve recurrence relations for a big-$O$ notation. Thinking about the problem conceptually doesn't really help me, but I feel like I could use some form of ...
0
votes
4answers
40 views

Why is my reasoning wrong in determining how many functions there are from set A to set B?

I am trying to count how many functions there are from a set $A$ to a set $B$. The answer to this (and many textbook explanations) are readily available and accessible; I am not looking for the ...
1
vote
4answers
50 views

Proving onto and 1-1 functions

I understand the 1-1 function side of things, but I still don't really get how to prove that the function is onto Question: Prove that the function $f:\mathbb{R}-\{2\} \to \mathbb{R}-\{5\}$ defined ...
0
votes
0answers
25 views

Bijectivity of a function $f(i,j)=\frac{(i+j)(i+j+1)}{2}+j$

Define $f\colon \mathbb N\times \mathbb N \rightarrow \mathbb N$ by $f(i,j)=\frac{(i+j)(i+j+1)}{2}+j$. how can I prove that f is bijective help please! I should prove that f is surjective and ...
3
votes
2answers
76 views

Find the generating function of the sequence $a_n = \sum\limits_{k=0}^n k(k-1)$

Find the generating function of the sequence $ a_n =\sum\limits_{k=0}^n k(k-1)$ My try: Let's assume $k(k-1)$ is genereated by $F(x)$ then $a_n$ is generated by $\frac{F(x)}{1-x}$ (that's a ...
1
vote
0answers
33 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 ...
0
votes
1answer
37 views

Prove the growth of Fibonacci numbers

Consider a function defined by $f(1) =1$$f(2)=2$$f(n)=f_{n-1}+f_{n-2}$ for all $n>2$. Show that this function grows exponentially. how can I prove this using Master theorem, not using any other ...
0
votes
1answer
46 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| ...
3
votes
3answers
519 views

How many functions are transitive?

Let the set of all functions defined as: $\left\{a,b,c,d\right\} \rightarrow \{a,b,c,d\}$ How many functions are transitive? I've been told to use the fact that a function is transitive iff "it's ...
2
votes
1answer
57 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 ...
1
vote
0answers
123 views

Is this function $f^n_b : \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}^n$ a surjection?

In this text the fractional part of a real $x$ shall be denoted $\{x\}$, such that $x = \lfloor x \rfloor + \{x\}$. Let the set of functions $f^n_b : \mathbb{R}_{\geq 0} \to \mathbb{R}_{\geq 0}^n$ be ...
0
votes
2answers
56 views

What does let $F$ denote the set of all functions from $\{1, 2, 3\}$ to $\{1, 2, 3\}$ mean?

Let $F$ denote the set of all functions from $\{1, 2, 3\}$ to $\{1, 2, 3\}$. I'm supposed to prove that this statement is true or false, $$∀f ∈ F, \;∃g ∈ F\tag i$$ so that $g(f(1)) = 2$ But I'm not ...
0
votes
2answers
71 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
0answers
36 views

Reversible smoothing of a two dimensional function (or an image)

Smoothing of an image, or a two dimensional function is quite easy, there are many methods to achieve it, using average of near elements. But how to make it reversible? Maybe DCT (discrete cosine ...
0
votes
1answer
50 views

How to derive this formula about the bracket function?

Is there a direct way of proving that $$ [nx] = [x] + [x+\frac{1}{2}] + [x+\frac{1}{3}] + \ldots + [x+ \frac{1}{n}]$$ for each real number $x$ and for each positive integer $n$? My effort: Let ...
1
vote
0answers
16 views

Existence of a particular transformation

I've a set of data points $S = \{ x | x\in [0,1]\}$ (i.e. real values from the unit interval). In some cases I've big clusters in the data and I want to spread the values in between the unit interval ...
0
votes
3answers
41 views

Prove a function is surjective or injective

so I'm having trouble figuring out why this question is surjective / where $0$ comes from. $f : \mathbb{N} \longrightarrow \mathbb{N}$ where $f(x) = x + 1$. so given N begins from $0$ it goes: ...
0
votes
1answer
14 views

Classifying relations as functions

so I'm having a bit of trouble actually working out the relation here, I'm fine with determining whether its a function/partialfunction etc I just don't understand how to produce the relation and get ...
2
votes
2answers
70 views

Constructing a function similar to x^3 between [0,1]

I'm trying to construct a function $f$, in order to normalize a dataset(obviously where all the element come from $[0,1] \in \mathbb{R}$. The big picture is that the envisioned $f: [0,1] \rightarrow ...
-1
votes
2answers
63 views

Is $x^2+25x+4 \in \mathcal{O}(x^2)$? If yes how? If no why not? [closed]

Is $x^2+25x+4 \in \mathcal{O}(x^2)$ ? if yes how ?, if no why? i know x^2+25x+4≤25x^2+25x+25≤25x^2+25x^2+25x^2=75x2 for some x what confuses me is x^2+25x+4≤25x^3+25x+25≤25x^3+25x^3+25x^3=75x3 ...
0
votes
3answers
62 views

How can I calculate summations of modulus expressions?

I know that the following holds true: $$\sum_{k=1}^n k = {n (n + 1) \over 2} $$ Can modulus expressions be simplified in similar ways? For example: $$\sum_{k=1}^n (k\bmod x) = ?? $$ To be clear, ...
1
vote
1answer
53 views

Discrete Math - onto, 1-1 functions

Let $S = \{3,B\}$ Give an example of a function $f: S \times S \to S$ that is onto. Give an example of a function $g: S \to S \times S$ that is 1-1. Give an example of a function $h: ...
2
votes
4answers
43 views

Trying to understand how many functions there are from A to B.

I'm trying to understand why there are $B^A$ functions from $A$ to $B$. If $A=${$a,b$} and $B=${$1,2,3$} then the functions from $A$ to $B$ are $f(a)=1$, $f(b)=1$, $f(a)=2$, $f(b)=2$, $f(a)=3$, ...
0
votes
1answer
53 views

Prove that function f is injective, if function (g o f) is injective as well

I'm sort of stuck with this type of proof. Not quite sure how to go about it. I was wondering if someone could help me out to get started with it. I guess that the two hypotheses I have are these: ...
1
vote
2answers
93 views

Trouble understanding Big O notation for a sum of n integers [duplicate]

This problem is an example in a Discrete Math textbook. How can big-O notation be used to estimate the sum of the first n positive integers? Solution: Because each of the integers in the sum of the ...
0
votes
1answer
11 views

Function form understanding

I dont understand what is the function when im given this kind of form: f= {<1,1>,<2,3>,<3,2>}. I understand functions when they are given in lambda form. For example how can I find the ...
0
votes
1answer
40 views

Defining a bijective function from $2\mathbb{N}$ to $3\mathbb{Z}-1$?

$2\mathbb{N}=\{2n:n\in\mathbb{N}\}$ and $3\mathbb{Z}-1=\{3n-1:n\in\mathbb{Z}\}$ Work: So far, my plan is to first define a bijective function from $2\mathbb{N}$ to $\mathbb{N}$ and then define ...
0
votes
3answers
54 views

Proving that function $f:[0,\infty)\rightarrow [0,\infty)$ defined by $f(x)=\frac{x^2}{1-x}$ is bijective.

I am having a bit of trouble with the algebra for proving that the function is injective. Basically I set $f(a)=f(b)$ for $a,b\in[0,\infty)$ and $a,b\neq 1$. ...
0
votes
2answers
28 views

Bijection of a function.

Define the function f: $(2,\infty) -> (-\infty,-1)$ by $f(x)= \frac{-x}{x-2}$. Show that f is bijective. I know i need to prove both injective and surjective, and I was able to solve the equation ...
1
vote
2answers
96 views

How to prove a function from $\mathbb N\times \mathbb N$ to $\mathbb N$ is bijective. [duplicate]

I am having trouble with this problem: $f\colon \mathbb N\times \mathbb N \rightarrow \mathbb N$ is defined by $f(i,j)=\dfrac{(i+j-1)(i+j-2)}{2}+i$. How do you prove that $f$ is a bijection from ...
1
vote
2answers
68 views

Proving that a function from $N\times N$ to $N$ is bijective.

I am stuck on this problem: Define $f: N\times N \rightarrow N$ by $f(i,j)=\frac{(i+j-1)(i+j-2)}{2}+i$. How do you prove that $f$ is a bijection thus $N\times N$ and $N$ are numerically ...
0
votes
0answers
45 views

Proving that the set of irrational numbers is uncountable [duplicate]

Work: Assume that the set of irrational numbers is countable. Since $Q$ is infinite, it is therefore denumerable. Therefore, there exists a bijective function $f: N \rightarrow Q$. From here I am ...
1
vote
1answer
48 views

Proving that $f: N\times N \rightarrow N$ is surjective [duplicate]

I am having trouble proving that the function $$f: N\times N \rightarrow N, \ \ f(i,j)=2^{i-1}(2j-1)$$ is surjective. Work: I know that using the theorem in which $n$ is the product of prime numbers ...
0
votes
2answers
153 views

Proving that $f$ is a bijection from $N$x$N$ to $N$.

I am having trouble with the following problem: $f: N\times N\rightarrow N$ and $f(i,j)=2^{i-1}(2j-1)$. Prove that $f$ is a bijection thus $N\times N$ and $N$ are numerically equivalent. Work: I ...
2
votes
5answers
685 views

Explanation of recursive function

Given is a function $f(n)$ with: $f(0) = 0$ $f(1) = 1$ $f(n) = 3f(n-1) + 2f(n-2)$ $\forall n≥2$ I was wondering if there's also a non-recursive way to describe the same function. WolframAlpha tells ...
2
votes
3answers
50 views

Why is the inverse of this function not a function?

Why does $F^{-1}$ need to be defined on all of $Y$? I can have this function: $g(x)=x,\quad x\ne 3$ and even though it is not defined for all $x$ in its domain, it is still a function, right?
0
votes
1answer
43 views

How can a function not be one to one and be a function?

My understanding of the definition of a function Given any x, there is only one y that can be paired with x My understanding of a 1 to 1 function Given any y, there is only one x that can be paired ...
1
vote
1answer
42 views

Help with composite identity functions in discrete mathematics

I am having trouble with the following problem: For nonempty sets $A$ and $B$ and functions $f : A \rightarrow B$ and $g: B \rightarrow A$ suppose that $g \circ f = i_A$, the identity function on ...
0
votes
1answer
10 views

Does each element in domain need result for onto functions?

For onto functions, do all the elements in the domain have to give a result from the range? I know that for one-to-one, every single $x$ must give a result, and one that is a unique $y$. For onto ...