The set of all logical formulae: Countable or uncountable?

[Speakpigeon]

As I see it, the set of all logical formulae could be arranged like a tree with linear branches.

Because of that I also think that the set is commensurate to N.

I don't think any explicit proof is necessary but if anyone can think of why that wouldn't be the case, thanks to explain.

Perhaps, the worry I have in this respect is that branches may be seen as "directions" or as many axes and that, although branches are always short, the number of them definitely tends towards the infinite and rather fast, making the whole thing growing fast somewhere in between countable and uncountable.

Still, I cross fingers and lean towards countable...

Any view on that?
EB

 

[lpetrich]

Logical formulae can be implemented as strings of symbols that are chosen from some finite set. This means that one can use counting arguments on them. Here is what one finds:

• Finite and with some maximum length: finite.
• Finite and arbitrarily long: countably infinite.
• Infinitely long: continuum cardinality.

 

[Speakpigeon]

Logical formulae can be implemented as strings of symbols that are chosen from some finite set. This means that one can use counting arguments on them. Here is what one finds:

• Finite and with some maximum length: finite.
• Finite and arbitrarily long: countably infinite.
• Infinitely long: continuum cardinality.

Ah, yes! Thanks. That's indeed another way to look at it. Looks like that's all is needed to conclude. I guess it's even more than what I asked for. Thanks!
EB

 

[fromderinside]

- 30 -

 

[Kharakov]

Logical formulae can be implemented as strings of symbols that are chosen from some finite set. This means that one can use counting arguments on them. Here is what one finds:

• Finite and with some maximum length: finite.
• Finite and arbitrarily long: countably infinite.
• Infinitely long: continuum cardinality.

Q: Are transcendent functions and transcendent numbers of the "infinitely long" variety? Can you come up with a few cool examples?

 

[lpetrich]

Logical formulae can be implemented as strings of symbols that are chosen from some finite set. This means that one can use counting arguments on them. Here is what one finds:

• Finite and with some maximum length: finite.
• Finite and arbitrarily long: countably infinite.
• Infinitely long: continuum cardinality.

Q: Are transcendent functions and transcendent numbers of the "infinitely long" variety? Can you come up with a few cool examples?

Both of them are indeed "infinitely long".

There are several examples that I can choose, but I'll chose the exponential function:
\( \exp x = \sum_{n=0}^\infty \frac{x^n}{n!} \)
exp(1) = e, the base of the natural logarithms. It is known to be transcendental.

 

[steve_bank]

Given simple and or logic, you can always add more inputs and logic. I'd say it is infinite.

c = a AND B
c = a AND ( b AND c)....

 

[Juma]

As I see it, the set of all logical formulae could be arranged like a tree with linear branches.

Because of that I also think that the set is commensurate to N.

I don't think any explicit proof is necessary but if anyone can think of why that wouldn't be the case, thanks to explain.

Perhaps, the worry I have in this respect is that branches may be seen as "directions" or as many axes and that, although branches are always short, the number of them definitely tends towards the infinite and rather fast, making the whole thing growing fast somewhere in between countable and uncountable.

Still, I cross fingers and lean towards countable...

Any view on that?
EB

You havent defined what a ”logical formula” is.
How do we decide if something is a LF or not?
How do we decide if two LF are equal or different?

 

[Kharakov]

Logical formulae can be implemented as strings of symbols that are chosen from some finite set. This means that one can use counting arguments on them. Here is what one finds:

• Finite and with some maximum length: finite.
• Finite and arbitrarily long: countably infinite.
• Infinitely long: continuum cardinality.

Q: Are transcendent functions and transcendent numbers of the "infinitely long" variety? Can you come up with a few cool examples?

Both of them are indeed "infinitely long".

There are several examples that I can choose, but I'll chose the exponential function:
\( \exp x = \sum_{n=0}^\infty \frac{x^n}{n!} \)
exp(1) = e, the base of the natural logarithms. It is known to be transcendental.

You know, I can express Pi as Pi, and that's only 2 symbols. It's almost infinitely short. Not quite, but almost.

 

[lpetrich]

You know, I can express Pi as Pi, and that's only 2 symbols. It's almost infinitely short. Not quite, but almost.

But that's a label, not a description of it or a way of finding its value.

 

[Kharakov]

You know, I can express Pi as Pi, and that's only 2 symbols. It's almost infinitely short. Not quite, but almost.

But that's a label, not a description of it or a way of finding its value.

Ok, it's the ratio between the circumference and diameter of a circle. Still almost infinitely short, compared to an infinite series.

 

[lpetrich]

You know, I can express Pi as Pi, and that's only 2 symbols. It's almost infinitely short. Not quite, but almost.

But that's a label, not a description of it or a way of finding its value.

Ok, it's the ratio between the circumference and diameter of a circle. Still almost infinitely short, compared to an infinite series.

"Pi" is a label. it is not a way of describing that number.

What you might be trying to get at is that pi is a "computable number". It is one that can be computed to arbitrary accuracy by running a Turing machine some suitable finite number of steps. In other words, using a finite-sized algorithm whose size stays fixed as one goes to higher and higher accuracy, even as it is run for more and more steps.

