0

Suppose we have some equality-candidate relation $"="$ and we want to check if it satisfies the axiom of substitution and we have some $n-variable$ function for that. Now do we have to check that

if $a=b$, then $f(x_1,x_2,...,a,...,x_n)=f(x_1,x_2,...,b,...,x_n)$ for every position from $1$ to $n$? For example if we have a relation-candidate $"="$ and we have defined what sum of integers $"+"$ means and regard it as two variable function, then do we need to prove that if $a=b$ then $+(a,c)=+(b,c)$ and $+(c,a)=+(c,b)$? What do we do in case of predicates-formulas?

Second question relates to lemma in Tao's Analysis section about constructing integers. So, what he does there is that he defines integers as ordered pairs $(a, b) ∈ N × N$ and places an equivalence relation $=$ on these pairs by declaring $(a, b) = (c, d)$ iff $a+d = c+b$. (Well, he uses a notation $(a,b)= a - b$ where sign $"-"$ doesn't mean anything. After checking that relation is indeed of equivalence he defines operations of sum and multiply on integers.

And proves lemma 4.1.3. that those operations are well-defined.

Lemma 4.1.3 (Addition and multiplication are well-defined). Let $a, b, a_0, b_0, c, d$ be natural numbers. If $(a - b) = (a_0−b_0)$, then $(a−b) + (c−d) = (a_0−b_0) +(c−d)$ and $(a−b) × (c−d) = (a_0−b_0)×(c−d)$, and also $(c−d)+(a−b) = (c−d)+(a_0−b_0)$ and $(c−d) × (a−b) = (c−d) × (a_0−b_0)$. Thus addition and multiplication are well-defined operations (equal inputs give equal outputs).

So, second question is what the point of that lemma(what "well-defined operations" means). If i understand correctly he just checks if our relation $"="$ for integers is suitable to be a relation of equality, showing in lemma that it satisfies the axiom of substitution for these operations.

famesyasd
  • 475
  • Equivalence is not a "candidate for equality". It is simply ignoring differences you don't care about at the moment. Equality means that the two objects under discussion are actually just one object being referred to twice. Addition and multiplication are defined on the natural numbers at this point. There is as yet no $+$ or $\times$ defined on equivalence classes of ordered pairs of natural numbers untill he does so. But for that definition to work, it has to give an equivalence class as output for any two inputs, not just some arbitrary set. So he has to show that in fact, it does. – Paul Sinclair May 06 '17 at 04:21
  • I'm sorry i couldn't understand your comment in full. I do agree that $"∼"$ relation is not the same thing as $"="$. I don't know why i decided to mistype "places an equivalence relation $"="$ " with $"∼"$ sign. But i guess the point is that we consider this relation to be of equality type so after that he denotes it with $"="$ sign. But to have a right of doing so we need to check if it satisfies the axiom of substitution for operations $"+"$ and $"×"$ and that's what he does in lemma. Am i guessing right? – famesyasd May 06 '17 at 04:53
  • @PaulSinclair And i couldn't understand your last couple of sentences. I will write down the definitions he gives for $"+"$ and $"×"$, wondering if that helps. The sum of two integers, $(a−b) + (c−d)$, is defined by the formula $(a−b) + (c−d) := (a + c)−(b + d)$. The product of two integers, $(a−b) × (c−d)$, is defined by $(a−b) × (c−d) := (ac + bd)−(ad + bc)$. – famesyasd May 06 '17 at 04:55
  • @PaulSinclair i got some of your point in finishing sentences, i realized that $a-b$ is a set, but set is an object, functions map some objects to others, so what he needs to show to make his definitions work? – famesyasd May 06 '17 at 17:19

2 Answers2

1

Let me start by saying that I am not familiar with Tao's presentation. But this is a well-known construction dating back to the 19th century, so any variances between what Tao does and what I describe are almost certainly philosophic instead of in substance.

