Questions tagged [elementary-set-theory]

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, differences and complements, De Morgan's laws, Venn diagrams, relations, etc. More advanced topics should use (set-theory) instead.

Filter by
Sorted by
Tagged with
1
vote
0answers
36 views

Prove that for any set A and B, the cardinality of the set of all functions mapping A to B is $\vert B \vert ^ {\vert A \vert}$

What I do is for finite sets A, B, let $A={a_1, a_2, ...a_n}$ and $B={b_1, b_2, ...b_m}$ A function f assigns each element $a_i$ of $A$ to an element $b_j = f (a_i)$ of $B$; there are $m$ ...
16
votes
7answers
11k views

How to prove that $\mathbb{Q}$ ( the rationals) is a countable set

I want to prove that $\mathbb{Q}$ is countable. So basically, I could find a bijection from $\mathbb{Q}$ to $\mathbb{N}$. But I have also recently proved that $\mathbb{Z}$ is countable, so is it ...
0
votes
1answer
46 views

Is it possible to define such a set that contains countable many computable and countable many non-computable infinite sequences?

I don't know anything about it. Therefore, I may have used the wrong words in the question. We know that there are uncountable many non-computable infinite sequences which is consist of elements $\...
0
votes
2answers
32 views

Prove that if $A \setminus B ⊆ C ∩ D$ and $x \in A$ and $x \not \in D$ then $x \in B$

Suppose $A \setminus B ⊆ C ∩ D$ and $x \in A$. Prove that if $x \not \in D$ then $x \in B$. We can rewrite $A \setminus B ⊆ C ∩ D$ using logical connectives as follows: $(x \in A \land x \not \in B) \...
0
votes
5answers
63 views

How to prove that a function $f:X\to X$ is injective if and only if surjective?

I intuitively understand it and can prove for finite sets. But can you prove it? And my proof relies on counting the elements. Can you show it without counting or using cardinalities?
0
votes
2answers
66 views

What is the cardinality of $\Bbb Q ^4$?

What is the cardinality of $\Bbb Q ^4$? I understand that $\vert \Bbb Q \vert=\aleph _0$, and $\vert \Bbb Q ^4 \vert$ supposed to be $\aleph _0$, is there any formal proof to this?
0
votes
2answers
23 views

Sets re: equality and subsets

The italics are my comments. This is a proof from a text on abstract algebra that seems a bit ambiguous. But I'm just learning sans instructor. My question is: is there a convention in set theory ...
2
votes
1answer
28 views

The images of two arbitrary functions can partition their domains

The source of this problem is from Dugundji's Topology. Let $f\colon X \to Y$ and $g\colon Y \to X$ be any two maps. Show that $X$ and $Y$ can each be expressed as disjoint unions: $X = X_1 \cup X_2$ ...
64
votes
6answers
34k views

Produce an explicit bijection between rationals and naturals?

I remember my professor in college challenging me with this question, which I failed to answer satisfactorily: I know there exists a bijection between the rational numbers and the natural numbers, but ...
-1
votes
1answer
26 views

Proving that if a family of sets $\cal{A} \ne \emptyset$ is totally ordered with respect to $\subseteq$ then $\bigcap\cal{A} \in \cal{A}$.

Assume that $\mathcal{A} \neq \emptyset$ is an arbitrary family of subsets of $X$, such that $(\mathcal{A}, \subseteq)$ is a total ordering. I want to prove that the intersection of all members of $\...
2
votes
1answer
51 views

To prove a the given below set is a generating set in my example

Consider a set, say $A=\{1,2,3,4,5,6\}$. Let $\mathcal{P}(A)$ be the power set of $A$. Consider $$ S=\big\{ \{1,2,5\}, \{2,3,6\}, \{3,4,1\}, \{4,5,2\}, \{5,6,3\}, \{6,1,4\} \big\} $$ We have to ...
-3
votes
2answers
94 views

Which of the following sets is bijection to set of Integers?

