let f be a function so that f: N → N. Define rec∞(f ) = {n ∈ N | f -1(n) is infinite}, as in, the set of all the naturals such that they have infinite pre-images in f. Show the following: 1. The set X1 = {f : N → N | |rec∞(f)| = 1} is countable. 2. The set X2 = {f : N → N | |rec∞(f)| = 2} isn't countable.

let f be a function so that f: N → N. Define rec∞(f ) = {n ∈ N | f -1(n) is infinite}, as in, the set of all the naturals such that they have infinite pre-images in f. Show the following: 1. The set X1 = {f : N → N | |rec∞(f)| = 1} is countable. 2. The set X2 = {f : N → N | |rec∞(f)| = 2} isn't countable.

Elements Of Modern Algebra

8th Edition

ISBN:9781285463230

Author:Gilbert, Linda, Jimmie

Publisher:Gilbert, Linda, Jimmie

Chapter1: Fundamentals

Section1.7: Relations

Problem 11E: Let be a relation defined on the set of all integers by if and only if sum of and is odd. Decide...

See similar textbooks

Related questions

Q: 7. (10 points) Let f: A B be onto. Prove that S((C)) = C for all sets CC B.

Q: 7. i) How many functions are there from the set {1, 2, 3, ...,k} where k is a positive integer, to…

Q: How many one-to-one functions are there from a set with m elements to a set with n elements, where…

Q: A0) = 2, A2) = 5 and f(n) = 2 An - 1) +3 (n - 2) + fAn - 3) for all n> 3. Find f(4).

A: Solution:

Q: suppose g: A---> B and f: B---> C are both one-to-one. prove f o g is one-to-one

Q: Let Z be the set of integers, determine f:Z->Z, such that, for all integers a and b,…

Q: Given the following function f:N --> N, define the following set: rec∞(f) = {n ∈ N | f -1(n) is…

A: Set :

Q: Suppose the set of natural numbers is constructed by the constant 0 and the successor function s.…

Q: 2. Let N = {1,2,3,...}. Are the following functions injective, surjective and/or bijec- tive? (i) f:…

Q: 5. Let A = {a,b} and B = {1,2,3}. (a) Write out all functions f: A → B using two-line notation. How…

A: Note:- As per our guidelines, we can answer the first part of this problem as exactly one is not…

Q: A = {5,6} B = {5, 7 ,8} S = {n | n >= 3 is an odd integer} A relation R from AxB to S is defined…

Q: c) Describe the set of all 7. For a function f:A → B, the statement "f is surjective" is defined by…

Q: Count the number X of functions y: (20, 21,..., 23) → (5,6,...,8) so that is not onto. X =

A: Given function φ:(20,21,...,23)→(5,6,...,8)

Q: Let D be the set of all finite subsets of positive integers. Define a function T:Z* → D as follows:…

A: Since T(n)=The set of positive divisors of n. Since 17 ,5 are prime numbers.

Q: 8) a) List the elements of each of the following sets, using the .' notation where necessary: i)…

A: Since it is multiple questions with multipart. As per our company guidelines, we have to solve the…

Q: Given a finite set S, find all possible values of |S] so that the set {(a, b) | (a E S) A (b e S) ^…

Q: 15. Let A be an infinite set. Prove that there exists an injective function f: N→ A.

Q: II. Let Q-set of all real numbers, A-index set. Identify the generalized union and intersection of…

Q: Z is the set of integers, R is the set of real numbers. 3) Each function f is defined as f: R -> R.…

A: The objective is to find the function is one-one or not one-one. (a) fx=x+1x-1for all real numbers x…

Q: ) A) Show that the set of all odd integers is countable, by producing a 1-1 unction F From J onto…

Q: 3. Consider the set X = {a,b,c} and the function f: X→ X defined by the rules f(a) = b. f (b) = a…

A: The set X=a, b, c and the function f:X→X defined by the rules fa=b, fb=a, fc=b. We have to find the…

Q: Show that the interval [0,1] is a closed set in R

Q: Choose the correct option. The number of onto function from the set {1,2,….,11} to the set…

A: Let the set A be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} and the set B be {1, 2, 3, 4, 5, 6, 7, 8, 9,…

Q: Suppose that f is holomorphic in an open set N C C. Prove that f is constant if either one of the…

A: (a) Let f(z)=u+iv. Then R(f)=u. Given that R(f) is constant .Then u=c ,a constant . Then ux=uy=0.…

Q: 9: Determine whether fis injective, surjective or bijective. TROPHE ZBAN DAN d. Suppose f: N→ N has…

Q: Let D be the set of all finite subsets of positive integers. Define a function T:Z+ → D as follows:…

Question

let f be a function so that f: N → N. Define rec∞(f ) = {n ∈ N | f ^-1(n) is infinite}, as in, the set of all the naturals such that they have infinite pre-images in f. Show the following:
1. The set X1 = {f : N → N | |rec∞(f)| = 1} is countable.
2. The set X2 = {f : N → N | |rec∞(f)| = 2} isn't countable.

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

SEE SOLUTION Check out a sample Q&A here

Step 1: Given :

Step 2: Proof 1

Step 3: Proof 2

Solution

Step by step

Solved in 4 steps with 48 images

SEE SOLUTION Check out a sample Q&A here

Similar questions

Let be a relation defined on the set of all integers by if and only if sum of and is odd. Decide whether or not is an equivalence relation. Justify your decision.
Give an example of a relation R on a nonempty set A that is symmetric and transitive, but not reflexive.
Prove that if f is a permutation on A, then (f1)1=f.
21. A relation on a nonempty set is called irreflexive if for all. Which of the relations in Exercise 2 are irreflexive? 2. In each of the following parts, a relation is defined on the set of all integers. Determine in each case whether or not is reflexive, symmetric, or transitive. Justify your answers. a. if and only if b. if and only if c. if and only if for some in . d. if and only if e. if and only if f. if and only if g. if and only if h. if and only if i. if and only if j. if and only if. k. if and only if.
13. Consider the set of all nonempty subsets of . Determine whether the given relation on is reflexive, symmetric or transitive. Justify your answers. a. if and only if is subset of . b. if and only if is a proper subset of . c. if and only if and have the same number of elements.
In each of the following parts, a relation R is defined on the power set (A) of the nonempty set A. Determine in each case whether R is reflexive, symmetric, or transitive. Justify your answers. a. xRy if and only if xy. b. xRy if and only if xy.
A relation R on a nonempty set A is called asymmetric if, for x and y in A, xRy implies yRx. Which of the relations in Exercise 2 areasymmetric? In each of the following parts, a relation R is defined on the set of all integers. Determine in each case whether or not R is reflexive, symmetric, or transitive. Justify your answers. a. xRy if and only if x=2y. b. xRy if and only if x=y. c. xRy if and only if y=xk for some k in . d. xRy if and only if xy. e. xRy if and only if xy. f. xRy if and only if x=|y|. g. xRy if and only if |x||y+1|. h. xRy if and only if xy i. xRy if and only if xy j. xRy if and only if |xy|=1. k. xRy if and only if |xy|1.
Let f:AB and g:BA. Prove that f is one-to-one and onto if fg is one to-one and gf onto.