We are trying to build integers from the natural numbers $\Bbb N$. So we introduce the relation $\sim$ on $\Bbb N^2$ by $(a, b) \sim (c,d)$ if and only if $a+d = b + c$, and prove that it is an equivalence relation (reflexive, symmetric, transitive). For any $(a,b) \in \Bbb N$, we define its equivalence class to be the set $[(a,b)] := \{(c,d) \in \Bbb N^2\mid (c,d) \sim (a,b)\}$, and note that $(a,b) \sim (c,d)$ if and only if $[(a,b)] = [(c,d)]$.

Then we define $\Bbb Z$ to be the set of equivalence classes. So what exactly are the elements of $\Bbb Z$? They are sets of ordered pairs of natural numbers. There is no addition or multiplication yet defined on these sets.

You offered definitions of addition and multiplication, but unless Tao is doing something unusual (but not entirely unheard of), your definitions are not exactly right. The definitions you gave were between pairs of natural numbers. But the elements of $\Bbb Z$ are not pairs. They are sets of pairs. The actual definitions are:

  • for $x, y \in \Bbb Z, x + y := [(a + c, b + d)]$ and $x\times y := [(ac+bd, ad+bc)]$ for some $(a,b) \in x, (c, d) \in y$.

Now there is an issue with these definitions: we want $x + y$ and $x \times y$ to each be a single element of $\Bbb Z$, but the definitions depend on arbitrarily chosen representatives $(a,b)$ of $x$ and $(c,d)$ of $y$. If instead we chose a different representative $(a', b') \in x$, would we get the same element of $\Bbb Z$ to be $x + y$? And similarly for $y$ and $x \times y$?

This is what Tao means by being well-defined. For this definition of $x + y$ to work, we need that for any $(a, b), (a', b') \in x$ and any $(c, d), (c', d') \in y$, that $[(a + b, c + d)] = [(a' + b', c' + d')]$. Otherwise there will be more than one element of $\Bbb Z$ that meets the definition. As already noted, $[(e,f)] = [(g. h)]$ if and only if $(e,f) \sim (g,h)$ (this is a general property of equivalence relations and their equivalence classes). So we can translate the condition for $x + y$ to be well-defined to the statement:

If $(a, b) \sim (a',b')$ and $(c,d) \sim (c', d')$, then $(a + c, b + d) \sim (a' + c', b' + d')$.

So that is what Tao proves to show that the definition of $x + y$ makes sense - that it really does define exactly one element of $\Bbb Z$ to be the sum of $x$ and $y$.

And similarly for $x \times y$.

