This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

8
votes
2answers
635 views

countable group, uncountably many distinct subgroup?

I need to know whether the following statement is true or false? Every countable group $G$ has only countably many distinct subgroups. I have not gotten any counter example to disprove the statement ...
8
votes
2answers
1k views

Cardinality of the infinite sets

Consider the following problem: Which of the following sets has the greatest cardinality? A. ${\mathbb R}$ B. The set of all functions from ${\mathbb Z}$ to ${\mathbb Z}$ C. The ...
8
votes
5answers
4k views

How can one prove that the union of two finite sets is again finite, without the use of arithmetic?

The notion that the union of two finite sets is again finite is something I took as intuitively true for quite a while. A proof using arithmetic is relatively straight forward. Suppose $A$ and $B$ ...
8
votes
4answers
1k views

Simple Set Theory Question

I'm starting to learn Set Theory and I'm stuck on a question: Show that the relations $$(A \cup C)\subset(A\cup B), (A\cap C) \subset (A\cap B)$$ when combined, imply $C\subset B$. If it's in anyone's ...
8
votes
3answers
590 views

Uncountability of countable ordinals

According to Wikipedia, there are uncountably many countable ordinals. What is the easiest way to see this? If I construct ordinals in the standard way, $$1,\ 2,\ \ldots,\ \omega,\ \omega +1,\ \omega ...
8
votes
2answers
389 views

Is $\emptyset \in \emptyset$ or $\emptyset \subseteq \emptyset$?

Can someone give an argument, if possible using only the axioms of set theory, because I'm very weak there and have virtually no background, except the usual knowledge of the operation with sets one ...
8
votes
4answers
745 views

What's the cardinality of all sequences with coefficients in an infinite set?

My motivation for asking this question is that a classmate of mine asked me some kind of question that made me think of this one. I can't recall his exact question because he is kind of messy (both ...
8
votes
3answers
758 views

In Cantor's Diagonalization Argument, why are you allowed to assume you have a bijection from naturals to rationals but not from naturals to reals?

Firstly I'm not saying that I don't believe in Cantor's diagonalization arguments, I know that there is a deficiency in my knowledge so I'm asking this question to patch those gaps in my ...
8
votes
1answer
344 views

Why is the collection of all groups considered a proper class rather than a set?

According to Wikipedia, The collection of all algebraic objects of a given type will usually be a proper class. Examples include the class of all groups, the class of all vector spaces, and ...
8
votes
5answers
757 views

Definition of the Infinite Cartesian Product

