Tagged Questions
2
votes
1answer
64 views
Can we write every uncountable set $U$ as $V∪W$, where $V$ and $W$ are disjoint uncountable subsets of $U$? [duplicate]
Is it true that for every uncountable set $U$, we can write $U=V∪W$, where $V$ and $W$ are disjoint uncountable subsets of $U$ ?
5
votes
2answers
127 views
The Axiom of Choice and definability
I've seen a lot of relations between the notion of the existence of a definable set with a given property and the necessity of AC is proving that there is a set with the property. For example:
Under ...
4
votes
2answers
46 views
Does the existence of this quotient set depend on the Axiom of Choice?
We know the familiar equivalent relation on $\mathbb{R}$, which is
$$
x\sim y\Leftrightarrow x-y\in\mathbb{Q}
$$
After quoting this relation, we have the quotient set
$$
\mathbb{R}/_\sim = \{x + ...
4
votes
4answers
112 views
Do we always use the Axiom of Choice when picking from uncountable number of sets?
I know there are uncountable number of equivalence classes defined by the relation defined here: Equivalence classes of "$x \sim y \Longleftrightarrow x -y $ is rational". (the relation is ...
3
votes
3answers
83 views
Equivalence with the axiom of choice
This is a problem from Tao's Analysis I.
We are asked to show that the axiom of choice is equivalent to the statement that for any sets $A$ and $B$ for which a surjection $g:B\to A$ exists, an ...
2
votes
4answers
73 views
Cardinals of set operations without AC
Given info: $|A|=\mathfrak{c}$ , $|B|=\aleph_0$ in ZF (no axiom of choice).
Prove: $|A\cup B|=\mathfrak{c}$
If $B \subset A\implies|A \backslash B|=\mathfrak{c}$?
I have found several places ...
3
votes
2answers
96 views
Wellordering vs. Zorn's lemma
Many mathematicians outside mathematical logic dislike wellorderings, ordinals and corresponding transfinite arguments. They use zorn's lemma instead and claim one does not need ordinals at all. ...
3
votes
2answers
71 views
Second-countable implies separable/Axiom countable choice
Let $(X,\mathscr T)$ be a topological space, and $(B_n)_{n\ge1}$ a countable basis for X. Under this assumptions, X is separable.
The proof of this assertion is as follows:
We can assume without ...
4
votes
2answers
72 views
Existence of an injection from $\Bbb N$ without the axiom of choice
If you have a set $A$, and it satisfies that for some $x\in A$, there is a bijection between $A$ and $A\setminus\{x\}$.
Does that imply that there is an injection from $\Bbb N$ to $A$?
It is clearly ...
3
votes
2answers
110 views
Choice function for a collection of nonempty subsets of $\{0,1\}^\omega$ [duplicate]
Possible Duplicate:
Finding a choice function without the choice axiom
Is possible to construct a Choice function for a collection of nonempty subsets of $X=\{0,1\}^\omega$? (Without AC)
...
3
votes
2answers
76 views
Is it correct, or legitimate to write $P(\prod_{i \in I}{X_i}) = \prod_{i \in I}{P(X_i)}$?
I'm trying to formulate Axiom of Choice in terms of $P(\prod_{i \in I}{X_i})$, but end up with the following questions.
Let $P(X)$ be the power set of $X$.In general, is it correct, or legitimate to ...
3
votes
3answers
316 views
Infinite set as union of disjoint countable sets.
Question:
Prove, with the help of Zorn's lemma, that infinite set, $X$ can be represented union of disjoint countable sets.
My attempt:
I know that a countable union of countable sets must be ...
3
votes
2answers
67 views
Proving Dedekind finite implies finite assuming countable choice
I'd like to show that if a set $X$ is Dedekind finite then is is finite if we assume $(AC)_{\aleph_0}$. As set $X$ is called Dedekind finite if the following equivalent conditions are satisfied: (a) ...
3
votes
0answers
39 views
Follow up on “Proof of $X \times X \hookrightarrow X$ implies $[X]^2 \hookrightarrow X$”
This is a follow up on this earlier question of mine.
We have the following statements:
(HSO) For every infinite set $X$ there exists an injection $f: X \times X \hookrightarrow X$
(HSU) For every ...
3
votes
2answers
344 views
Countable unions of countable sets
It seems the axiom of choice is needed to prove, over ZF set theory, that a countable union of countable sets is countable.
Suppose we don't assume any form of choice, and stick to ZF. What are the ...
2
votes
1answer
71 views
Is $\kappa^\lambda=2^\lambda$($2 \le \kappa<\lambda$,$\lambda$ infinite) valid in set models of ZF?
Let $2 \le \kappa<\lambda$(both cardinal numbers), in which $\lambda$ is infinite. Then these formula as follows hold where in ZFC:
$\lambda+\kappa=\lambda$
$\lambda\cdot\kappa=\lambda$
...
1
vote
1answer
44 views
$A+\alpha\sim A$ when $\omega\le\alpha<h(A)$
I have been considering about $A+\alpha\sim A$ when $\omega\le\alpha<h(A)$, in which $h(A)$ is the Hartogs number of $A$.
If there is $\alpha$ s.t. $\omega\le\alpha<h(A)$, we can get $\alpha ...
1
vote
2answers
79 views
Is there any Dedekind-infinite set can be split to two smaller Dedekind-infinite sets?
I have been considering about $A+\alpha\sim A$ when $\omega\le\alpha<h(A)$, in which $h(A)$ is the Hartogs number of $A$.
If there is $\alpha$ s.t. $\omega\le\alpha<h(A)$, we can get $\alpha ...
3
votes
1answer
112 views
Proof of $X \times X \hookrightarrow X$ implies $[X]^2 \hookrightarrow X$
Consider the following two statements (where $[X]^2$ denotes the set of all unordered two-element subsets of $X$):
(HSO) For every infinite set $X$ there exists an injection $f: X \times X ...
3
votes
3answers
66 views
Proving equivalences of statements equivalent to AC
I'm doing the following exercise from Just/Weese:
Show in ZF that (WO) implies (IC) and that (IC) implies (SC).
where
(WO) Every set can be well-ordered.
(IC) For any two sets $X,Y$ either there ...
4
votes
2answers
82 views
Why is AC needed for $|\bigcup X_i|=|\bigcup Y_i|$, $\forall i$ $|X_i|=|Y_i|$, $\{X_i\}_{ i\in I}$, $\{Y_i\}_{i\in I}$ pairwise disjoint?
On Page 60, Set Theory, Jech(2006),
5.9 If $\{X_i : i \in I\}$ and $\{Y_i : i \in I\}$ are two disjoint families such that $|X_i| = |Y_i|$ for each $i \in I$, then $|\cup_{i \in I}X_i| = |\cup_{i ...
6
votes
3answers
103 views
Statement not provable from ZF
I'm doing the following exercise from Just/Weese:
Some thoughts: To show that the statement is not provable from $ZF$ I could either show that it implies the axiom of choice or Tychonoff or I could ...
3
votes
2answers
65 views
Using a choice function to find an inverse for $F\colon A\to P(B)$
Let $A$ and $B$ be arbitrary non-empty sets and let $F\colon A\to P(B)$, be an arbitrary function which covers $B$ in the sense that $\forall b \in B$, $\exists a \in A$ such that $b \in F(a)$ holds.
...
4
votes
1answer
81 views
Is $\aleph_0$ the minimum infinite cardinal number in $ZF$?
$\aleph_0$ is the least infinite cardinal number in ZFC. However, without AC, not every set is well-ordered.
So is it consistent that a set is infinite but not $\ge \aleph_0$? In other words, is it ...
1
vote
1answer
65 views
Confused about why “disjointifying” implies “AC”
Assume I have the following
(DIS) For every indexed family $\{A_i : i \in I \}$ there exists a family $\{B_i : i \in I \}$ of pairwise disjoint sets such that $B_i \subset A_i$ for all $i \in I$ and ...
3
votes
1answer
32 views
Making a choice function if $A_i$ are well-ordered for each $i$
Let $A_i$ be a family of sets such that each $A_i$ is well-ordered. Let $\varphi(x,S,W)$ be the formula $$ \forall z ( (z,x) \in W \rightarrow z \notin S)$$
where $W$ is the well-order on $S$. Then ...
1
vote
4answers
121 views
Which kind product of non-zero number non-zero cardinal numbers yields zero?
Let $I$ be a non-empty set. $\kappa_i$ is non-zero cardinal number for all $i \in I$.
If without AC, then $\prod_{i \in I}\kappa_i=0$ seems can be true(despite I still cannot believe it).
But what ...
0
votes
1answer
103 views
Does Axiom of Choice naturally hold?
Let $A$ be a set of non-empty sets, then $\bigcup A$ is a set. Furthermore, $(\bigcup A)^{A}$ is a non-empty set. Besides let $P$ be a binary predicate such that for all $X\in A$ there is a unique $x ...
2
votes
2answers
104 views
Possible inaccuracy in Wikipedia article about initial ordinals
I quote from the Wikipedia article:
"So (assuming the axiom of choice) we identify $\omega_\alpha$ with $\aleph_\alpha$, except that the notation $\aleph_\alpha$ is used for writing cardinals, and ...
4
votes
3answers
296 views
How to define a well-order on $\mathbb R$?
I would like to define a well-order on $\mathbb R$. My first thought was, of course, to use $\leq$. Unfortunately, the result isn't well-founded, since $(-\infty,0)$ is an example of a subset that ...
14
votes
5answers
892 views
Importance of Axiom of Choice
First a quick question regarding the definition of the axiom of choice. Do the sets have to be mutually disjoint nonempty sets or just non-empty? One source states: "For any set X of nonempty sets, ...
2
votes
2answers
525 views
Finding an inverse injection for a surjection
Question:
Let $X$ and $Y$ be sets, and let $f\colon X\to Y$ be a surjection.
Prove that there is an injection $g\colon Y\to X$ such that $f(g(y)) = y$ for
every $y\in Y$.
I do not have an idea how ...
3
votes
3answers
216 views
Which set is unwell-orderable?
In textbook it says that every well-orderable set is equipotent to an initial ordinal number. However, of course unwell-orderable cannot equipotent to any ordinal number, but is there any set is ...
5
votes
1answer
127 views
Axiom of choice question
I recently read a proof that had the following in it: "since $A$ is non-empty, we can find an element $x$ in $A$." This proof did not mention the axiom of choice, but it seems to me that it would be ...
2
votes
2answers
140 views
Why would the axiom of choice be needed if ordinals are well-ordered without AC?
Will ordinals be well-ordered without AC? This seems to be obviously true, as they are by definition well-ordered.
Why would we then need the axiom of choice. We can just form a bijection function to ...
2
votes
3answers
247 views
Finding a choice function without the choice axiom
Is there a way to define a choice function on the set of subsets of $\{0,1\}\times\{0,1\}\times\ldots = \prod_{n \in \mathbb N} \{0,1\}$ in ZF? I know that $\prod_{n \in \mathbb N} \{0,1\}$ is ...
4
votes
2answers
603 views
Is there a Cantor-Schroder-Bernstein statement about surjective maps?
Let $A,B$ be two sets. The Cantor-Schroder-Bernstein states that if there is an injection $f\colon A\to B$ and an injection $g\colon B\to A$, then there exists a bijection $h\colon A\to B$.
I was ...
3
votes
1answer
85 views
Finite family of infinite sets / A.C.
Let $\{A_i\mid i\in n\}$ be a finite family of infinite sets. ( That is, $A_i$ is infinite for every $i\in n$ and $n\in \mathbb{N}$)
Here, we can choose representative $a_i$ from each $A_i$ and ...
0
votes
1answer
88 views
Existence statement and Axiom of Choice
Let $I$ be an infinite set.
Suppose that for every $i\in I$, there exists a set $S_i$ satisfies a statement $\psi(S_i)$.
Here, is constructing a family of such $S_i$ (i.e. $\{S_i\}$ for $i\in I$) ...
0
votes
2answers
108 views
Why is choosing elements in equivalence classes not a choice?
This is Asaf's answer from this link:
How do we know an $ \aleph_1 $ exists at all?
I don't understand this sentence that is;
From each equivalence class choose the representative which is an ...
2
votes
1answer
174 views
Countable union of countable sets(ZF)
Let ${{E_n}}_{n\in \mathbb{N}}$ be a sequence
such that every $E_n$ is countable.
Let $g_n : \mathbb{N} \to E_n$ be a bijection for every $n\in \mathbb{N}$.
Let $\alpha (n,k) = g_n(k)$
Let $A$ be ...
1
vote
2answers
211 views
Non-aleph infinite cardinals
I'm now confused with a concept of $\aleph$.
1.$\aleph$ is a cardinal number that is well-ordered in ZF.(Defined as an initial ordinal that is equipotent with). Does that mean $\aleph_x$ in ZF may ...
2
votes
2answers
238 views
Cardinality of the complex numbers in ZF
As you all know, cardinality of $\mathbb{R} = 2^{\aleph_0}$ can be proved in ZF, since cardinality of $\mathbb{N} \times \mathbb{N} = \aleph_0$ can be proved in ZF.
I know that the statement 'For any ...
1
vote
3answers
272 views
A way to well-order real line
How is well-ordering in real line possible?
I know that the axiom of choice provides possible well-ordering, but intuitively, this does not seem to make sense.
How can you compare 1.111111.... and ...
-4
votes
2answers
687 views
Is there a well-ordering of the reals , measurable or not?
I just stumbled on these two claims:
"Nice" well-orderings of the reals
and, in the answer, no well-ordering of the reals is Lebesgue measurable.
And I am surprised. Is there a ...
2
votes
2answers
252 views
Tukey's lemma by axiom of choice
How can i prove Tukey's lemma directly from axiom of choice?
Tukey' lemma : every nonempty collection of finite character has a maximal element with respect to inclusion.
Help
9
votes
5answers
273 views
Prove that every set with more than one element has a permutation without fixed points
I cannot prove this statement so need help.
This problem is one of exercises right after the chapter about Hausdorff's maximal principle and Zorn's Lemma. Thus, you cannot use the concept of cardinal ...
5
votes
2answers
347 views
Why don't you need the Axiom of Choice when constructing the “inverse” of an injection?
Suppose $f:X\rightarrow Y$ is a surjection and you want to show that there exists $g:Y\rightarrow X$ s.t. $f\circ g=\mathrm{id}_Y$. You need the AC to show this.
However, suppose $f$ is a injection ...
5
votes
1answer
276 views
The Axiom of Choice and the Cartesian Product.
I understand that the axiom of choice, given the axioms of ZF set theory, is equivalent to the statement that "the Cartesian product of any family of nonempty sets is nonempty." I've been unable to ...
1
vote
1answer
173 views
Ordering countable subsets of $[0,1]$
I've been trying to find a way to consistently generate bijections between $\mathbb{N}$ and countable sets of Real numbers in $[0,1]$. Given any such set, by definition there is a bijection to the ...
