Wikipedia:Reference desk/Archives/Mathematics/2022 December 16

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 16

"graph" predicate meaning in Diagonal lemma + another question

Looking at the section Background it introduces ${\mathcal {G}}_{f}(x,y)$ as a ""graph" predicate".

What does "graph" mean here?

Based on the page Predicate a predicate represents (some wff which can be true or false depending on the particular values of the variables given to the predicate, in this case x and y) and is interpreted as (a relation on x and y).

So my second question is, does the definition of predicate make the Diagonal lemma invalid for systems that have more than two different truth values (i.e. a truth value that's neither true nor false)?  AltoStev (talk) 11:51, 16 December 2022 (UTC)

Out of my realm, but I'm 99% sure this refers to Graph (discrete mathematics). --Jayron32 11:55, 16 December 2022 (UTC)

It is closely related to the concept of the graph of a function, which for a given function $f$ is the set of pairs $(x,y)$ such that $f(x)=y$ for some $x$ in the domain of $f.$ In the proof of the diagonal lemma, sets are represented as predicates, using the obvious one-one correspondence between sets and predicates, where a set $S$ corresponds to the predicate $P$ defined by $x\in S\Leftrightarrow P(x).$ This applies equally to multivariate predicates, so the predicate $G_{f}$ representing the graph of $f$ is defined by $f(x)=y\Leftrightarrow G_{f}(x,y).$ In the proof of the diagonal lemma, we see a similar definition, but instead of using values (abstract mathematical objects), we work with numerals (which you can think of as strings of symbols).

Without inspecting the details of an alternative logic, it is not possible to assert with certainty that the proof will go through, but the proof is constructive and does not depend on "classical" axioms that do not hold in many-valued logics, such as the law of excluded middle.  --Lambiam 12:55, 16 December 2022 (UTC)

The reason I asked the second question was because I got confused and thought that a third truth value would break the one-to-one correspondence between sets and predicates, but I just realized that the relations can just stay the same as long as there exists some truth value denoted "true".  AltoStev (talk) 14:24, 16 December 2022 (UTC)