So, proof by induction works in N because there is a clear and defined "next" element...

You're using the bijection to translate your problem to the naturals, you are doing induction on the naturals. This means that the form your induction takes will depend heavily in the bijection you use.

The naturals are defined as the set of numbers upon which induction works.

This is an entirely different form of induction. On the reals you aren't doing induction on individual real numbers, that is frankly impossible. Instead you are using topology techniques to do induction on sets of real numbers. This real induction is also not widely known or used.

There also exist other forms of induction, the most interesting of which is structural induction.

If you agree [math]\mathbb{Q}\cong\mathbb{Z}\times\mathbb{Z}[/math], then all you need is to construct a map [math]\mathbb{Z}\to\mathbb{Z}\times\mathbb{Z}[/math]. I'll present such a map.

First you can see [math]\mathbb{N}\cong\mathbb{Z}[/math] by taking the map [math]f:\mathbb{Z}\to\mathbb{N}[/math] s.t. [math]f(a)=2a,\ f(b)=-2b+1[/math] for [math]a>0,\ b\leq0[/math].

Since [math]\mathbb{Z}[/math] has unique factorization into primes, then any [math]z\in\mathbb{Z}[/math] can be written as [math]z=2^n(2k+1)[/math], where [math]n\in\mathbb{N},\ k\in\mathbb{Z}[/math]. So [math]\mathbb{Z}\cong\mathbb{N}\times\mathbb{Z}\cong\mathbb{Z}\times\mathbb{Z}[/math]. Therefore [math]\mathbb{Z}\times\mathbb{Z}\cong\mathbb{Q}[/math].

This.

Let [math] (A, \rightarrow) [/math] be a reduction system ( which means [math] \rightarrow[/math] is a relation in [math]A[/math], in other words a subset of [math]A \times A[/math].

We say that [math] \rigtharrow[/math] is terminating if, given an element [math]a_0[/math], you cannot build an infinite chain of elements relating to each other starting at [math]a_0[/math] ([math]a_0 \rightarrow a_1 \rigtharrow a_2 \rigtharrow ... \rigtharrow ... [/math])

Now, given a reduction system, we can define (well founded) induction to be the following rule (for any property P on A) :
If, (given x, when all successors of x verify P, then x also verify P), then all x verify P.

Turns out, induction and termination are equivalent.

([math]\rigtharrow[/math] in previous message are obviously [math] \rightarrow[/math])

>This is an entirely different form of induction. On the reals you aren't doing induction on individual real numbers, that is frankly impossible. Instead you are using topology techniques to do induction on sets of real numbers. This real induction is also not widely known or used.
user is obviously talking about transfinite induction, which 1) has absolutely nothing to do with the topology of the reals and 2) absolutely is doing induction on individual real numbers. Assuming choice, transfinite induction works for any set regardless of whether you give it a topology or not.

stop being a faggot

Transfinite induction on the reals requires the axiom of choice. It is therefore pig disgusting and obviously false.

Real induction on linearly ordered sets is superior.
math.uga.edu/~pete/realinduction.pdf

/r/ sauce?

>requires the axiom of choice. It is therefore pig disgusting and obviously false.
Given a family of nonempty sets [math]S_0, S_1, \ldots[/math] indexed by the natural numbers, do you believe it is possible for [math]\prod_{i=0}^\infty S_i[/math] to be empty? If not, congratulations: you just used the axiom of choice.

It is empty. In order to prove otherwise you have to write a sentence of infinite length or give a convoluted argument using garbage like double negation.

Decent bait, but in the future you should try making claims that aren't blatantly false. The product clearly isn't NECESSARILY empty, unless you want to claim that [math](0,0,\ldots) \not\in \prod_{i=0}^\infty \{0,1\}[/math]. The question was whether it is POSSIBLE for the product to be empty. Maybe try bringing up Banach-Tarski or arguments from ontological maximalism next time you want to argue against AC.

Term Rewriting and All That, by Baader and Nipkow

>(0,0,...)
Not math.

Sentences of infinite length aren't legal in formal logic.

Thank you!

>Z
>countable
okay, what's the number of integers then? I'll wait for you to count them all.

It's the age the universe will reach, counted in Planck time.

