Mdthbs

Well-ordered Cartesian product in ZF

Why do Martians have to wear space helmets?

Can you create a free-floating MASYU puzzle?

Possibility to correct pitch from digital versions of records with the hole not centered

Wouldn't putting an electronic key inside a small Faraday cage render it completely useless?

My professor has told me he will be the corresponding author. Will it hurt my future career?

Why does mean tend be more stable in different samples than median?

Why is there paternal, for fatherly, fraternal, for brotherly, but no similar word for sons?

Is it acceptable that I plot a time-series figure with years increasing from right to left?

Shipped package arrived - didn't order, possible scam?

What was the significance of Spider-Man: Far From Home being an MCU Phase 3 film instead of a Phase 4 film?

Taking advantage when HR forgets to communicate the rules

How do I check that users don't write down their passwords?

Why do we need a bootloader separate from our application program in microcontrollers?

Bringing coumarin-containing liquor into the USA

Initializing variables in an "if" statement

What do I need to see before Spider-Man: Far From Home?

How to deal with a Murder Hobo Paladin?

Any way to meet code with 40.7% or 40.44% conduit fill?

Gory anime with pink haired girl escaping an asylum

Are "confidant" and "confident" homophones?

As a supervisor, what feedback would you expect from a PhD who quits?

What's the difference between a type and a kind?

Is conquering your neighbors to fight a greater enemy a valid strategy?

Well-ordered Cartesian product in ZF

Transfinite Induction and the Axiom of ChoiceProving properties of enumeration of infinite cardinalsAC iff $P(delta)$ can be well-ordered for all $deltain{bf On}$Prove using transfinite induction that if ordinals $alpha$ and $beta$ are countable, then so is $alpha + beta$.Trying to understand the sum of ordinalsTransfinite induction on class of ordinals.Shrinking a family of sets preserving cardinalityOrdinals and the Von Neumann universeOrdinal addition proof involving $0$Show that ordinal addition is associativeWell-ordered sets are order-isomorphic to a unique ordinal and proof by induction over the ordinals

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}

2

$begingroup$

Can it be proved in ZF that the product $prod_{alpha < kappa} S_alpha$ is nonempty given${ S_alpha }_{alpha < kappa}$ a family of nonempty set and $kappa > 0$ is an ordinal?


It seems possible with transfinite induction, yet I cannot seems to show the limit case holds for the predicate $varphi(alpha) := exists f (f text{ is a choice function for} { S_beta }_{beta < alpha})$

set-theory axiom-of-choice ordinals

share|cite|improve this question

edited 8 hours ago

Asaf Karagila♦

313k3434 gold badges448448 silver badges782782 bronze badges

asked 8 hours ago

Vinh KhangVinh Khang

10677 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I realize that this might be a duplicate of math.stackexchange.com/questions/7065/…, let me know if it is.
  $endgroup$
  – Asaf Karagila♦
  8 hours ago
  

  
  
  
  

add a comment | 

2

$begingroup$

Can it be proved in ZF that the product $prod_{alpha < kappa} S_alpha$ is nonempty given${ S_alpha }_{alpha < kappa}$ a family of nonempty set and $kappa > 0$ is an ordinal?


It seems possible with transfinite induction, yet I cannot seems to show the limit case holds for the predicate $varphi(alpha) := exists f (f text{ is a choice function for} { S_beta }_{beta < alpha})$

set-theory axiom-of-choice ordinals

share|cite|improve this question

edited 8 hours ago

Asaf Karagila♦

313k3434 gold badges448448 silver badges782782 bronze badges

asked 8 hours ago

Vinh KhangVinh Khang

10677 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I realize that this might be a duplicate of math.stackexchange.com/questions/7065/…, let me know if it is.
  $endgroup$
  – Asaf Karagila♦
  8 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

