FOL with a full and restricted language vs. “typeless” FOL
up vote
0
down vote
favorite
Background
In my readings on algebraic logic, two notions I've come across repeatedly that cause me a bit of confusion are the notions of a logic with a full and restricted language and a typeless logic.
A language in this context is a triple $langle alpha, mathcal{R}, rho rangle$, where the ordinal $alpha$ is the dimension of the language (which determines the length of the sequence of variables in the language: $langle v_j : j < alpha rangle$), $mathcal{R}$ the set of relation symbols, and $rho$ the rank function $rho : mathcal{R} to beta$, $beta leq alpha$, that assigns a rank/arity to every relation symbol. In a full language, the rank of every relation symbol is $alpha$. The language is restricted if every relational atomic formula is of the form $R_i (v_0, dots, v_j, dots)_{j < rho(R)}$, i.e., the variables all occur in a fixed order and without repetition.
So, in a full and restricted language, every relation symbol has rank/arity $alpha$. By contrast, in a typeless ("rank-free"/"type-free") logic the arity of the relation symbols is not "fixed in advance" but rather is "given by the model".
Practically, the two languages look very similar. In full languages the variables can be left out since their order and number is determined by the dimension of the language. In typeless approaches the variables are left out since the arity of relation symbols is unknown. In either case, what you're left with is a version of FOL that behaves much like a propositional modal logic.
What confuses me is that in full and restricted languages, authors often say things that suggest that the arity of relation symbols isn't as fixed as it initially appears. For example in their "Algebraizable Logics" (1989, p. 69) Blok and Pigozzi write "...[R]elation variables represent relations of all possible ranks." (emphasis added). In their "Algebraic Logic" (2001, p. 223) note that the atomic formulas of languages with different dimensions are identified, so that a language with a larger dimension contains the formulas of languages with smaller dimensions -- and apparently the differing rank of the relation symbols is no impediment to this.
By contrast a typeless logic leaves matters of rank entirely to the semantics. So, there is no problem with identifying relation symbols from languages of different dimensions on the syntactic side since they're not given a rank (in the syntax) that might make them prima facie distinct. However, to compound my confusion, Tarek Sayed Ahmed in "Three Interpolation Theorems for Typeless Logics" (2012, p. 1003) suggests that, in fact, typeless logics have full languages. On the other hand, in "Finite Schema Completeness for Typeless Logic and Representable Cylindric Algebras" (1991) András Simon clearly distinguishes between a "typeless language", which doesn't possess a rank function at all, and a full language -- though he notes that that his typeless language can be easily interpreted as a full language.
TL;DR
In what sense do relation symbols in full languages "represent relations of all possible ranks" (especially larger ranks), and how do full languages differ from typeless languages (if they differ at all)?
first-order-logic algebraic-logic
asked Nov 14 at 22:30
Dennis
1,083621
add a comment |
up vote
0
down vote
favorite
Background
In my readings on algebraic logic, two notions I've come across repeatedly that cause me a bit of confusion are the notions of a logic with a full and restricted language and a typeless logic.
A language in this context is a triple $langle alpha, mathcal{R}, rho rangle$, where the ordinal $alpha$ is the dimension of the language (which determines the length of the sequence of variables in the language: $langle v_j : j < alpha rangle$), $mathcal{R}$ the set of relation symbols, and $rho$ the rank function $rho : mathcal{R} to beta$, $beta leq alpha$, that assigns a rank/arity to every relation symbol. In a full language, the rank of every relation symbol is $alpha$. The language is restricted if every relational atomic formula is of the form $R_i (v_0, dots, v_j, dots)_{j < rho(R)}$, i.e., the variables all occur in a fixed order and without repetition.
So, in a full and restricted language, every relation symbol has rank/arity $alpha$. By contrast, in a typeless ("rank-free"/"type-free") logic the arity of the relation symbols is not "fixed in advance" but rather is "given by the model".
Practically, the two languages look very similar. In full languages the variables can be left out since their order and number is determined by the dimension of the language. In typeless approaches the variables are left out since the arity of relation symbols is unknown. In either case, what you're left with is a version of FOL that behaves much like a propositional modal logic.
What confuses me is that in full and restricted languages, authors often say things that suggest that the arity of relation symbols isn't as fixed as it initially appears. For example in their "Algebraizable Logics" (1989, p. 69) Blok and Pigozzi write "...[R]elation variables represent relations of all possible ranks." (emphasis added). In their "Algebraic Logic" (2001, p. 223) note that the atomic formulas of languages with different dimensions are identified, so that a language with a larger dimension contains the formulas of languages with smaller dimensions -- and apparently the differing rank of the relation symbols is no impediment to this.
By contrast a typeless logic leaves matters of rank entirely to the semantics. So, there is no problem with identifying relation symbols from languages of different dimensions on the syntactic side since they're not given a rank (in the syntax) that might make them prima facie distinct. However, to compound my confusion, Tarek Sayed Ahmed in "Three Interpolation Theorems for Typeless Logics" (2012, p. 1003) suggests that, in fact, typeless logics have full languages. On the other hand, in "Finite Schema Completeness for Typeless Logic and Representable Cylindric Algebras" (1991) András Simon clearly distinguishes between a "typeless language", which doesn't possess a rank function at all, and a full language -- though he notes that that his typeless language can be easily interpreted as a full language.
TL;DR
In what sense do relation symbols in full languages "represent relations of all possible ranks" (especially larger ranks), and how do full languages differ from typeless languages (if they differ at all)?
first-order-logic algebraic-logic
asked Nov 14 at 22:30
Dennis
1,083621
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Background
In my readings on algebraic logic, two notions I've come across repeatedly that cause me a bit of confusion are the notions of a logic with a full and restricted language and a typeless logic.
A language in this context is a triple $langle alpha, mathcal{R}, rho rangle$, where the ordinal $alpha$ is the dimension of the language (which determines the length of the sequence of variables in the language: $langle v_j : j < alpha rangle$), $mathcal{R}$ the set of relation symbols, and $rho$ the rank function $rho : mathcal{R} to beta$, $beta leq alpha$, that assigns a rank/arity to every relation symbol. In a full language, the rank of every relation symbol is $alpha$. The language is restricted if every relational atomic formula is of the form $R_i (v_0, dots, v_j, dots)_{j < rho(R)}$, i.e., the variables all occur in a fixed order and without repetition.
So, in a full and restricted language, every relation symbol has rank/arity $alpha$. By contrast, in a typeless ("rank-free"/"type-free") logic the arity of the relation symbols is not "fixed in advance" but rather is "given by the model".
Practically, the two languages look very similar. In full languages the variables can be left out since their order and number is determined by the dimension of the language. In typeless approaches the variables are left out since the arity of relation symbols is unknown. In either case, what you're left with is a version of FOL that behaves much like a propositional modal logic.
What confuses me is that in full and restricted languages, authors often say things that suggest that the arity of relation symbols isn't as fixed as it initially appears. For example in their "Algebraizable Logics" (1989, p. 69) Blok and Pigozzi write "...[R]elation variables represent relations of all possible ranks." (emphasis added). In their "Algebraic Logic" (2001, p. 223) note that the atomic formulas of languages with different dimensions are identified, so that a language with a larger dimension contains the formulas of languages with smaller dimensions -- and apparently the differing rank of the relation symbols is no impediment to this.
By contrast a typeless logic leaves matters of rank entirely to the semantics. So, there is no problem with identifying relation symbols from languages of different dimensions on the syntactic side since they're not given a rank (in the syntax) that might make them prima facie distinct. However, to compound my confusion, Tarek Sayed Ahmed in "Three Interpolation Theorems for Typeless Logics" (2012, p. 1003) suggests that, in fact, typeless logics have full languages. On the other hand, in "Finite Schema Completeness for Typeless Logic and Representable Cylindric Algebras" (1991) András Simon clearly distinguishes between a "typeless language", which doesn't possess a rank function at all, and a full language -- though he notes that that his typeless language can be easily interpreted as a full language.
TL;DR
In what sense do relation symbols in full languages "represent relations of all possible ranks" (especially larger ranks), and how do full languages differ from typeless languages (if they differ at all)?
first-order-logic algebraic-logic
asked Nov 14 at 22:30
Dennis
1,083621
Background
In my readings on algebraic logic, two notions I've come across repeatedly that cause me a bit of confusion are the notions of a logic with a full and restricted language and a typeless logic.
A language in this context is a triple $langle alpha, mathcal{R}, rho rangle$, where the ordinal $alpha$ is the dimension of the language (which determines the length of the sequence of variables in the language: $langle v_j : j < alpha rangle$), $mathcal{R}$ the set of relation symbols, and $rho$ the rank function $rho : mathcal{R} to beta$, $beta leq alpha$, that assigns a rank/arity to every relation symbol. In a full language, the rank of every relation symbol is $alpha$. The language is restricted if every relational atomic formula is of the form $R_i (v_0, dots, v_j, dots)_{j < rho(R)}$, i.e., the variables all occur in a fixed order and without repetition.
So, in a full and restricted language, every relation symbol has rank/arity $alpha$. By contrast, in a typeless ("rank-free"/"type-free") logic the arity of the relation symbols is not "fixed in advance" but rather is "given by the model".
Practically, the two languages look very similar. In full languages the variables can be left out since their order and number is determined by the dimension of the language. In typeless approaches the variables are left out since the arity of relation symbols is unknown. In either case, what you're left with is a version of FOL that behaves much like a propositional modal logic.
What confuses me is that in full and restricted languages, authors often say things that suggest that the arity of relation symbols isn't as fixed as it initially appears. For example in their "Algebraizable Logics" (1989, p. 69) Blok and Pigozzi write "...[R]elation variables represent relations of all possible ranks." (emphasis added). In their "Algebraic Logic" (2001, p. 223) note that the atomic formulas of languages with different dimensions are identified, so that a language with a larger dimension contains the formulas of languages with smaller dimensions -- and apparently the differing rank of the relation symbols is no impediment to this.
By contrast a typeless logic leaves matters of rank entirely to the semantics. So, there is no problem with identifying relation symbols from languages of different dimensions on the syntactic side since they're not given a rank (in the syntax) that might make them prima facie distinct. However, to compound my confusion, Tarek Sayed Ahmed in "Three Interpolation Theorems for Typeless Logics" (2012, p. 1003) suggests that, in fact, typeless logics have full languages. On the other hand, in "Finite Schema Completeness for Typeless Logic and Representable Cylindric Algebras" (1991) András Simon clearly distinguishes between a "typeless language", which doesn't possess a rank function at all, and a full language -- though he notes that that his typeless language can be easily interpreted as a full language.
TL;DR
In what sense do relation symbols in full languages "represent relations of all possible ranks" (especially larger ranks), and how do full languages differ from typeless languages (if they differ at all)?
first-order-logic algebraic-logic
first-order-logic algebraic-logic
asked Nov 14 at 22:30
Dennis
1,083621
asked Nov 14 at 22:30
Dennis
1,083621
asked Nov 14 at 22:30
Dennis
1,083621
asked Nov 14 at 22:30
Dennis
1,083621
asked Nov 14 at 22:30
Dennis
1,083621
1,083621
add a comment |
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2998909%2ffol-with-a-full-and-restricted-language-vs-typeless-fol%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
