This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, ...

learn more… | top users | synonyms

2
votes
1answer
97 views

Count amount of pairs $(a,b)$ from two sets $A$ and $B$ such that $a\neq b$

I have two sets $A=\{1,2,3\}$ and $B=\{2,3,4\}$ How do I count the amount of pairs $(a,b)$ where $a\in A$ and $b\in B$, such that $a\ne b$ This problem can easily be done on paper, but how can I ...
2
votes
2answers
88 views

Number of ways to select numbers, each 1 from different lists without repetition

I want the numbers of ways to select numbers each 1 from different lists without allowing repetition. Eg- List 1 : 5, 100, 1 List 2 : 2 List 3 : 5, 100 List 4 : 2, 5, 100 I want to select 1 ...
0
votes
1answer
63 views

let $a,b,x,y$ be cardinal numbers such that $a \le b$ and $x \le y$, prove that $a^x \le b^y$.

let $a,b,x,y$ be cardinal numbers such that $a \le b$ and $x \le y$, prove that $a^x \le b^y$. let $\operatorname{card} A=a$, $\operatorname{card}B=b$, and so on. From the given conditions I know ...
0
votes
1answer
188 views

Cartesian product of sets

Let $a$ be a $2\times 1$ vector where each $i$th element $a_i$ taking value $1$ or $0$. Let $\mathcal{A}$ be the set of all possible values of $a$, i.e. $\mathcal{A}:=\{(0,0), (1,1), (1,0), (0,1)\}$. ...
1
vote
1answer
45 views

Proving $(A \cup B) -C = (A-C) \cup (B-C)$

Proving $(A \cup B) -C = (A-C) \cup (B-C)$ I did it as follows, but I'm not sure about the method. Let me know if there is a fault. Let $x \in (A \cup B) -C $ $$ x \in (A \cup B) \land x \notin C \\ ...
3
votes
1answer
78 views

Proof:"Infinite subset of $\mathbb N$ is countable [duplicate]

I've read a proof of the statement:"An infinite subset of $\mathbb N$ is countable; that is, if $A \subset \mathbb N$ and if $A$ is infinite, then $A$ is equivalent to $\mathbb N$." in Carothers' ...
1
vote
3answers
119 views

Notation: the set of two-element subsets of $\Bbb N$ [duplicate]

Let $\{a,b\}\subseteq \Bbb N$. Is there a special name or notation for sets of this type, for example $\Bbb N^{2\ge}$? Any subset size may be used, but the specific size and denoting that order does ...
2
votes
2answers
434 views

Surjectivity of a piecewise function $f:(-1,1)\to \mathbb R$

Function $f$ is defined as $f: (-1, 1) \to \mathbb{R}$. $$ f(x) = \begin{cases} -x/(x-1),&x\geq 0 \\ x/(x+1),&x \leq 0 \end{cases} $$ Let $y \in \mathbb{R}$. How would I prove that there ...
1
vote
2answers
97 views

Cardinality of the set of multiples of “n”

I've yet another question about the cardinality of sets. Apologies, but I just can't seem to fully grasp it. For what it's worth, I have tried searching the site for a solution to this problem. Let ...
1
vote
3answers
115 views

Help with proof of contrapositive of well-ordering principle

Prove by induction on $n$ that if $A$ is a set of positive integers without a least element, then $\mathbb{N}_n \subseteq \mathbb{Z}^+ - A$ for every $n$ so that $A$ is the empty set. I don't ...
3
votes
1answer
66 views

If $A$ is a set, explain why $A^0 = \{\emptyset\}$

I think I may have this but I think it's best I check as I don't have the solution. Let $A$ be a set. $A^0 = \dfrac{A^1}{A^1}$ $A$ / $B$ is everything in $A$ that isn't in $B$ Therefore $A$ / $A$ ...
1
vote
2answers
98 views

Term for a general subset that does not include infinity

I tried to find the answer to my questions for a while but did not succeed, and I hope that was not only because of deficits in my search terms. My question is as follows: Let $\mathcal{A}$ be a set ...
1
vote
0answers
97 views