(1) If $X$ and $Y$ are two sets, we define the Cartesian product $X \times Y$ as the set of ordered pairs $(x,y)$, such that $x \in X$ and $y \in Y$. (2) On the other hand [Folland, Real Analysis, ...
8
votes
4answers
593 views

The set of all sets of the universe?

I can't understand Russell's paradox. What I understand is that Russell's paradox arises because the set of all sets that are members of themselves is empty. That it's impossible to find a set that's ...
8
votes
2answers
462 views

Does taking the power set give you the “next biggest cardinal”

I know that if you take the power set of a set, it has a higher cardinality. Therefore there are an infinite number of them as $P^{n}(\mathbb{N})$(the nth power set of the naturals) Let's say $$C_{n} ...
8
votes
3answers
274 views

Is there any way to save this “proof” that $\aleph_0=\aleph$? [closed]

I came up with this idea of proving that $\aleph_0=\aleph$. I know this is not true at all, but maybe there is more to it than I can see. we start with the inequality $\aleph_0 \leq ...
8
votes
2answers
309 views

Why is $|Y^{\emptyset}|=1$ but $|\emptyset^Y|=0$ where $Y\neq \emptyset$

I have a question about the set of functions from a set to another set. I am wondering about the degenerate cases. Suppose $X^Y$ denotes the set of functions from a set $Y$ to a set $X$, why is ...
8
votes
3answers
233 views

Group of groups

The product $\times$ of two groups is associative and commutative and there's a neutral element $\{1\}$. Let's say I create "virtual groups" which are inverses with respect to $\times$ (like getting ...
8
votes
2answers
647 views

How do the sets $\emptyset\times B,\ A\ \times \emptyset, \ \emptyset \times \emptyset $ look like?

If we have a function $f:A \rightarrow B$, then one way to give meaning, I think, to this function, in terms of set theory, is to say, that $f$ is actually a binary relation $f=(A,B,G_f)$, where $G_f ...
8
votes
3answers
326 views

“The set of all true statements of first order logic”

In one of my lectures, the lecturer put a bunch of examples of sets on the board, stuff like the set of all humans, set of all well typed programs in some programming language, the set of all true ...
8
votes
3answers
291 views

With Choice, is any linearly ordered set well-ordered if no subset has order type $\omega^*$?

I've been fumbling around with order types and ordinals these past few days. I read about partial, total, and well-ordered structures, and I'm curious to see if a linearly ordered set has no subset ...
8
votes
2answers
133 views

Can we expand numbers on the left to produce irrational numbers?

I have seen examples of irrational numbers that are expanded on the right, after the decimal point: e.g. $\pi = 3.14159265...$ But can we expand numbers on the left side as well? e.g. Is ...
8
votes
1answer
133 views

How do I eliminate useless subsets?

BACKGROUND / MOTIVATION: The other day, I was given a finite covering $\mathcal{B} = \{I_1, \ldots, I_n\}$ of $[0, 1]$ by open intervals, and I wanted to refine it by eliminating useless intervals, ...
8
votes
3answers
172 views

Can we take images of equivalence relations?

Given a function $f : X \rightarrow Y$, it is well-known that we can take the image under $f$ of any subset $A \subseteq X$, and we can take the preimage under $f$ of any subset $A \subseteq Y$. This ...
8
votes
1answer
489 views

When is $x=\{ x\}$?

Inspired by this question: When/for which $x$ do we have $x=\{ x\}$ ?
8
votes
3answers
215 views

“If $n=0$ there is nothing to prove”

Suppose that I must prove a theorem by (strong) induction on $\mathbb N$. If the statement of the theorem has sense, for example, for $n\ge 1$, often as base case one chooses $n=0$ and says "for $n=0$ ...
8
votes
2answers
2k views

Countable/uncountable basis of vector space

I've stumbled upon this exercise in algebra book, in chapter dealing with vector spaces' dimensions. Prove that basis of the field of real numbers $\mathbb R$ as vector space over the field of ...
8
votes
2answers
153 views

Are quantifiers a primitive notion?

Are quantifiers a primitive notion? I know that one can be defined in terms the other one, so question can be posed, for example, like this: is universal quantifier a primitive notion? I know, that ...
8
votes
2answers
113 views

Can we conclude $\prod_{\kappa \in Crd, \kappa=1}^{\kappa<\aleph_\alpha}\kappa=2^{\aleph_\alpha}$ in ZFC?

In complex analysis, there is a function called Euler's Gamma function. Whenever given a positive integer $n+1$, it will return $n!=\prod_{i=1}^{i < n+1}i$. I'm not sure if there is similar ...
8
votes
3answers
1k views

Show $S = f^{-1}(f(S))$ for all subsets $S$ iff $f$ is injective

Let $f: A \rightarrow B$ be a function. How can we show that for all subsets $S$ of $A$, $S \subseteq f^{-1}(f(S))$? I think this is a pretty simple problem but I'm new to this so I'm confused. Also, ...
8
votes
3answers
175 views

How do I read this question? (subject: bijections)

Introduction In Basic Algebra I, I am struggling with fully understanding the following exercise: Show that $S\overset{\alpha}{\to}T$ is injective if and only if there is a map ...
8
votes
1answer
954 views

Prove: If $A \subseteq C$ and $B \subseteq D$, then $A \cap B \subseteq C \cap D$

Is the form and correctness of my elementwise proof of this correct? I don't have any other way of getting feedback for my proofs and I want to improve. Proof. Suppose $A, B, C, D$ are sets such ...
8
votes
2answers
87 views

How should one think about results that depend on AC?

I just encountered this: "(Theorem of A. H. Stone) Every metric space is paracompact... Existing proofs of this require the axiom of choice... It has been shown that neither ZF theory nor ZF ...
8
votes
2answers
187 views

Set theory based on inclusion

There are several axiomatizations of set theory based on inclusion rather than membership. I found only two papers, but they are both in German, and I could not read them even using a disctionary. Can ...
8
votes
2answers
637 views

Meaning of pullback

I was wondering if the following two meanings of pullback are related and how: In terms of Precomposition with a function: a function $f$ of a variable $y$, where $y$ itself is a function ...
8
votes
3answers
180 views

Existence of a certain subset of $\mathbb{R}$

To every real $x$ assign a finite set $\mathcal{A}(x)\subset \mathbb{R}$ where $x\not\in \mathcal{A}(x)$. Does there exist $\mathcal{W}\subset \mathbb{R}$ such that: $$1.\;\;\mathcal{W}\cap ...
8
votes
2answers
141 views

Name for a function whose image has smaller cardinality than its domain

I asked this question in the comments of this question, whose title would have done just as well for mine. But I suppose it should be a separate question. Is there a name for functions ...
8
votes
1answer
64 views

Graphs with uncountably many vertices

Let $ \mathcal{H}$ be the class of all graphs with at most $ 2^{\aleph_0}$ vertices not containing a complete subgraph of size $ \aleph_1$. Show that there is no graph $ H \in \mathcal{H}$ such that ...
8
votes
1answer
862 views

What is the number of bijections between two multisets?

Let $P$ and $Q$ be two finite multisets of the same cardinality $n$. Question: How many bijections are there from $P$ to $Q$? I will define a bijection between $P$ and $Q$ as a multiset $\Phi ...
8
votes
1answer
213 views

An exercise in infinite combinatorics from Burris and Sankappanavar

Exercise 6.7 in chapter IV of Burris and Sankappanavar's A Course in Universal Algebra starts as follows: Show that for $I$ countably infinite there is a subset $S$ of the set of functions from ...
7
votes
4answers
507 views

How to Decompose $\mathbb{N}$ like this? [duplicate]

Possible Duplicate: Partitioning an infinite set Partition of N into infinite number of infinite disjoint sets? Is it possible to find a family of sets $X_{i}$, $i\in\mathbb{N}$, such ...
7
votes
6answers
410 views

subsets and sets

I'm not so bad in math however I want to understand math the way mathematicians do, so I picked up this book How to Think Like a Mathematician. The book seems the book that I'm looking for. ...
7
votes
5answers
2k views

how do we assume there is infinity?

Definition of infinite: A set is infinite iff it is equivalent to one of its proper subsets. We know that our universe doesn't contain infinite number of elements, so how do we assume there is ...
7
votes
6answers
1k views

Why is the supremum of the empty set $-\infty$ and the infimum $\infty$? [duplicate]

I read in a paper on set theory that the supremum and the infimum of the empty set are defined as $\sup(\{\})=-\infty$ and $\inf(\{\})=\infty$. But intuitively I can't figure out why that is the case. ...
7
votes
3answers
5k views

What is a null set?

I am very confused with null sets. I get that a set which has no elements will be called a null set but I am not getting the examples given below. Please help me by explaining how $P,Q,R$ are all ...
7
votes
7answers
2k views

Partition of N into infinite number of infinite disjoint sets?

Is it possible to have a countable infinite number of countable infinite sets such that no two sets share an element and their union is the positive integers?
7
votes
4answers
531 views

How many subsets of $\mathbb{N}$ have the same cardinality as $\mathbb{N}$?

How many subsets of $\mathbb{N}$ have the same cardinality as $\mathbb{N}$? I realize that any of the class of functions $f:x\to (n\cdot x)$ gives a bijection between $\mathbb{N}$ and the subset ...
7
votes
5answers
366 views

If $\mathcal{P}(A)=\mathcal{P}(B)$, then $A=B$? [duplicate]

Prove, disprove, or give a counterexample: If $\mathcal{P}(A)=\mathcal{P}(B)$, then $A=B$. Assume $\mathcal{P}(A)=\mathcal{P}(B)$. Since we know $A \subseteq A$, we know $A \in ...
7
votes
2answers
686 views

Troll Maths : Bijection between P(N) and N?

I just wanted to know what's wrong in the following argument: Say I take a number and rewrite as a binary. e.g 155 = 10011011 Then I can relate the number with a subset of N, which contains the ...
7
votes
7answers
228 views

Is $\mathbb{C}$ equal to $\mathbb{R}^2$?

Complex numbers are usually formally defined as pairs of real numbers. Although there are operations on $\mathbb{C}$, such as complex multiplication, which are not found in operations usually applied ...
7
votes
7answers
339 views

Rational numbers $\mathbb Q$

$$\Bbb{Q} = \left\{\frac ab \mid \text{$a$ and $b$ are integers and $b \ne 0$} \right\}$$ In other words, a rational number is a number that can be written as one integer over another. ...
7
votes
3answers
464 views

If $f \circ g = f$, prove that $f$ is a constant function.

Suppose $A$ is a nonempty set and $f: A \rightarrow A$ and for all $g:A \rightarrow A,$ $f \circ g = f$. Prove that $f$ is a constant function. This result seems obvious, but I can't seem to find ...
7
votes
4answers
2k views

Interpretation of limsup-liminf of sets

What is an intuitive interpretation of the 'events' $$\limsup A_n:=\bigcap_{n=0}^{\infty}\bigcup_{k=n}^{\infty}A_k$$ and $$\liminf A_n:=\bigcup_{n=0}^{\infty}\bigcap_{k=n}^{\infty}A_k$$ when $A_n$ are ...