Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

It occured to me that when you perform division in some algebraic system, such as $\frac a b = c$ in $\mathbb R$, the division itself represents a relation of sorts between $a$ and $b$, and once you calculate this relation, the resulting element $c$, being 'merely' the relation or some kind of representation of it, has lost the information about what either $a$ or $b$ may have been.

So division destroys or weakens information. Other operations have similar peculiarities. Multiplication such as $a b = c$ is very 'lossy' in $\mathbb R$, but not as lossy in $\mathbb N$ since the set of possible divisors of $c$ is finite.

So my question is, are there any formalizations which account for (or may be able to account for) this particular aspect of mathematical operations (or functions/relations in general)?

share|improve this question
9  
+1 For the interesting question. –  Code-Guru Mar 11 '13 at 2:00
    
@Code-Guru : as per what you said! +1 –  Arjang Mar 11 '13 at 2:19
    
Probably I didn't understand the question. Any function or map defines an equivalence relation : two elements on which our function operates are identified if they give the same result under the operation. So are you asking about how much can one cover about the elements of an equivalence class, knowing just the class? if so, you are roughly asking about controlling partitions of sets. This is so vague. –  Yassine Guerboussa Dec 2 '13 at 18:45
1  
@YassineGuerboussa thanks, you may be right as i'm fairly new to math. i'm not particularly interested in any specific kind of interpretation or answer, so if you post your comment as an answer that would be O.K. i'm more interested in getting a bit more clarity on the general matter, which you've provided here. still i encourage people to think about it in their own ways if they have any ideas –  amr Dec 2 '13 at 20:02
1  
I suppose that any non-injective function would be considered lossy, no? Your measurement of how "lossy" a function is seems to be grounded in the size of the preimage of particular elements. So I guess, for a given function, you could discuss how "lossy" it is by considering the supremum of the cardinalities of all preimages of elements in the codomain. –  Dan M. Katz Dec 7 '13 at 21:31

2 Answers 2

up vote 5 down vote accepted
+500

You are asking, if I understand right, for how much information is lost during the mapping from two elements to another symbol indicating the relation. In your example, function division maps $a,b$ to $\frac ab$, which you choose $c$ to represent the relation of $a,b$.

Unfortunately, we can say nothing on loss of information for that because essentially they contain no information. In the area of information theory, we discuss information only for possiblities. Possibility means uncertaint. Uncertainty implies information. That is how Boltzmann defines entropy as a measure for information. $$S=k_B\ln\Omega$$ where $\Omega$ is the total number of possibilities, $k_B$ is a constant. The point is, rather than measuring the loss of information of elements, which is the only one of possibilities, we can measure that for the sets in which elements belong to. The Sets here are, of course, domain and range of the function.


Follow the idea above, we introduce some notations. The mapping $\Phi$ has domain $\mathcal D$ and range $\mathcal R$. The size of a set $A$ is denoted by $|A|$ and the information it contains by $S_A$. Further assume both $\mathcal D$ and $\mathcal R$ is finite. We can define the information of $\mathcal D$ contains is logarithm of the total number of possibilities of $\mathcal D$, namely $$S_{\mathcal D}:=\ln|\mathcal D|$$ Sometimes function $\Phi=\Phi(x_1,\ldots,x_n)$ is an $n$-variable function where $x_i\in X_i$, then $\mathcal D=X_1\times\cdots\times X_n$ is cartesian product of each domain, in which case $|\mathcal D|=|X_1|\cdots|x_n|$. On the other hand, we don't want define $S_\mathcal R=\ln|\mathcal R|$ because $\mathcal R$ is not dependent with $\mathcal D$. They are connected by function $\Phi$. Thus we denote $n_y=|\Phi^{-1}(y)|$ and $\displaystyle p_y=\frac{n_y}{\sum_{y\in\mathcal R}n_y}=\frac{n_y}{|\mathcal D|}$for each $y\in\mathcal R$, where $\Phi^{-1}(y)\in\mathcal D$ is the preimage of $y$. Now the definition of information of $\mathcal R$ with respect to $\Phi$ is defined as $$S_\mathcal R:=\sum_{y\in\mathcal R}p_y\ln\frac{1}{p_y}$$ Hence the loss of information $$\Delta S=S_\mathcal D-S_\mathcal R\geq0$$ The inequality follows the maximum of concave function $S_\mathcal R$ is $S_\mathcal D$ where $n_y=1$ for each $y$. In another word, the information retains invariant if and only if the function is one-to-one. This definition is consistent with both the definition of entropy in information theory and, which is the most important, our intuition of loss of information.

We can easily generalize this method to cases where both domain and range are compact, just through replacing summation by integration and size by measure.


As for other cases, this method doesn't work any more but we still have some ways to roughly approximate the loss.

Note function $\Phi$ itself defines an equivalent relation $\sim$ and we can further define the quotient space $$\mathcal Q=\mathcal D/\sim$$ and $$\Delta S=\dim\mathcal D-\dim\mathcal Q$$ This has also correspondence in many areas such as linear algebra, group theory, topology etc. Sometimes we call the space of $\sim$ kernel. When the kernel is zero space, we say two spaces are isomorphic.


At the last, to give an explantion for your example $c=\Phi(a,b)=ab$, if $a,b\in\mathbb Q$, we have $\Delta S^\mathbb Q=\dim_\mathbb Q(\mathbb Q\times\mathbb Q)-\dim_\mathbb Q(\mathbb Q)=2-1=1$, while if $a,b\in\mathbb R$, we have $\Delta S^\mathbb R=1$. Although both value equal to 1, knowing that the cardinal of 1 dimensional rational number is less than that of real number, the information loss from rational multiplication is less than that from real multiplication.

I hope this will help even if this may not be what you want.

share|improve this answer

Your particular example of information being lost in multiplication or division is really the reason one studies ideals in ring theory, normal subgroups in group theory, and kernels in general. But I think prime ideals explain it best.

The prime factorization of a number represents how much information was lost in creating it. A prime number only has one factorization, so if it is a product, we know the factors. The more prime factors an element has, the more information is lost in creating it.

Mathematicians generalized this to 'prime ideals' where a class of products (called an ideal) has information loss measured by the number of of prime ideals in its decomposition.

Fields have the greatest information loss, as every element can occur from a product with any given factors.

Ideals can also be used in another way to destroy information. Quotienting by an ideal causes you to lose information in proportion to the size of the ideal. Quotienting the integers by the ideal of multiples of 10 tells you the last digit of a number, while quotienting hy multiples of 2 only tells you if a number is odd or even.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.