Wikipedia:Reference desk/Archives/Mathematics/2023 October 18

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.

October 18

What is the fewest number of symbols mathematics actually needs?

I know much of mathematics is based around defining constructs in terms of more elementary constructs using more basic sets of symbols (such as subtraction as equivalence classes, addition as repetition of the successor function, natural numbers as sets, etc.), eventually trickling down to a set of axioms such as ZFC. I also know that even the ZFC axioms could be expressed with fewer symbols, such as replacing all logical operators in them with NANDs/NORs, rewriting existential/universal quantifications to use solely one or the other, using prefix notation to remove the need for parentheses with regards to binary operations, and so on.

So what is the actual minimum set of symbols one needs to define to be able to represent ZFC's axioms (or more loosely mathematics in general)? So far I think I've narrowed it down to

1. $P$ (for arbitrary predicates),
2. $x$ (for arbitrary sets),
3. ^* (for differentiating multiple predicates/sets in the same axiom, in a manner similar to Proof sketch for Gödel's first incompleteness theorem#Gödel numbering),
4. $\{$ and $\}$ (for set-builder notation),
5. $\forall$ (for universal quantification),
6. $($ and $)$ (for illustrating the bounds of quantifiers),
7. $\in$ (for set membership), and
8. $\mid$ (for logical operations and for set-builder notation),

(which for context would turn the axiom of empty set, $\exists x\,\forall y\,\lnot (y\in x)$, into $(\forall x((\forall x*((x*\in x)\mid (x*\in x)))\mid (\forall x*((x*\in x)\mid (x*\in x)))))\mid (\forall x((\forall x*((x*\in x)\mid (x*\in x)))\mid (\forall x*((x*\in x)\mid (x*\in x)))))$--not bothering with prefix notation since it wouldn't change anything), but are all of those symbols truly independent and irreducible? Can that list be improved, or is that list even insufficient?

(Disclaimer: not a mathematician.) 2603:8001:4542:28FB:D1A0:7BBB:E6CF:5C27 (talk) 06:22, 18 October 2023 (UTC) (Please send talk messages here instead)

If your formulas do not have to follow the most common conventional notation, you can use Polish notation to dispense with the grouping brackets $($ and $)$. I suspect $\mid$ can then be omitted without introducing an ambiguity. To be sure, I'd need to see a formal grammar for your expressions; can $\forall$ take a variable number of arguments? You can then also replace $\{$ and $\}$ by a single prefix symbol, either a new one such as $\{\!\},$ or by repurposing another symbol such as $\textstyle \int .$ Also, depending on the formal grammar, you may always know for any given variable name position whether it is a predicate or a set, or the distinction may not matter – in some approaches predicates are sets (or the other way around). Then, instead of using $P,P*,P{*}*,...$ and $x,x*,x{*}*,....$ you can use the variable names $*,**,*{*}*,...\,.$ Even if sets and predicates are different animals, you can nevertheless choose to replace the notation $\alpha {\in }\beta$ (or ${\in }\alpha \beta$ in Polish notation) by just $\beta \alpha ,$ so that $\in$ is not needed. If this all works, you're left with $*,\textstyle \int$ and $\forall .$  --Lambiam 07:30, 18 October 2023 (UTC)

PS. I see the naive use of variable names $*,**,*{*}*,...$ does not work, since two variables can be juxtaposed, and we wouldn't be able to distinguish $*~*\!\!*$ and $*\!\!*~*.$ So some extra symbol is needed, say $x.$ Note also that we might choose to encode symbols as a sequence of other symbols, for example $x\to 0,$ $*\to 10,$ $\textstyle \int \to 110,$ $\forall \to 111.$  --Lambiam 07:42, 18 October 2023 (UTC)

Everything you wrote above is encoded with just two symbols: bit 0 and bit 1... --CiaPan (talk) 07:52, 18 October 2023 (UTC)

Whilst a superficially quite clever observation, it seems reasonable to interpret the word "symbol" in the original question in the sense usually implied in information theory and your ones and zeros as those symbols' informational content. 2A01:E0A:D60:3500:F8C0:6C77:38AA:8D84 (talk) 16:06, 18 October 2023 (UTC)

I think that POV may be too symbol-centric. What you really want is language and model for expressing and proving theorems of ZFC. Such a language has a set of formal symbols, a grammar that generates valid sentences, and semantics that connects it with ZFC. As demonstrated above one could use fewer symbols with a more complex grammar, or more symbols with a simpler grammar. If they are valid models, they will have a similar information-theoretic complexity. We know that Turing machines can be used to prove any true assertion in ZFC--just set a Turning machine to enumerate all true statements in ZFC, it will get to your assertion eventually. Then 0 and 1, or a mark and its absence, are a valid symbol set for this task. --{{u|Mark viking}} {Talk} 18:00, 18 October 2023 (UTC)

I don't think so; whilst it would certainly be possible to encode the eight originally suggested symbols P, x, * and so on as binary strings 000, 001, 010, up to 111, or perhaps even to use some sort optimised variable length encoding, you still have eight distinct symbols; they're just spelled differently. 2A01:E0A:D60:3500:2A0F:F398:F5E6:A1B7 (talk) 18:16, 18 October 2023 (UTC)

A relevant term here is compositionality. If "$111$" is not a symbol on its own but a sequence of three symbols supposed to mean $\forall$ when combined, can we retrieve this meaning by composing it from the three meanings of these symbols? Somewhat obviously not in a simple straightforward way, but I expect it is possible using higher-order functions to denote meanings like in Montague grammar and Church encodings. See also Continuation-passing style.  --Lambiam 19:17, 18 October 2023 (UTC)

Leon Henkin found 5 primitive symbols sufficed: ( ) f , and ⊃ . The ref is

Henkin, L. (1949). "The completeness of the first-order functional calculus". The Journal of Symbolic Logic, 14(3), 159-166 https://www.jstor.org/stable/2267044 . The symbol f is a constant and belongs to the set of propositional symbols; for each number n there is a set of functional symbols which separate into variables or constants; the set of individual variables must be infinite (Henkin 1949 p.159). -- Ancheta Wis   (talk | contribs) 06:29, 19 October 2023 (UTC)

The first-order functional calculus is less powerful than ZFC, which is incomplete by Gödel's results. Next to these five symbols, which are constants, Henkin uses further symbols, such as for propositional and functional variables.  --Lambiam 21:18, 19 October 2023 (UTC)

To go to the other end of the spectrum; if you look at what Gödel wrote you'll see as well as the straightforward alphabet he used Hebrew and Greek and Gothic as well. And I haven't the foggiest what some of the mathematical symbols in Unicode are supposed to mean. ;-) NadVolum (talk) 22:05, 19 October 2023 (UTC)

⦲ means a snowman-free set.  --Lambiam 13:21, 20 October 2023 (UTC)

Ha ha, exactly! rofl ⧂ NadVolum (talk) 19:58, 22 October 2023 (UTC)