Is the set of proposition symbols necessarily a countable set? [duplicate]
$begingroup$
This question already has an answer here:
Why do first order languages have at most countably many symbols?
2 answers
I am busy latedays with "Logic and Structure" of Van Dalen in order to get some familiarity with logic.
Proposition symbols are introduced (on page 7) as members of an infinitely countable set ${p_0,p_1,p_2,dots}$.
My first thought was: why not just a set without any further specification?
Uptil now I could not find a satisfying answer.
Let me mention that I did find a proof (on page 44) that every (syntactically) consistent set of propositions is contained in a set of propositions that is maximally consistent, and in that proof it is used that the set of proposition symbols is countable.
That however can also be proved if there is no countability, but then by application of the lemma of Zorn.
So I wondered if the countability is there because this (i.e. Zorn/axiom of choice) must be avoided for some reason.
I really don't know...
So my question is:
Is there a special reason/motivation to go for an (infinitely) countable set of proposition symbols?
logic propositional-calculus
asked Dec 11 '18 at 11:53
drhabdrhab
102k545136
$endgroup$
marked as duplicate by Noah Schweber logic
Users with the logic badge can single-handedly close logic questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 11 '18 at 15:08
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
|
show 1 more comment
$begingroup$
This question already has an answer here:
Why do first order languages have at most countably many symbols?
2 answers
I am busy latedays with "Logic and Structure" of Van Dalen in order to get some familiarity with logic.
Proposition symbols are introduced (on page 7) as members of an infinitely countable set ${p_0,p_1,p_2,dots}$.
My first thought was: why not just a set without any further specification?
Uptil now I could not find a satisfying answer.
Let me mention that I did find a proof (on page 44) that every (syntactically) consistent set of propositions is contained in a set of propositions that is maximally consistent, and in that proof it is used that the set of proposition symbols is countable.
That however can also be proved if there is no countability, but then by application of the lemma of Zorn.
So I wondered if the countability is there because this (i.e. Zorn/axiom of choice) must be avoided for some reason.
I really don't know...
So my question is:
Is there a special reason/motivation to go for an (infinitely) countable set of proposition symbols?
logic propositional-calculus
asked Dec 11 '18 at 11:53
drhabdrhab
102k545136
$endgroup$
marked as duplicate by Noah Schweber logic
Users with the logic badge can single-handedly close logic questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 11 '18 at 15:08
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
How exactly is a "proposition symbol" defined in this book?
$endgroup$
– Martin Rosenau
Dec 11 '18 at 12:22
$begingroup$
@MartinRosenau The book starts with a "language" based on an "alphabet" containing 1) proposition symbols 2) connectives 3) auxiliary symbols (brackets and comma). Base on that propositions are introduced and proposition symbols are (together with the symbol $bot$ for "false") the atomic propositions. So I am afraid that "proposition symbol" is a rather primitive notion that is not defined on base of entities that were introduced earlier. So in a way comparable with "sets" in set-theory (they are not defined).
$endgroup$
– drhab
Dec 11 '18 at 12:31
1
$begingroup$
You are right; see e.g. Mendelson's textbook. Proving the Completeness Th for FOL (page 84) there is a Lemma : "The set of expressions of a language $text L$ is denumerable. Hence, the same is true of the set of terms, the set of wfs and the set of closed wfs." At page 113 : "in the notion of first-order language, we allow a noncountable number of predicate letters, function letters, and individual constants, we arrive at the notion of a generalized first-order language." Then the previous result is re-proved using the well-ordering of the set of expressions and transfinite induction.
$endgroup$
– Mauro ALLEGRANZA
Dec 11 '18 at 13:06
$begingroup$
In theory, we could have a language with uncountably many symbols; for example, they could be line segments of length $in (0,,1)$. This probably goes unexplored to ensure every symbol can be unambiguously identified, without the requirement for infinite precision in measurements.
$endgroup$
– J.G.
Dec 11 '18 at 13:15
$begingroup$
@MauroALLEGRANZA Thank you. I found this online and it matches with your quotes.
$endgroup$
– drhab
Dec 11 '18 at 13:23
|
show 1 more comment
$begingroup$
This question already has an answer here:
Why do first order languages have at most countably many symbols?
2 answers
I am busy latedays with "Logic and Structure" of Van Dalen in order to get some familiarity with logic.
Proposition symbols are introduced (on page 7) as members of an infinitely countable set ${p_0,p_1,p_2,dots}$.
My first thought was: why not just a set without any further specification?
Uptil now I could not find a satisfying answer.
Let me mention that I did find a proof (on page 44) that every (syntactically) consistent set of propositions is contained in a set of propositions that is maximally consistent, and in that proof it is used that the set of proposition symbols is countable.
That however can also be proved if there is no countability, but then by application of the lemma of Zorn.
So I wondered if the countability is there because this (i.e. Zorn/axiom of choice) must be avoided for some reason.
I really don't know...
So my question is:
Is there a special reason/motivation to go for an (infinitely) countable set of proposition symbols?
logic propositional-calculus
asked Dec 11 '18 at 11:53
drhabdrhab
102k545136
$endgroup$
This question already has an answer here:
Why do first order languages have at most countably many symbols?
2 answers
I am busy latedays with "Logic and Structure" of Van Dalen in order to get some familiarity with logic.
Proposition symbols are introduced (on page 7) as members of an infinitely countable set ${p_0,p_1,p_2,dots}$.
My first thought was: why not just a set without any further specification?
Uptil now I could not find a satisfying answer.
Let me mention that I did find a proof (on page 44) that every (syntactically) consistent set of propositions is contained in a set of propositions that is maximally consistent, and in that proof it is used that the set of proposition symbols is countable.
That however can also be proved if there is no countability, but then by application of the lemma of Zorn.
So I wondered if the countability is there because this (i.e. Zorn/axiom of choice) must be avoided for some reason.
I really don't know...
So my question is:
Is there a special reason/motivation to go for an (infinitely) countable set of proposition symbols?
This question already has an answer here:
Why do first order languages have at most countably many symbols?
2 answers
logic propositional-calculus
logic propositional-calculus
asked Dec 11 '18 at 11:53
drhabdrhab
102k545136
asked Dec 11 '18 at 11:53
drhabdrhab
102k545136
edited Dec 11 '18 at 13:09
drhab
asked Dec 11 '18 at 11:53
drhabdrhab
102k545136
asked Dec 11 '18 at 11:53
drhabdrhab
102k545136
asked Dec 11 '18 at 11:53
drhabdrhab
102k545136
102k545136
marked as duplicate by Noah Schweber logic
Users with the logic badge can single-handedly close logic questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 11 '18 at 15:08
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Noah Schweber logic
Users with the logic badge can single-handedly close logic questions as duplicates and reopen them as needed.
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 11 '18 at 15:08
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
$begingroup$
How exactly is a "proposition symbol" defined in this book?
$endgroup$
– Martin Rosenau
Dec 11 '18 at 12:22
$begingroup$
@MartinRosenau The book starts with a "language" based on an "alphabet" containing 1) proposition symbols 2) connectives 3) auxiliary symbols (brackets and comma). Base on that propositions are introduced and proposition symbols are (together with the symbol $bot$ for "false") the atomic propositions. So I am afraid that "proposition symbol" is a rather primitive notion that is not defined on base of entities that were introduced earlier. So in a way comparable with "sets" in set-theory (they are not defined).
$endgroup$
– drhab
Dec 11 '18 at 12:31
1
$begingroup$
You are right; see e.g. Mendelson's textbook. Proving the Completeness Th for FOL (page 84) there is a Lemma : "The set of expressions of a language $text L$ is denumerable. Hence, the same is true of the set of terms, the set of wfs and the set of closed wfs." At page 113 : "in the notion of first-order language, we allow a noncountable number of predicate letters, function letters, and individual constants, we arrive at the notion of a generalized first-order language." Then the previous result is re-proved using the well-ordering of the set of expressions and transfinite induction.
$endgroup$
– Mauro ALLEGRANZA
Dec 11 '18 at 13:06
$begingroup$
In theory, we could have a language with uncountably many symbols; for example, they could be line segments of length $in (0,,1)$. This probably goes unexplored to ensure every symbol can be unambiguously identified, without the requirement for infinite precision in measurements.
$endgroup$
– J.G.
Dec 11 '18 at 13:15
$begingroup$
@MauroALLEGRANZA Thank you. I found this online and it matches with your quotes.
$endgroup$
– drhab
Dec 11 '18 at 13:23
|
show 1 more comment
$begingroup$
How exactly is a "proposition symbol" defined in this book?
$endgroup$
– Martin Rosenau
Dec 11 '18 at 12:22
$begingroup$
@MartinRosenau The book starts with a "language" based on an "alphabet" containing 1) proposition symbols 2) connectives 3) auxiliary symbols (brackets and comma). Base on that propositions are introduced and proposition symbols are (together with the symbol $bot$ for "false") the atomic propositions. So I am afraid that "proposition symbol" is a rather primitive notion that is not defined on base of entities that were introduced earlier. So in a way comparable with "sets" in set-theory (they are not defined).
$endgroup$
– drhab
Dec 11 '18 at 12:31
1
$begingroup$
You are right; see e.g. Mendelson's textbook. Proving the Completeness Th for FOL (page 84) there is a Lemma : "The set of expressions of a language $text L$ is denumerable. Hence, the same is true of the set of terms, the set of wfs and the set of closed wfs." At page 113 : "in the notion of first-order language, we allow a noncountable number of predicate letters, function letters, and individual constants, we arrive at the notion of a generalized first-order language." Then the previous result is re-proved using the well-ordering of the set of expressions and transfinite induction.
$endgroup$
– Mauro ALLEGRANZA
Dec 11 '18 at 13:06
$begingroup$
In theory, we could have a language with uncountably many symbols; for example, they could be line segments of length $in (0,,1)$. This probably goes unexplored to ensure every symbol can be unambiguously identified, without the requirement for infinite precision in measurements.
$endgroup$
– J.G.
Dec 11 '18 at 13:15
$begingroup$
@MauroALLEGRANZA Thank you. I found this online and it matches with your quotes.
$endgroup$
– drhab
Dec 11 '18 at 13:23
$begingroup$
How exactly is a "proposition symbol" defined in this book?
$endgroup$
– Martin Rosenau
Dec 11 '18 at 12:22
$begingroup$
How exactly is a "proposition symbol" defined in this book?
$endgroup$
– Martin Rosenau
Dec 11 '18 at 12:22
$begingroup$
@MartinRosenau The book starts with a "language" based on an "alphabet" containing 1) proposition symbols 2) connectives 3) auxiliary symbols (brackets and comma). Base on that propositions are introduced and proposition symbols are (together with the symbol $bot$ for "false") the atomic propositions. So I am afraid that "proposition symbol" is a rather primitive notion that is not defined on base of entities that were introduced earlier. So in a way comparable with "sets" in set-theory (they are not defined).
$endgroup$
– drhab
Dec 11 '18 at 12:31
$begingroup$
@MartinRosenau The book starts with a "language" based on an "alphabet" containing 1) proposition symbols 2) connectives 3) auxiliary symbols (brackets and comma). Base on that propositions are introduced and proposition symbols are (together with the symbol $bot$ for "false") the atomic propositions. So I am afraid that "proposition symbol" is a rather primitive notion that is not defined on base of entities that were introduced earlier. So in a way comparable with "sets" in set-theory (they are not defined).
$endgroup$
– drhab
Dec 11 '18 at 12:31
1
1
$begingroup$
You are right; see e.g. Mendelson's textbook. Proving the Completeness Th for FOL (page 84) there is a Lemma : "The set of expressions of a language $text L$ is denumerable. Hence, the same is true of the set of terms, the set of wfs and the set of closed wfs." At page 113 : "in the notion of first-order language, we allow a noncountable number of predicate letters, function letters, and individual constants, we arrive at the notion of a generalized first-order language." Then the previous result is re-proved using the well-ordering of the set of expressions and transfinite induction.
$endgroup$
– Mauro ALLEGRANZA
Dec 11 '18 at 13:06
$begingroup$
You are right; see e.g. Mendelson's textbook. Proving the Completeness Th for FOL (page 84) there is a Lemma : "The set of expressions of a language $text L$ is denumerable. Hence, the same is true of the set of terms, the set of wfs and the set of closed wfs." At page 113 : "in the notion of first-order language, we allow a noncountable number of predicate letters, function letters, and individual constants, we arrive at the notion of a generalized first-order language." Then the previous result is re-proved using the well-ordering of the set of expressions and transfinite induction.
$endgroup$
– Mauro ALLEGRANZA
Dec 11 '18 at 13:06
$begingroup$
In theory, we could have a language with uncountably many symbols; for example, they could be line segments of length $in (0,,1)$. This probably goes unexplored to ensure every symbol can be unambiguously identified, without the requirement for infinite precision in measurements.
$endgroup$
– J.G.
Dec 11 '18 at 13:15
$begingroup$
In theory, we could have a language with uncountably many symbols; for example, they could be line segments of length $in (0,,1)$. This probably goes unexplored to ensure every symbol can be unambiguously identified, without the requirement for infinite precision in measurements.
$endgroup$
– J.G.
Dec 11 '18 at 13:15
$begingroup$
@MauroALLEGRANZA Thank you. I found this online and it matches with your quotes.
$endgroup$
– drhab
Dec 11 '18 at 13:23
$begingroup$
@MauroALLEGRANZA Thank you. I found this online and it matches with your quotes.
$endgroup$
– drhab
Dec 11 '18 at 13:23
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
While I have not seen this book, it seems to be an undergraduate text.
The statements in propositional logic are finite strings of symbols.
So that one does not run out of proposition symbols when writing complicated statements, they allow infinitely many proposition symbols.
A proof is a finite list of statements.
But then any proof will require finitely many proposition symbols, but there is no upper limit on this finite number.
This shows countably many is enough.
There are languages that allow propositions to be infinite strings.
There is a Wikipedia page on infinitary logic
answered Dec 11 '18 at 13:14
JayJay
2,87311728
$endgroup$
$begingroup$
Thank you. I have no doubt that countable will be enough. It was more that starting with a set PROP of propositions I wanted to construct a Boolean algebra having as element equivalence classes on PROP. I disliked the thought that this could only lead to Boolean algebra's having a countable number of elements.
$endgroup$
– drhab
Dec 11 '18 at 13:34
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
While I have not seen this book, it seems to be an undergraduate text.
The statements in propositional logic are finite strings of symbols.
So that one does not run out of proposition symbols when writing complicated statements, they allow infinitely many proposition symbols.
A proof is a finite list of statements.
But then any proof will require finitely many proposition symbols, but there is no upper limit on this finite number.
This shows countably many is enough.
There are languages that allow propositions to be infinite strings.
There is a Wikipedia page on infinitary logic
answered Dec 11 '18 at 13:14
JayJay
2,87311728
$endgroup$
$begingroup$
Thank you. I have no doubt that countable will be enough. It was more that starting with a set PROP of propositions I wanted to construct a Boolean algebra having as element equivalence classes on PROP. I disliked the thought that this could only lead to Boolean algebra's having a countable number of elements.
$endgroup$
– drhab
Dec 11 '18 at 13:34
add a comment |
$begingroup$
While I have not seen this book, it seems to be an undergraduate text.
The statements in propositional logic are finite strings of symbols.
So that one does not run out of proposition symbols when writing complicated statements, they allow infinitely many proposition symbols.
A proof is a finite list of statements.
But then any proof will require finitely many proposition symbols, but there is no upper limit on this finite number.
This shows countably many is enough.
There are languages that allow propositions to be infinite strings.
There is a Wikipedia page on infinitary logic
answered Dec 11 '18 at 13:14
JayJay
2,87311728
$endgroup$
$begingroup$
Thank you. I have no doubt that countable will be enough. It was more that starting with a set PROP of propositions I wanted to construct a Boolean algebra having as element equivalence classes on PROP. I disliked the thought that this could only lead to Boolean algebra's having a countable number of elements.
$endgroup$
– drhab
Dec 11 '18 at 13:34
add a comment |
$begingroup$
While I have not seen this book, it seems to be an undergraduate text.
The statements in propositional logic are finite strings of symbols.
So that one does not run out of proposition symbols when writing complicated statements, they allow infinitely many proposition symbols.
A proof is a finite list of statements.
But then any proof will require finitely many proposition symbols, but there is no upper limit on this finite number.
This shows countably many is enough.
There are languages that allow propositions to be infinite strings.
There is a Wikipedia page on infinitary logic
answered Dec 11 '18 at 13:14
JayJay
2,87311728
$endgroup$
While I have not seen this book, it seems to be an undergraduate text.
The statements in propositional logic are finite strings of symbols.
So that one does not run out of proposition symbols when writing complicated statements, they allow infinitely many proposition symbols.
A proof is a finite list of statements.
But then any proof will require finitely many proposition symbols, but there is no upper limit on this finite number.
This shows countably many is enough.
There are languages that allow propositions to be infinite strings.
There is a Wikipedia page on infinitary logic
answered Dec 11 '18 at 13:14
JayJay
2,87311728
answered Dec 11 '18 at 13:14
JayJay
2,87311728
answered Dec 11 '18 at 13:14
JayJay
2,87311728
answered Dec 11 '18 at 13:14
JayJay
2,87311728
2,87311728
$begingroup$
Thank you. I have no doubt that countable will be enough. It was more that starting with a set PROP of propositions I wanted to construct a Boolean algebra having as element equivalence classes on PROP. I disliked the thought that this could only lead to Boolean algebra's having a countable number of elements.
$endgroup$
– drhab
Dec 11 '18 at 13:34
add a comment |
$begingroup$
Thank you. I have no doubt that countable will be enough. It was more that starting with a set PROP of propositions I wanted to construct a Boolean algebra having as element equivalence classes on PROP. I disliked the thought that this could only lead to Boolean algebra's having a countable number of elements.
$endgroup$
– drhab
Dec 11 '18 at 13:34
$begingroup$
Thank you. I have no doubt that countable will be enough. It was more that starting with a set PROP of propositions I wanted to construct a Boolean algebra having as element equivalence classes on PROP. I disliked the thought that this could only lead to Boolean algebra's having a countable number of elements.
$endgroup$
– drhab
Dec 11 '18 at 13:34
$begingroup$
Thank you. I have no doubt that countable will be enough. It was more that starting with a set PROP of propositions I wanted to construct a Boolean algebra having as element equivalence classes on PROP. I disliked the thought that this could only lead to Boolean algebra's having a countable number of elements.
$endgroup$
– drhab
Dec 11 '18 at 13:34
add a comment |
$begingroup$
How exactly is a "proposition symbol" defined in this book?
$endgroup$
– Martin Rosenau
Dec 11 '18 at 12:22
$begingroup$
@MartinRosenau The book starts with a "language" based on an "alphabet" containing 1) proposition symbols 2) connectives 3) auxiliary symbols (brackets and comma). Base on that propositions are introduced and proposition symbols are (together with the symbol $bot$ for "false") the atomic propositions. So I am afraid that "proposition symbol" is a rather primitive notion that is not defined on base of entities that were introduced earlier. So in a way comparable with "sets" in set-theory (they are not defined).
$endgroup$
– drhab
Dec 11 '18 at 12:31
1
$begingroup$
You are right; see e.g. Mendelson's textbook. Proving the Completeness Th for FOL (page 84) there is a Lemma : "The set of expressions of a language $text L$ is denumerable. Hence, the same is true of the set of terms, the set of wfs and the set of closed wfs." At page 113 : "in the notion of first-order language, we allow a noncountable number of predicate letters, function letters, and individual constants, we arrive at the notion of a generalized first-order language." Then the previous result is re-proved using the well-ordering of the set of expressions and transfinite induction.
$endgroup$
– Mauro ALLEGRANZA
Dec 11 '18 at 13:06
$begingroup$
In theory, we could have a language with uncountably many symbols; for example, they could be line segments of length $in (0,,1)$. This probably goes unexplored to ensure every symbol can be unambiguously identified, without the requirement for infinite precision in measurements.
$endgroup$
– J.G.
Dec 11 '18 at 13:15
$begingroup$
@MauroALLEGRANZA Thank you. I found this online and it matches with your quotes.
$endgroup$
– drhab
Dec 11 '18 at 13:23