Profile

Cover photo
mukesh tiwari
Attends Indian Institute of Information Technology and Management Gwalior
Lives in Gwalior
215 followers|18,324 views
AboutPostsPhotosVideos

Stream

mukesh tiwari

Shared publicly  - 
 
 
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 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...
40 comments on original post
1
Add a comment...

mukesh tiwari

Shared publicly  - 
 
 
Our lecture notes on static program analysis are now online - with implementation and exercises.
View original post
1
Add a comment...

mukesh tiwari

Shared publicly  - 
 
 
Need a algorithm to solve your problem? You can start here, and see if solution already exists.
#programming #algorithm +Khan Academy #computerscience  
View original post
2
Add a comment...

mukesh tiwari

Shared publicly  - 
 
 
So you want to be a proof engineer? Which books to read. #proofcraft
I want to verify software! Will prove theorems for money! What do I need to learn? You're a programmer, maybe with a computer science or math degree. You're interested in program verification and proofs, but have no previous experience in these. You want to learn. Here's what you should read.
4 comments on original post
3
Boyd Smith's profile photomukesh tiwari's profile photo
2 comments
 
+Boyd Smith Yes it is the title of job in NICTA.
Add a comment...

mukesh tiwari

Shared publicly  - 
 
 
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.
Algorithms, Etc. by Jeff Erickson December 2014 revision. This page contains lecture notes and other course materials for various algorithms classes I have taught at the University of Illinois, Urbana-Champaign. The notes are numbered in the order I cover the material in a typical undergraduate ...
1
Add a comment...

mukesh tiwari

Shared publicly  - 
 
 
Tom Ball, Ras Bodik, +Greg Morrisett, and I are organizing a new kind of programming languages conference. We already have several excellent conferences, but they are focused on incremental bits of novelty. We want to create a new kind of venue that complements these: to present and discuss big-picture questions and long-running programs; to view progress along the long arc of a research effort. The conference is May 3-6, 2015 in lovely Asilomar (on the Pacific Coast), CA, USA.

If this sounds interesting, please: don't just +1 it, reshare it. Why? To keep costs down and retain ownership of the conference with the community, we are independent, not affiliated with any organizations. That means you are the only PR channel we have. So please do us a favor. Thanks.
1
Add a comment...
Have him in circles
215 people
Chandrasekhar Dronavajjala's profile photo
amit kumar's profile photo
Quoc Anh Trinh's profile photo
Ravi Raj's profile photo
Renu Raj Garg's profile photo
Anshul Malik's profile photo
komal bal's profile photo
Vishnu Meena's profile photo
Sanjith Warrier's profile photo

mukesh tiwari

Shared publicly  - 
 
 
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!
Interactive compiler -. Share. Tweet. About. Google+ page · About Matt · Contact Matt. Source: Name: Load Save Save as... Permalink. Permalink: Compiler: Compiler options: Filter: Unused labels. Directives Comment-only lines. Intel syntax. Colourise. Code editor. // Type your code here, ...
2 comments on original post
1
1
Slobodan Jelic's profile photo
Add a comment...

mukesh tiwari

Shared publicly  - 
 
 
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
Programming with Refinement Types. An Introduction to LiquidHaskell. Ranjit Jhala, Eric Seidel, Niki Vazou. 1.Introduction · 1.1. Well-Typed Programs Do Go Wrong · 1.2. Refinement Types · 1.3. Audience · 1.4. Getting Started · 1.5. Sample Code · 2.Logic & SMT · 2.1. Syntax · 2.2.
View original post
1
Add a comment...

mukesh tiwari

Shared publicly  - 
 
 
"Applied Crypto Hardening"

94 page PDF guide to configuring SSL, PGP, SSH and other cryptographic tools.
4 comments on original post
1
Add a comment...

mukesh tiwari

Shared publicly  - 
 
 
proofcraft.org: new blog about proof and Isabelle.

This week: Isabelle syntax highlighting in markdown and HTML.
Wouldn't it be nice to just include snippets of Isabelle code in markdown or html and have them show up rendered with symbols and highlighting? For instance on a blog? Or a list like the Top 100 theorems? Or on github? Set your quick_and_dirty flags and read on.
1
Add a comment...

mukesh tiwari

Shared publicly  - 
1
Add a comment...

mukesh tiwari

Shared publicly  - 
 
 
Algomation. al·go·ma·tion. /ˌanəˈmāSHən/. noun. 1. A didactic, animated, exposition of algorithms. 2. An algorithm in a state of motion. Search Now ». Featured Algorithms. Ⓒ Duncan Meech - Algomation 2014 · Sign In - RegisterSign OutCreate AlgorithmMy AlgorithmsForgot PasswordChange ...
1
Add a comment...
People
Have him in circles
215 people
Chandrasekhar Dronavajjala's profile photo
amit kumar's profile photo
Quoc Anh Trinh's profile photo
Ravi Raj's profile photo
Renu Raj Garg's profile photo
Anshul Malik's profile photo
komal bal's profile photo
Vishnu Meena's profile photo
Sanjith Warrier's profile photo
Education
  • Indian Institute of Information Technology and Management Gwalior
    present
Basic Information
Gender
Male
Birthday
July 21
Other names
Sahil Tiwari
Story
Tagline
keep learning
Work
Occupation
Student
Employment
  • Student, present
Places
Map of the places this user has livedMap of the places this user has livedMap of the places this user has lived
Currently
Gwalior
Previously
Mughalsarai(Varanasi)