Quick order preserving map question

  • Thread starter EV33
  • Start date
  • Tags
    Map
In summary: The answer is yes, it means that if order is preserved then it means that if x<y then f(x)<f(y) or f(x)=f(y).
  • #1
EV33
196
0

Homework Statement



Let X and Y be ordered sets in the order topology.
I want to show that a function f:X→Y is injective. We are given that f is surjective and preserves order.

Homework Equations



Definition of an order preserving map:

If x≤y implies f(x)≤f(y)

The Attempt at a Solution



So if we assume that it is not injective then we are assuming that f(x)=f(y) and x[itex]\neq[/itex]y.

Then either x>y or y<x. Assuming both, would clearly be a contradiction since it can only be one or the other in an ordered set.

Now I need to show that x>y raises a contradiction and similarly x<y also raises a contradiction.


My main question here is if x<y is it a contradiction if f(x)=f(y)?
It seems like if order is preserved then if x<y then f(x)<f(y)
but by the definition, it appears that if x<y then f(x)<f(y) or f(x)=f(y).

Thank you for your time.
 
Last edited:
Physics news on Phys.org
  • #2
EV33 said:

Homework Statement



Let X and Y be ordered sets in the order topology.
I want to show that a function f:X→Y is injective. We are given that f is surjective and preserves order.

Homework Equations



Definition of an order preserving map:

If x≤y implies f(x)≤f(y)

The Attempt at a Solution



So if we assume that it is not injective then we are assuming that f(x)=f(y) and x[itex]\neq[/itex]y.

Then either x>y or y<x.
Assuming both, would clearly be a contradiction since it can only be one or the other in an ordered set.

Now I need to show that x>y raises a contradiction and similarly x<y also raises a contradiction.
Yes, you do. Use the fact that f is an order preserving map. If x< y, what can you say about f(x) and f(y)?


My main question here is if x<y is it a contradiction if f(x)=f(y)?
It seems like if order is preserved then if x<y then f(x)<f(y)
but by the definition, it appears that if x<y then f(x)<f(y) or f(x)=f(y).
What, exactly, is that definition? "if x< y the [itex]f(x)\le f(y)[/itex]?

Thank you for your time.
 
  • #3
Thank you, HallsofIvy. Actually, what you just said is exactly what my question is. My question was probably a little convoluted so let me restate it.

I was trying to ask, if we have a function that preserves order
and x<y

1) do we conclude that f(x)<f(y)

2)or do we conclude that f(x)≤f(y)

The definition makes me think it is the second option but if I didn't have the definition I would have thought it was the first.
 
Last edited:
  • #4
Just to make it more clear what I am asking. If order is preserved does it mean

if x<y implies f(x)<f(y)
if x>y implies f(x)>f(y)
if x=y imples f(x)=f(y)
if x≤y imples f(x)≤f(y)
if x≥y imples f(x)≥f(y)
 

1. What is a quick order preserving map?

A quick order preserving map is a function that takes in two sets with a specified order, and returns a mapping between elements of the two sets while preserving their original order.

2. How is a quick order preserving map different from a regular map?

A regular map does not necessarily preserve the original order of the elements in the two sets, whereas a quick order preserving map specifically ensures that the order remains the same.

3. What is the purpose of using a quick order preserving map?

Quick order preserving maps are commonly used in computer science and mathematics to maintain the order of elements in a set while performing operations such as sorting or merging.

4. How is the efficiency of a quick order preserving map determined?

The efficiency of a quick order preserving map is determined by the time complexity of its operations, which is typically measured in terms of the number of comparisons or swaps required.

5. Are there any limitations to using a quick order preserving map?

One limitation of quick order preserving maps is that they may not be suitable for all types of data, as certain data structures or operations may require a different type of mapping. Additionally, the implementation of a quick order preserving map may also affect its efficiency and limitations.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
218
  • Calculus and Beyond Homework Help
Replies
5
Views
214
  • Calculus and Beyond Homework Help
Replies
9
Views
543
  • Calculus and Beyond Homework Help
Replies
20
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
592
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
501
  • Calculus and Beyond Homework Help
Replies
3
Views
811
  • Calculus and Beyond Homework Help
Replies
10
Views
2K
Back
Top