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
1answer
22 views

Can a set have subsets of different lengths

Can a set $S$ be defined as such $S = \lbrace(x_0), (x_1, y_1),(x_2, y_2,z_2),...\rbrace$? Or should every element be of equal length?
0
votes
0answers
40 views

Sets operations

I stopped by these two problems: $A = \{0, \{0\}\}$. What are the proper subsets of $A$? I thought those were $\{0\}$ and $\{\{0\}\}$, but I'm not quite sure. $\{\{0\}\} \cup\{0\}$ Here, I'm ...
1
vote
0answers
31 views

I have lost part of text of problem condition.

I have the only last sentence. Prove that $X \approx X \times \{ x \}$ for every set$X$ and every object $x$. Question. What does mean the $\approx ?$ That there exist a biective map between the two ...
0
votes
2answers
53 views

Prove that a set infinite if it has infinite proper subset

Suppose that $A$ is an infinite set and $A \subsetneq C$. Use the definition of "infinite set" to prove that $C$ is infinite also. I am trying to prove that $C$ is infinte. Definition (Infinite ...
0
votes
0answers
22 views

Find an image of function

Let $f$ be function $f: \mathbb{R} \times \mathbb{R} \to \mathbb{R} \times \mathbb{R}$ and $f(x,y)=(y+1, x-1)$ find image for set $A=\{(x,y)\in \mathbb{R} \times \mathbb{R} : x^2+y^2=1 \}$ we have ...
0
votes
1answer
31 views

In a binary vector $ x \in \{0,1\}^{k}$ what does the $^{k}$ mean?

In a binary vector $ x \in \{0,1\}^{k}$ what does the $^{k}$ mean? I understand that $\in$ means 'is a possible outcome' or 'in' so x can be 0 or 1, but I'm not sure what the $^{k}$ means.
1
vote
1answer
16 views

Meaning of Function Involving Product of Sets

The function is $h:R^2 \times R^2\rightarrow R \times R$ such that $h((a, b), (c, d)) = (a + b, c - d)$. What is the meaning of this function? Here are my thoughts: $R^2$ is a mathematical object, ...
0
votes
1answer
49 views

What tools should be used to prove that a real function is one-to-one and onto?

Let $A = \mathbb R \setminus \{−1/2\}$ and $B =\mathbb R \setminus \{2\}$. Define $f : A \to B$ by the rule $$f(x) = \frac{4x − 3}{2x+1}$$ for all $x \in A$. Show that $f$ is one to one and onto. Find ...
1
vote
2answers
29 views

A set is finite, then there exists a bijective map from the set to some natural number?

Def : A set $X$ is finite if every injective map from $X$ to $X$ is surjective. Using this, how can I prove that if $X$ is finite, then there exists a bijective map from $X$ to some natural number. ...
0
votes
0answers
20 views

What is the general idea of forcing theory

I am trying to get the general idea of forcing freom here without getting into further details (for now). So, for example, suppose my model contains the real line $\mathbb R$ with the (usual order on ...
1
vote
1answer
39 views

Arithmetics of cardinalities: if $A=C$ and $B=D$ then $A\times B=D\times C$

Suppose that $A, B, C$, and $D$ are sets with the cardinalities related as $A=C$ and $B=D$. Prove that the cardinality of $A\times B$ is equal to the cardinality of $D\times C$. I know that I must ...
1
vote
2answers
48 views

The complement of a finite set in a countable set is countable

Let $X$ be a countable set. Let $A \subset X$. How can I prove that if $A$ is finite then $X \setminus A$ is countable? I started off by supposing that $X \setminus A$ is finite and then need ...
1
vote
1answer
33 views

Write down the union and intersection of $100$ sets

I'm trying to solve the following exercise in elementary set theory. Let $A_i=\{-i,i+1,-i+2,...,i\}$. We are asked to explicitly find and write down $\bigcup_{i=1}^{100} A_i$ and ...
0
votes
1answer
16 views

Countability of specific sets

I need some help with the following: are the following countable or uncountable? the set of all lines in the plane with rational slope. - I think this is countable Q{$0$} - I know Q is countable ...
3
votes
1answer
49 views

Proof Verification of Schröder–Bernstein theorem

So I've spent some time studying the Schröder–Bernstein theorem, but I'm trying to do the exercise in "Naive Set Theory" by Paul Halmos regarding the theorem. The exercise is finding an alternative ...
2
votes
1answer
26 views

Find image of two variables function

I have problem with proving using double inclusion that it's an image of function where we have open interval for instance: Find image $f[A]$ where $A=(0,2) \times (1,3)$ of $f(x,y)=|x-y|$. My try: ...
1
vote
1answer
36 views

Showing that $A \subseteq B$ for $A=\{6t\mid t \in \mathrm Z\}$ and $B=\{3t\mid t \in \mathrm Z\}$

Let $A=\{6t\mid t \in \mathrm Z\}$, and $B=\{3t\mid t \in \mathrm Z\}$. Then, show $A$ is a subset of $B$ and prove or disprove that $A = B$. I already know that $A \neq B$, for I can pick a ...
1
vote
2answers
43 views

Functions whose codomain's form depends from the element taken from the domain

As in the title, I have a notational problem regarding functions whose codomain directly depends on the elements taken from the domain. Here there is an example. Let $X$ be a set with $x \in X$. Let ...
0
votes
1answer
35 views

Double checking answers to a set question / power sets

I'm practicing for an exam coming up and I want to make sure I understand power sets. I've answered this question and I was hoping someone could tell me if my answer is correct. ...
1
vote
1answer
23 views

Let $A$, $B$ and $C$ be three sets. If $A$ belongs to $B$ and $B$ is a subset of $C$, is it true that $A$ is a subset of $C$ too?

Let $A$, $B$ and $C$ be three sets. If $A$ belongs to $B$ and $B$ is a subset of $C$, is it true that $A$ is a subset of $C$ too? The answer in my textbook reads - No. Let $A=\{1\}$, ...
0
votes
1answer
17 views

Function to represent the smallest element of a set

I was wondering if there is a way to represent the smallest $x \in S$ where $S$ is some set of real numbers. According to the WOP, there must be a smallest value. But how do I go about representing ...
1
vote
3answers
97 views

Show that $a\in X\Longrightarrow\mathcal{P}(a)\in\mathcal{P}(\mathcal{P}(\bigcup X))$

Do not understand the solution I have been given, $\mathcal{P}(a)\in\mathcal{P}(\mathcal{P}(\bigcup X))\Longleftrightarrow\mathcal{P}(a)\subseteq\mathcal{P}(\bigcup X))$ [simplifying RHS of equation ...
0
votes
1answer
18 views

proving that a subset of a set has a functional mapping that is a subset of another

i wanted to prove: Let $f:X\to Y$ be a mapping from $X$ into $Y$. Show that if $A$ and $B$ are subsets of $X$, then: $$(A \subset B) \implies \left(f(A) \subset f(B)\right)$$ but i thought ...
10
votes
3answers
505 views

Sole minimal element: Why not also the minimum?

A minimal element (any number thereof) of a partially ordered set $S$ is an element that is not greater than any other element in $S$. The minimum (at most one) of a partially ordered set $S$ is an ...
1
vote
1answer
42 views

Decide if sets are equivalent

I have problem with understanding how to solve such problems, I'd be grateful for explanation. Let $\displaystyle A= \{f \in \{ 0,1\}^{N \times N} : \exists l \in N \ \ \forall k\ge l \ \ \forall ...
0
votes
1answer
51 views

Strange definition for finitely generated subspaces

My teacher gave a definition of a finitely generated subspace $[S]$. I don't even know what does this mean and why it's useful to define, but he said that: Suppose a vector space $(V,+,\cdot)$, and ...
1
vote
2answers
38 views

Difficulty understanding Zorn's Lemma.

This is a question on chap. 9 of Introduction to Set Theory of Hrbacek and Jech. The book define that the Zorn's Lemma is: If every chain in a partially ordered set has an upper bound, then the ...
4
votes
1answer
69 views

Rules for translating quantifiers to set operations?

I had this excercise in measure theory where I had to show that certain sets are measurable and I realized there was some mechanical procedure going on. Here is the question: Let $f_n:X\to ...
0
votes
1answer
28 views

Proving the formula for the cardinality of cartesian products.

Consider sets A and B where |A|=m and |B|=n. Prove by induction on n for a given m that |AB| = mn for all m,n ∈ N where AB = cartesian product. My attempt : Base Case - consider when n = 0 so B is ...
0
votes
2answers
43 views

Tell whether the relation is reflexive, symmetric, asymmetric, antisymmetric or transitive.

Tell whether the relation is reflexive, symmetric, asymmetric, antisymmetric or transitive.Identify equivalence relations or partial orders. $R$ is the relation on people such that $a R b$ if $a$ ...
7
votes
7answers
192 views

How can $\mathbb Q$ be countable, when there is no “next” rational number?

I understand this proof that $\mathbb{Q}$ is countable: The rational numbers are arranged thus: $$\displaystyle \frac 0 1, \frac 1 1, \frac {-1} 1, \frac 1 2, \frac {-1} 2, \frac 2 1, \frac {-2} ...
2
votes
0answers
50 views

Software to solve basic set equations (in algebra of sets)?

What symbolic math software is able to solve basic set equations? E.g. $X \setminus A = C \setminus X $, for $X$
1
vote
1answer
24 views

How do I give the inverse of a bijective function

I have proved the function being bijective, but I don't know how to inverse it. So if someone could please show the steps how to do it I would be very grateful. Below is the provided proofs for ...
2
votes
2answers
314 views

Counterexample to if g ◦ f is surjective, then f and g are surjective

I want less of an answer and more of an explanation if possible please. I understand I'm looking for a range of either f and g that is NOT surjective(does not cover all the codomain), but that their ...
0
votes
2answers
17 views

Confused on a question on sets and functions

Let $f: R \rightarrow R$ where $f(x) = x^2$. Determine $f(A)$ for the following subset A taken from the domain R. A = {2,3} A = (-3,3) A = [-7,2] So the first one I figured out to be {4,9}. I'm ...
0
votes
1answer
24 views

Sets, Set Notation and Equations Problem

Let $A,B,C \subseteq Z^2 $ where $ Z = \{(x,y) \mid y = 2x+1 \}, B = \{(x,y) \mid y = 3x\}$, and $C = \{ (x,y)\mid x-y=7\}$. Determine a) $A \cap B$ b) $B \cap C$. I've tried plugging in $x$ values ...
8
votes
0answers
40 views