Can it be proved in ZF that the product $prod_{alpha < kappa} S_alpha$ is nonempty given${ S_alpha }_{alpha < kappa}$ a family of nonempty set and $kappa > 0$ is an ordinal?


It seems possible with transfinite induction, yet I cannot seems to show the limit case holds for the predicate $varphi(alpha) := exists f (f text{ is a choice function for} { S_beta }_{beta < alpha})$

set-theory axiom-of-choice ordinals

share|cite|improve this question

edited 8 hours ago

Asaf Karagila♦

313k3434 gold badges448448 silver badges782782 bronze badges

asked 8 hours ago

Vinh KhangVinh Khang

10677 bronze badges

$endgroup$

share|cite|improve this question

edited 8 hours ago

Asaf Karagila♦

313k3434 gold badges448448 silver badges782782 bronze badges

asked 8 hours ago

Vinh KhangVinh Khang

10677 bronze badges

share|cite|improve this question

edited 8 hours ago

Asaf Karagila♦

313k3434 gold badges448448 silver badges782782 bronze badges

asked 8 hours ago

Vinh KhangVinh Khang

10677 bronze badges

edited 8 hours ago

Asaf Karagila♦

313k3434 gold badges448448 silver badges782782 bronze badges

edited 8 hours ago

Asaf Karagila♦

313k3434 gold badges448448 silver badges782782 bronze badges

asked 8 hours ago

Vinh KhangVinh Khang

10677 bronze badges

asked 8 hours ago

Vinh KhangVinh Khang

10677 bronze badges

2 Answers
2

active

oldest

votes

5

$begingroup$

No, of course not. Not even in the case that $kappa=omega$, as that would be exactly countable choice which is known to be unprovable.

Moreover, even if you assume that for any ordinal $kappa$ the product of $kappa$ non-empty sets is non-empty, you still cannot prove the axiom of choice in general. In fact, you cannot even prove that every uncountable cardinal is comparable with $aleph_1$.

share|cite|improve this answer

answered 8 hours ago

Asaf Karagila♦Asaf Karagila

313k3434 gold badges448448 silver badges782782 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Does the principle in your second paragraph have a standard name?
  $endgroup$
  – Alex Kruckman
  2 hours ago
  

  
  
  
  

add a comment | 

3

$begingroup$

The transfinite induction you're probably imagining fails at every limit ordinal.

I suppose you're thinking "then take the union of the functions we have so far", but which of them? Since there are many sequences for each shorter length, in order for "take the union" to work you need to be able to point to just one of each length in a way that fits together -- but that is exactly what $alpha$-choice which you're just trying to prove is for. So this argument actually begs the question.

Even though we think of the induction as a process that happens in sequence, that's not how it works formally. In the induction step for $alpha$ all the induction hypothesis lets you assume is that there exist one or more sequences of every length shorter than $alpha$ -- you don't have a particular selection of them already singled out as "the ones we chose in previous steps". There are no "previous steps", because the induction step in transfinite induction must be proved just once but for an arbitrary $alpha$.

This may be easier to wrap your mind around if you remember how to prove transfinite induction from the fact that ordinals are well-ordered. In this proof you're not actually doing anything step by step -- it's an indirect proof where we say, once and for all, something like this:

Suppose the desired property fails for at least one ordinal. Then bla bla well-ordered bla bla, and therefore there is a smallest $alpha$ that the property fails for. Then apply the induction step just once, for that $alpha$, and conclude that the property doesn't actually fail there after all -- a contradiction.

This proof never applies the induction step to all the ordinals before the supposed first point where the property fails. So we shouldn't assume when we apply it that it "has already run", so to say, for the smaller ordinals. We just know that its conclusion is, somehow, true for each of them independently.

share|cite|improve this answer

edited 8 hours ago

answered 8 hours ago

Henning MakholmHenning Makholm

251k1717 gold badges329329 silver badges572572 bronze badges

$endgroup$

add a comment | 