Paul Sinclair
  • 43,643
  • i have two minor questions left: firstly we define $∼$ on ordered pairs, then we get integers and Tao places $"="$ on them saying that $[(a,b)]=[(c,d)]$ iff $a+b=c+d$(that's his definition!), but since we can prove that $(a,b)∼(c,d)$ if and only if $[(a,b)]=[(c,d)]$, and we have defined $(a,b)∼(c,d)$ iff $a+d=c+b$, that means we can prove his definition, right? the equality he is defining is not something new, in fact, it's just an equality between sets! and we already know that it's reflexive, symmetric and transitive so we don't have to check those properties(as he does). – famesyasd May 07 '17 at 09:05
  • second: i thought that way of defining operations was nice: let [a,b] and [c,d] be some integers, [a,b]+[c,d] we map to [a+c,b+d](that is also an integer, isn't it?), so we have an operation if anything, it's just for us it is important for it to give the same output to equal inputs, say, if we have [a,b]=[a',b'] then [a,b]+[c,d]=[a',b']+[c,d] and i have proved it(and Tao proves it in lemma). So well-defining means that it's not like we have not defined operations or anything but we have checked that they are just what we needed? – famesyasd May 07 '17 at 09:48
  • also having checked that operations are well-defined we would also had checked that our equality-relation satisfies the axiom of substitution. $<-$ that's how i have interpreted it, but your definition of operations is different from mine. i don't get it, why do you have to choose representatives from class+how it works? i mean, do you map from $N^2$ because of representatives or something? let's say we choose firstly some class $[a,b]$ that would be mapping from $Z$ i think, but then we have to choose some representative from it so what mapping would it be? – famesyasd May 07 '17 at 10:04
  • "the equality he is defining is not something new, in fact, it's just an equality between sets". It is equality between sets and it is already defined. This is NOT a definition he is making. If something is already defined, you do not define it again. What he defines is that integers are equivalence classes of $\sim$. That $[a] = [b]$ when $a \sim b$ is then a statement provable from the definition of equivalence classes. It is not a definition itself. – Paul Sinclair May 07 '17 at 17:09
  • Your definition of the operations is the same as mine. The only difference is that for some reason you are not recognizing what you are doing in it. You say that $[a, b] + [c, d] = [a +c, b+ d]$ is your definition, but in that definition you have chosen representatives! In order to make that definition, you need to have actual numbers $a, b, c,$ and $d$, so that you can add $a +c$ and $b+d$. But $[a,b]$ is a set of many different pairs. Which pair provides the values $a$ and $b$? Your definition depends on that choice, so you have to show it always gives the same result. – Paul Sinclair May 07 '17 at 17:23
  • And we don't have to prove any properties of equality such as substitution, exactly because this is not some new definition of equality. It is just equality of sets, that was there from the beginning, and which we already know satisfies these properties. – Paul Sinclair May 07 '17 at 17:25
  • ok, in a mean-time i understood what well-defined function means, but i thought about it in a narrow way, say we have $f:2->3$ and $f:2->4$ but another point is when we have an equality relation between objects a and b, then we must/or just should? have $f(a)=f(b)$ i guess that follows from set theory or something. so on reals $f$ should(or must?) behave like $f(1/2)=f(0.5)$. In our case we might have a problem with equivalence class, so we need to prove that f gives same outputs for whatever its equal forms can be, and those forms we get by selecting a representative. – famesyasd May 07 '17 at 19:47
  • my last question: i have read that further we have an isomorphism between natural numbers and some integers, thus we can "identify" them. Not only it affects our notation for integers(we can write $n$ instead of $[n,0]$) we also start to consider naturals as a subset of integers(though it is clearly not) so is there any formal-rigorous background to justify this reasoning or is it all very informal? where can i read about this? ty anyway for helping! – famesyasd May 07 '17 at 20:05
  • If you "have an equality relation" between $a$ and $b$, that means that $a$ and $b$ are simply two names for the same thing. So of course any function should have the value for both, but it really means the same value for the same thing. If you call you wife "sweety" sometimes and "honey" others, that doesn't make you are a bigamist. The thing about equivalence classes is that when first modding out the equivalence relation, the only way you have to define anything on the classes is by the elements in them, so you have to make your definition give the same answer regardless of the one chosen. – Paul Sinclair May 08 '17 at 23:29
  • You really shouldn't think of what you've been building as being "the" natural numbers or "the" integers. Rather, the natural numbers, integers, rationals, etc. are just some sets that obey certain lists of axioms, and about which nothing else is known. What you have been building are models of the natural numbers and integers - specific sets meeting those axioms, thereby proving that there are sets that meet them. You built your model of the integers from your model of the natural numbers, and behold, a certain subset of the integers also turns out to model the natural numbers. – Paul Sinclair May 08 '17 at 23:35
  • alright, i'm fine for now, but if something else appears to be asked or added should i do it here or in a new question?(i mean it might appear after some serious time like couple of weeks-months) – famesyasd May 09 '17 at 07:38
  • If it is a clarification of something I've said here, then you can ask it here. But otherwise, you should ask it as a new question. – Paul Sinclair May 09 '17 at 16:12
0

I don't know about the first part of your question.

But in the third edition of Tao's Analysis I, the remark

equal inputs give equal outputs.

has been appended to Lemma 4.1.3. So given two integers which are considered equal, i.e. $\text{integer}(a, b) = \text{integer}(a', b') \Leftrightarrow a + b' = b' + a$, an addition with another integer $\text{integer}(c, d)$ will, again, be considered equal

$$ \text{integer}(a, b) + \text{integer}(c, d) = \text{integer}(a', b') + \text{integer}(c, d). $$

No word said if this definition of equality is reflexive, symmetric, transitive or substitutive.

Max Herrmann
  • 1,406