• Banno
    23.4k
    Jim, Jeff, Jenny... that's three.

    1 is the proper name for that number; 2 , for the next number. and on it goes. So there are at least countably infinite proper names.

    Suppose I take the set of infinite lists of ones and zeros. I know from Cantor's diagonal that this is uncountable. So I give each its own name; are there then uncountably many proper names?

    First-order predicate logic apparently assumes only a countable number of proper names: a,b,c...

    How would it change if there were an uncountable number of proper names?
  • apokrisis
    6.8k
    An infinite number would be names of infinite length and thus require an infinite time to be actually said. So there’s that problem.
  • TheWillowOfDarkness
    2.1k


    There is an important clarification to make there: it would require infinite moments of stating names.

    Someone could do it, they would just have to be an infinite series of moments of speaking a name. The issue isn't actually requiring infinite time, it's living/being the infinite speaker.
  • andrewk
    2.1k
    If the alphabet is countable and names are required to be finite, then the set of all names is countable. If either of those is not the case, the set of names is uncountable.

    Note - the requirement that names be finite does not mean there has to be an upper limit on the length of a name. With a countable alphabet, there could be names of length n for every integer n, yet the set of names would still be countable as long as no names were infinitely long (or even, as long as there were only countably many infinitely-long names).
  • Banno
    23.4k
    so is there an implicit assumption in first order logic that there are no more than a countable number of constants?
  • Banno
    23.4k
    Or alternately, what happens if we take the number of individuals in an interpretation of first order Predication to be uncountable?
  • andrewk
    2.1k
    Then most of them cannot be referred to individually. Only a countable number of objects can be referred to individually, because there is only a countable number of names (aka 'constant expressions') that can be used to refer to them. They can be referred to as part of a group - like 'all real numbers between 3 and 5' - but not individually.

    My understanding is that it is this feature that caused Thorvald Skolem to question whether the unnamable real numbers really exist. If they don't, then the real numbers are countable.

    Don't ask me what 'exist' means in this context though. I have no idea.
  • apokrisis
    6.8k
    I missed out a few key words. I meant that individual names would have infinite length and so you would have to wait an infinite time to discover whether the reference is to Jim...............my or his brother, Jim............mi.
  • TheWillowOfDarkness
    2.1k


    That's not an issue of the speaker because they are the one taking the action. They're always of the time of their speech.

    It's not technically an issue with regards to knowing either, as someone might realise which name someone is going to say prior to them finishing. I could hear someone say "Jim..." and know they were going to end with "my." This example is also not an infinite naming. An infinite naming would not end in "my" to "mi," it would continue forever, endless sounds being spoken.

    We are only locked out of hearing the end of an infinite naming or naming with ends after our hearing does (as in the case of JIm... my or Jim...mi" ).
  • apokrisis
    6.8k
    That's not an issue of the speaker because they are the one taking the action.TheWillowOfDarkness

    In what sense would they have ever taken the action? The point here is that predication needs to name the name to make some definite claim. Monkey with infinity and you are dealing with ambiguity.
  • andrewk
    2.1k
    individual names would have infinite length and so you would have to wait an infinite time to discover whether the reference is to Jim...............my or his brother, Jim............mi.apokrisis
    One wouldn't have to wait an infinite time for that, if we know that the reference is to one or the other, because two different infinite strings must have a first character that differs, and that first character must be in a finite-numbered position. It's just that one wouldn't know how long one has to wait to see the differing character.

    It would however take an infinite time do indicate exactly which individual one was referring to.
  • Banno
    23.4k
    Only a countable number of objects can be referred to individually, because there is only a countable number of namesandrewk

    That's what I am questioning. Is there an argument in suport of this contention?
  • andrewk
    2.1k
    Yes.
    It is readily proven that for any positive integer n, there is only a countable number of different n-tuples from a countable alphabet. One proves this by constructing a one-to-one map from the positive integers (which are countable) to the set of all such n-tuples.

    It is also readily proven that a countable union of countable sets is countable (it is in fact the proof from the previous paragraph, applied to the case n=2). The set of all finite strings from a countable alphabet is the union, for n going over all positive integers, of the set of all strings of length n, each of which we know is countable from the previous paragraph. This is a countable union of countable sets, and hence countable.
  • Banno
    23.4k
    I can see that. Thanks for articulating it.

    there is only a countable number of different n-tuples from a countable alphabet.andrewk

    What if one used an uncountable alphabet?
  • Banno
    23.4k
    Say we use the alphabet (0,1).

    Say we allow "words" of infinite length.

    Then we know we have an non denumerable number of "words"...
  • TheWillowOfDarkness
    2.1k


    They are the infinite speaker, one who is an endless series of moments speaking this infinite name. There is no ambiguity to this infinity. It's an endless series of moments of speech.

    "Jim..." but without an end, an endless presence of utterances into perpetuity, existing moments of using a sound/letters which never cease.
  • apokrisis
    6.8k
    It would however take an infinite time do indicate exactly which individual one was referring to.andrewk

    Like I said then.
  • apokrisis
    6.8k
    There is no ambiguity to this infinity. It's an endless series of moments of speech.TheWillowOfDarkness

    Studiously missing the point as usual.
  • andrewk
    2.1k
    What if one used an uncountable alphabet?Banno
    Then we could refer to an uncountable number of individuals using sequences of just one letter.

    Whether that entails that we can use it to refer to all the real numbers depends on whether we accept the Continuum Hypothesis. Indeed the continuum hypothesis is precisely the assertion that no uncountable set has a lower cardinality than that of the reals. It can neither be proven nor disproven by ZFC - the foundational axioms of most of mathematics.
  • Banno
    23.4k
    Then we could refer to an uncountable number of individuals...andrewk
    So it seems.

    And my question is, what are the consequences?

    Since ZFC relies on hereditary sets and hence contains no individuals, it doesn't count here.
  • apokrisis
    6.8k
    So you want to commit to the position that 0.999.... and 1 pick out two different proper names here? Cool.
  • apokrisis
    6.8k
    Still don’t get it? My point was about physical limitations on logically inspired notions. An infinite string has the problem it can’t actually be said in less than infinite time.

    You reply by pointing out that this isn’t a problem if strings terminate in finite time. Way to go.
  • Banno
    23.4k
    It would however take an infinite time do indicate exactly which individual one was referring to.andrewk

    I don't understand this bit - what do you mean?
  • Banno
    23.4k
    All I have been able to find so far is the Löwenheim-Skolem Theorem:
    [quote...]if a countable theory has a model, then it has a countable model.[/quote]

    What I am after is, what happens when the model is uncountable?
  • andrewk
    2.1k
    I don't understand this bit - what do you mean?Banno
    It's just that if one were to try to pick out an individual by printing out the decimal places one by one, one would never be finished picking it out, because at any time there would still be an infinite number of decimal places that had not been printed out yet.
    What I am after is, what happens when the model is uncountable?Banno
    An uncountable model of a countable theory will contain uncountably many elements that cannot be individually picked out by any constant term. But the L-S theorem tells us that the model will contain a countable sub-model. A countable submodel of the real numbers, that satisfies all the axioms of the real numbers, can be constructed as follows:

    1. Let N be the natural numbers.

    2. Define map f from the power set of the reals to itself such that, for any subset A of the reals, f(A) is the set of all reals that can be picked out as the unique satisfier of a proposition with a single free variable that only uses symbols from the theory's alphabet and real numbers in A.

    3. Define D to be the transitive closure of N under the operation f, that is:
    D = N ∪ f(N) ∪ f(f(N)) ∪ ........

    Then D is a countable subset of R that satisfies the axioms of the real numbers.

    This is an application of the downward L-S theorem. The upwards L-S theorem says that there are also models at all cardinalities larger than the one we started with. But that is less surprising (to me) because it just involves tipping in lots more unnamable individuals.
  • Banno
    23.4k
    It's just that if one were to try to pick out an individual by printing out the decimal places one by one, one would never be finished picking it out, because at any time there would still be an infinite number of decimal places that had not been printed out yet.andrewk

    OK - I get that.

    It's a side issue.
  • Banno
    23.4k
    An uncountable model of a countable theory will contain uncountably many elements that cannot be individually picked out by any constant term.andrewk

    Perhaps I'm missing something about uncountable sets. Can one set with aleph-1 elements be mapped to another set with aleph-1 elements?

    So could an uncountable number of individuals be mapped to an uncountable number of names?
  • andrewk
    2.1k
    In some cases yes. Whether we can do it in an individual case depends on whether we can specify a mechanism. An unsatisfying mechanism that may always work (I haven't thought through whether it would) for cases where the names and the model have the same uncountable cardinality would be to use the axiom of choice, perhaps together with transfinite induction. But same-cardinality cases that we know would work via a non-AC mechanism are easier to grasp:

    Consider an alphabet made up of symbols, each of which is a square of side length 1cm that is black below a line at height r cm above the base and white above that, where r can be any real number in the interval (0,1). Then the alphabet has the same uncountable cardinality as the real numbers, and a one-to-one map between the symbols and the reals is that which maps the symbol with line height r to the real number tan((r - 0.5) x pi / 2).
bold
italic
underline
strike
code
quote
ulist
image
url
mention
reveal
youtube
tweet
Add a Comment