Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [cardinals]

This tag is for questions about cardinals and related topics such as cardinal arithmetics, regular cardinals and cofinality. Do not confuse with [large-cardinals] which is a technical concept about strong axioms of infinity.

0
votes
1answer
64 views

Examples of Commutative Semigroups Where the Cardinality of the Carrier Set is Greater Than $\mathfrak c$.

Given: A set $M$. A binary operation $+$ defined on $M$ $+: M \times M \to M$ $\text{ that is both associative and commutative.}$ satisfying the following properties: P-1: $\text{For every } x,y,z \...
1
vote
2answers
70 views

Proving $A\subset B\implies |A|\leq |B|$

I would like to prove the following: Let $A,B\subset\mathbb{R}$ be non-empty finite sets. Prove that if $A\subset B$, then $|A|\leq |B|$. We are also given the following theorem: Theorem $1....
2
votes
2answers
61 views

Injection from cardinal $\lambda$ to cardinal $\kappa$ implies $\lambda\leq\kappa$

I'm trying to prove that if there is an injection $f:\lambda\to\kappa$ (for $\lambda$,$\kappa$ cardinal numbers) then $\lambda\leq\kappa$. This is not true if they are just ordinal numbers, for ...
1
vote
1answer
30 views

Let $\mathfrak F$ be the set of injective mappings $f:\Bbb N\to\Bbb N$. Then $|\mathfrak F|=2^{\aleph_0}$

Let $\mathfrak F$ be the set of injective mappings $f:\Bbb N\to\Bbb N$. Then $|\mathfrak F|=2^{\aleph_0}$. This is an alternative proof to one in my textbook. Does it look fine or contain flaws? ...
1
vote
1answer
80 views

Suppose that $\aleph_0\le |A|<|B|$. Compare $|\mathcal {P}(A)|$ and $|\mathcal {P}(B)|$, $|A^B|$ and $|B^A|$, $|B^A|$ and $|B|$

Suppose that $\aleph_0\le |A|<|B|$. Compare below cardinalities. $|\mathcal {P}(A)|$ and $|\mathcal {P}(B)|$ $|A^B|$ and $|B^A|$ $|B^A|$ and $|B|$ My attempt: From $|A|<|B|$, I ...
2
votes
1answer
65 views

Question about Hungerford's definition about cardinality

In Hungerford's Algebra, he firstly defines that equipollent is a relation between two sets $A$, $B$ if there exists bijective $f:A\rightarrow B$, then proves Equipollence is an equivalence ...
0
votes
1answer
76 views

Let $X,Y,Z$ be nonempty sets. Then $|(X^Y)^Z|=|X^{Y\times Z}|$

Let $X,Y,Z$ be nonempty sets. Then $\left |\left(X^Y\right)^Z\right|=\left|X^{Y\times Z}\right|$. Please help me verify this proof! Thank you so much! My attempt: We define a mapping $F$ that ...
1
vote
0answers
53 views

The set of sequences of $\Bbb N$ and $\mathcal{P} (\Bbb N)$ are equinumerous.

The set of sequences of $\Bbb N$ and $\mathcal{P} (\Bbb N)$ are equinumerous. My attempt: Let $S,S_1,S_2$ be the sets of sequences, finite sequences, and infinite sequences of $\Bbb N$ respectively....
1
vote
2answers
65 views

Cardinality of $\{0,1\}^\mathbb{N}$

For if I understand this correctly, given any two sets X and Y, $card(X^Y)=cardX^{cardY}.$ However, from what I read, $\{0,1\}^{\Bbb N}$ is supposedly countable. It is also said that $2^{\aleph_0}>\...
1
vote
2answers
70 views

Without the Axiom of Choice, must two nonempty sets have a surjection between them? [duplicate]

Let $A$ and $B$ be two nonempty sets. Can we show, without using the Axiom of Choice, that there must either be a surjection $A\to B$ or $B\to A$? With Choice we can do this by using Zorn to obtain a ...
2
votes
1answer
39 views

Regular cardinal for a fixpoint of the exponential

