5 ms·

I don't think there's any confusion of the finite and infinite numbers in Cantor's diagonalization argument. Here's the most generic form of Cantor's argument:

I don't think there's any confusion of the finite and infinite numbers in Cantor's diagonalization argument. Here's the most generic form of Cantor's argument: there is no surjective function from a set A to its power set P(A). We prove this by contradiction. Consider any function f: A -> P(A) , i.e. it takes elements of A and outputs subsets of A. Suppose this function is surjective: i.e. for all y in P(A) there is some x in A such that f(x) = y. But let q = { a in A | a is not in f(a) }. Clearly this is a valid set. And if f is surjective, there must be some x in A such that f(x) = q. Is x in q? If x were in q, then x would be in f(x), so that's a contradiction. If x were not in q, then by the definition of q x would be in q, which is also a contradiction. Thus we have a contradiction, so f cannot be surjective. As you can see, nowhere do we make any logical jumps that would only make sense in the case of finite sets. This proof is as straightforward as the proof that there is no set of all sets. We don't use the axiom of choice, the argument is even valid in constructive mathematics (though you have to make some adjustments). Now, we define one set X as being "less than" another set Y if and only if there is no surjective function from X to Y. You'll see that this definition corresponds exactly to the usual notions of size for finite sets, and makes intuitive sense (if for every y we have an x, there must be at least as many xs as ys). Now, just plug in the set of natural numbers into Cantor's theorem and you get: the power set of natural numbers is larger than the set of natural numbers.

criloz2 5y ago
If you are counting a set, you necessarily are creating a map between the item of the set you are counting and the natural numbers, this is basics, how come that you can say such statement about the sizes of power set of natural number and natural number?, from where the notion of the cardinality comes if not from counting, and counting implies a map to a natural number, so the set of natural number is bigger than its selves?
- openasocket 5y ago
  Cardinality doesn't have to do with "counting" necessarily. Two sets X and Y are said to have the same cardinality if there is a function f : X -> Y where f is a bijection. By bijection we mean it has two properties: that for all a,b in X, if f(a) = f(b), then a = b (this is also called the injective property), and for all c in Y, there is some d in X such that f(d) = c (this is called the surjective property). Set X has cardinality less than Y if there is no such bijective function, but there is a function f: X -> Y that is injective. Conversely, X has cardinality larger than Y if there is no such bijective function, but there is a function f: X -> Y that is surjective. All you have to do to compare the size of two sets is to look at the functions mapping one to the other. No "counting" involved.
  - criloz2 5y ago
    This make much more sense, so most time the cardinality which people refer is with respect to the set of natural numbers, but according to you, we can have this relation between any two sets. The problem is not make those things clear in the wording. Why not just called it "the cardinality order relation", and try it always like a binary relation, instead of a property that each set has in insolation.
    - mcguire 5y ago
      Typically, unless you specify the other set, it's assumed to be N, the natural numbers. And when you have a bijection between some other set and (some subset of) the natural numbers, you're doing something equivalent to counting.
    - openasocket 5y ago
      Well you can use this relationship to establish the cardinal numbers. You can use "there exists a bijective function between sets X and Y" as an equivalence relation between sets. And with a equivalence relation you can talk about partitioning things into their equivalence classes. But because we are talking about a relationship between all sets it gets tricky to formally construct things (because there is no set of all sets for you to use to define things, so you can't just say "take the sets under the equivalence relations"). There are multiple ways to explicitly construct them, but they tend to be pretty complicated compared to just talking about bijections. The constructions I know about either require the axiom of choice or the axiom of regularity (every non-empty set A contains an element that is disjoint from A). But you don't need any of that to establish a lot of the properties of cardinalities
      - criloz2 5y ago
        It is possible to make a set that contains all the set except itself, operationally this pretty simple, I am working on creating a language programming based on set theory, so this will be an easy way to define some notion of universal set. fn contain(u0:(universal, set), u1:(universal, set)){ return false } fn contain(u:(universal, set), s:set){ return true } but don't how much logical sense it will make
shannifin 5y ago
> You'll see that this definition corresponds exactly to the usual notions of size for finite sets, and makes intuitive sense. This has always been my problem with the idea of some infinities being "bigger" than others. This definition does not correspond to the usual notion of size for finite sets, because finite sets actually have size. So rather than making "intuitive sense", it makes no sense (to me). Having no surjective function from one set to another makes sense, but defining one set necessarily as "less than" the other does not, as the word "less" cannot, in such a context, mean what its definition implies. > (if for every y we have an x, there must be at least as many xs as ys) The lack of a surjective function does not mean that we cannot have an X for every Y, it just means we can't map an X for every Y with a surjective function. It doesn't mean a pairing cannot exist (at least not abstractly, which is how all infinite sets exist anyway). The pairing can simply be random and undefinable. There, now a pairing exists and both sets are the same "size". (It's not a surjective function, but if the point is simply to compare "sizes", then what does it matter?)