Your Answer

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3283402%2fwell-ordered-cartesian-product-in-zf%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

5

$begingroup$

No, of course not. Not even in the case that $kappa=omega$, as that would be exactly countable choice which is known to be unprovable.

Moreover, even if you assume that for any ordinal $kappa$ the product of $kappa$ non-empty sets is non-empty, you still cannot prove the axiom of choice in general. In fact, you cannot even prove that every uncountable cardinal is comparable with $aleph_1$.

share|cite|improve this answer

answered 8 hours ago

Asaf Karagila♦Asaf Karagila

313k3434 gold badges448448 silver badges782782 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Does the principle in your second paragraph have a standard name?
  $endgroup$
  – Alex Kruckman
  2 hours ago
  

  
  
  
  

add a comment | 

5

$begingroup$

No, of course not. Not even in the case that $kappa=omega$, as that would be exactly countable choice which is known to be unprovable.

Moreover, even if you assume that for any ordinal $kappa$ the product of $kappa$ non-empty sets is non-empty, you still cannot prove the axiom of choice in general. In fact, you cannot even prove that every uncountable cardinal is comparable with $aleph_1$.

share|cite|improve this answer

answered 8 hours ago

Asaf Karagila♦Asaf Karagila

313k3434 gold badges448448 silver badges782782 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Does the principle in your second paragraph have a standard name?
  $endgroup$
  – Alex Kruckman
  2 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

No, of course not. Not even in the case that $kappa=omega$, as that would be exactly countable choice which is known to be unprovable.

Moreover, even if you assume that for any ordinal $kappa$ the product of $kappa$ non-empty sets is non-empty, you still cannot prove the axiom of choice in general. In fact, you cannot even prove that every uncountable cardinal is comparable with $aleph_1$.

share|cite|improve this answer

answered 8 hours ago

Asaf Karagila♦Asaf Karagila

313k3434 gold badges448448 silver badges782782 bronze badges

$endgroup$

share|cite|improve this answer

answered 8 hours ago

Asaf Karagila♦Asaf Karagila

313k3434 gold badges448448 silver badges782782 bronze badges

answered 8 hours ago

Asaf Karagila♦Asaf Karagila

313k3434 gold badges448448 silver badges782782 bronze badges

answered 8 hours ago

Asaf Karagila♦Asaf Karagila

313k3434 gold badges448448 silver badges782782 bronze badges

3

$begingroup$

The transfinite induction you're probably imagining fails at every limit ordinal.

I suppose you're thinking "then take the union of the functions we have so far", but which of them? Since there are many sequences for each shorter length, in order for "take the union" to work you need to be able to point to just one of each length in a way that fits together -- but that is exactly what $alpha$-choice which you're just trying to prove is for. So this argument actually begs the question.

Even though we think of the induction as a process that happens in sequence, that's not how it works formally. In the induction step for $alpha$ all the induction hypothesis lets you assume is that there exist one or more sequences of every length shorter than $alpha$ -- you don't have a particular selection of them already singled out as "the ones we chose in previous steps". There are no "previous steps", because the induction step in transfinite induction must be proved just once but for an arbitrary $alpha$.

This may be easier to wrap your mind around if you remember how to prove transfinite induction from the fact that ordinals are well-ordered. In this proof you're not actually doing anything step by step -- it's an indirect proof where we say, once and for all, something like this:

Suppose the desired property fails for at least one ordinal. Then bla bla well-ordered bla bla, and therefore there is a smallest $alpha$ that the property fails for. Then apply the induction step just once, for that $alpha$, and conclude that the property doesn't actually fail there after all -- a contradiction.

This proof never applies the induction step to all the ordinals before the supposed first point where the property fails. So we shouldn't assume when we apply it that it "has already run", so to say, for the smaller ordinals. We just know that its conclusion is, somehow, true for each of them independently.

share|cite|improve this answer

edited 8 hours ago

answered 8 hours ago

