Representative Set for Relation S on N → { 0 , 1 } s.t. ⟨...

Nico Patterson

Nico Patterson

Answered

2022-11-11

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?

Answer & Explanation

lelestalis80d

lelestalis80d

Expert

2022-11-12Added 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.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?