There's no cardinal $\kappa$ such that $2^\kappa = \aleph_0$

I am trying to prove that a cardinal $\kappa$ such that $2^\kappa = \aleph_0$ . My attempt: We suppose it exists. Since $\kappa<2^\kappa$, in particular, $\kappa<\aleph_0$. But that implies ...
3
votes
0answers
35 views

an introduction to axiomatic set theory that is not enderton

So I've been reading Endertons Elements of set theory which is easy to understand when it comes to the essential axioms, but there are a number of topics which seem to gloss over important ...
2
votes
1answer
35 views

Collection of surjective functions implies axiom of choice

if I have this: (a) If $\left \{ f_i:A_i\rightarrow B_i|i\epsilon I \right \}$ is a collection of surjective functions then $\prod_{i\epsilon I} f_i: \prod_{i\epsilon I} A_i\rightarrow ...
0
votes
1answer
16 views

Identify this relation to be an injection, surjection, bijection or non-function

Identify this relation as an injection, surjection, bijection or non-function, where f:A->B, with x an element of A, and the value of f is determined by: f(x)=the number of elements of x, A={subsets ...
-1
votes
0answers
28 views

Identify this relation as an injection, surjection, bijection or non-function

Identify as an injection, surjection, bijection or non-function, where $f:A\to B$, with $x\in A$, and the value of $f$ is determined by: $$f(x)=\sin x, \quad A=\{\text{real numbers}\},\quad ...
0
votes
1answer
39 views

Prove that a subset of $\Bbb R$ is equinumerous to $\Bbb R$ using Schröder–Bernstein thorem

Math 3345 Section 16 Exercise 14 Let A be a subset of $\Bbb R$ which contains a non-degenerate interval I. Prove that A is equinumerous to $\Bbb R$ (Hint: use Schröder–Bernstein theorem.) Here's what ...
0
votes
2answers
17 views

What is $A^c \cap B^c \cap C^c$

I am working with boolean algebra for my Navy coursework and I was wondering if anyone knew what the formula for $A^c \cap B^c \cap C^c$ is? Also does $A^c \cap B^c \cap C^c = (A \cap B \cap C)^c$? ...
0
votes
1answer
39 views

Showing that two cartesian products are equinumerous

Math 3345 Section 16 Exercise 9 Let A, B, C, D be sets such that A is equinumerous to C and B is equinumerous to D. Show that AxB is equinumerous to CxD. I believe I have the correct answer for when ...
1
vote
1answer
63 views

Something I don't understand about Hilbert's grand hotel

So I want to know if Hilbert's hotel "story" holds for this statement: $\wp (\mathbb{N}) \sim \wp (\mathbb{N})\smallsetminus \left \lbrace\emptyset\right\rbrace$ So, If the statement wasn't talking ...
2
votes
1answer
45 views

Sets and Notation.

There is a set like: $V = \{f : R \to R \mid f(x) = ax + c \text{ with } a, c \in \mathbb{R} \}$ I do not know what "$:$" means. I do not know what "$|$" means. I think the meaning is something ...
-1
votes
1answer
25 views

How to prove that cardinal numbers of sets and unions of them are equal

Let A, B, C, D be sets. If I know that $A\sim C$ and that $B\sim D$, In addition I know that: $C\cap D = \varnothing$ and also, $A\cap B = \varnothing$ Does it imply that $A\cup B\sim C\cup D$? ...
2
votes
2answers
74 views

In $\mathsf{Rel}$, are any two objects isomoprhic?

My knowledge of categories is rather basic, and I was just trying to find out what are isomoprhisms in $\mathsf{Rel}$ where objects are sets and morphisms are relations. As far as I got, an ...
0
votes
1answer
22 views

Equivalency of Set Notation

This is a very simple question. Let's say there is $ Z_{1} \cup Z_{2} $ Where $ Z_{1} = \emptyset $ and $ Z_{2} $ = $ \left\{ x \mspace{4mu} | \mspace{4mu} x \in \mathbb{R},\mspace{4mu} 9<x ...
0
votes
1answer
14 views

For every equivalence relation $R$, find $B$ and function $f$ such that $R_f = R$

Given $A,B$ groups and a function $f:A\rightarrow B$, we define the relation $R_f$ as $(x,y)\in R_f$ if $f(x)=f(y)$. Q: For every equivalence relation $R$ on $A$, find a $B$ and a function $f:A ...