Let $\lambda$ be a fixed regular cardinal. I would need (for a proof) to find a regular cardinal $\mu>\lambda$ such that $\mu^\lambda=\mu$. What I can understand is that the mapping $\mu\mapsto \...
0
votes
1answer
18 views

Set Representation with tabular form, the number of elements

In set theory, the order in which elements are listed is immaterial but elements must not be repeated. So {1, 1} is not permitted. Then the number of elements in set {1,a} (a is real number) is 1 or ...
7
votes
1answer
111 views

What is the cardinality of the set of equivalence classes of countable order types under bi-embeddability?

Two ordered sets have the same order type if there exists an order isomorphism between them. Now the set $X$ of all order types of countable totally ordered sets has cardinality $2^{\aleph_0}$; see ...
3
votes
2answers
70 views

Why does $1^{\aleph_0}=1$ but $\aleph_0^{\aleph_0}\neq\aleph_0$?

Note: $k$ is finite number. $1\cdot 1=1$ $1^k=\underbrace{1\cdot1\dots1}_{k}=1$ $1^{\aleph_0}=\underbrace{1\cdot1\dots1}_{\aleph_0}=1$ $\aleph_0\cdot\aleph_0=\aleph_0$ $\aleph_0^k=\underbrace{\...
1
vote
1answer
70 views

Does the Continuum hypothesis say anything about the cardinality of the set $3^{{\aleph}_0}$?

I thought of this amazing method which produces a set of cardinality $3^n$ from a set of cardinality $n$: If we take a set S of cardinality $n$ and produce ordered pairs of the form (A,B), where A ...
2
votes
1answer
64 views

Strange Cardinal Notation

Is anybody aware of any references which may justify this notation? $$ \LARGE \aleph^{\aleph^{\aleph\dots}_{\aleph\dots}}_{\aleph^{\aleph\dots}_{\aleph\dots}} $$ In particular, using Cardinals for ...
0
votes
1answer
62 views

Cardinality of finite sets in first order set theory

How would one determine if two finite sets have the same cardinality using first order set theory? Would there be a formula for showing that $$ F(x,y) \iff |x|=|y|?$$
0
votes
1answer
44 views

Is there a standard notation for an ordinal number with cardinality of the continuum?

Under ZFC, the real numbers can be well-ordered. So, there is some ordinal number whose cardinality is that of the continuum. Is there a standard notation for this number? For example, the first ...
0
votes
1answer
28 views

Existence of a funcion $T: [2^{\kappa}]^2 \rightarrow \kappa$, containing all partial functions $f$ with $|$dom$(f)| = \kappa$

Let $\kappa$ be a cardinal. I want to prove that there is a function $T: [2^{\kappa}]^2 \rightarrow \kappa$ with the following property ($[2^{\kappa}]^2$ being the subsets of $2^{\kappa}$ that have 2 ...
2
votes
0answers
62 views

Hypertask, Arithmetical hierarchy and beyond

Good day, I would love to ask this question. Lets have a hypercomputer capable of doing a hypertask, that is performing uncountably many computational steps in finite time(the same amount of steps ...
1
vote
0answers
46 views

Is there a good notion of hypercomputation which allows inaccessible-length computations?

Good day, I would like to ask, whether a good notion of hypercomputation which allows inaccessible-length computations exists. I am familiar with a notion of supertask, which is a countably many ...
1
vote
0answers
103 views

$\vert \mathbb{R}^{\mathbb{Z}} \vert = \vert \mathbb{R} \vert $? [duplicate]

I want to show that $\vert \mathbb{R}^{\mathbb{Z}} \vert = \vert \mathbb{R} \vert $. Do the real numbers and the countable product of real numbers have the same cardinality?
0
votes
1answer
28 views

Given any set $X$ and any $A,B\subseteq X$, is true that for every bijection $f:A\to B$ there exists $\phi\in\text{Sym}(X)$ such that $f={\phi|}_A$?

Given any (not necessarily finite) set $X$ as well as arbitrary $A,B\subseteq X$, can we always find for every bijection $f:A\to B$ a permutation $\phi\in\text{Sym}(X)$ such that $f={\phi|}_A$ (the ...
0
votes
2answers
31 views

Given any (not necessarily finite) set $X$ as well as arbitrary $A,B\subseteq X$ is it true that $|A|=|B|\implies |X\setminus A|=|X\setminus B|$?

Given any (not necessarily finite) set $X$ as well as arbitrary subsets $A\subseteq X$ and $B\subseteq X$ if we know there exists a bijection $f:A\to B$ does this imply there exists a bijection $g:X\...
0
votes
1answer
43 views

Cardinality of sets ($\aleph_0$, distinct elements)

Which answers are correct? $| \{1000, 1001 \}| = 2$: True. $| \{1, 2, 2, 3 \}| = 4$: False. There are only $3$ distinct elements. The cardinality of $\mathbb{N} \times \mathbb{Z}$ is $\aleph_0$: I'd ...
2
votes
1answer
45 views

If $\kappa$ is infinite and $\kappa$ is not a sum of $<\kappa$ cardinals each less than $\kappa$, then $\kappa$ is regular.

An infinite cardinal $\kappa$ is regular if $\mathrm{cf}(\kappa) = \kappa$. It is known that if $\kappa$ is regular, then for any family $(\kappa_i)_{i \in I}$ of cardinals $\kappa_i < \kappa$ ...
0
votes
1answer
49 views

What order of infinity is the set of vectors whose components sum to $0$?

I was wondering this question today, but I don't really have the machinery to answer it, and I'm not sure how to search for such an answer. Here's the set up of the problem: What is the order of ...
2
votes
3answers
81 views

Does any uncountable subset of $\mathbb{R^n}$ have the same cardinality as $\mathbb{R}^m$?

We can map $[0,1]$ to $\mathbb{R}$ (in fact any closed interval of $\mathbb{R}$, there's nothing special about $[0, 1]$) bijectively, but is the same true for $[0,1]\times[0,1] \times[0,1]$ and $\...
0
votes
0answers
24 views

If $X$ is a finite set and $Y \subset X$ then $Y$ is finite. Moreover, $|Y| \le |X|$ [duplicate]

If $X$ is a finite set and $Y \subset X$ then $Y$ is finite. Moreover, $|Y| \le |X|$ I assumed $X=\{x_0,x_1,x_2,\ldots,x_{n-1}\}$ and made a one-to-one sequence $<x_0,x_1,x_2,\ldots,x_{n-1}>$ ...
2
votes
3answers
130 views

Cardinal of a finite set is unique

I have been thinking about how I can prove whether a cardinal of a finite set is unique, after some thoughts I figured out it would be better to prove it in such a way, If $n \in \mathbb{N}$, then ...
1
vote
1answer
195 views

Could Hypercomputer solve undecidable problems? [closed]

firstly lets assume that a human brain is no more powerfull then a Turing Machine. A question that I would like to ask is whether a hypercomputer capable of doing uncountably many computational steps ...
1
vote
1answer
57 views

Why is the $\aleph$ hierarchy a discrete hierarchy? [duplicate]

The $\aleph$ hierarchy, I think, is a sequence of infinite cardinals. $\aleph_0$ is $|\mathbb{N}|$, possibly by definition. $\aleph_1$ is the next highest cardinal. A lot has been written about ...
8
votes
1answer
184 views

Where can I find a proof of ($\aleph_1 \leq 2^{\aleph_0}$ is independent of ZF)?

In "A tutorial on countable ordinals" [1], in page 25, Forster uses the fact that $\aleph_1 \leq 2^{\aleph_0}$ is independent of ZF to prove that there is no definable family of fundamental sequences ...
0
votes
2answers
57 views

If $A^X$ is equipotent to $B^X$ does it imply that A is equipotent to B?

I was able to prove the converse of this statement to be true.However, I have some doubt whether the statement above is true. If true please provide a rigorous proof and if false please provide a ...
1
vote
1answer
58 views

Question on $[\mathbb{N}]^{\omega}$

I'm reading Fremlin's article about $\mathfrak{p} = \mathfrak{t}$, and in 4B proposition, he shows that $\Vdash_{\mathbb{P}}\,\mathcal{P}(\mathbb{N}) = \mathcal{P}(\mathbb{N})\check{}$, where $\mathbb{...
1
vote
1answer
69 views

ZF with “double powersets”, is there a set with the same size as ℝ?

If you replace the axiom of the powerset, with one guaranteeing the existence of double powersets only ... roughly speaking, what changes? Here's the axiom of power set in ZF**, written out in first ...
2
votes
1answer
38 views

Cardinality of reduced products

Suppose $\mathcal{A}_i (i \in I)$ is a family of $L$-structures and consider the reduced product $\mathcal{A}$ of this family by a filter $F \subseteq \mathcal{P}(I)$. Is there a way to determine the ...
-3
votes
1answer
92 views

2-huge cardinal, the most usual definition [closed]

How are 2-huge cardinals usually defined? Is the definition contained in Jech's set theory book (the millennium edition)? Which page?
-1
votes
2answers
58 views

Methods For Listing Countable Sets

The most famous (non trivial) example of listing a countable set is the argument showing that the rational numbers are countable: $$ \begin{array}{cccc} \frac11 & \frac12 & \frac13 & \...
3
votes
4answers
649 views

Dimension of vector space, countable, uncountable?

In set theory, when we talk about cardinality of a set we have notions like finite set, countably infinite and uncountably infinite sets. Main Question Let's talk about dimension of a vector space....
0
votes
2answers
139 views

Confusion between finite set and countable set?

I wanted to find set $A$ such that the cardinality of power set is (1)finite, (2)countable and (3) uncountable. My efforts For finite set, it is very easy as we can take $A$ to be any finite ...
-3
votes
3answers
155 views

Are the points on a unit circle a countable set? [closed]

I was watching this video: https://youtu.be/s86-Z-CbaHA Near 4:10, he says that all the real numbers between 0 and 1 are uncountable. But near 8:38, he says that all the points on that circle are ...
1
vote
0answers
40 views

Show the cardinality of the infinite union of sets is less than the cardinality of the Cartesian product of those sets.

Let $X_0, X_1, X_2, \dotsc$ be sets such that $X_0 \neq \emptyset$ and $$Card(X_0) < Card(X_1) < Card(X_2) < \dotsc$$ Prove that $Card(\bigcup\limits_{i=0}^{\infty}X_i) < Card(\prod\...
0
votes
1answer
33 views

Disjoint unions and countability

First, let me say that when I say countable set I mean a set whose cardinality is less than or equal to the cardinality of $\mathbb{N}$. A set whose cardinality is strictly equal to the cardinality of ...
7
votes
2answers
196 views

Is there a Partition of $[0,1]$ into closed, countably infinite sets?

I'm wondering whether it is possible to Partition the closed interval $[0,1]$ into closed, countably infinite sets. The only observations I could make were as follows: When we remove the endpoints, ...
0
votes
1answer
42 views

Does every graph have a maximum stable set?

(Don't confuse this question with that one about maximal stable sets.) The answer is positive for finite graphs of course. In infinite graphs the matter becomes interesting. Let's revisit the ...
0
votes
1answer
89 views

A cardinality number to the square is itself?

Is there a cardinal number $\kappa$ so that $\kappa \cdot \kappa$ (which is the cardinality of the set of the Cartesian product of $\kappa$ by itself) is not equivalent to $\kappa$? My progress: I ...
1
vote
1answer
59 views

Mahlo operation, consistency border [closed]

Can a (relatively consistent) cardinal notion be given so that its usual Mahlo operation is (probably at least) not consistent?
0
votes
2answers
46 views

Prove: for every $a < b \in \mathbb{R}, \ |(a, b)| = |[a,b)| = |(a.b]| = |[a,b]| = |\mathbb{R}|$

Prove: the cardinality of every interval in $ \mathbb{R}$ is equals to $ \vert \mathbb{R} \vert = 2^{\aleph_{0}}$ I know how to prove that the cardinality of every closed interval in $\mathbb{R}$ ...
0
votes
1answer
47 views

Transfinity of $\mathbb{Q}$ and $\mathbb{Z}$ [closed]

I have read in here: https://math.stackexchange.com/a/2899795/588260 that $\mathbb{Q}$ is 'larger' than $\mathbb{Z}$. I assume it has to do with transfinities in which the one of $\mathbb{Q}$ has a ...