criloz2 5y ago

If you are counting a set, you necessarily are creating a map between the item of the set you are counting and the natural numbers, this is basics, how come that you can say such statement about the sizes of power set of natural number and natural number?, from where the notion of the cardinality comes if not from counting, and counting implies a map to a natural number, so the set of natural number is bigger than its selves?

openasocket 5y ago
Cardinality doesn't have to do with "counting" necessarily. Two sets X and Y are said to have the same cardinality if there is a function f : X -> Y where f is a bijection. By bijection we mean it has two properties: that for all a,b in X, if f(a) = f(b), then a = b (this is also called the injective property), and for all c in Y, there is some d in X such that f(d) = c (this is called the surjective property). Set X has cardinality less than Y if there is no such bijective function, but there is a function f: X -> Y that is injective. Conversely, X has cardinality larger than Y if there is no such bijective function, but there is a function f: X -> Y that is surjective. All you have to do to compare the size of two sets is to look at the functions mapping one to the other. No "counting" involved.
- criloz2 5y ago
  This make much more sense, so most time the cardinality which people refer is with respect to the set of natural numbers, but according to you, we can have this relation between any two sets. The problem is not make those things clear in the wording. Why not just called it "the cardinality order relation", and try it always like a binary relation, instead of a property that each set has in insolation.
  - mcguire 5y ago
    Typically, unless you specify the other set, it's assumed to be N, the natural numbers. And when you have a bijection between some other set and (some subset of) the natural numbers, you're doing something equivalent to counting.
  - openasocket 5y ago
    Well you can use this relationship to establish the cardinal numbers. You can use "there exists a bijective function between sets X and Y" as an equivalence relation between sets. And with a equivalence relation you can talk about partitioning things into their equivalence classes. But because we are talking about a relationship between all sets it gets tricky to formally construct things (because there is no set of all sets for you to use to define things, so you can't just say "take the sets under the equivalence relations"). There are multiple ways to explicitly construct them, but they tend to be pretty complicated compared to just talking about bijections. The constructions I know about either require the axiom of choice or the axiom of regularity (every non-empty set A contains an element that is disjoint from A). But you don't need any of that to establish a lot of the properties of cardinalities
    - criloz2 5y ago
      It is possible to make a set that contains all the set except itself, operationally this pretty simple, I am working on creating a language programming based on set theory, so this will be an easy way to define some notion of universal set. fn contain(u0:(universal, set), u1:(universal, set)){ return false } fn contain(u:(universal, set), s:set){ return true } but don't how much logical sense it will make

shannifin 5y ago

> You'll see that this definition corresponds exactly to the usual notions of size for finite sets, and makes intuitive sense. This has always been my problem with the idea of some infinities being "bigger" than others. This definition does not correspond to the usual notion of size for finite sets, because finite sets actually have size. So rather than making "intuitive sense", it makes no sense (to me). Having no surjective function from one set to another makes sense, but defining one set necessarily as "less than" the other does not, as the word "less" cannot, in such a context, mean what its definition implies. > (if for every y we have an x, there must be at least as many xs as ys) The lack of a surjective function does not mean that we cannot have an X for every Y, it just means we can't map an X for every Y with a surjective function. It doesn't mean a pairing cannot exist (at least not abstractly, which is how all infinite sets exist anyway). The pairing can simply be random and undefinable. There, now a pairing exists and both sets are the same "size". (It's not a surjective function, but if the point is simply to compare "sizes", then what does it matter?)