From Vector Spaces to Periodic Functions (2019) | Hacker News Reader

From Vector Spaces to Periodic Functions (2019)

susam.in

59 pointssusam25 comments

Didnt Bona say:"The Axiom of Choice is obviously true, the Well–ordering theorem is obviously false; and who can tell about Zorn's Lemma?"

I thought of this construction:

Let f, the first function have period 1, g the second have period √2.

Define the equivalence relationship that x~y if x = y + a + b√2 for some a and b. Pick for each class a unique representative using the Axiom of Choice. For each representative e, define

f(a+b√2+e) = b√2, g(a+b√2+e) = a + e

By construction, any number can be represented through a unique (a, b, e). And f and g manifestly have the right periods.

Do you mean real x and y, and rational a and b? (Ie, "x~y if x = y + a + b√2 for some [rational] a and b".)

My bad, a and b are integers. That's why the periods work out.

> The axiom of choice is allowed.

Why does this need to be stated explicitly? Why does the axiom of choice not enjoy the privilege of being a first-class axiom like other axioms? Why do many proofs need to state the assumption of this axiom explicitly before using it?

Because it gets you applications like this (or Banach-Tarski), which make you wonder how much it deserves its place. To some extent this is more due to Tertium Non Datur than to the axiom of choice, but my impression is ZF doesn't know enough about infinite sets to get to the really counter-intuitive stuff.

There are counter-intuitive results in ZF without choice too:

- Collection of non-empty sets with empty cartesian product.

- Infinite set without a countable infinite subset.

- There is a pair of sets such that neither is equinumerous with a subset of the other.

More or less, our intuition about seemingly obvious ideas is completely thrown off without choice. Banach-Tarski at least has the property that it probably doesn't directly apply to the real world (if you can split an object into probably physically impossible sets and then rejoin them correctly then you can double the volume of the physical object) and so doesn't really violate our intuition -- the premise doesn't apply in the real world, so no conclusion really matters. It's like claiming that every element of the empty set is a leprechaun with a pot of gold -- it's true, but it doesn't matter in any meaningful sense.

Iiuc your examples are undecidable rather than true in ZF. That's why we can add Axiom of Choice without getting contradictions.

Well, sure. Without choice there exist models of ZF where those properties hold. Adding choice precludes those models -- i.e., it restricts our axioms in a way which prevents certain kinds of unexpected results.

Proofs (at least when they are written "the usual" way) are human-to-human communication, not human-to-machine encoding. A proof depending on AC is a more interesting fact than it depending on, say, the axiom schema of specification, so it makes sense that the author might want to say "hey, pay attention to that".

It is partly historical notoriety. It allows one to prove certain statements that seem counter-intuitive. So proofs that employ it can often be viewed with some skepticism.

Moreover, this axiom is _independent_ of the other axioms in ZFC. It is in fact possible to have entirely self-consistent "worlds" of mathematics, ones where axiom of choice is true, and ones where it is false.

More details and examples of alternate axioms are in the Wikipedia article: https://en.wikipedia.org/wiki/Axiom_of_choice

If it seems weird that math can give you contradictory results, remember that the difference only shows up when you deal with some form of infinity (e.g. when performing an operation on an infinitely large set). For any usage of math in the real world, the truth or falsity of this axiom won't give you contradictory results.

I seem to be missing something. I’m reading this as looking for functions f and g from R to R, such that f(x)+g(x)=1 and f(x+p)=f(x).

If I were reading that correctly, then for any periodic f, g(x)=1-f(x) would do, meaning any old periodic function would do.

What an I missing?

Am I also reading it right that the author is saying the axiom of choice is equivalent to the statement that every vector space has a finite basis? I don’t get how that allows infinite dimensional vector spaces. If not, and it’s just that every vector space has a basis that’s maybe infinite, then what’s the justification of the Hamel basis being finite?

I feel like I’m missing a lot between the lines here.

> What an I missing?

Identity function means that f(x) = x, not f(x) = 1.

Doh. Thanks.

This is where it lost me. Vector spaces can have infinite basis sets.

> Am I also reading it right that the author is saying the axiom of choice is equivalent to the statement that every vector space has a finite basis?

Not quite. The axiom of choice is equivalent to saying every vector space has a Hamel basis, which is to say every element can be represented as a finite combination of elements of the Hamel basis. It doesn't imply that the Hamel basis is finite itself.

That R as a vector space over Q has a finite basis is an amazing fact.

What do you mean? The real vector space defined over the rationals is infinite-dimensional; it can't have a finite basis. I think any basis of R over Q would have to be not only infinite, but uncountably so.

Do you mean that any given vector of the space can be represented using a linear combination of a finite subset of the basis elements with rational scalar coefficients?

You're right, any basis of R over Q has to be uncountably infinite. If a countable basis existed, we could for example write R as the union of the subspaces spanned by the n first basis elements, indexed by n. That would mean R is countable, since a countably-indexed union is countable.

> any basis of R over Q has to be uncountably infinite.

It's actually trivial to give a (infinite but) countable set of (non-orthogonal) basis vectors: 2^i for integer i. 0 and 1 are both rationals (scalars), and every real number has a (possibly infinite) binary expansion, eg e = 10.1011011111100001... = 1·2^1 + 0·2^0 + 1·2^-1 + 0·2^-2 + ...

That's not a basis of R at all. If you want to create a basis of R you better choose irrational elements in your basis, otherwise the Q-span is contained in Q.

What I think you want to say is that "any real number has a binary expansion". Which is true, but the binary sequences don't form a vector space over R, but a Z/2-module. And as a Z/2-module, your { 2^i for integer i } isn't even a basis because you need infinite expansions to express most real numbers. The span of a basis are only the finite linear combinations.

(FWIW, I think you've given a description of the dyadic rationals.)

> any given vector of the space can be represented using a linear combination of a finite subset of the basis elements with rational scalar coefficients?

FWIW, this is definitely false:

x = q₀·√2/1 + q₁·√3/3 + q₂·√5/9 + q₃·√7/27 + q₄·√11/81 + ... = Σᵢ(qᵢ·√πᵢ/3ⁱ)

for rational qᵢ.

Edit: primes approximate e^i, so 2^i isn't large enough.

This isn't false; it's a theorem. Using the axiom of choice, all vectors of any space can be represented as finite linear combinations. In the case of infinite-dimensional vector spaces, this means you would need at most n vectors from the infinite basis B, and n scalars from the underlying field F.

I'm interested in what you're trying to demonstrate with your example though, or if we misunderstand each other, because this theorem is very well established.

έςϧѯ ̑ ͜ ˀ ̑ ѯˀ ...//en.wikipedia.org/wiki/Tensor ...?

Each element is representable as a finite sum of basis elements; this is true of all vector spaces (they all have Hamel bases). However, this does not mean that the basis itself is finite.

Reply on news.ycombinator.com