How to describe any partition a set

For ignore of a better word, I will use word "partition" try to describe what I mean. How to describe partition(where over lapping subsets are allowed) of a set mathematically? In another word, ...
0
votes
1answer
80 views

tuple of tuples notation

Is the following notation right for indicating a $\mathit{m}-$tuple of $\mathit{n_{j}}-$tuples (I mean that each tuple of the $\mathit{m}-$tuple has a different number of elements)? ...
1
vote
0answers
109 views

If A and B are disjoint finite sets, use induction on $|B|$ to show that $|A \cup B|$ is finite.

I'm asked "If A and B are disjoint finite sets, use induction on $|B|$ to show that $|A \cup B|$ is finite. " The main reason I'm having difficulty with this is that it seems so obvious I don't know ...
2
votes
1answer
166 views

Question about the cardinality of sets and infinity

Let's say we have $\mathbb{N}$, the set of natural numbers: $\{1, 2, 3, 4, 5...\}$ ...which has a cardinality of infinity, and the set $A_x$ which consists of the variable "$x$" (so $\{x\}$). If I ...
1
vote
1answer
37 views

The range of a function $f : n^+ \to \omega$ has a largest element.

I am completely lost on this question: Assume that $n \in \omega$ and $f: n^{+} \rightarrow \omega$. Show that $ran\ f$ has a largest element. What I don't understand is that we are given no ...
1
vote
3answers
40 views

Why is this relation transitive?

On $A = \{1,2,3,4,5\}$, define the relation $R = \{(1,1),(1,2),(2,1),(2,2),(3,3),(3,4),(4,3),(4,4),(5,5)\}$. According to my book this relation is transitive, but according this definition there has ...
1
vote
0answers
70 views

Mysterious membership-relation question in Enderton's `Elements of Set-Theory'

The question I am currently working on states (mysteriously): ``Simplify $\in^{-1}_{\omega} [\{7,8\}]$". For those who have the text, this is exercise #18 in Enderton's `Elements of Set Theory' on ...
1
vote
2answers
64 views

Subtracting a set from a set of set

Let say that I have a set of set X = { {a,b}, {a,c}} and I want to remove the element {a,b} from X. What is the proper way to write this subtraction operation. X \ {a,b} or X \ {{a,b}} I think ...
0
votes
1answer
70 views

Proving theorems on relations

I came across the following three statements about relations. I understand why the statements are true, but I am not sure how to demonstrate them mathematically. In the following, $A,B$ are sets and ...
2
votes
2answers
164 views

Fun quiz: where did the infinitely many candies come from?

Story 1: Let there be a bowl $A$ with countably infinite many of candies indexed by $\mathbb{N}$. Let bowl $B$ be empty. After $1/2$ unit of time, we take candy number 1 and 2 from $A$ and put ...
0
votes
3answers
73 views

Show that $A \cup B = (A$ \ $B ) \cup (A \cap B) \cup (B$ \ $A)$

Let $A, B$ be finite sets. Show that $A \cup B = (A$ \ $B ) \cup (A \cap B) \cup (B$ \ $A)$. Deduce that $|A| + |B| = |A \cup B| + |A \cap B|$ These are obvious when considering Venn diagrams but ...
1
vote
1answer
50 views

Question about the proof of this lemma: If $\alpha$, $\beta$ are ordinals, then either $\alpha \subset \beta$ or $\beta \subset \alpha.$

Proof: Clearly $\alpha \cap \beta$ is an ordinal, $\alpha \cap \beta = \gamma.$ Then $\gamma = \alpha$ or $\gamma = \beta$. For, if not, then $\gamma \not= \alpha$ and $\gamma \not= \beta$. Then ...
1
vote
1answer
89 views

Halmos Set theory - what is meant by this set (power sets chp 5)?

What does set D mean here? Could someone please explain in words what it is a set of? How does the sentence follow from it and can someone please translate the sentence? And how do De Morgan's laws ...
1
vote
2answers
99 views

“Unclosure” on a set with binary operation