Which of the following sets is bijecton to set of integers: A. $(\mathbb{Z}^{101})$ B. $(\mathbb{Z} \times \mathbb{Q})$ C. $(\mathbb{Z} \times \mathbb{R})$ D. $(\mathbb{R}^2)$ This was ...
1
vote
1answer
441 views

Need Help Showing that the Composition of Bijections is a Bijection

Let $f\colon X \rightarrowtail Y$ and $g\colon Y \rightarrowtail Z$ be bijections. Prove that $g \circ f:X \rightarrowtail Z$ is a bijection. Since $f$ and $g$ are bijections, they are both one to ...
0
votes
2answers
58 views

Are these two sets same? $\{x \in \mathbb Z \mid x>5 \}$ and $\{x \mid x \in \mathbb Z \land x>5 \}$

Consider two following sets: $\{x \in \mathbb Z \mid x>5 \}$ $\{x \mid x \in \mathbb Z \land x>5 \}$ Is there any difference between two sets above?
-1
votes
0answers
26 views

Composition of canonical functions for equivalence relations [on hold]

Let $G$ and $H$ be equivalence relations on $A$, and suppose that $G\subseteq H$. If $\pi_{1}$ is the canonical function from $A$ to $A/G$, $\pi_{2}$ is the canonical function from $A$ to $A/H$, and $...
0
votes
1answer
83 views

What is the cardinality of $A$ if $A = \{\{A\}\}$? [on hold]

What is the cardinality of $A$ if $A = \{\{A\}\}$? I think one is the answer since the outer set has one element, a set. But that seems to simple to be right.
0
votes
0answers
32 views

Property of Set Function related to Supermodularity

Have set functions with the following property been studied? If so, what is the name of the property? Let $\Omega$ be a set of elements, and let $f:\mathcal P(\Omega) \rightarrow \mathbb{R}$ be a ...
2
votes
2answers
27 views

How to represent a set of variables are different elements of a set mathematically?

Lets say that we have set $A$. The variables $m_{1}$, $m_{2}$, $\cdots$ $m_{N}$ are elements of the set $A$ but with exclusivity. The variables have to be different elements of the set. How can I ...
0
votes
0answers
37 views

Defining sets in intuitionistic logic

I'm somewhat familiar with the school of intuitionistic logic. I know that an intuitionistic logician thinks of infinity as constructive as apposed to complete. Thus a intuitionistic logician cannot ...
2
votes
0answers
50 views

Proof verifications for set equality

Can I get a proof verification? Are there any flaws in this proof? The examples in the book are only for sets bounded either above or below. Prove $$\cup_{n\in \mathbb{N}}(0,\frac{n}{n+1})=(0,1)$$ ...
0
votes
4answers
408 views

Find minimum number of customers that must have visited the bakery that day?

A bakery sells three kinds of pastries -pineapple, choclate and black forest. On a particular day, the bakery owner sold the following number of pastries : $90$ pineapple , $120$ chocolate and ...
2
votes
3answers
206 views

How do I define this subset using mathematical notation?

Assume $P = \{2, 3, 5, 7, 11, 13, 17, 19, 23,....\}$ or in another words, P is the set consisting of all prime numbers. Now, suppose we want to form the set $S$, which is subset of $P$,and whose ...
2
votes
1answer
42 views

Problems with proof of $\omega_1=\bigcup\{X_\xi|\xi\in\omega_1\}$

