From ProofWiki
Jump to navigation Jump to search

Function Schemes

Let $\mathcal R \subseteq A \times B$ be a relation. Then $\mathcal R$ is a function iff it is left-total and many-to-one.

Instead of $\mathcal R$ we usually denote a function by $f$ or $g$.

We may specify a function using a function scheme. For example:

$f:A \to B$
$f:x \mapsto E(x)$

The first line is the form of $f$ showing the domain of $f$ as $A$ and the codomain of $f$ as $B$.

The second line is the rule of $f$ where for $x \in A$ we may use $E(x)$ (which is an expression involving $x$) to find the image of $x$.

A function may be introduced with different levels of specification:

  • Full scheme: "Define $f:\mathbb{N} \to \mathbb{N};x \mapsto 2x + 5^x$." is a full scheme for $f$. Notice that because $f$ is a definite object we do not use the keyword "let".
  • Codomainless scheme: "Let $f:x \mapsto 2x + 5^x$ be a function where $x \in \mathbb N$" is a codomainless scheme for $f$. In many applications we do not find the concept of a codomain to be useful which is why we may introduce a function this way.
  • Form only scheme: "Let $f:A \to B$ be a function." is a form only scheme for $f$.
  • Rule only scheme: "Let $f(x)=5x - 3$ be a function." is a rule only scheme for $f$. The form of $f$ may be implicit or may need to be investigated as to what it could be.
  • Empty scheme: "Let $f$ be a function." is an empty scheme for $f$.

There exist full schemes that are invalid schemes such as:

$f:\{1, 2, 3\}\to \{1, 4\};x\mapsto x^2$

This is invalid because $f(3) = \varnothing$. Often we may change the form such that $f$ becomes a valid scheme once more.


To be kept 2nd from the top so that loose sand may percolate down the page and so I can put a sandcastle on top.


The Note section on Definition:Relation

A relation (a binary relation to be specific) has three parts:

  • Domain
  • Codomain
  • Graph

"Let $\mathcal R \subseteq S \times T$ be a relation." means we have a relation where:

  • $S$ is the domain
  • $T$ is he codomain
  • $\mathcal R$ is the graph

Just like with an algebraic structure we usually refer to the whole relation by its graph symbol.

So we say things like:

"Thus $\mathcal R$ is symmetric."

Not sure where to go from here...


I impose all my will on the world and state now once and for all that:

$\N = \{1,2,3,...\}$
$\N^- = \{-1,-2,-3,...\}$
$\Z^+ = \{0,1,2,3,...\}$
$\Z^- = \{0,-1,-2,-3,...\}$
$\Z^\times = \{...,-2,-1,1,2,...\}$
$\Z = \{...,-2,-1,0,1,2,...\}$

What happens: "Wind and crickets." :) --Jshflynn (talk) 14:14, 18 March 2013 (UTC)

Alternatively we have the house style versions $\N_{>0}, \Z_{<0}, \Z_{\ge 0}, \Z_{\le 0}, \Z_{\ne 0}$ and $\Z$ which are preferred on this site. --prime mover (talk) 15:06, 18 March 2013 (UTC)
Your will is by no means standard: $\N = \{0,1,\ldots\}$ is pretty common, and $\Z^*$ is often the group of units of $\Z$, so $\Z^* = \{\pm 1\}$. The preferred versions have the advantage that there's little chance of confusion about what is intended, and this matters on a site has no "notation database" (side note: maybe it such a thing would be worthwhile anyway?). Unambiguity (disambiguity?) wins in this case. --Linus44 (talk) 22:49, 18 March 2013 (UTC)
See the "Symbol Index" for a start on such a notation database. --prime mover (talk) 23:17, 18 March 2013 (UTC)
Edit conflict! :)
You beat me to it PM. I should say that the thing above was a bad joke by me. --Jshflynn (talk) 23:25, 18 March 2013 (UTC)
In appropriate contexts (where the naturals are understood to be Von Neumann naturals), you can use $\omega$ for $\{ 0, 1, \dots \}$. Obviously that won't work when dealing with the naturals in lambda calculus or other such things. --Dfeuer (talk) 02:53, 19 March 2013 (UTC)
Such uses need to be explained in the context. The use of $\omega$ is purely conventional and has absolutely no intrinsic merit. --prime mover (talk) 06:18, 19 March 2013 (UTC)
Obviously. Of course all of these letters are purely conventional and have no intrinsic merit. --Dfeuer (talk) 16:57, 19 March 2013 (UTC)
I changed $\mathbb Z^*$ to $\mathbb Z^\times$ based on what Linus44 said. --Jshflynn (talk) 17:08, 19 March 2013 (UTC)
Actually $\Z^\times$ is also used for the Definition:Group of Units of Ring according to L_F. --prime mover (talk) 22:01, 19 March 2013 (UTC)
Damn -_- --Jshflynn (talk) 22:28, 19 March 2013 (UTC)
In fact ${}^*$ is an example of "typewriter notation": ${}^\times$ can't be done on a typewriter, so ${}^*$ was used instead. --Linus44 (talk) 22:43, 19 March 2013 (UTC)
Definition of Mathematics: eternally squabbling pointlessly over notation. --prime mover (talk) 22:44, 19 March 2013 (UTC)
Oh yeah. @PM I don't know if you're still working on your large pdf (which I thank you for again) but definition 49.1 uses $\mathbb Z^*$ for $\mathbb Z_{\neq 0}$ from there on. --Jshflynn (talk) 01:46, 20 March 2013 (UTC)

