1
vote
2answers
76 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
44 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
36 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
35 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
45 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
630 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
42 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
40 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 ...
0
votes
0answers
10 views

Discrete Math Trace recursive function

Does anybody know how to trace this function by specifying the recursive calls to the function? The inputs are: A = {24, 15, 7, 10, 8, 30}, i = 2, n = 6 RandomElement(A) returns an element of A ...
1
vote
1answer
16 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
8 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 ...
0
votes
0answers
20 views

Discrete Math identity function proof

Hi I am having trouble with this question: 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 $A$. How do ...
1
vote
1answer
28 views

Help with identity functions in discrete mathematics

I have trouble with trying to solve 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 ...
-1
votes
3answers
41 views

Proving functions are injective and surjective

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 of $A$. ...
0
votes
3answers
25 views

Injective and Surjective Function Examples

I am having trouble with this problem: Give an example of a function $f:Z \rightarrow N$ that is a. surjective but not injective b. injective but not surjective Work: I came up with examples such ...
0
votes
1answer
14 views

Proving Integer Modulo is Well-Defined

I have trouble figuring out this problem: $h: Z_4 \rightarrow Z_6$ by $h([a])=[3a]$ for each $a\in Z$. Prove that h is well-defined thus it is a function and that h is neither injective nor ...
0
votes
1answer
39 views

Confusion surrounding functions

Hey there Mathematics, Slightly confused over some of the things in my quiz and was wondering if I could get an explanation: I thought with the first question that it's just one-to-one from X to Y ...
1
vote
2answers
23 views

Help with Discrete Math Functions and Bijections

I have trouble with the following problem: Prove that the function $f(x)=x^2-2x+3$, with domain $x\in (-\infty, 0)$, is a bijection from $(-\infty, 0)$ to its range. Work: I tried to first prove ...
0
votes
1answer
27 views

Help with Functions in Discrete Mathematics

I am having trouble solving this problem: let $p$ be a positive prime number and let $f:Z_p -> Z_p$ be defined as $f([x])=[x^2]$. Show that $f$ is a function. Give examples of how it is not ...
0
votes
1answer
31 views

Equivalence Relation on R (real numbers)

Let R be the relation on R(real numbers) defined by: For all x, y (that belong) to R(real numbers), x relates y <=> x-y (that belongs) to Z. (a) Is R an equivalence relation? Prove your answer. ...
-1
votes
2answers
110 views

Give a Bijection that is in-between 2 intervals and use a formal proof to show that it is a bijection. [duplicate]

∀w,x,y,z ∈ R, w < x and y < z. Given that information, supply a bijection between the two intervals. (w,x) and (y,z) Then after you find the bijection, provide a formal proof that what you found ...
1
vote
1answer
51 views

Let A = {1,2,3,4} Let F be the set of all functions from A to A. (check the parts)

Let $\operatorname{S}$ be a relation on $F$ defined by: $\forall f, g \in F, f\,\operatorname{S}\,g \iff f(i) = g(i), \exists i \in A$. (a) Recall that the identity function $I_A : A \mapsto A$ is ...
0
votes
1answer
19 views

How many functions with A having 9 elements and B having 7 elements have only 1 element mapped to 7?

So, the question I have is: How many onto functions [9] --> [7] have only one element mapped to 7? This is asking how many functions with A having 9 elements and B having 7 elements have only 1 ...
0
votes
1answer
47 views

Discrete Math: Functions and Set Questions

1) Consider the function: $f: \mathbb{R} \to \mathbb{R}$ (Real to Real Number), where $f(x)=2+x^2$, what would be all of the preimages of $3$? 1) $11$ 2) $11$, $-11$ 3) $1$, $-1$ 4) $1$ 2) Let $D ...
1
vote
1answer
45 views

A one-to-one function from $\mathbb{Z}^+ \to (0,1)$?

I ran into a interesting homework question that asked me to find an example of a one-to-one function $f: \mathbb{Z}^+ \to (0,1)$. I'm thinking it should be some kind of linear function, or polynomial ...
0
votes
1answer
68 views

Let $S =\{1,2,3,4,5 \} $ For each give a brief explanation and simply answer to a number. (a) How many functions $f: S \longrightarrow S$ are there?

(b) How many one-to-one functions $f : S\longrightarrow S$ are there? (c) How many functions $f : S \longrightarrow S$ are there so that $f o f(1) = 2$ ? (d) How many onto functions $f: ...
0
votes
1answer
58 views

Prove that this function defined by f(x) is bijective.

Prove that the function $ f: \mathbb{R} - \{1\} \to \mathbb{R} - \{1\}$ defined by $ f(x) $ is bijective. $$ f(x)=\left({x+1\over x-1}\right)^3 $$ I am taking my first Computer Science ...
0
votes
3answers
65 views

Proving a function is a one to one correspondence

I understand that to show a function is a one to one correspondence, you have to show that the function is both one to one and onto. Proving a function is one to one seems simple enough. However for ...
3
votes
1answer
38 views

Discrete math functions help?

I'm doing a review for my discrete math test on functions and I'm having troubles with a few questions. Can I get some guidance in how to do these questions so I can be more prepared for the test? ...
0
votes
3answers
19 views

Function Mappings