Henning MakholmHenning Makholm

251k1717 gold badges329329 silver badges572572 bronze badges

$endgroup$

add a comment | 

3

$begingroup$

The transfinite induction you're probably imagining fails at every limit ordinal.

I suppose you're thinking "then take the union of the functions we have so far", but which of them? Since there are many sequences for each shorter length, in order for "take the union" to work you need to be able to point to just one of each length in a way that fits together -- but that is exactly what $alpha$-choice which you're just trying to prove is for. So this argument actually begs the question.

Even though we think of the induction as a process that happens in sequence, that's not how it works formally. In the induction step for $alpha$ all the induction hypothesis lets you assume is that there exist one or more sequences of every length shorter than $alpha$ -- you don't have a particular selection of them already singled out as "the ones we chose in previous steps". There are no "previous steps", because the induction step in transfinite induction must be proved just once but for an arbitrary $alpha$.

This may be easier to wrap your mind around if you remember how to prove transfinite induction from the fact that ordinals are well-ordered. In this proof you're not actually doing anything step by step -- it's an indirect proof where we say, once and for all, something like this:

Suppose the desired property fails for at least one ordinal. Then bla bla well-ordered bla bla, and therefore there is a smallest $alpha$ that the property fails for. Then apply the induction step just once, for that $alpha$, and conclude that the property doesn't actually fail there after all -- a contradiction.

This proof never applies the induction step to all the ordinals before the supposed first point where the property fails. So we shouldn't assume when we apply it that it "has already run", so to say, for the smaller ordinals. We just know that its conclusion is, somehow, true for each of them independently.

share|cite|improve this answer

edited 8 hours ago

answered 8 hours ago

Henning MakholmHenning Makholm

251k1717 gold badges329329 silver badges572572 bronze badges

$endgroup$

add a comment | 

$begingroup$

The transfinite induction you're probably imagining fails at every limit ordinal.

I suppose you're thinking "then take the union of the functions we have so far", but which of them? Since there are many sequences for each shorter length, in order for "take the union" to work you need to be able to point to just one of each length in a way that fits together -- but that is exactly what $alpha$-choice which you're just trying to prove is for. So this argument actually begs the question.

Even though we think of the induction as a process that happens in sequence, that's not how it works formally. In the induction step for $alpha$ all the induction hypothesis lets you assume is that there exist one or more sequences of every length shorter than $alpha$ -- you don't have a particular selection of them already singled out as "the ones we chose in previous steps". There are no "previous steps", because the induction step in transfinite induction must be proved just once but for an arbitrary $alpha$.

This may be easier to wrap your mind around if you remember how to prove transfinite induction from the fact that ordinals are well-ordered. In this proof you're not actually doing anything step by step -- it's an indirect proof where we say, once and for all, something like this:

Suppose the desired property fails for at least one ordinal. Then bla bla well-ordered bla bla, and therefore there is a smallest $alpha$ that the property fails for. Then apply the induction step just once, for that $alpha$, and conclude that the property doesn't actually fail there after all -- a contradiction.

This proof never applies the induction step to all the ordinals before the supposed first point where the property fails. So we shouldn't assume when we apply it that it "has already run", so to say, for the smaller ordinals. We just know that its conclusion is, somehow, true for each of them independently.

share|cite|improve this answer

edited 8 hours ago

answered 8 hours ago

Henning MakholmHenning Makholm

251k1717 gold badges329329 silver badges572572 bronze badges

$endgroup$

share|cite|improve this answer

edited 8 hours ago

answered 8 hours ago

Henning MakholmHenning Makholm

251k1717 gold badges329329 silver badges572572 bronze badges

answered 8 hours ago

Henning MakholmHenning Makholm

251k1717 gold badges329329 silver badges572572 bronze badges

answered 8 hours ago

Henning MakholmHenning Makholm

251k1717 gold badges329329 silver badges572572 bronze badges