A Relation Zoo

What follows is a table of specific types of transitive relations as they are named on $\mathsf{Pr} \infty \mathsf{fWiki}$.

The relation of interest shall be denoted $\mathcal R$ and it shall be on the set $S$.

Under Reflexivity

T means the relation is reflexive.
F means the relation is antireflexive.

These can both hold iff $S = \varnothing$.

Under Symmetry

T means the relation is symmetric.
F means the relation is antisymmetric.

These can both hold iff $\mathcal R$ is coreflexive as proved in Relation is Symmetric and Antisymmetric iff Coreflexive.

If they both hold and $\mathcal R$ is reflexive or connected then $\mathcal R$ is the diagonal relation on $S$.

If they both hold and $\mathcal R$ is antireflexive then $\mathcal R$ is the null relation on $S$.

We leave it blank if it is not of concern to us.

Under Connected

T means the relation is connected.
F means it is not.

We leave it blank if it is not of concern to us.

The Table

Reflexivity Symmetry Connectedness Name
T T Weak Total Preordering
T F Weak Partial Preordering
F T Strict Total Preordering
F F Strict Partial Preordering
T F T Weak Total Ordering
T F F Weak Partial Ordering
F F T Strict Total Ordering
F F F Strict Partial Ordering
T T Equivalence Relation
T T T Trivial Relation

In addition to this we name:

Similarly we name:

  • Null Relation: The relation that does not relate any pairs. It is transitive, antitransitive, negatively transitive, antisymmetric, and antireflexive, and is the only relation to be both symmetric and asymmetric. —Dfeuer (talk) 17:11, 19 March 2013 (UTC)

For the relational structure $\left({S, \mathcal R}\right)$ we name it as follows:

Blah blah blah :) --Jshflynn (talk) 13:06, 14 March 2013 (UTC)

True or not?

A non-empty semigroup $(S, \circ)$ is a group iff:

$\forall x \in S: x \circ_\mathcal P S = S \circ_\mathcal P x = S$

This definition of a group is given in An Introduction to Semigroup Theory (by John Howie). He states that its convenient for his set up but acknowledges that it is a highly unusual definition to give for a group.

Identity: Let $x$ be an element of your choice. Then there is a $p$ such that $px = x$.

Let $y$ be any element.

Then there is a $q$ such that $xq = y$.

Then $py = p(xq) = (px)q = xq = y$.

So $p$ is a left identity.

Now $pp = p$.

Let $y$ be any element.

Then there is a $q$ such that $qp = y$.

Then $yp = (qp)p = q(pp) = qp = y$.

So $p$ is a right identity as well. Rename it $e$.

Inverses: By the premise each element has a left inverse and a right inverse.

I believe we have a theorem that takes it from there, but just in case:

Suppose that:

$xy = zx = e$

$yx = (zx)(yx) = z(xy)x = zex = zx = e$

So each right inverse is a left inverse. --Dfeuer (talk) 19:04, 19 March 2013 (UTC)

Hooray! Thx Dfeuer. Now I wonder what happens if I change it to this:
$\forall x \in S: x \circ_\mathcal P S = S$
--Jshflynn (talk) 22:28, 19 March 2013 (UTC)
Let $S = \{a, b\}$ for distinct $a$ and $b$. Let $pq = q$ for $p, q \in S$.
$S$ is a semigroup: It's obviously closed. $p(qr) = pr = r = (pq)r$.
$pS = S$ trivially.
$S$ is not a group because it has no identity. $ab = b$ but $ba = a$. --Dfeuer (talk) 22:51, 19 March 2013 (UTC)
Prove or disprove: There is only one such 2-element semigroup, up to isomorphism. How many 3-element semigroups break your conjecture? --Dfeuer (talk) 02:03, 20 March 2013 (UTC)