There are two “shift functions” mapping $\Bbb N$ into $\Bbb N$: $f(n)=n+1$ and $g(n)=\max\{0,n-1\}$ for $n\in\Bbb N$. How to show that $(g\circ f)(n)=n$ for all $n$, but that $(f\circ g)(n)=n$ does ...
0
votes
3answers
41 views

Prove that a function is one to one without graphing

I know that you can prove a function is one to one by graphing it and using the horizontal line test. But in my notes it showed another way to prove a function is one to one but I am not sure if I am ...
1
vote
2answers
28 views

An example of a function whose domain is the set of positive integers and range is the set of integers?

I was browsing through one of my old pre-calc books, and I feel a bit ashamed to say I can't think of a simple answer. It intuitively feels impossible, as there are half as many points in the domain ...
0
votes
4answers
46 views

How many different functions $f: A \rightarrow B$ are there if $|A| = m$ and $|B| = n$

I'm not quite sure of what this question is asking. Can someone explain please
3
votes
0answers
54 views

Find generating function For sequences

Can anyone out here help? The exercise says: "Find the generating function for each of the sequences below (the general term is given)" Now, the question is how do you find one for those: a) $U_n = ...
0
votes
1answer
16 views

One to one function behaviour

Like in pigeon hole principle , if one set of objects(S1) has more items than others set of objects(S2) and we try to fit that S1 in S2 ( that is mapping the values of S1 to S2 , we end up getting ...
1
vote
0answers
16 views

Counting Surjective functions without using the formula

Ok, so suppose I have a Domain set A with 5 elements {1,2,3,4,5} that maps to CoDomain set B with 3 elements {A,B,C} How do I find how many surjective functions there are? My intuition was to take ...
0
votes
1answer
17 views

Partial and Total functions

OK guys I have to find the number of partial and total functions $ f:A\rightarrow A $ , where $ |A|=n $. The answers are respectively $ (n+1)^n $ and $ n^n $, but I just can't figure out how exactly ...
3
votes
2answers
44 views

one-to-one and onto functions help

I am trying to understand this exercise. Define $S : \mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ by the rule: For all integers $n$, $S(n) =$ the sum of the positive divisors of $n$. a. Is $S$ one-to-one? ...
0
votes
2answers
42 views

one-to-one and onto function question

I am trying to understand this exercise: Let S be the set of all strings of 0's and 1's, and define f: S -> $Z^{nonneg}$ by f(s) = the length of s, for all string in S. a. Is f one-to-one? The ...
2
votes
1answer
58 views

Bijective function proof in $R\times R$ and $Z\times N$

How can I verify if these functions are bijective? $ f_4:\Bbb{R^2} \rightarrow \Bbb{R^2}, \ (x,\ y)\mapsto (x+y,\ x-y)$ $ f_5:\Bbb{Z} \times \Bbb{N^*} \rightarrow \Bbb Q, \ (p,\ q)\mapsto p + ...
0
votes
1answer
26 views

show that R is an equivalent relation

Let $m>1$ be an integer, the relation $R$ on $\mathbb{N}$ given by $R=\{(a,b):a\equiv b \mod m\}$ , that is $aRb \Rightarrow a\equiv b\mod m$ where $a\equiv b\mod m$ iff $m$ divides $a-b$. Show ...
1
vote
1answer
496 views

Prove that between every two rational numbers a/b and c/d that there is a rational number and there are an infinite number of rational numbers [duplicate]

So the full problem is Prove that between every two rational numbers $a/b$ and $c/d$ that: There is a rational number There are an infinite number of rational numbers I am having ...
0
votes
1answer
74 views

Needed a math function, Don't know what to call it?

I need a math function $f(\ell)\to n$ whose input is a list of numbers and whose output is a noisy value (random value added to original input to get noisy output). The function $f(\cdot)$ should have ...
1
vote
2answers
34 views

Confusion over Directly Proving Surjectivity

I have a question related to the surjectivity of a function. I understand what surjectivity is, in the sense that, if $f:X\longrightarrow Y$, then $f$ is surjective if $\forall_{y\in Y}\exists_{x\in ...
0
votes
1answer
61 views

discrete math question with function growth

Consider three functions, defined recursively, each with the same initial value $V(1)=T(1)=U(1)=3$ but different recurrence relationships for $n>1$: ...
-3
votes
3answers
55 views

discrete one to one function proof [closed]

Prove the following function is one to one function $$f : \mathbb N\times \mathbb N \to \mathbb N ,\quad f( i , j ) = 2^i3^j$$
0
votes
1answer
50 views

How to prove such program is uncomputable

We say that two programs are equivalent if they give the same output on every input. Prove that it is impossible to write a computer program that takes as input two pieces of code, code1 and code2, ...
0
votes
2answers
178 views

How to show this function is an injection (one to one)?

Consider the function $f: \mathbb N$ × $\mathbb N$ → $\mathbb R$, $f(a,b) = a+b \sqrt{11}$ How do I show this function is an injection (one to one)?
2
votes
5answers
57 views

What functions $f: A \to B$ and $g: B \to A$, satisfy a restriction such that $f$ is not invertible but $f \circ g=id_B$?

I am caught up on the notation of $id_B$. I'm thinking that $f=x^2$, or something along those lines, but not so sure as to what $g$ may be.
1
vote
2answers
26 views

Function and its inverse in Discrete Mathematics

Prove that : if $L \subseteq M,$ then $f^{-1}(L) \subseteq f^{-1}(M)$.