Explanation Given information: X = { x 1 , x 2 , ....... , x n } be a set with n elements. Concept used: In one-to-one function, distinct elements in domain are mapped with distinct elements in co-domain. Proof: Let X = { x 1 , x 2 , ....... , x n } and S be the set of all strings of 0 ' s and 1 ' s of length n . Define f : P ( X ) → S such that f ( A ) = a string of 0 ' s and 1 ' s of length n such that x i ∈ A if and only if i th place is 1 in the string. To show f is one-to-one, let f ( A ) = f ( B ) . Let x i ∈ A i th place is 1 in the string f ( A ) To determine (b) To find: Total number of subsets of a set with n elements.

5th Edition

ISBN: 9780357035283

Author: EPP

Publisher: Cengage

See similar textbooks

Videos

Question

Chapter 7.2, Problem 56ES

To determine

(a)

To prove:

If X={x1,x2,......,xn} be a set with n elements, then a one-to-one correspondence from P(X), the set of all subsets of X, to the set of all strings of 0's and 1's that have length n.

To determine

(b)

To find:

Total number of subsets of a set with n elements.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 7.2, Problem 55ES

Chapter 7.2, Problem 57ES

Students have asked these similar questions

Explain the key points and reasons for 12.8.2 (1) and 12.8.2 (2)

Q1: A slider in a machine moves along a fixed straight rod. Its distance x cm along the rod is given below for various values of the time. Find the velocity and acceleration of the slider when t = 0.3 seconds. t(seconds) x(cm) 0 0.1 0.2 0.3 0.4 0.5 0.6 30.13 31.62 32.87 33.64 33.95 33.81 33.24 Q2: Using the Runge-Kutta method of fourth order, solve for y atr = 1.2, From dy_2xy +et = dx x²+xc* Take h=0.2. given x = 1, y = 0 Q3:Approximate the solution of the following equation using finite difference method. ly -(1-y= y = x), y(1) = 2 and y(3) = −1 On the interval (1≤x≤3).(taking h=0.5).

Ф sketch stability x= -4x + 2xy - 8 y° = 4 y 2 - x² чуг.

Chapter 7 Solutions

Discrete Mathematics With Applications

Ch. 7.1 - Given a function f from a set X to a set Y, f(x)...Ch. 7.1 - Given a function f from a set X to a set Y, if...Ch. 7.1 - Prob. 3TY Ch. 7.1 - Given a function f then a set X to a set Y, if...Ch. 7.1 - Prob. 5TY Ch. 7.1 - Prob. 6TY Ch. 7.1 - Prob. 7TY Ch. 7.1 - Prob. 8TY Ch. 7.1 - Prob. 9TY Ch. 7.1 - Prob. 1ES