[math] \aleph_0 [/math]

> Mathematicians are like Frenchmen: whatever you say to them they translate into their own language and forthwith it is something entirely different.
>> Goethe

>implying it makes sense to count Z
>implying it even makes sense to count the even numbers in N

The inductive argument to count the even naturals isn't consistent.

1 -> 2
2 -> 4
3 -> 6
...
x -> 2x

Only a brainlet thinks this is consistent. The largest number on the left is always half the number on the right. Therefore if there are N naturals then there are at least N naturals larger than the largest natural.

>muh bijection
Just admit that you're doing some shady dark magic and you don't give a fuck about consistency
>but the naturals don't have a largest element
Which is why it's stupid to talk about things like "countable infinity" in the first place.

>Which is why it's stupid to talk about things like "countable infinity" in the first place.
Perhaps you should find out what the word "countable" means before trying to argue which things are and are not countable.

The same thing applies to the word "consistent", by the way.

Perhaps you should construct an argument before trying to argue

>spew a bunch of incomprehensible garbage
>"why didn't you address my point????"

What said. An argument with what? There is nothing coherent in , and that guy does not appear to be talking about countability at all.

>"i think this guy is wrong but i don't know why"
>"i should just tell him he doesn't know what words mean"

...

No, seriously -- how do you imagine I could argue with incoherent rambling not related to the concept it tries to talk about?

If I were to give a long explanation about why the cosine root function is not bounded because in fact it can swim underwater just like a fish can, there is not much to argue about besides "what the fuck are you talking about". Arguing individual points only works when the basic concepts involved are being used roughly correctly.

That is not the reason induction works on the naturals. The naturals have an axiom called the well ordered property. Every nonempty subset of the naturals has a least element, 'a' such that a=1, If P(k) is true then P(k+1) is true.

Then P(n) is true for every natural n>=1.

Proof: Let S be the set of naturals such that P is false. Assume there is an element in S. Then S has a least element 'a' because S is a nonempty subset of the naturals. By assertion a=/=1 so a>1. Since a is least, a-1 is not in S, then P(a-1) is true. But by property 2, P(a) must be true. This is a contradiction and thus our assumption that S is nonempty is false. S is empty and P(n) is true for every natural n>=1.

wouldn't the 2*infinity make more sense for integers?

not if there's infinity evens and infinity odds and both are non-overlapping subsets of the naturals

Good try, but (0,0,...) isn't a sentence. It's an alternate way of expressing the sequence [math](a_n)[/math] defined by [math]a_n = 0[/math] for all n. No infinite sentences required.

