Difference between revisions of "Relations and Functions"
From Suhrid.net Wiki
Jump to navigationJump to search| (7 intermediate revisions by the same user not shown) | |||
| Line 6: | Line 6: | ||
* A binary relation between A and B is '''any subset of A X B'''. | * A binary relation between A and B is '''any subset of A X B'''. | ||
* Thus a relation R is given by R: P(A X B). R is a member of the powerset of the cartesian product of A and B. | * Thus a relation R is given by R: P(A X B). R is a member of the powerset of the cartesian product of A and B. | ||
| + | * A relation '''IS-A''' set, so all set operations can be applied on relations. | ||
= Functions = | = Functions = | ||
| + | |||
| + | * A function is a relation where a single element cannot be mapped to more than one element. No two maplets with the same source. No diverging arrows. | ||
| + | * A partial function is where not all the source elements are mapped to a target. | ||
| + | * A total function is where all the source elements are mapped to a separate target. (Note, all the targets need not be used). | ||
| + | * An injective function is where the target elements of the maplet dont have multiple sources. No converging arrows. | ||
| + | ** Partial injective : No converging arrows for a target and not all sources are mapped to a target. | ||
| + | ** Total injective: No converging arrows for a target and all sources are mapped to a target. | ||
| + | * Surjective function is where all the target elements are mapped by the function. | ||
| + | ** Partial surjective is where all sources are not mapped but all targets are. | ||
| + | ** Total surjective is where all sources are mapped and all targets are. (There can be converging arrows). | ||
| + | * A bijective function is one a function which is an injection, a surjection and is total. | ||
| + | |||
| + | = Sequences = | ||
| + | |||
| + | * A sequence is a specialised sort of function. | ||
| + | * It is a '''partial function''' which maps numbers to elements. | ||
| + | * Sequence starts from 1 and are consecutive. | ||
| + | * s : seq PERSON | ||
| + | ** Is shorthand for s: N ⟶ PERSON | ||
| + | ** Together with the restriction, dom s = 1..#s | ||
| + | * By default a sequence includes null. To exclude null from a sequence use seq₁ | ||
| + | * Sequences may have repeated elements. | ||
| + | * To specify that a sequence has distinct elements use iseq | ||
| + | * Also written as s == <g, x, p>. g is in 1st pos, x in 2nd, p in 3rd. | ||
Latest revision as of 09:08, 15 February 2012
Relations
- An ordered pair (a,b) consists of two elements.
- In Z, ordered pairs are represented using the maplet notation: a ⟼ b
- The cartesian product, A X B is the set of all ordered pairs of A and B.
- A binary relation between A and B is any subset of A X B.
- Thus a relation R is given by R: P(A X B). R is a member of the powerset of the cartesian product of A and B.
- A relation IS-A set, so all set operations can be applied on relations.
Functions
- A function is a relation where a single element cannot be mapped to more than one element. No two maplets with the same source. No diverging arrows.
- A partial function is where not all the source elements are mapped to a target.
- A total function is where all the source elements are mapped to a separate target. (Note, all the targets need not be used).
- An injective function is where the target elements of the maplet dont have multiple sources. No converging arrows.
- Partial injective : No converging arrows for a target and not all sources are mapped to a target.
- Total injective: No converging arrows for a target and all sources are mapped to a target.
- Surjective function is where all the target elements are mapped by the function.
- Partial surjective is where all sources are not mapped but all targets are.
- Total surjective is where all sources are mapped and all targets are. (There can be converging arrows).
- A bijective function is one a function which is an injection, a surjection and is total.
Sequences
- A sequence is a specialised sort of function.
- It is a partial function which maps numbers to elements.
- Sequence starts from 1 and are consecutive.
- s : seq PERSON
- Is shorthand for s: N ⟶ PERSON
- Together with the restriction, dom s = 1..#s
- By default a sequence includes null. To exclude null from a sequence use seq₁
- Sequences may have repeated elements.
- To specify that a sequence has distinct elements use iseq
- Also written as s == <g, x, p>. g is in 1st pos, x in 2nd, p in 3rd.
