Representative Set for Relation S on N rightarrow {0,1} s.t. ⟨f,g⟩ in S Leftrightarrow exists bijection h:N rightarrow N s.t.f=g circ h

Nico Patterson 2022-11-11 Answered
Representative Set for Relation S on N { 0 , 1 } s.t. f , g S bijection h : N N s.t. f = g h
Problem: Define a relation S on N { 0 , 1 } as follows: f , g S there exists a bijection h : N N s.t. f = g h.
S is an equivalence relation on N { 0 , 1 } (no need to prove this). Write a Representative set for the relation S. There's no need to prove that the relation you wrote is indeed a Representative set.
Reminder: Suppose T X × X is an equivalence relation over X.     A X will be called a Representative set of T, if it occurs that: x X . | [ x ] T A | = 1.
Attempt: I don't really know what Representative set to define. It seems to me I'm missing something simple here. I tried to look at the functions: f 1 ( n ) = 0 , f 2 ( n ) = 1 , f 3 ( n ) = { 0 n=0 1 else , f 4 ( n ) = { 0 n N e v e n 1 n N o d d , n N . None of these functions relate through relation S since there does not exist a bijection between them. I feel lost, do you have any idea what to do?
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

lelestalis80d
Answered 2022-11-12 Author has 23 answers
Step 1
A representative set would be { f : N { 0 , 1 } | f is monotonic } { h }, where h(n) is defined s.t. h ( n ) n mod 2.
Here, a monotonic function is one which is either monotonically increasing or monotonically decreasing.
Let's prove that this is a representative set.
Consider some function g : N { 0 , 1 }. Consider S i = g 1 ( i ) for i = 0 , 1. Each S i is either finite or infinite.
If S 0 and S 1 are both finite, then N = S 0 S 1 is finite. This is contradictory.
If S 0 and S 1 are both infinite, then they must both be in bijection with N. So we take some bijections k : N S 0 and j : N S 0 . Then consider the bijection u ( n ) = k ( n / 2 ) if n is even, u ( n ) = j ( ( n 1 ) / 2 ) if n is odd. Then u is a bijection, and g u = h.
Step 2
Suppose only one is finite: WLOG, take S 0 finite and S 1 infinite. Then take m N and bijections k : { n N | n < m } S 0 and j : N S 1 . Define the bijection u ( n ) = k ( n ) if n < m, u ( n ) = k ( n m ) if n m. Then g u is a monotonically increasing function N { 0 , 1 }.
I'll leave it as an exercise to show that this is the only member of the representative set equivalent to g. Hint: if ( k , g ) S, then consider | k 1 ( { i } ) | for i = 0 , 1.
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2020-11-09
Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.
asked 2021-08-02

Suppose that A is the set of sophomores at your school and B is the set of students taking discrete mathematics at your school. Express each of these sets in terms of A and B. 
a) the set of sophomores taking discrete mathematics in your school 
b) the set of sophomores at your school who are not taking discrete mathematics 
c) the set of students at your school who either are sophomores or are taking discrete mathematics 
Use these symbols: 

asked 2021-08-18

Discrete Mathematics Basics

1) Find out if the relation R is transitive, symmetric, antisymmetric, or reflexive on the set of all web pages.where (a,b)R if and only if 
I)Web page a has been accessed by everyone who has also accessed Web page b.
II) Both Web page a and Web page b lack any shared links.
III) Web pages a and b both have at least one shared link.

asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2022-06-22
Is this true for chromatic numbers?
If we take the graph G = ( V ( G ) , E ( G ) ) and partition the edges E(G) into k sets, forming k subgraphs of the form H i = ( V ( G ) , E ( H i ) ) for i { 1 , . . . , k } such that | E ( H i ) | 1 for each subgraph H i . Furthermore, we let χ(G) be the chromatic number of the graph G.
Does it hold that i = 1 k χ ( H i ) χ ( G )? How would we prove it? I know that this holds when k = 2. How about other values k 3?
For the case k = 2 we can take H , H ¯ G such that H = ( V ( G ) , E ( H ) ) and H ¯ = ( V ( G ) , E E ( H ) ). If the coloring C H : V ( G ) [ χ ( H ) ] is a coloring of H and C H ¯ : V ( G ) [ χ ( H ¯ ) ] is a coloring of H ¯ , we are able to construct a coloring C G of G with at most χ ( H ) χ ( H ¯ ) colors by letting C G ( v ) = ( C H ( v ) , C H ¯ ( v ) ). We can also observe that every edge (u,v) in G belongs to either H or H ¯ and hence C G ( u ) differs from C G ( v ) in at least one of the coordinates.
Can this same argument potentially be generalized for the case of partitioning G into k subgraphs such that | E ( H i ) | 1 for each subgraph?
asked 2022-06-24
Finding X for density function
A city's fire brigade is deployed approximately every 2 days to extinguish a fire. The number of operations X per week is assumed to be Poisson distributed. Calculate the density and the distribution function of the time T that elapses between two fires. Represent both functions graphically.
I have this formula for the density function:
f ( x ) = μ x x ! exp μ
μ = 2 because 2 days pass between fires I think but I am not sure what X should be.
asked 2022-09-06
Could you help me to start this demonstration by contrapositive
If a,b,c are positive numbers such that a + b > c, then a > c / 2 or b > c / 2.

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question