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

3
votes
4answers
50 views

Book/Article recommendation

I am a first year Math major in the university, this summer I want to self study and go over some specific subjects. Firstly, can someone can give a suggestion for a detailed book/article about the ...
0
votes
1answer
9 views

Simple question about indexing edges of an undirected graph.

As far as I understand, for an undirected graph $\mathcal{G}=(\mathcal{N},\mathcal{E})$, the set of edges is defined as unordered 2-element subsets of $\mathcal{N}$. So, for example, $\mathcal{E} = ...
0
votes
4answers
53 views

Can we write programs for all functions if we have an infinite alphabet?

If we have a finite alphabet, then the set of programs we can write is countably infinite (aleph naught). The set of all functions is uncountably infinite (cardinality of real numbers). If we have ...
1
vote
3answers
53 views

Cantor diagonalization and fundamental theorem

Can the Cantor diagonal argument be use to check countability of natural numbers? I know how it sounds, but anyway. According to the fundamental theorem of arithmetic, any natural number can be ...
0
votes
0answers
10 views

Proving the properties of big union of unions for indexed sets

Let $I$ be an index set, and for each $i \in I$, let $J_{i}$, be another index set. For each $i \in I$ and $j \in J_{i}$, let $U_{j}$ be a set. Set X = $\bigcup\limits_{i\in I}J_{i}$. Prove that: ...
2
votes
2answers
22 views

Proof of: $X$ is finite $\iff X$ is Tarski-finite

I am self-studying Horst Herrlich, Axiom of Choice (Lecture Notes in Mathematics, Vol. 1876). In the fourth chapter, he deals with different definitions of finite set. Here is the classical one: ...
0
votes
1answer
24 views

question about Herbert B.C. Enderton's book a mathematical introduction to logic

I hope someone can help me. My question arises on page 114 of the second edition of the book. Here the notion of 'prime formula' is introduced to enable one to view a formula as a formula of ...
2
votes
1answer
31 views

Terminology on pullbacks

I'm quite confused with the use of pullbacks, and in particular I wonder which terminology I shall use in the following examples. Let $X$ and $Y$ be arbitrary sets. Suppose that $f,g:X\to Y$ and I ...
2
votes
1answer
46 views

Proof that there is a bijection, if there are injective maps in both directions

Let $A$ and $B$ be two sets. Let $f:A\to B$ be injective such that $Im(f) \subsetneq B$. Let $g:B\to A$ be injective such that $Im(g) \subsetneq A$. Obviously $A$ and $B$ are not finite sets. Can ...
8
votes
3answers
644 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 ...
2
votes
1answer
53 views

Prove this result about construction of sets

In Enderton's book on Set Theory, the following problem is given after introducing the notion of sets as an infinite hierarchy (I hope this much explanation is sufficient; if not, please mention and ...
3
votes
2answers
38 views

The union of all the open sets in a family of topologies

I'm starting studying topology for the first time and my teacher just wrote this. I just don't understand the last line: Let $\{\tau_\alpha\}$ be a family of topologies on X. [...] To say that ...
2
votes
5answers
47 views

How to show if A is denumerable and $x\in A$ then $A-\{x\}$ is denumerable

My thoughts: If $A$ is denumerable then it has a bijection with $\mathbb{N}$ So therefore $A\rightarrow \mathbb{N}$. Then x is a single object in A and A is infinite. So if a single object is ...
1
vote
1answer
30 views

Divide Notation for Sets?

In the book "Abstract Alegbra" by Dummit and Foote, on page 260, problem 41c states: ...
1
vote
1answer
80 views

Alternative set therories?

Is there a version of set theory that allows the existence of a set that does not admit the empty set as a member? I.e., reject the axiom $A\cup \emptyset = A$
3
votes
3answers
465 views

Does there exist two distinct set which are not an element of a given infinite set?

Let $X$ be an infinite set. Under ZFC, it is true that $X\notin X$. So there is at least one set which is not an element of $X$. Is there another element distinct from $X$ which is not a member of ...
1
vote
4answers
58 views

Bijection between $\mathbb N^+ \times \mathbb R^+$ and $\mathbb R^+$

Let $\mathbb N^+$ denote the set of natural numbers bigger than $0$ and let $\mathbb R^+$ denote the set of real numbers bigger than $0$. Is there a way to write down an explicit bijection between ...
1
vote
0answers
29 views

Family of equivalent unitary representations is not a set.

