4 ms·
>> I go further, parenthesis are really just functions (in the mathematical sense); so all of first order logic comes down to making functions into variables (a
by YeGoblynQueenne 5y ago
>> I go further, parenthesis are really just functions (in the mathematical
sense); so all of first order logic comes down to making functions into
variables (a la `y=f(...)`).
I don't get what you mean. Here's a quick reminder of first-order logic (FOL)
syntax. In FOL, an atomic formula or atom is a predicate symbol followed by n ≥
0 comma-separated terms in parentheses, where n is the arity of the predicate,
terms are variables or functions, variables are quantified over functions and
constants, a function is a function symbol followed by m ≥ 0 comma-separated
terms in parentheses where m is the arity of the function and a constant is a
function with arity 0.
A FOL language consists of disjoint sets of predicate symbols and functions, and
variables. So for example, suppose you have a language with set of predicate
symbols S = {P/2} (i.e. P has arity 2), set of function symbols F = {ƒ/1} and
set of variables V = {x, y}. We can create the following atoms: P(ƒ(x), y), P(x,
ƒ(x)), P(ƒ(y), y), P(x, ƒ(y)), P(ƒ(ƒ(x)),y), P(x, ƒ(ƒ(y))), ... etc.
We can combine atoms with the two quantifiers, ∀ and ∃ and the four logic
operators ∧, ∨, → and ¬ to make well-formed formulae: ∀x∃y: P(ƒ(x), y)) ∨ P(x,
ƒ(x)) etc.
With this in mind, how is FOL making functions into variables? Can you explain
this a bit?
- bsedlm 5y ago> Can you explain this a bit? Not very well but I'll try. The idea is I'm trying to describe cannot be restricted to syntax, the summary of FOL you give is strictly syntactical. What I'm trying to observe is how predicates, functions, and variables are all variable. I mean they're all substitute-able; in this sense they're all "variable". Predicates get evaluated to booleans so I understand them in the same "level of variable" as logical connectives. Functions always end up being evaluated into things in the domain, same as the variables; so I understand both variables and functions in their own "second level of variable". And so, understanding (trying to) FOL this way, syntactically defined functions aren't really functions, but indirect variables. Which makes me think that the quantifiers are the actual functions (the parenthesis) which I was referring to. In this sense the real important thing about parenthesis is the binding variables, setting them into a scope. But by this point my intuition tells me I've assumed something wrong or maybe I just leaped over something(?). All I know is there's a reason quantifiers only take in variables (as syntactically defined) and I am trying to pin down this reason, but as I said, I still *have questions about quantifiers. In any case I've already spent way too long writing this post which might be wrong or slightly wrong/imprecise and I cannot tell how wrong and somebody would need to tell me or ask me something poignant.
- sdbrady 5y agoI think what you're getting has truth. For myself, I would generalize what you're saying as any given formula/expression is embedded in some context/environment. If one continues to "step back" or go one meta (or repeatedly so), you'll find that at some point, you, the reader/interpreter, will need to fill in some implicit or unreified context. We could call these things (shared) assumptions or axioms. As you say, if I use a function `f` to form a term in my formula written in first-order logic, the definition of `f` is implied because it is expressed "somewhere else". The question is then "where is that expressed?". Since the definition of `f` is assumed from the point of view (semantics) of first-order logic, the definition of `f` could be interpreted as "variable" at a "higher" level. Going to your parenthesis point, I agree that it is indicating the scope (i.e., the context/environment), and in that sense, I interpret parenthesis here as a kind of meta function, akin to how macros are "compile-time" functions rather than "run-time" functions. I think first-order logic and relatedly most (all?) logic programming languages are missing a facility for "reasoning" about terms themselves. The reflexive answer to this is types, but this is largely wielded as a developer tool not as a means of expressing meaning. Adding constraints to logic programming is perhaps some of the way there and has the benefit (hope) that type-like ideas could be expressed compositionally as logical formulas rather than as declarations provided by the language. My own pursuit of this subject is to see if these "levels", as you hint at, can be traversed and integrated into one logical formula language and notation. This all implies some kind of homoiconic metaprogramming, but easier said than done.
- bsedlm 5y agoIndeed, I feel like I'm reaching towards a generalized understanding of context. It seems to me that unless the logical languages are restricted from reasoing about themselves they become either incomplete or worse, inconsistent. I have a sensation that on the computer science side of things, unless "reasoning about terms themselves" is somehow 'handled' (restricted) one can end up with undecidable systems, or worse... But I still have questions about complexity so I cannot really undesrtand how completeness and soundness realte to decideability.
- YeGoblynQueenne 5y ago