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

-2
votes
0answers
43 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
144 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|. [closed]

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
23 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
54 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
3answers
108 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
55 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
34 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
44 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
107 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
42 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
74 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
87 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
41 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
27 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
44 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
63 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
42 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$. ...
4
votes
2answers
71 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 ...
1
vote
1answer
81 views

Looking for a bijection between this set and natural numbers

I am a computer programmer, and I am struggling with this mathematical problem without finding a consistent and efficient solution. Let $A_{k, M}$ be the set of all the possible assignments for $n_1, ...
3
votes
3answers
37 views

An example of symmetric transitive relation that is not reflexive on a set of natural numbers $\mathbb{N}$ [duplicate]

An example of symmetric transitive relation that is not reflexive on a set of natural numbers $\mathbb{N}$. My guess is that such relation does not exist, but I don't know how to prove it.
1
vote
1answer
36 views

Why do we need the axiom of choice in showing the non-emptiness of an infinite Cartesian product

Given $I$ a set of indexes and $X_i$ a set of topological spaces, define The Cartesian product: $\prod_{i \in I}X_i = \{ f:I \rightarrow \bigcup X_i | f(i) \in X_i \}$ I have read that we need ...
3
votes
2answers
58 views

finite additivity&countable additivity

Let $\tau$ be a semialgebra of subsets of $\Omega$ and let P: $\tau\rightarrow [0,1]$, with $P(\Omega)=1$, and it satisfies finite additivity: $P\big(\bigcup_{i=1}^{n}D_i\big)=\sum_{i=1}^{n}P(D_i)$ ...
-1
votes
2answers
88 views

Showing that $A\rightarrowtail A \times \{x\}$ is a bijection

$A\rightarrowtail A \times \{x\}$ where $A$ is any set and $\{x\}$ is an arbitrary one-object set. How would I show the following is a bijection ( one to one and onto)? I know if I turn it into a ...
0
votes
2answers
55 views

Prove that the sets $S$ and $D$ have the same cardinality

Prove that the sets $S$ and $D$ have the same cardinality, where $S = \{(x,y)\mid-1\leq x \leq 1\text{ and }-1\leq y\leq 1\}$ and $D = \{(x,y)\mid x^2 + y^2 \leq 1\}$.
2
votes
2answers
34 views

Composition of injections (proof)

I'm trying to prove that composition of injections is an injection. I want to know if this is a good proof: Composition of injections is an injection. Let $f:S_1\rightarrow S_2$ and ...
1
vote
2answers
60 views

Prove $|A| = |B|$

Let $A= \{a_1,a_2,a_3,\ldots\}$. Define $B = A − \{a_{n^2} : n \in\mathbb N\}$. Prove that $|A|=|B|$. I would say that $B = \{a_2,a_3,a_5,a_6,\ldots\}$. Thus $B$ is a infinite subset of $A$ and ...
0
votes
1answer
45 views

Why we use ANY in the definition of a maximal element?

I am confused about the following definition: "a maximal element of a subset S of some partially ordered set is an element of S that is not smaller than any other element in S." I do not understand ...
6
votes
3answers
120 views

Functions with different codomain the same according to my book?

My book gives the following definition: A function $f$ from $A$ to $B$ is defined as $f\subseteq A\times B$ such that if $(a,b)\in f$ and $(a,b_1)\in f$ then $b=b_1$ and there exists a $(a,b)\in ...
1
vote
0answers
57 views

Zuckerman's “Sets and Transfinite Numbers”

I am beginning a study in set theory and I found an old book in my school's library by Martin Zuckeman called Sets and Transfinite Numbers which was published in the 1970's. Has anyone used this text ...
1
vote
1answer
60 views

How to prove that $f:\mathbb{N}\rightarrow X$ where $f$ maps to an element in a set, is a bijection?

Let $X$ and $Y$ be disjoint finite sets, $|X|=n$ and $|Y|=m$, so that we have the following bijections: $f:\mathbb{N}_n \rightarrow X$ and $g:\mathbb{N}_m \rightarrow Y$ I need to prove that ...
1
vote
0answers
45 views

How can I find the smallest set of groups of $n$ elements such that every element is in the same group as every other at least once?

Background: I'm working on a King of the Hill challenge for Programming Puzzles & Code Golf, and I've run into a problem with how I'm creating the individual matchups (groups of 4 entries). ...
2
votes
4answers
87 views

Prove $A \subset \emptyset \iff A = \emptyset$

How does one prove this? Can one prove by contradiction by saying: Let $A$ be any set such that $A$ contains at least one element. Now assume $A \subset \emptyset$. This is clearly absurd by the ...
2
votes
1answer
26 views

Finding two functions, $f, g$, such that $\mathrm{sup}(g \circ f[\omega]) < \mathrm{sup} (g[\omega + \omega])$

I've been working for some time on Schimmerling's A course on Set Theory, and, thanks to you guys, I'm now almost finishing chapter 3 on ordinals (hah!). In one of the last exercises, he ask us to ...
13
votes
6answers
2k views

A strange puzzle having two possible solutions

A friend of mine asked me the following question: Suppose you have a basket in which there is a coin. The coin is marked with the number one. At noon less one minute, someone takes the coin ...
0
votes
4answers
91 views

Which of these sets is bigger?

I am a fourth year computer science student and I am taking second year level maths because they are very useful for computer stuff. At the end of the linear algebra lecture the Prof left us with a ...
0
votes
0answers
22 views

$a\le b$ iff there exist $\left|A\right|=a, \left|B\right|=b$ and $A\subseteq B$ [duplicate]

$a\le b$ iff there exist $\left|A\right|=a, \left|B\right|=b$ and $A\subseteq B$ My Proof: $(\Leftarrow)$ $A\subseteq B$ implies immediately that $\left|A\right|\le\left|B\right|$. Hence, $a\le ...
3
votes
1answer
65 views

What is a 'disjunct' of a union called?

Say I have a set $C = A \cup B$ and I want to refer to $A$ in natural language. Had the expression been a Boolean formula with a disjunction, then I would call $A$ the first disjunct. Is there a ...
0
votes
3answers
61 views

Conceptually: A set whose elements can only be probabilistically characterized?

Sorry for the informality here, but was musing over the basic concepts around describing a set in real world usage: A finite set of explicitly named elements, this apple and that apple, nothing more ...