I have recently come across a statement in the book: Kazhdan's property (T) by B. Bekka, P. de la Harpe, A. Valette at the beginning Appendix F.2. Fell topology on sets of unitary representations. ...
0
votes
0answers
30 views

Quotient respect to an equivalence relation.

I have the natural numbers $\mathbb{N}$, in ZF. I want to construct the integers $\mathbb{Z}$ taking the quotient respect to usual the equivalence relation $R$ on $\mathbb{N}\times\mathbb{N}$ that is ...
0
votes
1answer
51 views

axiom of regularity and empty set

So we have axiom of regularity which says that any set (let's call it $A$) has a subset $B$ such that $A\cap B = \emptyset$. But thinking about such sets as $C = \{1, 2\}$ and $D = \{3, 4\}$ we still ...
-2
votes
0answers
42 views

Cardinality of the set of all functions on R [duplicate]

What is the cardinality of the set of all function on R?
1
vote
2answers
26 views

If $R$ is a transitive realation, then $R\circ R\subseteq R$

Here's the question I'm struggling with: Let R be a transitive relation on a set A. Prove the R composed with R is a subset of R. I'm kind of lost on how to prove this. I've started with saying: ...
1
vote
3answers
135 views

An empty set minus a nonempty set and the difference between two disjoint nonempty sets?

Let $E, F$ be two sets. 1) If $E$ is empty and $F$ is nonempty, is their difference $E \setminus F$ meaningful? 2) If $E, F$ are both nonempty and disjoint, is their difference $E \setminus F$ ...
-3
votes
0answers
39 views

Let T be the set of positive integers, and let E be the set of positive even integers. Prove that |T| = |E|. [on hold]

I am not too sure how to do this. Obviously the set of positive even integers is a subset of positive integers. So it is countable. HELP PLEASE
0
votes
2answers
60 views

Removing one 1 from real number $0.111111…$

Let us say that there is a real number $0.1111......$ where $1$ gets repeated after 0. Now we remove one $1$ out of all $1$'s. Would the new real number be equal to the old real number, or would it be ...
0
votes
0answers
21 views

“Arbitrary” Products, Unions, and Intersections of Classes

Recently going through the nlab article on categories, I noticed at the end of this section the use of a disjoint union of disjoint unions of the hom-sets in order to produce the class of morphisms in ...
0
votes
2answers
27 views

Is this an error? (An Introduction to the Theory of Computation by Eitan Gurari)