I was wondering if there is any usefulness to having a set that has no closure under a particular operation. For example, the set of prime numbers, $\mathbb{P}$ along with multiplication of integers ...
1
vote
0answers
51 views

Which basis orders [for the natural numbers] have been proven?

The set $A$ of nonnegative integers is called an additive basis of order $h$ if every nonnegative integer can be written as the sum of $h$ not necessarily distinct elements of $A$. For example, the ...
0
votes
5answers
66 views

Is it the case that for all sets $A, B, C,$ and $D$, $(A \times B) \cup (C \times D) = (A \cup B) \times (C \cup D)$?

I think I have managed to work this out, however there is no solution provided with the question so I thought it best to check. My working: Let $(x,y) \in (A \times B) \cup (C \times D)$ ...
1
vote
1answer
66 views

Closure Question in Enderton's 'Elements of Set Theory'

I am currently working on a follow-up question to the one I did here: Closure question from Enderton's 'Elements of Set-theory' I am unsure though whether I am on the right track with the ...
0
votes
1answer
60 views

Closure question from Enderton's 'Elements of Set-theory'

I am working on the following question but am unsure how to prove that $C^{*} \subseteq C_{*}$. Any help and comments would be appreciated. For those with Enderton's text on-hand, the page number is ...
0
votes
2answers
84 views

Explanation of the formula $f^{-1}(Y)=\{x \in A |f(x) \in Y\}$ for the preimage of a set

So I found a Definition in the book that goes like this to find the pre-image of a set: $$f^{-1}(Y)=\{x \in A |f(x) \in Y\}$$ Example of the theorem being used: Let $A = \{1,2,3,4,5,6\}$ and ...
0
votes
1answer
123 views

Question about proof on basis

I found this proof online, but I have a bit of trouble understanding it. Question: Let X be a set, and let $B \subseteq \mathcal P \left({X}\right)$. Define $B^* =${ $U \subseteq X:$ There is an ...
3
votes
1answer
426 views

Can I pull out an arbitrary element from a set?

Suppose there is an onto function $f: \Bbb R \to \{0, 1\}$. I want to show that there is a function $g: \{0, 1\} \to \Bbb R$, such that $f(g(b)) = b$. I know that there are two element in the domain ...
2
votes
1answer
31 views

Union closure of a set of five finite sets

I've been playing with some basic set theory while looking at the Union-closed sets conjecture. Pretty basic question, but given four finite sets $A,B,C,D, \mathcal{Y}$ where $$A \cup B = C \cup D = ...
2
votes
1answer
62 views

Can polynomials with degree at least 2 over $\mathbb{R}$ have finite number of solutions in $End(\mathbb{R},+)$

Consider a polynomial of degree at least 2 with all coefficients in $\mathbb{R}$. We are concern with set of solution for the polynomial in $End(\mathbb{R},+)$ - the endomorphism ring of the abelian ...
0
votes
1answer
141 views

Question about proving that a finite intersection of big unions is a big union of finite intersections

Let $I_{1}$,...$I_{k}$ be index sets and for each $1 \leq m \leq k$ and each $j \in I_{m}$, let $U_{j}$ be a set. Prove that: $$(\bigcup\limits_{j_{1}\in I_{1}}U_{j_{1}}) \cap ... ...
0
votes
3answers
114 views

the use of Cartesian product

I am currently studying in secondery level. I read cartesian product the other day and I found it absolutely bizarre. In my text book, there is this "order pair" which I understood fairly well and ...
0
votes
2answers
45 views

Relations on set A and conditions of existence of descending chains

I am reading through the Elements of Set theory by Herbert Enderton and even though I have passed this exercise long ago,the more I look at my solution the less I believe it. Problem goes like this: ...
4
votes
4answers
192 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
34 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
79 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
109 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
1answer
220 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
178 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: ...
1
vote
1answer
266 views

question about Herbert B. 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 ...
3
votes
1answer
51 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 ...
5
votes
1answer
106 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 ...
10
votes
5answers
1k 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
72 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
61 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 ...