Exercise on Posets, Chains and upper bounds

  • Thread starter jacobrhcp
  • Start date
  • #1
169
0

Homework Statement



Suppose X and Y are sets. Let P be all pairs (A,f) where A is a subset of X and f is a function from X to Y. Then P is a poset with the relation (A,f)=<(B,g) iff A is a subset of B and f is the restriction of g to A.

Show that if C={(Ai,fi)|i in I} is a chain in P, there is a unique function f:U Ai -> Y such that for each i, fi is the restriction of f that Ai.

Homework Equations



A chain is subset of P such that for all elements p,q in the chain p=<q or q=<p.

The Attempt at a Solution



lets start out with (A1,f1)

f1:A1->Y = (f2:A2->Y restricted to A1)

and so

f1: A1->Y = (fn:An->Y restricted to the intersection of all Ai's)
but "restricted to the intersection of all Ai's" is the same as "restricted to A1", or more generally to Aj, the jth member of the chain. This is true because there are all inside eachother by definition of the poset.

so would fn:An->Y fit the role of the fuction we were looking for?
would therefore (An,fn) be the upper bound asked for?

It feels too simple to be the right answer.
 
Last edited:

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,847
966

Homework Statement



Suppose X and Y are sets. Let P be all pairs (A,f) where A is a subset of X and f is a function from X to Y. Then P is a poset with the relation (A,f)=<(B,g) iff A is a subset of B and f is the restriction of g to A.

Show that if C={(Ai,fi)|i in I} is a chain in P, there is a unique function f:U Ai -> Y such that for each i, fi is the restriction of f that Ai.

Homework Equations



A chain is subset of P such that for all elements p,q in the chain p=<q or q=<p.

The Attempt at a Solution



lets start out with (A1,f1)

f1:A1->Y = (f2:A2->Y restricted to A1)

and so

f1: A1->Y = (fn:An->Y restricted to the intersection of all Ai's)
but "restricted to the intersection of all Ai's" is the same as "restricted to A1", or more generally to Aj, the jth member of the chain. This is true because there are all inside eachother by definition of the chain.

so would fn:An->Y fit the role of the fuction we were looking for?
would therefore (An,f) be the upper bound asked for?

It feels too simple to be the right answer.
It is. What "f" are you talking about? "fn:An-> Y" doesn't "fit the role of the function we were looking for" because it is not a function- it is the set of functions you are originally given. And "would (An,f) be the upper bound asked for" doesn't make sense because you have not defined f.

I think what you are trying to say is this: If x in the union of the Ai's, then there exist at least one Ai that contains x. Define f(x)= fi(x). Of course, you need to show that is "well defined"; that is, that it doesn't matter which of the possibly many Ai's containing x you choose to define f(x).
 
  • #3
169
0
but fn is a function, isn't it? it is the biggest member in the chain, n is the biggest member of I. The only thing I'm worried about is whether I has a biggest member.

But your interpretation of what I was trying to say is better. Showing that it doesn't matter which of the Ai's I'd pick is, I think, just working out the restriction demand on functions in the chain. Thanks again for your help.
 

Related Threads on Exercise on Posets, Chains and upper bounds

  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
0
Views
4K
  • Last Post
Replies
4
Views
869
  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
11
Views
6K
  • Last Post
Replies
0
Views
1K
Replies
1
Views
2K
Top