In this book chapter 1 (link: http://web.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-onese1.html#Q2-20001-5) it says: Similarly, f2 is a binary representation over {0, 1} of the natural ...
1
vote
0answers
19 views

Non-section representation of an intersection of sets

Let $X,\bar X,Y$ be arbitrary sets and $A\subseteq X\times Y$, $\bar A\subseteq \bar X\times Y$ be arbitrary as well. Denote: $$ A_x :=\{y\in Y:(x,y)\in A\} $$ and similarly for $\bar A$. Consider a ...
1
vote
1answer
51 views

Is my proof on showing that the set of monotone functions on $[a,b]$ has cardinality of continum correct?

I was given an exercise problem to show that the cardinality of the set of all monotone functions on $[a,b]$ is $\aleph$. I came out with a proof which I am not sure if it is correct. My proof: Let ...
1
vote
2answers
42 views

finding a group that satisfy: $x,y\in A_n\Rightarrow x\in y \vee y\in x \vee y=x$

for all natural number $n$ need to show a set $A_n$ with $n$ terms which satisfy: $x,y\in A_n\Rightarrow x\in y \vee y\in x \vee y=x$ i tried to think recursively but i'm stuck. thanks!
1
vote
2answers
94 views

My proof of the recursion principle (without the axiom of replacement)

(The proof in my book uses the axiom of replacement. My proof doesn't use it. Any hints and recommendations are welcomed.) The recursion principle Let $y_0$ be any element of a set $Y$ and ...
0
votes
0answers
33 views

Recursion Theorem question

I am trying to prove the following in Enderton's text 'Elements of Set Theory' (exercise 8 of chapter 4): Let $f$ be a one-to-one function from $A$ into $A$, and assume that $c \in A - ran \ f$. ...
2
votes
1answer
33 views

Confused about this set representation and conclusions

I'm pursuing Set Theory by Enderton and am having trouble understanding the following idea. Early in the book, the author constructs an "informal view" of sets, which he says he will refine further ...
0
votes
1answer
40 views

If A and B are subsets of the universal set S thendo we know that A intersection (not B) is a subset of A

If $A$ and $B$ are subsets of the universal set $S$ then do we know that $A$ intersection (not $B$) is a subset of $A$? Well, if $S = \{1,2,3,4,5\}$ and $A = B = \{1,2\}$ then not $B = \{3,4,5\}$ and ...
2
votes
2answers
102 views

Is the Axiom of Choice necessary to prove $\mathbb R \approx \mathcal P(\omega)$?

I am self-studying Horst Herrlich, Axiom of Choice (Lecture Notes in Mathematics, Vol. 1876), and I'm getting quite confused about cardinal arithmetic without AC. Here (Which sets are well-orderable ...
1
vote
1answer
41 views

Proving some properties of $\Bbb N$ without using recursion

I will try to prove that if $a, b, c \in \Bbb N$ and $a \in b \in c$, then $a \in c$ (the transitivity property). I will not use recursion or the replacement axiom. Actually we can proove in the same ...
2
votes
2answers
72 views

Proof for Surjections

I'm reading through Basic Algebra I (which I enjoy so far. Thoughts on this for self-studying?) and am having a difficult time proving surjection. I believe I understand the concept, but when it comes ...
1
vote
2answers
86 views

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

Can someone tell me if this proof is acceptable? Assume $A \not\subseteq C$. This means that there is an $x \in A$ such that $x \not\in C$. But since $\forall x \in A: x \in B$ and $\forall x \in B: ...
1
vote
1answer
34 views

Defining an ordered pair as a set

In mathematics we define mathematical objects in terms of other mathematical objects. For example, some textbooks define $(a,b)$ as a set. Such as, $$(a,b):= \{\{a\},\{a,b\}\}$$ Now, the cardinality ...
0
votes
2answers
28 views

Set and cardinality injection and surjection proof [duplicate]

Let X be a set. Prove there is an injection from $X \rightarrow 2^X$. Prove that there is not a surjection from $X \rightarrow 2^X$. My try- Assume to the contrary that $f: X \rightarrow 2^X$. is a ...
1
vote
2answers
37 views

Showing the natural number same cardinality as as even?

I am having problem with the onto part of this problem. $\mathbb{N}\rightarrow \mathbb{E}$ My function or pattern is $x \rightarrow f(x)=2x$ Which take my natural to even. One to One ...
2
votes
3answers
102 views

How to show the integers have same cardinality as the natural numbers?

How would I show the following have a bijection. Which is one to one and onto ofcourse. $\mathbb{Z}\rightarrow \mathbb{N}$ I know I need to find a function. But I do not see the pattern that makes ...
0
votes
2answers
26 views

Help with constructing power set

I' trying to construct the power set of $A = \{\phi, \{a\}\}$ and would appreciate some help. Now, the definition of a power set says that it's the set of all possible subsets of a given set. ...
0
votes
1answer
33 views

How to deduce number of unordered distinct pairs using set operations and bijections

In (b) of the example, we are ask to calculate the number of ordered pairs of distinct positive integers. I like the first method's answer (using bijections, set operations) because it clearly shows ...
0
votes
0answers
43 views

Two definitions of functions

In literature on logic and set theory, there seem to be two different definitions of functions, one more general than the other. First of all, a function $f\colon X\to Y$ consists of three element ...
0
votes
2answers
73 views

$\Bbb Z^\ast$ What is this notation?

What does $\Bbb Z^\ast$ mean? I would think some subset of the integers but I cannot find a definition. Thank you.
0
votes
1answer
61 views

Prove the reflexivity of $\subseteq$.

My professor gave me a list of exercises, I've been able to figure out what mechanism I should exploit to prove them, but I'd like to know if it's good. Until now we've been taught a little logic and ...
1
vote
1answer
28 views

The function space from $n$ to $m$ and the exponent $m^n$ are equinumerous (proof)

Can someone provide a tip with creating the bijection for the titular problem? Any tip is helpful! Update: $n=\{ 0,\ldots,n-1 \}$, $m=\{ 0,\ldots,m-1 \}$, and $ m^n=\{0,\ldots,m^n-1\} $. In other ...
2
votes
0answers
40 views

Elementary set-theory question

Very basic problem, just wanted to be sure I did this correctly. The problem is "Show that $X-Y = X \cap \overline{Y} $". There was hint in the problem telling one to let our universe $U=X \cup Y$. ...
3
votes
2answers
65 views

Uncomputability of subset relation

I suppose this obvious question should already be answered in plenty of places, but for some reasons I cannot find a proof of this anywhere. Prove or disprove that their exist a set $X$ that is ...