I have the proof of following lemma, which I do not really understand: Let $(X,<)$ be a well orderd uncountable set. Let $\omega_1=\{\xi\in X|X_\xi\,\,\text{countable}\}$ and $X_\xi=\{\alpha\in X|\...
4
votes
5answers
575 views

Trying to find a flaw in my proof that there are more rearrangements of an infinite series than real numbers

So I had this thought that I was trying to prove as an exercise Let $\mathbb{R}$ be the set of real numbers and let $\mathbb{S}$ be the set of all possible rearrangements of the alternating ...
0
votes
1answer
27 views

Expression for finitely many events occur?

For a sequence of events [B1 , B2,....], We can express event that infinitely many events occur as $\bigcap_{n=1}^\infty \left(\bigcup_{n\geq k} B_k\right)$ How can I express the event that ...
1
vote
1answer
38 views

Elementary set theory proof by contradiction

Let $A = \{x \in \Bbb{R} : |2x -1| \leq 5\}$, let $B = \{x \in \Bbb{R} : |2x - 1| < 3\}$, let $D =\{x \in \Bbb{R} : x^2(7-x^2) \geq 7\}$ and let $E = \{x \in \Bbb{R} : 2x(x-2)(x+2) \geq 5 \}$. ...
1
vote
1answer
61 views

$\{\sqrt[3]{x}| x\in \mathbb{Q}\}$ and $\{x\in \mathbb{Q}|\sqrt[3]{x} \}$, what is the difference? [on hold]

Consider two following sets: $$A = \{\sqrt[3]{x}\mid x\in \mathbb{Q}\}$$ $$B = \{x\in \mathbb{Q}\mid \sqrt[3]{x} \}$$ What is the difference between the two sets?
1
vote
2answers
46 views

For $ n\to\infty $, does $A_{n\to\infty}$ contain all possible infinite length sequences?

I don't claim to have chosen the right words and notations in the question. I'm trying to understand the concepts. Let, the set $A_n$ is given. The set of $A_n$, is the set of all possible ...
4
votes
1answer
104 views

If $X$ is an infinite set, then is $\sum_{i=1}^\infty |X|=|X|$?

I used the above to solve a problem, but I am not sure if this is true (and if it is true does it require a proof or is it obvious). I think it is true because $|X| + |X| = |X|$, so it should follow ...
0
votes
2answers
58 views

When is $\mathbb{N}\setminus A$ finite?

I have the topological space $(\mathbb{N},\tau_{\text{kof}})$ where $\tau_{\text{kof}}=\{U\subseteq\mathbb{N}|\mathbb{N}\setminus U\,\,\text{finite}\} \cup \{\emptyset\}$ Now I want to show, that ...
2
votes
2answers
38 views

Question about proof for intersection of a set family with union of a set

I am studying this proof and there are a few things I need help understanding. Let $A$ be a set and $B_i$, for $i \in I$ be a family of sets Prove $ A \cup (\cap_{i \in I}B_i)$=$\cap_{i \in I}(A \...
1
vote
1answer
27 views

Defining subgraph and subset of directed graph

Following the lines of this question Need help with Graph notation for a subgraph , I am trying to define the subset of vertices connected to a specific vertex $v_i$ and need some help working through ...
0
votes
2answers
45 views

Proving two sets of even integers are equal

This is a question I found in the proof book I am practicing in. This seems like a ridiculous thing to prove, so I don't know what the author is looking for. Prove $\{n \in \mathbb{Z}:n$ is even$\}$...
1
vote
1answer
63 views

for a function $f:A→B$ with $\left|A\right|<\left|B\right|$ is there any possibility not to be injective?

if we have two sets like $A$ and $B$ with cardinality $\left|A\right|<\left|B\right|$ and assume a function $f:A→B$ is there any possibility for $f$ not to be injective? Because I assumed $A=[1,2,3]...
2
votes
2answers
43 views

Proof Verification that Every Finite Set has a Unique Cardinality

Is my proof correct for proving that every finite set has a unique cardinality? My part of the proof is as follows: "Let $A = \{a_1, a_2, ..., a_n\}$ be an arbitrary set with $n$ elements, and let $f:...
1
vote
1answer
69 views

Prove that a set cannot have two different size $𝑚$ and $𝑛, 𝑚≠n$.

We define the number of elements in set by bijections as follows: $|X| = n$ means that there exists a bijection from X to the set $\{1,2 \dots, n\}$. I already showed that: if $X$ and $Y$ have ...
0
votes
4answers
83 views

A Set is Infinite if, and only if, it is in One-to-one Correspondence with a Proper Subset of Itself

Can someone explain what that means? How can there exist an injective function from an infinite set to a proper subset of itself. A function from a set A to a set B where B has fewer elements than A ...
0
votes
0answers
23 views

Describe the set $\{ z\in \mathbb{C}: |z^2 -1|<1\}$ [duplicate]

Let $z=a+ib$ $|z^2-1|<1$ $(z^2-1)(\overline{{z^2-1}})<1$ $z^2\overline{z^2}-z^2-\overline{z^2}<0$ $|z^2|^2<2Rez^2=a^2-b^2$ What can we say further? Is there any mistake? Is it ...
0
votes
2answers
34 views

Unique Equivalence Classes

Not sure if this is a suitable question here, but I'm having trouble understanding the intuition behind a theorem I've read in a textbook. So it says the following: "If $\mathscr R$ is an ...
0
votes
2answers
137 views

What is the justification for calling a hereditary system an independent system?

I was learning about set systems and hereditary systems and I noticed that they also call a hereditary system a independence system and that didn't quite make sense to me intuitively. First recall ...
2
votes
1answer
55 views

Confusion about Notation of the Cardinality of a Set

One textbook I'm reading says that the definition of two sets having the same cardinality is as follows: "Two sets A and B have the same cardinality if there exists a bijection $f:A \rightarrow B$." ...
2
votes
4answers
63 views

What is the Simplest Explanation for the Countability of the Integers?

What is the simplest (or at least simple to understand) if one wanted to explain why the set of Integers has the same cardinality as the set of natural numbers to students who have a vague idea of why ...
0
votes
3answers
32 views

What does the symbol “`\`” mean in the context of set operation?

I am learning group by using this post let's call this figure_1. everything is OK until the set of B shows up. what I already known is The union is notated A ⋃ ...
1
vote
1answer
14 views

If I wanted to generate a sequence of elements using the element position in the sequence as a variable, how would that variable be written?

I'm trying to create a sequence of elements which are dependent on their position in the sequence. What I mean is that I want the value $r$ in position 1 equal to 1, on position 2 equal to 2 and so on....
3
votes
3answers
716 views

Is this proof of the Archimedean Property valid?

Archimedean property: The set of natural numbers $\mathbb{N}$ is not bounded above. Proof : Suppose $\mathbb{N}$ is bounded above. Then, by the supremum property, there exits a lowest upper bound "$...
0
votes
1answer
39 views

Can recursion done on sets be done in reverse?

Given the recursive definition below: $$\begin{align} \text{Basis Step} &: 3 \in S \\ \text{Recursive Step} &: \{x, y\} \in S \implies (x+y) \in S \end{align}$$ This means members of the set ...
0
votes
2answers
75 views

How can I describe the set of homomorphisms and what is its cardinality?

There are actually two questions here. Neither of these is a homework question. Let $\text{hom}(\mathfrak{A},\mathfrak{B})$ (not to be confused with the Hom functor) be the class$^0$ of homomorphisms ...
5
votes
1answer
1k views

Existence and uniqueness up to isomorphism of the real numbers from axioms

Pretty much what the title says: how does one prove the existence and uniqueness of the real number system from the ordered field axioms together with the least-upper-bound property (or maybe some ...
0
votes
1answer
56 views

Proof verification: uniqueness of empty set [duplicate]

My question doesn't concern the standard-proof of the uniqueness of the empty set, which uses the lemma that the empty set is a subset of every set. My question concerns an alternate proof that I made ...
0
votes
1answer
33 views

If set $A = \{-2, -1,0,1,2 \}$ and function $f$ is defined as $f: A \to Z $ given by $f(x) = x^2 -2x -3$, then what is the preimage of $-3$? [closed]

If set $A = \{-2, -1,0,1,2 \}$ and function $f$ is defined as $f: A \to Z $ given by $f(x) = x^2 -2x -3$, then what is the preimage of $-3$?