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
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
731 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
739 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
3answers
582 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
5answers
734 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
588 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
3answers
256 views

A “Cantor-Schroder-Bernstein” theorem for partially-ordered-sets

If A and B are partially-ordered-sets, such that there are injective order-preserving maps from A to B and from B to A, is there necessarily an order-preserving bijection between A and B ?
8
votes
2answers
458 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
305 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
224 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
3answers
321 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
2answers
632 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
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
3answers
163 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
486 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
174 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
952 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
86 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
180 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
635 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
179 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
140 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
844 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
505 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
400 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
4answers
1k views

Why is an empty function considered a function?

A function by definition is a set of ordered pairs, and also according the Kurastowski, an ordered pair $(x,y)$ is defined to be $$\{\{x\}, \{x,y\}\}.$$ Given $A\neq \varnothing$, and ...
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
995 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
528 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
357 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
680 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
225 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
322 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
456 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
2answers
605 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 ...
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 ...
7
votes
2answers
320 views

Must $g$ be the identity if $f = g \circ f$?

I am finding it hard to solve the following problem. Let $A$ is a set and $f : A \rightarrow A$ and $g : A \rightarrow A$. If $f = g \circ f$, must $g$ be an identity function always? Will there be ...
7
votes
2answers
201 views

cartesian product $A^2 = A$, possible?

Do there exist non-empty sets $A$ such that $A\times A = A$? $A\times A = A$ looks a little strange to me, since $A\times A$ seems somehow more complicated than $A$, hence it is unlike that they are ...
7
votes
3answers
418 views

What is “every inductive set”?

In Apostol's «Calculus I», on page 22 there is the following definition: A set of real numbers is called an inductive set if it has the following two properties: (a) The number 1 is in the set (b) ...
7
votes
3answers
686 views

Building the integers from scratch (and multiplying negative numbers)

Now I understand that what I am about to ask may seem like an incredibly simple question, but I like to try and understand math (especially something as fundamental as this) at the deepest level ...
7
votes
4answers
285 views

Supremum and ordinals

Question: Show that sup{$ \xi \dotplus 1 : \xi \in A $} is the least ordinal that is greater than each element of $A$. I tried to get a better feel for this by letting $A=3=${$0,1,2$}. Then I know ...