Another maths/logic thread! help please!

[megakid]

Hey

I've come unstuck with a question I've got for one of my module exercises.
I'm more looking for advice rather than a straight out answer, just to find out where I'm going wrong.

I've been asked to define, for the set of all such functions, an injective partial function.
I've defined the complete injective function as:

X >--> Y == { f: X<->Y | Ax:X; y1, y2:Y . x|-> y1 elementof f ^ x|-> y2 elementof f => y1 = y2 }

I'm stuck on the partial injective function - How do I define the above but with extra elements in X that arent mapped. I dont know how to show that.

Any help would be fantastic. And to those who dont understand what the hell I'm talking about, I'm sorry for dampening your Monday night

 

[benjo]

:\

 

[megakid]

After a bit more thought I *think* i've solved it -

X >-|-> Y == { f: X<->Y | Ax:dom(f); y1, y2:range(f) . x|-> y1 elementof f ^ x|-> y2 elementof f => y1 = y2 }

 

[Omicron]

According to someone on my MSN list you've defined an injective partial function
but he says your question 'I've been asked to define, for the set of all such functions, an injective partial function' makes no sense.

 

[Zefan]

:\

Quoted for truth

 

[Vonhelmet]

If I were to dig out my comp sci notes from uni I could help you.

Sadly, they're about 150 miles away.

 

[Lagz]

The question does indeed make no sense. Are you just trying to define a partial injective function?

 

[megakid]

Yeh sorry - just realised that makes no sense what-so-ever ... I'm just trying to define a partial injective function.

I've simplified it slightly:

X >--> Y == { f: X <--> Y | A[all] r,s:X . (f(r) = f(s)) => (r=s) }

Which means my version of a partial function would be:

X >-|-> Y == { f:X <--> Y | A[all] r,s:dom(f) . (f(r) = f(s)) => (r=s) }

 

[Lagz]

Its slightly strange that they have called it an "injective partial function" since partial and injective essentially mean the same thing (at least according to web definitions).

In that case your definition looks correct (its really just the definition of a partial function).

 

[megakid]

The difference between a total and partial function is that:

EDITED OUT TO AVOID CONFUSION

This has nothing to do with injection which is where each mapped element in X is mapped to a unique Y element. eg. If 2 is mapped to 4 then nothing else can be mapped to 4.

I have no issues with the concepts (I dont think?) - it's just the logic predicates that I'm writing to describe them.

EDIT wait - i think i've just completely confused myself...you might be right...I'll get back to you lol

EDIT2 - edited for correctness - completely wrong the first time.

 

[Lagz]

An injective function is simply a function where f(a) = f(b) => a=b.
It is indeed nothing to do with partial and total functions.

A partial function is a function which MAY have some a such that f(a) is not defined. Total functions are actually a subset of partial functions. It is not true that a partial function MUST have some a such that f(a) is undefined.

Since an injective function doesn't say anything about the type of function and since a partial function is essentially any function, saying the function is partial adds nothing to the definition.

 

[megakid]

An injective function is simply a function where f(a) = f(b) => a=b.
It is indeed nothing to do with partial and total functions.

A partial function is a function which MAY have some a such that f(a) is not defined. Total functions are actually a subset of partial functions. It is not true that a partial function MUST have some a such that f(a) is undefined.

Since an injective function doesn't say anything about the type of function and since a partial function is essentially any function, saying the function is partial adds nothing to the definition.

I see - I thought partial functions were a strict subset of total functions.

 

[Lagz]

Dont you mean the total functions are a strict subset of the partial functions (which is correct)? Its impossible for the partial functions to be a subset of the total functions - since there exists a partial function which is not a total function. . .for instance:

f(a) = underfined for all a

is not a total function, but is a partial one.

 

[megakid]

Yes sorry, my mind is in overdrive. Total functions are a strict subset of partial functions.

Actually have I got something completely wrong here -

Your definition of a partial function, which MAY have some a such that f(a) is not defined, bugs me.

X <--> Y

With a partial function, from your definition, this means that an element in X is unmapped - It says nothing about Y.

We've been taught differently here :S Says here straight off my Z/schema notes that a partial function (X -|-> Y) maps everything from the first set X, to just SOME things in Y.

 

[Lagz]

Your definition sounds a bit dodgy to me. Saying it only maps to 'some' things in Y suggests there is a Y which is not mapped to. This is obviously wrong. Consider the sets X = {1,2,3} and Y = {1,2}

A function:
f(1) = 1
f(2) = 2
f(3) = undefined
is clearly partial, yet maps to all elements in Y.

The definition of a partial function varies slightly depending on who defines it ! Formally speaking all a partial function is is a single valued function. . that is:

f(x) = a & f(x) = b => a=b

Note that all this definition says is that:
- where the function is defined it must have a single value
- the function may be undefined at some points

 

[Lagz]

With a partial function, from your definition, this means that an element in X is unmapped - It says nothing about Y.

It doesn't mean an element in X is unmapped. It just means an element in X MAY be unmapped. And no it doesn't really say anything about Y (apart from that any X which is mapped must point to a single value in Y - I didn't say this explicitly. . I assumed it was obvious ).

 

[megakid]

It doesn't mean an element in X is unmapped. It just means an element in X MAY be unmapped.

Yep - I understand that.

And no it doesn't really say anything about Y (apart from that any X which is mapped must point to a single value in Y - I didn't say this explicitly. . I assumed it was obvious ).

Hmmm doesnt that mean it's injective then?

 

[megakid]

Ok been reading and working things out a bit more, finally got it straight in my head.

Thanks a lot Lagz - you've been a great great help!

 

[Lagz]

*ignore me*