Ch. 7.1 - Let X={1,3,5} and Y={a,b,c,d}. Define g:XY by the...Ch. 7.1 - Indicate whether the statement in parts (a)-(d)...Ch. 7.1 - a. Find all function from X={a,b}toY={u,v} . b....Ch. 7.1 - Let Iz be the identity function defined on the set...Ch. 7.1 - Find function defined on the sdet of nonnegative...Ch. 7.1 - Let A={1,2,3,4,5} , and define a function F:P(A)Z...Ch. 7.1 - Let Js={0,1,2,3,4} , and define a function F:JsJs...Ch. 7.1 - Define a function S:Z+Z+ as follows: For each...Ch. 7.1 - Prob. 10ES Ch. 7.1 - Define F:ZZZZ as follows: For every ordered pair...Ch. 7.1 - Let JS={0,1,2,3,4} ,and define G:JsJsJsJs as...Ch. 7.1 - Let Js={0,1,2,3,4} , and define functions f:JsJs...Ch. 7.1 - Define functions H and K from R to R by the...Ch. 7.1 - Prob. 15ES Ch. 7.1 - Let F and G be functions from the set of all real...Ch. 7.1 - Prob. 17ES Ch. 7.1 - Find exact values for each of the following...Ch. 7.1 - Prob. 19ES Ch. 7.1 - Prob. 20ES Ch. 7.1 - If b is any positive real number with b1 and x is...Ch. 7.1 - Prob. 22ES Ch. 7.1 - Prob. 23ES Ch. 7.1 - If b and y are positivereal numbers such that...Ch. 7.1 - Let A={2,3,5} and B={x,y}. Let p1 and p2 be the...Ch. 7.1 - Observe that mod and div can be defined as...Ch. 7.1 - Let S be the set of all strings of as and bs....Ch. 7.1 - Consider the coding and decoding functions E and D...Ch. 7.1 - Consider the Hamming distance function defined in...Ch. 7.1 - Draw arrow diagram for the Boolean functions...Ch. 7.1 - Fill in the following table to show the values of...Ch. 7.1 - Cosider the three-place Boolean function f defined...Ch. 7.1 - Student A tries to define a function g:QZ by the...Ch. 7.1 - Student C tries to define a function h:QQ by the...Ch. 7.1 - Let U={1,2,3,4} . Student A tries to define a...Ch. 7.1 - Prob. 36ES Ch. 7.1 - On certain computers the integer data type goed...Ch. 7.1 - Prob. 38ES Ch. 7.1 - Prob. 39ES Ch. 7.1 - Prob. 40ES Ch. 7.1 - Prob. 41ES Ch. 7.1 - In 41-49 let X and Y be sets, let A and B be any...Ch. 7.1 - Prob. 43ES Ch. 7.1 - Prob. 44ES Ch. 7.1 - Prob. 45ES Ch. 7.1 - Prob. 46ES Ch. 7.1 - Prob. 47ES Ch. 7.1 - Prob. 48ES Ch. 7.1 - Prob. 49ES Ch. 7.1 - Prob. 50ES Ch. 7.1 - Each of exercises 51-53 refers to the Euler phi...Ch. 7.1 - Prob. 52ES Ch. 7.1 - Each of exercises 51-53 refers to the Euler phi...Ch. 7.2 - If F is a function from a set X to a set Y, then F...Ch. 7.2 - If F is a function from a set X to a set Y, then F...Ch. 7.2 - Prob. 3TY Ch. 7.2 - Prob. 4TY Ch. 7.2 - Prob. 5TY Ch. 7.2 - Prob. 6TY Ch. 7.2 - Prob. 7TY Ch. 7.2 - Given a function F:XY , to prove that F is not one...Ch. 7.2 - Prob. 9TY Ch. 7.2 - Prob. 10TY Ch. 7.2 - Prob. 11TY Ch. 7.2 - The definition of onr-to-one is stated in two...Ch. 7.2 - Fill in each blank with the word most or least. a....Ch. 7.2 - When asked to state the definition of one-to-one,...Ch. 7.2 - Let f:XY be a function. True or false? A...Ch. 7.2 - All but two of the following statements are...Ch. 7.2 - Let X={1,5,9} and Y={3,4,7} . a. Define f:XY by...Ch. 7.2 - Let X={a,b,c,d} and Y={e,f,g} . Define functions F...Ch. 7.2 - Let X={a,b,c} and Y={d,e,f,g} . Define functions H...Ch. 7.2 - Let X={1,2,3},Y={1,2,3,4} , and Z= {1,2} Define a...Ch. 7.2 - a. Define f:ZZ by the rule f(n)=2n, for every...Ch. 7.2 - Define F:ZZZZ as follows. For every ordered pair...Ch. 7.2 - a. Define F:ZZ by the rule F(n)=23n for each...Ch. 7.2 - a. Define H:RR by the rule H(x)=x2 , for each real...Ch. 7.2 - Explain the mistake in the following “proof.”...Ch. 7.2 - In each of 15-18 a function f is defined on a set...Ch. 7.2 - Prob. 16ES Ch. 7.2 - Prob. 17ES Ch. 7.2 - Prob. 18ES Ch. 7.2 - Referring to Example 7.2.3, assume that records...Ch. 7.2 - Define Floor: RZ by the formula Floor (x)=x , for...Ch. 7.2 - Prob. 21ES Ch. 7.2 - Let S be the set of all strings of 0’s and 1’s,...Ch. 7.2 - Define F:P({a,b,c})Z as follaws: For every A in...Ch. 7.2 - Les S be the set of all strings of a’s and b’s,...Ch. 7.2 - Let S be the et of all strings is a’s and b’s, and...Ch. 7.2 - Prob. 26ES Ch. 7.2 - Let D be the set of all set of all finite subsets...Ch. 7.2 - Prob. 28ES Ch. 7.2 - Define H:RRRR as follows: H(x,y)=(x+1,2y) for...Ch. 7.2 - Define J=QQR by the rule J(r,s)=r+2s for each...Ch. 7.2 - Prob. 31ES Ch. 7.2 - a. Is log827=log23? Why or why not? b. Is...Ch. 7.2 - Prob. 33ES Ch. 7.2 - The properties of logarithm established in 33-35...Ch. 7.2 - Prob. 35ES Ch. 7.2 - Prob. 36ES Ch. 7.2 - Prob. 37ES Ch. 7.2 - Prob. 38ES Ch. 7.2 - Prob. 39ES Ch. 7.2 - Suppose F:XY is one—to—one. a. Prove that for...Ch. 7.2 - Suppose F:XY is into. Prove that for every subset...Ch. 7.2 - Prob. 42ES Ch. 7.2 - Prob. 43ES Ch. 7.2 - In 44-55 indicate which of the function in the...Ch. 7.2 - In 44-55 indicate which of the function in the...Ch. 7.2 - Prob. 46ES Ch. 7.2 - Prob. 47ES Ch. 7.2 - Prob. 48ES Ch. 7.2 - Prob. 49ES Ch. 7.2 - Prob. 50ES Ch. 7.2 - Prob. 51ES Ch. 7.2 - Prob. 52ES Ch. 7.2 - Prob. 53ES Ch. 7.2 - Prob. 54ES Ch. 7.2 - Prob. 55ES Ch. 7.2 - Prob. 56ES Ch. 7.2 - Write a computer algorithm to check whether a...Ch. 7.2 - Write a computer algorithm to check whether a...Ch. 7.3 - If f is a function from X to Y’,g is a function...Ch. 7.3 - Prob. 2TY Ch. 7.3 - If f is a one-to=-one correspondence from X to Y....Ch. 7.3 - Prob. 4TY Ch. 7.3 - Prob. 5TY Ch. 7.3 - Prob. 1ES Ch. 7.3 - In each of 1 and 2, functions f and g are defined...Ch. 7.3 - In 3 and 4, functions F and G are defined by...Ch. 7.3 - In 3 and 4, functions F and G are defined by...Ch. 7.3 - Define f:RR by the rule f(x)=x for every real...Ch. 7.3 - Define F:ZZ and G:ZZ . By the rules F(a)=7a and...Ch. 7.3 - Define L:ZZ and M:ZZ by the rules L(a)=a2 and...Ch. 7.3 - Let S be the set of all strings in a’s and b’s and...Ch. 7.3 - Define F:RR and G:RZ by the following formulas:...Ch. 7.3 - Prob. 10ES Ch. 7.3 - Define F:RR and G:RR by the rules F(n)=3x and...Ch. 7.3 - The functions of each pair in 12—14 are inverse to...Ch. 7.3 - G:R+R+ and G1:RR+ are defined by G(x)=x2andG1(x)=x...Ch. 7.3 - H and H-1 are both defined from R={1} to R-{1} by...Ch. 7.3 - Explain how it follows from the definition of...Ch. 7.3 - Prove Theorem 7.3.1(b): If f is any function from...Ch. 7.3 - Prove Theorem 7.3.2(b): If f:XY is a one-to-one...Ch. 7.3 - Prob. 18ES Ch. 7.3 - If + f:XY and g:YZ are functions and gf is...Ch. 7.3 - If f:XY and g:YZ are function and gf is onto, must...Ch. 7.3 - Prob. 21ES Ch. 7.3 - If f:XY and g:YZ are functions and gf is onto,...Ch. 7.3 - Prob. 23ES Ch. 7.3 - Prob. 24ES Ch. 7.3 - Prob. 25ES Ch. 7.3 - In 26 and 27 find (gf)1,g1,f1, and f1g1 , and...Ch. 7.3 - In 26 and 27 find (gf)1,g1,f1 , and f1g1 by the...Ch. 7.3 - Prob. 28ES Ch. 7.3 - Suppose f:XY and g:YZ are both one-to-one and...Ch. 7.3 - Prob. 30ES Ch. 7.4 - A set is finite if, and only if,________Ch. 7.4 - Prob. 2TY Ch. 7.4 - The reflexive property of cardinality says that...Ch. 7.4 - The symmetric property of cardinality says that...Ch. 7.4 - The transitive property of cardinality say that...Ch. 7.4 - Prob. 6TY Ch. 7.4 - Prob. 7TY Ch. 7.4 - Prob. 8TY Ch. 7.4 - Prob. 9TY Ch. 7.4 - Prob. 1ES Ch. 7.4 - Show that “there are as many squares as there are...Ch. 7.4 - Let 3Z={nZn=3k,forsomeintegerk} . Prove that Z and...Ch. 7.4 - Let O be the set of all odd integers. Prove that O...Ch. 7.4 - Let 25Z be the set of all integers that are...Ch. 7.4 - Prob. 6ES Ch. 7.4 - Prob. 7ES Ch. 7.4 - Use the result of exercise 3 to prove that 3Z is...Ch. 7.4 - Show that the set of all nonnegative integers is...Ch. 7.4 - In 10-14 s denotes the sets of real numbers...Ch. 7.4 - Prob. 11ES Ch. 7.4 - In 10-14 S denotes the set of real numbers...Ch. 7.4 - Prob. 13ES Ch. 7.4 - Prob. 14ES Ch. 7.4 - Show that the set of all bit string (string of 0’s...Ch. 7.4 - Prob. 16ES Ch. 7.4 - Prob. 17ES Ch. 7.4 - Must the average of two irrational numbers always...Ch. 7.4 - Prob. 19ES Ch. 7.4 - Give two examples of functions from Z to Z that...Ch. 7.4 - Give two examples of function from Z to Z that are...Ch. 7.4 - Define a function g:Z+Z+Z+ by the formula...Ch. 7.4 - âa. Explain how to use the following diagram to...Ch. 7.4 - Prob. 24ES Ch. 7.4 - Prob. 25ES Ch. 7.4 - Prove that any infinite set contain a countable...Ch. 7.4 - Prove that if A is any countably infinite set, B...Ch. 7.4 - Prove that a disjoint union of any finite set and...Ch. 7.4 - Prove that a union of any two countably infinite...Ch. 7.4 - Prob. 30ES Ch. 7.4 - Use the results of exercise 28 and 29 to prove...Ch. 7.4 - Prove that ZZ , the Cartesian product of the set...Ch. 7.4 - Prob. 33ES Ch. 7.4 - Let P(s) be the set of all subsets of set S, and...Ch. 7.4 - Prob. 35ES Ch. 7.4 - Prob. 36ES Ch. 7.4 - Prove that if A and B are any countably infinite...Ch. 7.4 - Prob. 38ES

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.

(a) To prove: If X = { x 1 , x 2 , ...... , x n } be a set with n elements, then a one-to-one correspondence from P ( X ) , the set of all subsets of X , to the set of all strings of 0 ' s and 1 ' s that have length n .

Solution Summary: The author explains the one-to-one correspondence between distinct elements in a domain and distinct ones in co-domain.

Videos

(a)

To prove:

If X={x1,x2,......,xn} be a set with n elements, then a one-to-one correspondence from P(X), the set of all subsets of X, to the set of all strings of 0's and 1's that have length n.

(b)

To find:

Total number of subsets of a set with n elements.

Want to see the full answer?

Chapter 7 Solutions

(a) To prove: If X = { x 1 , x 2 , ...... , x n } be a set with n elements, then a one-to-one correspondence from P ( X ) , the set of all subsets of X , to the set of all strings of 0 ' s and 1 ' s that have length n .

Solution Summary: The author explains the one-to-one correspondence between distinct elements in a domain and distinct ones in co-domain.

Videos

(a) To prove: If X={x1,x2,......,xn} be a set with n elements, then a one-to-one correspondence from P(X), the set of all subsets of X, to the set of all strings of 0's and 1's that have length n.

(b) To find: Total number of subsets of a set with n elements.

Want to see the full answer?

Chapter 7 Solutions

(a)

To prove:

If X={x1,x2,......,xn} be a set with n elements, then a one-to-one correspondence from P(X), the set of all subsets of X, to the set of all strings of 0's and 1's that have length n.

(b)

To find:

Total number of subsets of a set with n elements.