The first statement isn't true because:

  • $\mathbb Z_2$ is a group (and therefore a semigroup) which satisfies it.
  • The right zero semigroup of order 2 satisfies it.
  • These aren't isomorphic.

I am guessing for the second question its between 15 and 22. I don't know yet. I'm trying to avoid just looking at semigroup tables. --Jshflynn (talk) 12:49, 20 March 2013 (UTC)

I think you misunderstood my question. How many 2 and 3-element semigroups are there (up to isomorphism) for which $xS = S$ for each $x$ but $S$ is not a group? The 2-element case should be easy. The other will be trickier, and I don't know how to do it yet without "cheating" with a computerized case analysis. --Dfeuer (talk) 15:23, 20 March 2013 (UTC)

Three-element case

My own first thoughts on the matter:

Let $S$ have three elements. Specifically, let $S = \{ a, b, c \}$

My first thought was to look at multiplication tables, but there are many many of those for 3-element magmas: $3^9$, in fact, as there are $3 \cdot 3$ ordered pairs, each of which could take one of 3 different values. So I turned to the condition that $xS = S$.

The condition that $xS = S$ is in the finite case equivalent to the statement that the mapping $f_x:S \to S$ defined by $f_x(y) = xy$ is a permutation (a bijection between $S$ and $S$).

There are 6 permutations of three elements, so there are $6^3$ ways to define left-multiplication, although a good number of those will be isomorphic. In any case, $6^3 = 216$ possibilities is a huge improvement over $3^9$ of them.

It should be pretty easy to write a computer program to generate all such, and check which are semigroups and which are groups. --Dfeuer (talk) 17:51, 20 March 2013 (UTC)


Something occurred earlier to do with my cookies. My proof was not saved :(

--Jshflynn (talk) 15:13, 9 March 2013 (UTC)

If you use Google Chrome there exists the ability to go back to the page that failed to be saved and you can then do an emergency cut-and-paste into a separate text editor from which you can then retrieve the material you would otherwise lose. --prime mover (talk) 16:01, 9 March 2013 (UTC)
I did not know that. Thanks :) --Jshflynn (talk) 16:12, 9 March 2013 (UTC)





User:Jshflynn/Left Zero Semigroup

User:Jshflynn/Right Zero Semigroup

User:Jshflynn/Rectangular Band Isomorphism Theorem

Equivalence Relation Alternative Definition 2

$(1)$ $\mathcal R$ is left total or right total.

$(2)$ $\mathcal R = \mathcal R^{-1}$

$(3)$ $\mathcal R \circ \mathcal R = \mathcal R$

Construct Notes

Presenting Relations:

$(a \mathrel{\mathcal R} b)$

$(a \mathcal R b)$

As for parentheses, you should be careful because $\lor$, $\land$, and $\lnot$ can have somewhat different meanings that can be confused without parentheses. For example, $a = b \wedge c = d$ could be read as $(a = b) \land (c = d)$ (that is, "$a = b$ and $c = d$", or it could be read as "$a = (b \wedge c) = d$" (that is, "$a$ equals the meet of $b$ and $c$, which also equals $d$). The same problem happens with $\lor$, which looks just like $\vee$, which can mean "join". Note also that $\neg$ may be read as "complement" in some cases, so you have to be just as careful there. --Dfeuer (talk) 07:59, 5 March 2013 (UTC)

Engine Fuel

I will be extracting some stuff off this if you don't mind:


Actually, I'd rather see it coming from some elements from the extensive reference list — notes like these can perish without warning. If you like the presentation, please make sure to grab a copy of it before it's too late. — Lord_Farin (talk) 07:40, 5 March 2013 (UTC)
Okay :) --Jshflynn (talk) 07:50, 5 March 2013 (UTC)

When did transclusion first appear on this site?

In particular when did it really take off?

There's something oddly pleasing about it.

Sometime around when I discovered its use in Trigonometric Identities, around 29th Dec 2010. My playlist at the time was the Beatles 1962-66 and 1967-70 which I'd just bought for the wife for xmas. Can you think of a more pleasurable occupation than doing maths while listening to the Beatles? --prime mover (talk) 21:24, 6 March 2013 (UTC)