That "sequence" is actually a function formalized as a set of ordered pairs, using set comprehension. It is different from an element in the set you describe (in case it's not obvious enough, there are no ordered pairs in that set).

More interestingly, consider a set of nonempty sets where at least one set contains only undefinable real numbers. Does a choice function exist?

>That "sequence" is actually a function formalized as a set of ordered pairs, using set comprehension. It is different from an element in the set you describe (in case it's not obvious enough, there are no ordered pairs in that set).
The two are equivalent. How you choose to encode them in set theory is irrelevant.

> More interestingly, consider a set of nonempty sets where at least one set contains only undefinable real numbers. Does a choice function exist?
Obviously. You can prove the existence of choice functions for any finite set without AC, so take one choice function that picks an undefinable real from the one set of undefinables, take another choice function that picks other reals in some way from the other sets, and then combine the two. The presence of undefinable reals changes nothing about the problem.

>The two are equivalent. How you choose to encode them in set theory is irrelevant.

They are not irrelevant when you are arguing technicalities about the axioms of set theory.

>The presence of undefinable reals changes nothing about the problem.
If it's do easy then you should be able to write a choice function over a finite collection of sets that picks out an undefinable real.

>They are not irrelevant when you are arguing technicalities about the axioms of set theory.
No, encoding details are entirely different than the consequences of axioms. In any case, infinite Cartesian products usually are encoded as functions from index sets to the elements of the sets being multiplied, so there isn't actually any difference even in the encoding. (0,0,...) is a collection of ordered pairs when represented in the usual way in ZFC.

>If it's do easy then you should be able to write a choice function over a finite collection of sets that picks out an undefinable real.
You do realize that finite choice is a consequence of ZF alone, and has nothing to do with the axiom of choice?
But if you want a formal proof, you can just use ordinary induction.
Base case: Suppose S is a family containing a single nonempty set [math]S_0[/math] (which may contain whatever strange objects you want). In general a choice function is just a function [math]f: S \to \bigcup S[/math] such that [math]f(T) \in T[/math] for each [math]T \in S[/math]. When S contains only one set, a choice function is merely an ordered pair whose first element is [math]S[/math] and whose second element is any element of [math]S_0[/math]. Given the usual encoding of ordered pairs as {{x},{x,y}}, the existence of such an ordered pair follows from the axiom of pairing. Therefore a choice function exists on any family consisting of a single set.
Inductive hypothesis: Suppose all families of at most n nonempty sets have a choice function. Let S contain n+1 nonempty sets. We can take a choice function on any [math]n[/math] of these sets and append an ordered pair [math](S_{n+1},s)[/math] for some [math]s \in S_{n+1}[/math] to extend the choice function to n+1 sets.
Therefore a choice function exists for all finite sets.

Also note that "definability" is not itself expressible in the language of ZFC. This may be the source of your confusion.

So basically you introduced terminology to trivialize an argument and then walked it back to saying that the terminology makes no difference because we're not using the typical encoding the terminology refers to. Great.

There are models of ZF without undefineable reals. ZF is happy with the obvious claim that the reals are just a countable union of countable sets. Choice is added specifically to create undefinable numbers while simultaneously making it impossible to get your hands on them. It puts you into dumb situations where you choice users have to claim things "obviously exist", fail to give an example, and then fall back to some variant of the "axiom of choice says they exist".

>Also note that "definability" is not itself expressible in the language of ZFC. This may be the source of your confusion.
A set is definable if you can write it in the language of axiomatic set theory. Undefinable sets exist in a model of set theory that lives in your head and allegedly satisfies the axioms of set theory.

This is a nice proof of induction, thx user.

underrated post right here. induction works on any complete ordered set with a minimal element (here "complete" means that every non-empty set which is bounded from below has an infimum). induction on the naturals is equivalent to showing that the set A of all naturals for which P(n) is false has no infimum (for suppose inf(A)=k. then k>1 by (1). on the other hand, since [math] k\in A[/math], we have [math] k-1\in A[/math] by (2), contradicting the assumption inf(A)=k).

the same idea extends in an obvious way to sets like [math] \mathbb{R}_{>=0}[/math]. if you want to show some property holds for all non-negative real numbers, it's enough to show that the set of all numbers for which it does not hold does not have an infimum. whether you want to call this "induction" is up to you, but i always thought of it as the same technique.

NxN is countable because (m, n) can be mapped to (2^m)*(3^n), giving an injection NxN->N. Since Z is countable, there is a bijection ZxZ->NxN, and there is a injection Q->Zx(Z\{0}), p/q mapped to (p, q), so there is an injection Q->ZxZ.

>So basically you introduced terminology to trivialize an argument and then walked it back to saying that the terminology makes no difference because we're not using the typical encoding the terminology refers to. Great.
No. (0,0,...) is identical to the function [math]f: \mathbb{N} \to \{0,1\}[/math] given by f(x) = 0. Unless you want to claim this object does not exist, the Cartesian product is clearly nonempty.

>There are models of ZF without undefineable reals. ZF is happy with the obvious claim that the reals are just a countable union of countable sets.
Even in ZF, the reals are still uncountable. The claim that a countable union of countable sets might be uncountable is nonobvious.

>Choice is added specifically to create undefinable numbers while simultaneously making it impossible to get your hands on them. It puts you into dumb situations where you choice users have to claim things "obviously exist", fail to give an example, and then fall back to some variant of the "axiom of choice says they exist".
This is simply untrue. There are models of ZFC where all reals are definable.

But if Q is equinumerous with N then there exists ordering of Q that is isomorphic to "regular" order of N, and therefore is well order. I don't think existence of well order has anything to do with induction, because well order can be constructed on R and yet there's no way to extend induction to reals.

Transfinite induction, that is induction on well ordered sets, not necessarily naturals, doesn't involve concept of +1

>and yet there's no way to extend induction to reals.
Multiple different methods of induction on the reals have already been mentioned in this very thread, retard.

Functions are formalized as sets of ordered pairs. The function you described contains elements of the form (x,0) where x is a natural. A set containing all such elements is not in the Cartesian product of anything except N×{0}.

>The claim that a countable union of countable sets might be uncountable is nonobvious.
On the contrary, arguing that the union of countable sets is countable requires the axiom of choice. There's simply no intuitive basis upon which to found that believe.

>This is simply untrue. There are models of ZFC where all reals are definable.
Simply not possible. It's a repercussion of an introductory theorem in formal language theory. Let S be a finite alphabet, then the set of words over that alphabet must be countable (you can order them by length and alphabetically). This means that the number of sentences, definitions, theorems, and proofs you can write is countable. It also means that things like ZFC (which is formalized over such a language) have the same constraints. Next take into account that the reals in ZFC are uncountable and you're forced to accept that you're only able to directly describe a countable subset of them (you can indirectly talk about undefinable reals by describing sets containing an uncountable number of reals, unfortunately proving such a set is non empty requires one to either use choice, a convoluted indirect argument involving double negation, or by demonstrating a definable real in the set, ). This proper subset is dubbed the definable reals and the algebraic numbers are a proper subset of them.

In a sense, the undefinable reals only exist in models of ZFC (i.e. your mental picture of ZFC) and we can't really prove things about them.

>A set containing all such elements is not in the Cartesian product of anything except N×{0}.
As I have said previously, this is incorrect. Infinite Cartesian products are usually encoded as the set of functions from an index set to elements of the sets being multiplied. So (0,0,...) is in fact a set of ordered pairs, specifically ordered pairs (x,0) where x is a natural.

>On the contrary, arguing that the union of countable sets is countable requires the axiom of choice. There's simply no intuitive basis upon which to found that believe.
Arguing that arbitrary countable unions are countable requires the axiom of choice. There are specific cases where you can demonstrate the countable union of countable sets is countable, and the intuition is to simply extend this to all sets.

>undefinable real memes
Your reasoning is only valid if the model of ZFC under consideration is a set. It fails for technical reasons if the model is a class. For more info consult this paper: arxiv.org/pdf/1105.4597.pdf

In any case this argument has nothing to do with choice, since set models of ZF also give you undefinable reals. The axiom of choice is literally irrelevant here.

Also note that there are other cases where your "undefinability by uncountability" argument fails. The Loweneim-Skolem theorem guarantees that there are countable models of ZFC. Clearly such a model can only contain countably many sets that encode a real number, so it is entirely possible for each of the [math]\aleph_0[/math] real numbers to be definable in such a model.

>Diagonal_argument.svg.png

>Infinite Cartesian products are usually encoded as the set of functions from an index set to elements of the sets being multiplied.
I don't get it. Are you using a definition of product that's completely different from the categorical notion of a product (i.e. a limit)? Where exactly is this "usually" done? Moreover, even if that were the case it seems like your argument in this respect boils down to "I'm just going to call it a thing that most people consider common sense and hope no one looks to closely at the formalism".

>There are specific cases ... simply extend this to all sets.
I hope your real world intuition isn't this poor. Perhaps I can interest you in pursuing a career in numerology.

>In any case this argument has nothing to do with choice, since set models of ZF also give you undefinable reals. The axiom of choice is literally irrelevant here.
The point is that the axiom of choice claims to give you a choice function that picks out undefinables, not that undefinables exist.

>That paper: If ZFC is consistent...
Ha!

I see you trying to ruse me into the muddy waters of Skolem's Paradox. How rude.

>I don't get it.
How else would you encode (0,0,...) in set theory besides a function from an index set to {0,1}? If you're going to be autistic about the formalism behind the Cartesian product, please at least give your own preferred encoding. Also note that "encoding" and "definition" are not the same thing.

>The point is that the axiom of choice claims to give you a choice function that picks out undefinables, not that undefinables exist.
Yeah, and ZF also gives you such a choice function, provided the family of sets is finite or at least sufficiently well-behaved.

>Ha!
Do you have any particular reason to believe ZFC is inconsistent?

>I see you trying to ruse me into the muddy waters of Skolem's Paradox.
There is no true paradox as long as you understand what you're talking about.

>in set theory
Well, given they choice is false, it would be [math]\emptyset[/math].
provemewrong.jpg

>sufficiently well-behaved
You can't even ask the sort of garbage I asked in ZF.

>Do you have any particular reason to believe ZFC is inconsistent?
Yes, let me show you:
>ZFC
>FC
>C

>There is no true paradox as long as you understand what you're talking about.
Nice try choice-tan but I'm not falling for your first/second order logic argument shifting bait.

>provemewrong.jpg
I already did. (0,0,...) is an element of the Cartesian product in question regardless of whether the axiom of choice holds and regardless of how you choose to encode it. (Protip: encoding it as {} does not mean it doesn't exist. {} exists.)

>You can't even ask the sort of garbage I asked in ZF.
Yes you can, (again) as I have already proven in this thread. It's just that ZF fails to construct an answer for certain families of sets, in a way entirely unrelated to whether the elements of those sets are definable.

>Yes, let me show you:
This entirely fails to answer the question. What reason do you have to believe that the axiom of choice is inconsistent with ZF axioms?

>Nice try choice-tan but I'm not falling for your first/second order logic argument shifting bait.
This has literally nothing to do with second-order logic. Stop bringing up irrelevant bullshit.

>regardless of whether the axiom of choice holds
Sorry, that was poor wording in my part. That is how i encode the product, not the elements in it. The axiom of choice is equivalent to the claim that every infinite product is non-empty. As a result, without AoC the infinite product may be empty which is consistent with my claim that one can't demonstrate an element in said product.

>Yes you can, (again) as I have already proven in this thread.
Proven? Perhaps you're confused. If you can write a provable statement about a set then that set is definable. Such nonsense sets only exist in the realm of informal philosophy.

>This entirely fails to answer the question. What reason do you have to believe that the axiom of choice is inconsistent with ZF axioms?
It's completely bonkers! What reason do you have to believe it's consistent? Are you approaching mathematics like a plebby empirical sciencepleb where you believe everything is true until someone provides evidence that it's false?

>This has literally nothing to do with second-order logic. Stop bringing up irrelevant bullshit.
Okay fine. This is the part where I say that downward lowenheim skolem only applies to first order theories and least upper bound is second order. Thus countable models of reals are just rationals. I await your counter claims on first and second order set theory.

in fact, any set whatsoever has a well-ordering. the issue is that the ordering may be extremely complicated and/or have nothing to do with other structures of the set. the reason induction over N is often viable is that the (well-)ordering on N interacts very nicely with the additive structure. if you construct a well-ordering on Q in the way you described, then you could very well prove something by induction in the same way as over N. the difficulty is that there is no simple formula for the next element of a given rational number with respect to this ordering, making it very impractical to apply the inductive step.

>without AoC the infinite product may be empty
SOME infinite products may be empty. But others are clearly not, for example [math]\prod_{i=0}^\infty \{0,1\}[/math] since (0,0,...) is provably an element of the Cartesian product.

>If you can write a provable statement about a set then that set is definable.
Objectively incorrect. In the theory of linear orders, no real numbers are definable, yet [math]\phi(x) = \forall y \exists z (x < y \to x < z \land z < y)[/math] is a provably true sentence that holds for the real number 0 (and every other real number, for that matter.

>What reason do you have to believe it's consistent?
Mathematicians have been using it for a century without finding an inconsistency, and most agree that it should be accepted as an axiom. Its consequences are more intuitive than the consequences of its negation. I will ask a third time: what reason (besides "lol I don't understand it so it must be crazy xD") is there to assume choice is inconsistent with ZF?

>This is the part where I say that downward lowenheim skolem only applies to first order theories and least upper bound is second order.
But we're not dealing with a theory for real analysis, but a theory for sets. Furthermore it is easy to construct some irrationals like [math]\sqrt{2}[/math] without the least upper bound requirement, so we are clearly not just dealing with the rationals.

Careful, you're going to trigger the ZFC-hater in the thread.