mukesh's interests

mukesh's posts

Post has shared content

Public

As a mathematician, it is sometimes hard to keep in mind that certain basic terms that have a very precise and accepted meaning in mathematics, can be interpreted differently by non-mathematicians. I was reminded of this recently when discussing one of the most fundamental mathematical notions, that of

0. Equality is a binary mathematical relation. That is to say, if x and y are two mathematical objects, then x=y is a mathematical statement (either true or false, depending on the precise values of x and y).

1. Equality is reflexive: for any mathematical object x, we have x=x.

2. The law of substitution (Leibniz's law): if x and y are mathematical objects with x=y, P is a statement, and Q is a statement formed from P by replacing one or more occurrences of x with y, then P is logically equivalent to Q.

From these laws one can deduce some further basic properties of equality, in particular

2'. If x and y are mathematical objects with x=y, A is a mathematical expression, and B is a mathematical expression formed from A by replacing one or more occurrences of x with y, then A=B.

3. Equality is symmetric: if x and y are mathematical objects with x=y, then y=x.

4. Equality is transitive: if x, y, and z are mathematical objects with x=y and y=z, then x=z.

These properties are completely self-evident and internalised to any working mathematician, to the point where one is probably not even aware of the dozens of times one uses these properties when writing a mathematical argument. However, these axioms serve a critical function of separating the mathematical conception of equality - in which x=y means that x and y have exactly the same value, and are interchangeable for each other in any mathematical expression or statement - with more informal interpretations of "x equals y" or "x is y" which are commonly accepted in English usage, but violate one or more of the above axioms of equality. For instance:

(a) Informally, "equals" or "is" is often used in the sense closer to the mathematical concepts of "is a subset of" or "is an element of", as in "cats are animals" or "36 = square number". This notion violates properties 2, 3, and 4 above: for instance, "cats are animals" and "dogs are animals" do not imply "cats are dogs". (But in analysis, we do "abuse" the equality sign in this fashion through notations such as the big-O notation, e.g. "X = Y + O(1)", or the ± notation, e.g. "x = ( - b ± sqrt(b^2-4ac))/2a". As with many other common abuses of notation, this is a situation in which the convenience and efficiency of the abuse can outweigh the technical violation of the formal rules of mathematical logic.)

(b) As a variant of (a), the symbol "=" is sometimes used informally to mean something like "has an attribute with value", e.g. "Alice = 23" to denote "Alice has age 23", or "AB=3" to denote "the line segment from A to B has length 3". As with (a), this usage tends to violate properties 2-4 above, but is often seen for instance in the homework assignments of undergraduate maths students, as a notational shorthand for a slightly longer, but more precise, English or mathematical sentence (e.g. writing |AB|=3 instead of AB=3); it may be formally incorrect usage, but the violation is often fairly harmless and can be properly understood from context.

(c) As further variant of (a), the symbol "=" is sometimes used informally to mean something like "is transformed into" or "has a consequence of", e.g. "Passing Go = $200", "water + heat = steam", or (as is sometimes seen in calculus homework assignments) "x^3 = 3x^2" or even "x^3 = 3x^2 = 6x". Again, this violates properties 2 and 3, and perhaps also 1, though one could argue that property 4 still survives.

(d) In some computer languages, the equals sign = is used as an assignment operator rather than a binary relation, basically violating all of the properties 0-4 above, e.g. "x=x+1" would be interpreted to mean "replace the value of x with the value of x incremented by 1". As this type of variable assignment is so at odds with the laws of first-order logic, its use is discouraged in mathematics (except perhaps in portions of a mathematical argument that are explicitly designated as "pseudocode" for describing an algorithm).

(e) The laws of equality prohibit distinct objects from being set equal to the same mathematical object; for instance, one cannot have a (non-degenerate) triangle whose vertices are given by A, A, and B, because the "location of A" then becomes ambiguous, in violation of the law of substitution. Similarly, one cannot discuss the concept of a set {2,2,3} consisting of three elements, two of which are the number 2 and the third is the number 3. However, it is perfectly permissible to have distinct objects being

(f) Occasionally, one sees the notion of equality used in a stronger sense than the mathematical notion of having equal value, in that one also requires equality of

A practising mathematician would implicitly know that the usage of the equality symbol = in mathematics is usually not intended to be of any of the interpretations (a)-(f) given above, but this seemingly obvious fact is not necessarily evident to non-mathematicians. Given how fundamental equality is to mathematics, this issue can be a real obstacle if one wishes to explain a mathematical argument to a non-mathematician...

*equality.*According to the laws of first-order logic, the equality symbol = obeys the following axioms:0. Equality is a binary mathematical relation. That is to say, if x and y are two mathematical objects, then x=y is a mathematical statement (either true or false, depending on the precise values of x and y).

1. Equality is reflexive: for any mathematical object x, we have x=x.

2. The law of substitution (Leibniz's law): if x and y are mathematical objects with x=y, P is a statement, and Q is a statement formed from P by replacing one or more occurrences of x with y, then P is logically equivalent to Q.

From these laws one can deduce some further basic properties of equality, in particular

2'. If x and y are mathematical objects with x=y, A is a mathematical expression, and B is a mathematical expression formed from A by replacing one or more occurrences of x with y, then A=B.

3. Equality is symmetric: if x and y are mathematical objects with x=y, then y=x.

4. Equality is transitive: if x, y, and z are mathematical objects with x=y and y=z, then x=z.

These properties are completely self-evident and internalised to any working mathematician, to the point where one is probably not even aware of the dozens of times one uses these properties when writing a mathematical argument. However, these axioms serve a critical function of separating the mathematical conception of equality - in which x=y means that x and y have exactly the same value, and are interchangeable for each other in any mathematical expression or statement - with more informal interpretations of "x equals y" or "x is y" which are commonly accepted in English usage, but violate one or more of the above axioms of equality. For instance:

(a) Informally, "equals" or "is" is often used in the sense closer to the mathematical concepts of "is a subset of" or "is an element of", as in "cats are animals" or "36 = square number". This notion violates properties 2, 3, and 4 above: for instance, "cats are animals" and "dogs are animals" do not imply "cats are dogs". (But in analysis, we do "abuse" the equality sign in this fashion through notations such as the big-O notation, e.g. "X = Y + O(1)", or the ± notation, e.g. "x = ( - b ± sqrt(b^2-4ac))/2a". As with many other common abuses of notation, this is a situation in which the convenience and efficiency of the abuse can outweigh the technical violation of the formal rules of mathematical logic.)

(b) As a variant of (a), the symbol "=" is sometimes used informally to mean something like "has an attribute with value", e.g. "Alice = 23" to denote "Alice has age 23", or "AB=3" to denote "the line segment from A to B has length 3". As with (a), this usage tends to violate properties 2-4 above, but is often seen for instance in the homework assignments of undergraduate maths students, as a notational shorthand for a slightly longer, but more precise, English or mathematical sentence (e.g. writing |AB|=3 instead of AB=3); it may be formally incorrect usage, but the violation is often fairly harmless and can be properly understood from context.

(c) As further variant of (a), the symbol "=" is sometimes used informally to mean something like "is transformed into" or "has a consequence of", e.g. "Passing Go = $200", "water + heat = steam", or (as is sometimes seen in calculus homework assignments) "x^3 = 3x^2" or even "x^3 = 3x^2 = 6x". Again, this violates properties 2 and 3, and perhaps also 1, though one could argue that property 4 still survives.

(d) In some computer languages, the equals sign = is used as an assignment operator rather than a binary relation, basically violating all of the properties 0-4 above, e.g. "x=x+1" would be interpreted to mean "replace the value of x with the value of x incremented by 1". As this type of variable assignment is so at odds with the laws of first-order logic, its use is discouraged in mathematics (except perhaps in portions of a mathematical argument that are explicitly designated as "pseudocode" for describing an algorithm).

(e) The laws of equality prohibit distinct objects from being set equal to the same mathematical object; for instance, one cannot have a (non-degenerate) triangle whose vertices are given by A, A, and B, because the "location of A" then becomes ambiguous, in violation of the law of substitution. Similarly, one cannot discuss the concept of a set {2,2,3} consisting of three elements, two of which are the number 2 and the third is the number 3. However, it is perfectly permissible to have distinct objects being

*labeled*by the same label, so long as one keeps the label of the object distinct from the object itself. For instance, one can certainly talk about an ordered triple (A,A,B), which can be thought of as a labeling of the set {1,2,3} in which 1 and 2 are assigned the label A and 3 is assigned the label B. (Similarly, given a careful definition of the notion of multiset, one can talk about a multiset {2,2,3} in which the number 2 occurs with multiplicity two and the number 3 occurs with multiplicity one.) So in formal mathematics one sometimes has to make a careful distinction between an object, and the name or label given to that object.(f) Occasionally, one sees the notion of equality used in a stronger sense than the mathematical notion of having equal value, in that one also requires equality of

*form*as well as*value*. For instance, with this notion, the fractions 2/4 and 3/6 would not be equal, because their forms are different (they have different numerators and denominators). As another example, with this interpretation, 2+3 is now not equal to 5 (the former is a sum, and the latter is not). This stronger notation of equality still obeys all the laws of mathematical equality, and can be accommodated by the device of introducing notions of "formal objects" (e.g. formal fractions, formal power series, formal polynomials, formal strings, etc.), and carefully distinguishing the formal object from their evaluations, e.g. distinguishing the formal fractions 2/4 and 3/6 from the real number 0.5 that they both evaluate to, or the formal string "2+3" from the number 2+3=5 that it evaluates to. This is necessary in order to preserve the law of substitution for mathematical concepts such as "numerator of a fraction" (or, for an example from more advanced mathematics, "degree of a polynomial" when working over a finite field). (One could argue that the failure to distinguish between a formal numeral and the number that it evaluates to is one of the reasons why mathematical identities such as 0.999... = 1 or 1+2+3+... = -1/12 can cause so much confusion.)A practising mathematician would implicitly know that the usage of the equality symbol = in mathematics is usually not intended to be of any of the interpretations (a)-(f) given above, but this seemingly obvious fact is not necessarily evident to non-mathematicians. Given how fundamental equality is to mathematics, this issue can be a real obstacle if one wishes to explain a mathematical argument to a non-mathematician...

Post has shared content

Public

Our lecture notes on static program analysis are now online - with implementation and exercises.

Post has shared content

Learn Assembler by writing C code and learn to write optimized C code by looking at its Assembler output:

http://gcc.godbolt.org/

Have fun!

http://gcc.godbolt.org/

Have fun!

Post has shared content

Programming with Refinement Types, an intro to SMT and LiquidHaskell with exercises.

http://ucsd-progsys.github.io/liquidhaskell-tutorial/

http://ucsd-progsys.github.io/liquidhaskell-tutorial/book.pdf

http://ucsd-progsys.github.io/liquidhaskell-tutorial/

http://ucsd-progsys.github.io/liquidhaskell-tutorial/book.pdf

Post has shared content

Need a algorithm to solve your problem? You can start here, and see if solution already exists.

#programming #algorithm +Khan Academy #computerscience

#programming #algorithm +Khan Academy #computerscience

Post has shared content

Public

"Applied Crypto Hardening"

94 page PDF guide to configuring SSL, PGP, SSH and other cryptographic tools.

94 page PDF guide to configuring SSL, PGP, SSH and other cryptographic tools.

Post has shared content

Public

So you want to be a proof engineer? Which books to read. #proofcraft

Post has shared content

Public

proofcraft.org: new blog about proof and Isabelle.

This week: Isabelle syntax highlighting in markdown and HTML.

This week: Isabelle syntax highlighting in markdown and HTML.

Post has shared content

New snapshot of my algorithms stuff, now with (unfinished) notes on languages and automata, with lots of exercises and pretty pictures.

I wrote the new notes for a new junior-level theory course that Lenny Pitt and I have been piloting for the last two semesters, which is now required for all computer science majors and all computer engineering majors at Illinois. You can see my beta version of the course at https://courses.engr.illinois.edu/cs498374/fa2014/. Lenny and Chandra Chekuri are teaching the first full-scale offering of the course next semester, with an enrollment of 400.

Did I mention that we're hiring theory faculty this year? We are indeed hiring theory faculty this year.

I wrote the new notes for a new junior-level theory course that Lenny Pitt and I have been piloting for the last two semesters, which is now required for all computer science majors and all computer engineering majors at Illinois. You can see my beta version of the course at https://courses.engr.illinois.edu/cs498374/fa2014/. Lenny and Chandra Chekuri are teaching the first full-scale offering of the course next semester, with an enrollment of 400.

Did I mention that we're hiring theory faculty this year? We are indeed hiring theory faculty this year.

Post has shared content

Wait while more posts are being loaded