Axioms

glebovg · **Joined:** Mon, 28 Dec 2009 00:16:28 UTC **Posts:** 228

Suppose we are constructing a proof and we want some integers

and

to satisfy finitely many conditions at once, do we need the axiom of choice, or a special case of the axiom of choice?

outermeasure · **Posted:** Tue, 17 Jul 2012 02:48:52 UTC

glebovg wrote:

Suppose we are constructing a proof and we want some integers

and

to satisfy finitely many conditions at once, do we need the axiom of choice, or a special case of the axiom of choice?

Finite choice is no problem --- just concatenate the choices in a conjunction.

glebovg · **Joined:** Mon, 28 Dec 2009 00:16:28 UTC **Posts:** 228

There are infinitely many integers and we only want particular integers to satisfy finitely many conditions. Are we guaranteed to find such integers without invoking any axioms?

Shadow · **Posted:** Tue, 17 Jul 2012 03:56:34 UTC

glebovg wrote:

There are infinitely many integers and we only want particular integers to satisfy finitely many conditions. Are we guaranteed to find such integers without invoking any axioms?

If you want to verify that two integers satisfy something, you won't need anything, just try and grab pairs and check to see if they work.

glebovg · **Joined:** Mon, 28 Dec 2009 00:16:28 UTC **Posts:** 228

But what if they are arbitrary and I am supposing they satisfy finitely many conditions?

Shadow · **Posted:** Tue, 17 Jul 2012 04:07:04 UTC

glebovg wrote:

But what if they are arbitrary and I am supposing they satisfy finitely many conditions?

In theory the integer axioms tell you what integers are, but that's REALLY PEDANTIC. If you have simple conditions you just list off integer pairs and check them. Unless they're REALLY WEIRD you can probably make a computer do it.

glebovg · **Joined:** Mon, 28 Dec 2009 00:16:28 UTC **Posts:** 228

Let $k,q \in {\mathbb N}$ and suppose

is an arbitrary large integer. What if, for example, we want to choose k>Nq

s.t. $kN|k!, (k-1)N|k!, \ldots, N|k!$ all hold? I cannot use a computer because all integers are arbitrary.

outermeasure · **Posted:** Tue, 17 Jul 2012 04:37:49 UTC

glebovg wrote:

Let $k,q \in {\mathbb N}$ and suppose

is an arbitrary large integer. What if, for example, we want to choose k>Nq

s.t. $kN|k!, (k-1)N|k!, \ldots, N|k!$ all hold? I cannot use a computer because all integers are arbitrary.

If $\mathbb{N}$ exists, then the set
$E_{k,q}=\{k\in\mathbb{N}:(kN\mid k!)\wedge((k-1)N\mid k!)\wedge\cdots\wedge (N\mid k!)\wedge (k>Nq)\}$
exists by axiom scheme of separation (you can write it out in full if you want). No axiom of choice is needed.

On the other hand, to assert $E_{k,q}$ is nonempty, you need to dig into the arithmetics of $\mathbb{N}$ , which again you don't need AC to see that $k=N^{Nq}$ or something like that works.

glebovg · **Joined:** Mon, 28 Dec 2009 00:16:28 UTC **Posts:** 228

Could you briefly explain the axiom schema of separation? I have not studied ZFC.

outermeasure · **Posted:** Tue, 17 Jul 2012 04:48:56 UTC

glebovg wrote:

Could you briefly explain the axiom schema of separation? I have not studied ZFC.

The axiom of separation is the axiom that says (loosely) given a set

and some property $\varphi$ , there exists a set which picks out those elements of

such that $\varphi$ holds $\{x\in A:\varphi(x)\}$ . It is called axiom scheme because in reality the axiom depends on $\varphi$ so this is actually a collection of axioms $\mathrm{Sep}_\varphi$ , one for each $\varphi$ .

Shadow · **Posted:** Tue, 17 Jul 2012 04:51:07 UTC

outermeasure wrote:

glebovg wrote:

Let $k,q \in {\mathbb N}$ and suppose

is an arbitrary large integer. What if, for example, we want to choose k>Nq

s.t. $kN|k!, (k-1)N|k!, \ldots, N|k!$ all hold? I cannot use a computer because all integers are arbitrary.

If $\mathbb{N}$ exists, then the set
$E_{k,q}=\{k\in\mathbb{N}:(kN\mid k!)\wedge((k-1)N\mid k!)\wedge\cdots\wedge (N\mid k!)\wedge (k>Nq)\}$
exists by axiom scheme of separation (you can write it out in full if you want). No axiom of choice is needed.

On the other hand, to assert $E_{k,q}$ is nonempty, you need to dig into the arithmetics of $\mathbb{N}$ , which again you don't need AC to see that $k=N^{Nq}$ or something like that works.

What do you mean? You just need to have it check based on your choice of k and N and q, just put a well-ordering on it and set it off. It may take a while, but if such exist it should find it eventually.

glebovg · **Joined:** Mon, 28 Dec 2009 00:16:28 UTC **Posts:** 228

outermeasure wrote:

glebovg wrote:

Could you briefly explain the axiom schema of separation? I have not studied ZFC.

The axiom of separation is the axiom that says (loosely) given a set

and some property $\varphi$ , there exists a set which picks out those elements of

such that $\varphi$ holds $\{x\in A:\varphi(x)\}$ . It is called axiom scheme because in reality the axiom depends on $\varphi$ so this is actually a collection of axioms $\mathrm{Sep}_\varphi$ , one for each $\varphi$ .

I found a separation theorem in a ZFC book, which pretty much proves the above (using some assumptions). Is that an older formulation of ZFC.

glebovg · **Joined:** Mon, 28 Dec 2009 00:16:28 UTC **Posts:** 228

outermeasure wrote:

glebovg wrote:

Let $k,q \in {\mathbb N}$ and suppose

is an arbitrary large integer. What if, for example, we want to choose k>Nq

s.t. $kN|k!, (k-1)N|k!, \ldots, N|k!$ all hold? I cannot use a computer because all integers are arbitrary.

If $\mathbb{N}$ exists, then the set
$E_{k,q}=\{k\in\mathbb{N}:(kN\mid k!)\wedge((k-1)N\mid k!)\wedge\cdots\wedge (N\mid k!)\wedge (k>Nq)\}$
exists by axiom scheme of separation (you can write it out in full if you want). No axiom of choice is needed.

On the other hand, to assert $E_{k,q}$ is nonempty, you need to dig into the arithmetics of $\mathbb{N}$ , which again you don't need AC to see that $k=N^{Nq}$ or something like that works.

So, how do I show it is nonempty? How do I show something similar in structure is nonempty? Is there a general approach?

S.O.S. Mathematics CyberBoard

Axioms

Who is online