Computable numbers include all algebraic numbers and most familiar transcendental numbers, like e and pi. Chaitin's family of constants are non-computable, since they are associated with whether or not a Turing machine will halt, and there is no Turing machine that can decide that in the general case.

 Definable real number mentions "Definability in models of ZFC" (set theory with the Zermelo-Fraenkel axioms and the axiom of choice).

A real number a is first-order definable in the language of set theory, without parameters, if there is a formula φ in the language of set theory, with one free variable, such that a is the unique real number such that φ(a) holds (see Kunen 1980, p. 153). This notion cannot be expressed as a formula in the language of set theory.

So I will call such numbers "definable numbers". These numbers include Chaitin's family of constants.

All these sets of numbers are countable, with cardinality aleph-0:

• Positive integers
• Nonnegative integers
• Integers
• Rational numbers
• Algebraic real numbers
• Computable real numbers
• Definable real numbers

Each set contains the sets above it in this list.

There are infinitely more real numbers than any of these kinds of numbers, meaning that nearly all real numbers are forever beyond our grasp. We know that they exist, but we cannot specify any of them with a finite-sized specification.

 

[steve_bank]

Funny how things we routinely use in math without question can become complicated, not a criticism an observation.

I get a sense as to what the debates were like around the time of Pythagoras. Probably heated and energetic.

 

[untermensche]

That is a big problem.

Today a human can go very far very fast in understanding of mathematics and some forget where they came from.

They confuse methods to make use of things with explanations of things.

They confuse carefully constructed scaffolds with naturally occurring organisms.

They are masters at making use of things and dispensing with understanding.

The final answer is what the professional test taker or maker wants.

 

[Jokodo]

That is a big problem.

Today a human can go very far very fast in understanding of mathematics and some forget where they came from.

They confuse methods to make use of things with explanations of things.

They are masters at making use of things and dispensing with understanding.

The final answer is what the professional test taker or maker wants.

That's an oddly contrived way of saying "I don't understand any of this shit and I'm proud of it too".

 

[untermensche]

That is a big problem.

Today a human can go very far very fast in understanding of mathematics and some forget where they came from.

They confuse methods to make use of things with explanations of things.

They are masters at making use of things and dispensing with understanding.

The final answer is what the professional test taker or maker wants.

That's an oddly contrived way of saying "I don't understand any of this shit and I'm proud of it too".

There is NOTHING you could understand that I could not.

But I have a life that requires I devote my study time to other things than basic math.

And from what I see here there really is no reason to do it.

You have nothing to teach me that would be of any utility to me.

Algebra and geometry and trigonometry have a lot of utility however, up to a point. I know these well.

And showing people their philosophical errors is important. Even blind mathematicians.

Saying things like: It is impossible to perform a function to an entity you cannot by definition even approach, like the last digit in an infinite string, is important.

 

[Jokodo]

That is a big problem.

Today a human can go very far very fast in understanding of mathematics and some forget where they came from.

They confuse methods to make use of things with explanations of things.

They are masters at making use of things and dispensing with understanding.

The final answer is what the professional test taker or maker wants.

That's an oddly contrived way of saying "I don't understand any of this shit and I'm proud of it too".

There is NOTHING you could understand that I could not.

But I have a life that requires I devote my study time to other things than basic math.

Sure, feel free to set your priorities as you say fit. If you think you have better things to do than study basic math, that's your call to make. Just don't pollute the discussions other people are having about mathematics with incoherent garbage until you've brought yourself at least up to second grade level.

In return, I promise not to interrupt any discussions about, say environmental protections with repeated yells about how "the sky is purple, not blue!"

 

[Kharakov]

Funny how things we routinely use in math without question can become complicated, not a criticism an observation.

I get a sense as to what the debates were like around the time of Pythagoras. Probably heated and energetic.

Well, maybe. I mean, generally, debates are performed at or near human body temperature, at least as far as I am aware. I might be incorrect about the primary substrate of consciousness, after all.

 

[untermensche]

There is NOTHING you could understand that I could not.

But I have a life that requires I devote my study time to other things than basic math.

Sure, feel free to set your priorities as you say fit. If you think you have better things to do than study basic math, that's your call to make. Just don't pollute the discussions other people are having about mathematics with incoherent garbage until you've brought yourself at least up to second grade level.

In return, I promise not to interrupt any discussions about, say environmental protections with repeated yells about how "the sky is purple, not blue!"

You just don't like being told you are peddling nonsense.

You think you can approach the last digit of an infinite string of digits. You think you can reach it and perform an operation on it.

You have no understanding of an infinite string.

There is no last digit to perform an operation on.

 

[Kharakov]

Ok, it's the ratio between the circumference and diameter of a circle. Still almost infinitely short, compared to an infinite series.

"Pi" is a label. it is not a way of describing that number.

What you might be trying to get at is that pi is a "computable number".

What I'm getting at "pi is a ratio between 2 different lengths, one of which isn't measurable with a non-transcendental, bendy ruler.